Cryptogram: AES Broken?

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."

Quantum computing for white hats

[kingpin2k]

Wouldn't the same quantum computing that allows people to break today's crypto enable white hats to use increasingly complex algorithms and S-boxes to protect data? I mean, it's not as if crypto crackers are going to have these bad ass machines while the good guys sit around on 486's, right? Am I missing something?

The end of privacy

[bjelkeman]

on the golden age of privacy

That is quite a funny statement. 99% of all email is being sent in clear text, often passing through gateways which have permanent wiretaps installed. Phone tapping is at an all time high in the west and there are cameras on nearly every street corner around where I live.

Privacy.... I had a lot more privacy 20 years ago, that is for certain.

Quantum Computing and Privacy

[hillct]

Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware. International politics would be forever changed. The basis for personal freedom (now based on privacy) would have to shift to something as alien as mutual trust and maybe even respect.

The focus of international intelligence gathering would shift radically back to human intelligence (which is already happening for other reasons) and the new basis for security would become that of access cintrol through discontinuity - if you network is not connected to your neighbor's, then he can't get access to it regardless of his technical sophistocation.

The days of the NSA Sneaker-Net would return (picture NSA computer geeks running from one terminal to another with DLTs in order to keep the systems in communication, such that data could only flow in one direction.

Disclaimer: IANAF - I Am Not A Futurist

--CTH

Strictly Speaking

[Beautyon]

All of cryptography depends on a small number of problems that are believed to be hard.

This is not true; The "One Time Pad" does not rely on a difficult problem like factoring for its basis.

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.

OTP is unbreakable, and so "the golden age of privacy" will not end because of quantum computers.

Now legislation ending the golden age of privacy is another matter entirely.

Re:Quantum Computing and Privacy

[sql*kitten]

Consider, for a moment, the social changes that would imediately take place if privacy were nonexistant, in the sense that all cryptography could be broken with a trivial effort by anyone and their brother, using off-the-shelf hardware

How would this technology work against one-time pads? Besides, historically technologies have always tended to balance. Someone makes a better tank, then someone makes a better tank-killer, then the cycle repeats. If today's sophisticated encryption can in the future be defeated with cheap devices, then the crypto that this future society considers sophisticated would be well beyond ours. Consider the relative computational power of Bletchly Park and the sophistication of Engima of the early 40s and the power and sophistication of a 21st Century desktop PC.

International politics would be forever changed.

Not really. It would simply switch from broadcast and ciphers to the diplomatic bag and codes - which is how it worked for centuries. Complexity in international affairs is nothing new.

Old data is the problem

[BESTouff]

The problem is that old encrypted data doesn't "evolve" with the computing/crypto capacity.

Imagine some black hat just archived all encrypted data he could get (bank transactions, private conversations, you name it) then decrypts them in 10 years when he can buy his brand new quantum computer. All this old data may prove very valuable for him.

Perhaps very sensitive data shouldn't even transit on the net because you can't tell if it'll be decryptable in the future.

So use one-time pads

[wiredog]

They're easy to generate. All you need is a good source of randomness. A small analog input card connected to a thermocouple wire with a bad (therefore noisy) connection makes a wonderful source of randomness. Use the low four bits of a 12 bit card. Two reads gives one random byte. String random bytes together to generate however many you need.

Once you have the list of numbers, get the list of words and phrases to encode. Put one random number next to each word or phrase (watch for duplicate codes here!)

Put the pad on a cd, send it to whoever you want to communicate with. Doing this last part is the only large potential insecurity, plus it's inefficient. But the one time pad is theoretically unbreakable.

MAYBE?

[Winterblink]

maybe we need to assume that any given type of crypto is only temporary

If I'm not mistaken, this is rule #1 of cryptography. Doesn't really matter what algorithm you use or how secure everyone or anyone thinks it is, they're always able to be cracked. Which cryptosystem you use is more a measure of reasonable security -- do you want your messages secured for years, decades, etc., with an assumed increase of computing power?

Re:The end of privacy

[Winterblink]

Hah, too true. :) The "golden age of privacy" would be known more as the "golden age of privacy that nobody bothered to take advantage of when they could".

Re:Quantum computing =/= no privacy

[afidel]

In fact elyptic curves appear to be immune to quantum techniques that have so far been postulated. This does not mean that a fast method will not be found to break EC's simply that there is not yet any knowledge of a technique that significantly weakens EC's.

One Time Pad != Encryption

[Kjella]

Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an OTP and he can communicate securely with home base, but I mean for everyday use?

The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.

The OTP "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of pad rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).

Kjella
Kjella

Re:Quantum computing =/= no privacy

[aminorex]

It will always be the case that crypto which depends
on computational intractability rather than a
demonstrable computational impossibility will always
be open to some future innovation rendering it
trivial to crack. Elliptic curve crypto seems to
have the best prospects for the future right now,
and you can use it right now: El Gamal is
implemented in GPG.

But to say that QC will render effective crypto a
historical artifact is clearly mistaken. If it
were true, it would imply that there are *no*
hard problems any more, once QC techniques are
employed. All that QC can do is compute functions
over a finite field with effectively infinite
parallelism. It's unfortunate that most crypto
systems today rely upon functions over a finite
field, but there are plenty of hard problems that
are only valid over function spaces, for example.

Re:Sounds like sour grapes...

[epine]

I was in contact with the Twofish team during their candidacy concerning some work I had done on an improved instruction sequencing. One member of the team told me they figured rinjy was the most elegant proposal and that they would be very happy to see it prevail. Sure, they wanted to win. But more than that, they wanted the security industry to adopt a solid foundation.

There are times when Bruce has struck me as shrill or biased, but this isn't one of those times. What he's dealing with here is the very deep theme about whether the world's cryptographic fraternity is capable of sensing the right turn more often than not. If the wise men can't lead us to paradise, who can?

I'd say that's an issue worth talking about.

Re:'the' or 'you'

[Peter T Ermit]

Sorry -- dark nl is correct, and you're wrong. Here's an example of how to use a one-time pad: Your pad = random string of bits, like 0111 0101 0001 Your message = string of bits, say, 1010 1010 1010 Encrypted message = pad XOR message = 1101 1111 1011 Decrypted message = pad XOR encrypted message = 1010 1010 1010. It has nothing to do with substituting for words or letters. The drawback to one-time pads is that each side needs to have the same pad, which must be at least as long as the message to be encrypted. The pad has to be shared and stored in a secure fashion, which makes it impractical in most cases.

Re:One Time Pad != Encryption

[ssimpson]

The definitive text on cryptography, The Handbook of Applied Cryptography [uwaterloo.ca], defines the OTP as a type of encryption...I know this is Slashdot but I don't think your arbitrary definitions help here.

Sending a CD worth of random data via a secure channel in advance and then sending an encrypted message with the knowledge that it will be unbreakable is sometimes worth prior thought. Sure, it may not be usefull for the masses who require this kind of security or don't know their going to communicate in the future but to claim that this cipher "isn't encryption" is bull.