Cryptogram: AES Broken? 277
bcrowell writes "The latest CryptoGram reports
that AES (Rijndael) and Serpent may have been broken. The good news is that when cryptographers say 'broken' they don't necessarily mean broken in a way that is practical to exploit right now. Still, maybe we need to assume that any given type of crypto is only temporary. All of cryptography depends on a small number of problems that are believed to be hard. And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy."
Re:Quantum cryptography (Score:1, Informative)
In those terms, quantum encryption sets us back to way before we had public key encryption. Except now it's not just key distribution that's the problem, but the actual comms link. I know I don't have the appropriate wire leaving my house to Amazon...
Re:Quantum computing for white hats (Score:3, Informative)
Slightly different quantum computation will do though, quantum crypto allows transmission of entirely secure messages, that is an unbreakable system. It isn't guarenteed by the hardness of a couple of mathematical challenges but by the actaul laws of physics themselves. Not only can a quantum crypto stream not be broken, but it can detect when somebody attempts to listen in. This has been demonstarted using both air and fibre as a transmission system (can't be arsed to google for a link but there should be plenty out there, it was textbook for our quantum computation course).
On the other hand, a quantum computer would break all the old cryptosystems quite easily (not sure about eliptic curves), however they are years away from being feasible and there are a lot of hard problems to solve first.
Re:Quantum computing =/= no privacy (Score:5, Informative)
Quantum computing would break a range of encryption techniques, especially most public-key techniques, but nothing known today rules out new and more robust digital encryption technologies being developed that Quantum Computers could not break, and I imagine plenty of people are working on them.
Re:Maybe? (Score:3, Informative)
Since the one-time pad [std.com], that's when. This has been mathematically proven, as well, as early as 1910 or 1920, if I remember well.
OTOH, it is true that a one-time pad is symmetric (sp?) crypto. modern crypto, such as AES, DES, Serpent and others mentioned in Cryptogram are assymetric, and, as such, more susceptible to cracking methods.
Definition of "Broken" (Score:2, Informative)
Re:Maybe? (Score:2, Informative)
AES and DES are symmetric. Serpent probably is too, inasmuch as it was an AES finalist.
Re:Maybe? (Score:3, Informative)
Re:So use one-time pads (Score:2, Informative)
Here it's fitting to note the words of Steve Bellowin:
In operation, there are many 'gotchas' to watch out for, never reuse a pad for example.
Google for 'Venona' and 'one time pad' for a good example of even the experts (KGB et al) getting one time pads wrong.
Addendum (Score:4, Informative)
(See here) [ibm.com]
That's the wrong way to use them. (Score:2, Informative)
If you number individual words and phrases, then you can only use each word or phrase once, otherwise it's not a one-time pad anymore. Think about it... how long would it take a cryptanalyst to figure out the code for "the" or "you"?
The pad should simply be a chunk of random bits, and both sides need to keep track of which bits have been used. Then encrypt your messages by xoring them with an unused stretch of bits.
Re:This was completely predicable because... (Score:1, Informative)
One of the requirements of the AES contest was that the algorithms could run on an 8-bit smartcard. Therefore Twofish, Mars, RC6, etc also have 8-bit implementations.
Re:Strictly Speaking (Score:2, Informative)
OTP is not unbreakable.
While the algorithm itself isn't breakable, the strenght of a OTP based solution will still depend on several weak points, like the random number source.
There's plenty of room for trying to attack it, using statistical analysis and estimates to try to be able to break it.
Re:This was completely predicable because... (Score:4, Informative)
Umm... you might be a little confused as to how AES was selected. AES selection criteria were public, as were discussions on the strengths (and weaknesses) of finalist algorithms. In addition, I know two of the AES conference program committee personally, and believe that had the NSA attempted any shinanigans, they would have been resisted and/or reported loudly.
These knee-jerk reactions to the NSA being evil really are counter-productive. Of course there are evil people in the US Government; there are evil people in every walk of life. I just don't think there are enough evil people in the NSA to conspire against the "good" people in the NSA.
You might be too young to remember, but back in the 70's there was a big commotion about the NSA modifying IBM's original S-Boxes. Many people at that time claimed very loudly that the NSA was inserting a back door into the algorithm. The NSA was pretty tight-lipped about why they made these changes; I think they still are, BTW. As it turns out, the original IBM S-Boxes were more succeptable to differential cryptanalysis than the ones the NSA reccomended for use with DES.
Remember that the NSA has a dual mandate. First, it is supposed to intercept, decode, and/or decrypt foreign elint intercepts. This is one of the reasons why they're one of the largest employers of foreign language specialists. Second, they are supposed to develop technologies to protect US national interests. The two missions sometimes conflict, but ever since Herb Lin at the National Academy of Sciences published his report on why it is in the US' national interest to allow widespread use of strong crypto for domestic applications, most (if not all) of the NSA types I've encountered have supported the development and use of strong crypto.
Of course, there are federal groups that like to sneak into people's homes and install keyboard sniffers. But, if that is going to be your law-enforcement surveilance technique of choice, why bother forcing bad crypto on the populous?
quantum computing & one time pads (Score:5, Informative)
I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.
As for public key cryptography, most but not all public key cryptosystems are completely broken by quantum computers. Luckily we still have some public key cryptosystems that have not yet been broken using quantum algorithms. Elliptic curve discrete log is one such example.
Some Clarifications (Score:3, Informative)
- ElGamal is not an elliptic curve algorithm. Its a classical public key encryption system based on the discrete logarithm problem. Most DL problems can be refactored as elliptic curve problems though, so perhaps the poster was referring to a possible EC ElGamal. At any rate, I'm pretty sure GPG uses classical ElGamal.
- Symmetric ciphers are rarely broken by raw computational power (brute force). In fact, algorithms above about 80 bits are impossible to break by brute force due to the laws of physics.
- Quantum Cryptography today involves means of transmitting data at very low bitrates over a channel in which eavesdropping is impossible. QC is pretty much only useful for exchanging keys for symmetric algorihms (like AES, Twofish) securely, as the data rate is to slow to be practical for anything else.
- Assymetric Cryptography (public key) is based on several hard problems. The two that are used widely today:
* The prime factoring problem (RSA)
* The Discrete Logarithm problem (DSA, ElGamal)
One will become widely available soon:
* The elliptic curve problem
- Yes, OTP is still perfectly secure, but its still perfectly useless, as w/ OTP you just shift the security to two other areas; truely random pad generation, and secure distribution of the pads.