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

Comments

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.

Re:Quantum computing =/= no privacy

[stevelinton]

Quantum Computing and Quantum Cryptography are unrelated technologoies. Quantum crypto is indeed "unbreakable", but requires a single physical channel connecting source and destination. It will not carry over routers and absolutely cannot be used for normal internet email for instance.

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

Factorisation of large primes is easy

[Anonymous Coward]

Contrary to what appears to be a prevailing belief on slashdot that it's difficult to factor large primes, with current advances in parallel computation and quantum computing this is actually quite an easy task. I present to you the following 1024 bit prime:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703

Now we have to factor it. We step up to the main terminal of our quantum computer beowulf cluster and type in the question, "Of which numbers is this the product?". Qubits flip, waveforms collapse, a cat in a box somewhere dies (of radiation poisoning, strangely, or charmingly), and out pops the statement:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703 * 1 = 11196101758632245023844192896470191898640653514665 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703

quantum computing & one time pads

[David Jao]

For a professional mathematician, reading all the uninformed opining here on quantum computing and one time pads is, frankly, painful on the eyes.

I'm a Ph.D student at Harvard. I've done cryptography research in the past. So listen up people.

1. Quantum computing does not destroy cryptography as we know it. It is important to realize exactly what quantum computing does and does not do. For symmetric ciphers, quantum computers reduce the cost of brute force search by a square root. So AES goes down from a 2^256 cipher to a 2^128 cipher. But 2^128 is still quite safe. And even if AES were to fall, it would not be an insurmountable problem to design something better.

   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.

2. One time pads are not the answer. Yes the security of one time pads has been proven but this proof relies on a stronger-than-you-think collection of assumptions that is almost never realized in real life. One time pads are very useful in certain situations but completely unsuitable for cryptography as most people use it.