Slashdot Mirror
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."
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.
Akvo.org - the open source for water and sanitation
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
--Got Lists? | Top 95 Star Wars Line
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.
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.
Serpent and Rijndael are vulnerable to this attack - it seems Twofish isn't - damn government should have chosen Twofish for AES instead...
Seriously, though - any approach that manages to reduce the difficulty of cracking these algorithms by a factor of 2^100 is impressive, and Schneier at least simplifies it enough that us folks with very rusty number theory can appreciate the achievement.
His comment later in Cryptogram about his name appearing on a list of banned words is much, much scarier - looks like he's upset someone in the content censorship Gestapo. That same content filter would deny access to today's Slashdot front page - nasty.
oh brave new world, that has such people in it!
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:
6 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703
6 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703 * 1 = 11196101758632245023844192896470191898640653514665 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703
11196101758632245023844192896470191898640653514
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:
11196101758632245023844192896470191898640653514
It's probably worth noting that IBM has already demonstrated a quantum computer running a factoring algorithm:
(See here)
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
Live today, because you never know what tomorrow brings
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.
-I like my women like I like my tea: green-
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?
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.