Agreed. In my case, I'm interested in cryptography.
While it is possible (and often *necessary*) to
be an auto-didact in cryptography proper,
formal schooling helps a *lot* in developing the math skills necessary to understand what's going on. Maybe you can sit down and teach yourself abstract algebra from scratch -- but it's a lot easier for me to take a course.
Eventually I expect to go for a PhD. It's not
required to "do cryptography." Plenty of respected
cryptographers don't have a doctorate. But look at it this way: it's a chance to spend 4-5 years doing nothing but hitting yourself up against the most interesting problems you can find.:-)
It describes a signature scheme with an "incremental" or "fast update" property. They claim that this signature scheme is ideal for settings in which there's a very small amount of trusted memory and CPU available to a virus monitoring program.
Tripwire style IDS seems to be extremely similar.
Anyone implemented this sort of thing or know if it's being used in a commercial product?
Happily the gap between practice and proofs seems to be closing. At least, OAEP has made its way into the PKCS #1 standard, and maybe from there it will be implemented. OAEP is pretty efficient - two hashes and two XORs on top of yer basic RSA operation.
In fact, if you are willing to treat hash functions as "random oracles" (a big if which could be a thread in itself), then it seems that you can get quite efficient, provably secure methods to do lots of crypto. It's just a question of knowing about it. Something which having OAEP in a widely-used standard might help.
Of course, what drove its adoption as part of the standard was the fact that the old standard was broken by Bleichenbacher at Crypto '98. Sad as it may seem, no one in the "wider" community seems to pay attention until someone comes up with a spectacular attack which the provably secure systems seem to resist. I'm sure there are some people of people busy fixing their old ISO-9796 signature compliant implementations, too...
With luck, though, the IEEE 1363 standard for public-key crypto will start moving that segment of crypto towards provably secure methods. (see page at http://www.manta.ieee.org/groups/1363/ ). No clue when this is going to hit symmetric crypto -- anyone have a guess?
I think you may be a bit optimistic about a review time of hours. No matter how easy it is to publish the data on the web, the review process still involves people sitting down and reading the paper to see if it's Any Good(tm). This takes time. How much time depends on the paper and the field and the reviewer, but it's likely more than just hours.
Maybe a good question to ask is what an electronic journal is supposed to offer over an electronic preprint server. Preprint servers exist for several of the sciences; the most well known is the xxx.lanl.gov, but there are other more specialised ones too (my favorites are eprint.iacr.org / philby.ucsd.edu and the Electronic Colloquium on Computational Complexity).
Generally preprint servers accept submissions from anyone and do almost no review before posting something -- something like "is this a scientific paper in English" (although standards do vary). Then it's up to the archive users to figure out if something is any good or not. This means new submissions can go up almost as soon as they are received. The flip side is that sometimes things turn out to be wrong, and then they're marked as such *after* dozens of people have downloaded it and spent precious time trying to figure out what the heck is going on.
So does the main "point" of an electronic journal come in having better peer review than a preprint server? or is there something else?
Violent agreement on the idea of a book on failed protocols. I think protocol design one of the areas which is needed most and understood least in cryptography. We're a long way from Bellare's "a cryptographer is a machine which turns primitives into protocols"...
Can we start compiling some examples of protocols, exercises, and material which would go into such a book?
Avi Rubin and Matt Franklin had a course on "Protocol Design" at NYU http://cs.nyu.edu/cs/dept_info/course_home_pages /fall96/G22.3033.02/
which has an list of references and some problem sets. In particular, there's a reference to some papers like J. Moore, "Protocol Failures in Cryptosystems," Proceedings of the IEEE, 5(76), 1988, 594-602.
and
P. Syverson, "Limitations on Design Principles for Public Key Protocols," IEEE Symposium on Security and Privacy, Oakland, CA, 1996, 62-72.
which look very interesting.
The differences between SSL 1.0, 2.0 and 3.0 should be in such a book as well. Especially the attacks in which an adversary can force use of a weaker cipher.
You'd probably also want a discussion of "security proofs" and "definitions of security." In particular, pointing out limitations in such things as BAN logic. I don't know much about specific failures here; anyone have an example?
A while back I asked on sci.crypt about "provably stupid protocols" -- protocols where the proofs were _correct_, but according to misguided definitions. Looking that up in Deja would produce some possible examples (though maybe not protocols in the sense you may be using).
It's a shame, but not too surprising, to hear that the book doesn't cover OAEP. Especially as Coron, Naccache, Joye, and Pailler have a paper in EUROCRYPT '00 about "New Attacks on PKCS #1 v1.5 Encryption" abstract at : http://www.eleves.ens.fr:8080/home/coron/science .html#8
I have not read the paper yet, but the abstract is scary.
Some background : the RSA function x^e mod n should not be used directly for encrypting data. For one thing, it's deteministic; the same x produces the same x^e always. An adversary can use this to look for common plaintexts (consider what happens if you encipher a message letter-by-letter this way...). For another, there are all kinds of clever attacks which can recover messages which are related, or can break the scheme if you send too many messages, and so on.
Dan Boneh has a cool overview of these attacks and others in his "Twenty Years of Attacks on RSA" paper http://crypto.stanford.edu/~dabo/abstracts/RSAat tack-survey.html
Some kind of padding scheme is necessary. Some padding schemes are better than others. The scheme which pads with random garbage at the end of the message, for instance, is not very good. The Public Key Crypto Standard (PKCS) #1 specifies the padding scheme used for RSA encryption. Version 1.5 had this scheme which was kind of thought to be sort of OK but nobody knew really. Now we are finding that it wasn't quite as good as we thought...
Optimal Asymmetric Encryption Padding (OAEP) is another padding scheme. It is specified in version 2 of PCKS #1 because it seems to resist the attacks which killed version 1.5 . The neat thing about it is that you would expect it to resist these attacks and others because there is a "proof of security" which relates breaking the padding to breaking the RSA problem.
That is, there's a proof which shows that extracting *any* information from the encrypted padded messages is just as hard as breaking the RSA problem on random instances. The scheme may still fail, but only if the RSA problem "underlying it" happens to be easy...like if we chose a too short modulus. We don't have to worry about stupid things like sending the wrong kind of messages any more.
Is it important that OAEP was omitted in a "practical" handbook? In my opinion, yes and no. There's no need for the proof of security to be included. But the *reason* for the proof, that is, the existence of these really subtle and weird attacks which can leak information when you're not expecting it...that seems quite important in practice. Along with an explanation of how to use schemes like OAEP to cut out as many of these attacks as possible.
It's worth noting, however, that OAEP *is* described in the _Handbook of Applied Cryptography_, which is available for download at http://cacr.math.uwaterloo.ca/hac/
No proofs here, just a straightforward diagram and "how to implement." For the actual proof, you can check out Bellare and Rogaway's paper at http://www-cse.ucsd.edu/users/mihir/papers/pke.h tml
OAEP is also specified in the IEEE P1363 standard, which has its website here : http://www.manta.ieee.org/groups/1363/
the standard covers other algorithms and protocols as well. The website's worth checking out.
While we're at it, does anyone know of a good treatment/introduction to the proofs of security involved in OAEP and similar?
Slashdot Mirror
Agreed. In my case, I'm interested in cryptography.
:-)
While it is possible (and often *necessary*) to
be an auto-didact in cryptography proper,
formal schooling helps a *lot* in developing the math skills necessary to understand what's going on. Maybe you can sit down and teach yourself abstract algebra from scratch -- but it's a lot easier for me to take a course.
Eventually I expect to go for a PhD. It's not
required to "do cryptography." Plenty of respected
cryptographers don't have a doctorate. But look at it this way: it's a chance to spend 4-5 years doing nothing but hitting yourself up against the most interesting problems you can find.
This reminds me of a paper I came across yesterday:
"Incremental Hashing With Application to Virus Protection" STOC '95 M. Bellare, O. Goldreich, S. Goldwasser
ftp://theory.lcs.mit.edu/pub/people/oded/
bgg-inc2.ps
It describes a signature scheme with an "incremental" or "fast update" property. They claim that this signature scheme is ideal for settings in which there's a very small amount of trusted memory and CPU available to a virus monitoring program.
Tripwire style IDS seems to be extremely similar.
Anyone implemented this sort of thing or know if it's being used in a commercial product?
Happily the gap between practice and proofs seems to be closing. At least, OAEP has made its way into the PKCS #1 standard, and maybe from there it will be implemented. OAEP is pretty efficient - two hashes and two XORs on top of yer basic
RSA operation.
In fact, if you are willing to treat hash functions as "random oracles" (a big if which could be a thread in itself), then it seems that you can get quite efficient, provably secure methods to do lots of crypto. It's just a question of knowing about it. Something which having OAEP in a widely-used standard might help.
Of course, what drove its adoption as part of the standard was the fact that the old standard was broken by Bleichenbacher at Crypto '98. Sad as it may seem, no one in the "wider" community seems to pay attention until someone comes up with a spectacular attack which the provably secure systems seem to resist. I'm sure there are some people of people busy fixing their old ISO-9796 signature compliant implementations, too...
With luck, though, the IEEE 1363 standard for public-key crypto will start moving that segment of crypto towards provably secure methods. (see page at http://www.manta.ieee.org/groups/1363/ ). No clue when this is going to hit symmetric crypto -- anyone have a guess?
I think you may be a bit optimistic about a review time of hours. No matter how easy it is to publish the data on the web, the review process still involves people sitting down and reading the paper to see if it's Any Good(tm). This takes time. How much time depends on the paper and the field and the reviewer, but it's likely more than just hours.
Maybe a good question to ask is what an electronic journal is supposed to offer over an electronic preprint server. Preprint servers exist for several of the sciences; the most well known is the xxx.lanl.gov, but there are other more specialised ones too (my favorites are eprint.iacr.org / philby.ucsd.edu and the Electronic Colloquium on Computational Complexity).
Generally preprint servers accept submissions from anyone and do almost no review before posting something -- something like "is this a scientific paper in English" (although standards do vary). Then it's up to the archive users to figure out if something is any good or not. This means new submissions can go up almost as soon as they are received. The flip side is that sometimes things turn out to be wrong, and then they're marked as such *after* dozens of people have downloaded it and spent precious time trying to figure out what the heck is going on.
So does the main "point" of an electronic journal come in having better peer review than a preprint server? or is there something else?
Violent agreement on the idea of a book on
s /fall96/G22.3033.02/
failed protocols. I think protocol design one of the areas which is needed most and understood least in cryptography. We're a long way from Bellare's "a cryptographer is a machine which turns primitives into protocols"...
Can we start compiling some examples of protocols, exercises, and material
which would go into such a book?
Avi Rubin and Matt Franklin had a course on "Protocol Design" at NYU
http://cs.nyu.edu/cs/dept_info/course_home_page
which has an list of references and some problem sets. In particular, there's a reference to
some papers like
J. Moore, "Protocol Failures in Cryptosystems," Proceedings of the
IEEE, 5(76), 1988, 594-602.
and
P. Syverson, "Limitations on Design Principles for Public Key
Protocols," IEEE Symposium on Security and Privacy, Oakland, CA, 1996, 62-72.
which look very interesting.
The differences between SSL 1.0, 2.0 and 3.0
should be in such a book as well. Especially the
attacks in which an adversary can force use of a weaker cipher.
You'd probably also want a discussion of "security proofs" and "definitions of security."
In particular, pointing out limitations in such things as BAN logic. I don't know much about specific failures here; anyone have an example?
A while back I asked on sci.crypt about "provably stupid protocols" -- protocols where the proofs were _correct_, but according to misguided definitions. Looking that up in Deja would produce some possible examples (though maybe not protocols in the sense you may be using).
What else?
It's a shame, but not too surprising, to hear that the book doesn't
cover OAEP. Especially as Coron, Naccache, Joye, and Pailler have a paper in EUROCRYPT '00 about
"New Attacks on PKCS #1 v1.5 Encryption"
abstract at :
http://www.eleves.ens.fr:8080/home/coron/scienc
I have not read the paper yet, but the abstract is scary.
Some background : the RSA function x^e mod n
should not be used directly for encrypting data.
For one thing, it's deteministic; the same x produces the same x^e always. An adversary can use this to look for common plaintexts (consider what happens if you encipher a message letter-by-letter this way...). For another, there are all kinds of clever attacks which can recover messages which are related, or can break the scheme if you send too many messages, and so on.
Dan Boneh has a cool overview of these attacks and others in his "Twenty Years of Attacks on RSA" paper
http://crypto.stanford.edu/~dabo/abstracts/RSAa
Some kind of padding scheme is necessary. Some padding schemes are better than others. The scheme which pads with random garbage at the end of the message, for instance, is not very good.
The Public Key Crypto Standard (PKCS) #1 specifies the padding scheme used for RSA encryption. Version 1.5 had this scheme which was kind of thought to be sort of OK but nobody knew really. Now we are finding that it wasn't quite
as good as we thought...
Optimal Asymmetric Encryption Padding (OAEP)
is another padding scheme. It is specified in version 2 of PCKS #1 because it seems to resist the attacks which killed version 1.5 . The neat thing about it is that you would expect it to resist these attacks and others because there is a "proof of security" which relates breaking the padding to breaking the RSA problem.
That is, there's a proof which shows that extracting *any* information from the encrypted padded messages is just as hard as breaking the RSA problem on random instances. The scheme may still fail, but only if the RSA problem "underlying it" happens to be easy...like if we chose a too short modulus. We don't have to worry about stupid things like sending the wrong kind of messages any more.
Is it important that OAEP was omitted in a "practical" handbook? In my opinion, yes and no.
There's no need for the proof of security to be included. But the *reason* for the proof, that is, the existence of these really subtle and weird attacks which can leak information when you're not expecting it...that seems quite important in practice. Along with an explanation of how to use schemes like OAEP to cut out as many of these attacks as possible.
It's worth noting, however, that OAEP *is* described in the _Handbook of Applied Cryptography_, which is available for download at
http://cacr.math.uwaterloo.ca/hac/
No proofs here, just a straightforward diagram and "how to implement." For the actual proof, you can check out Bellare and Rogaway's paper at
http://www-cse.ucsd.edu/users/mihir/papers/pke.
OAEP is also specified in the IEEE P1363 standard, which has its website here :
http://www.manta.ieee.org/groups/1363/
the standard covers other algorithms and protocols as well. The website's worth checking out.
While we're at it, does anyone know of a good treatment/introduction to the proofs of security involved in OAEP and similar?
The Wired article refers to the Los Alamos group on quantum computation.
Raymond Laflamme's home page (his name is mentioned in article)
http://qso.lanl.gov/~laf/
Quantum Crypto & Computation at Los Alamos
http://qso.lanl.gov/qc/
The 7-qubit computation does not seem to be mentioned yet on the experiments page, but odds are it will be up soon.