New Research Cracks AES Keys 3-5x Faster 176
Landing his first accepted submission, qpgmr writes "AES, generally thought to be the gold standard for encryption, is showing weaknesses. From Computerworld: 'Researchers from Microsoft and the [Belgian] Katholieke Universiteit Leuven have discovered a way to break the widely used Advanced Encryption Standard, the encryption algorithm used to secure most all online transactions and wireless communications.'"
The full paper has lots of details. Note that it would still take a few billion years with current computers to actually break anything, but there may be further vunerabilities yet to be discovered.
Correction (Score:5, Informative)
The Katholieke Universiteit Leuven (KUL) is a Belgian, specifically Flemish, university not Dutch.
Bruce Schneier's take (Score:5, Informative)
Re:That's some mighty fine print you got there... (Score:4, Informative)
E=MC^2 you fucking retard
Re:That's some mighty fine print you got there... (Score:4, Informative)
Lets say it takes 2 billion years to crack 1 key.
Two billion years? At a billion keys per second I make it around 10^60 years to brute-force a 256-bit key. Use a billion gigakey crackers and you'd still take 10^50 years.
That was the whole point of picking a 256-bit key. It's not crackable by brute force using conventional computers even in theory until you control most of the mass of the universe.
Any AES-256 crack will be based on algorithmic flaws or quantum cryptography, not brute-force with conventional computers.
Re:"current computers" (Score:4, Informative)
An interesting observation. Though it is dampened by the fact that brute forcing encryption is pretty much the poster child of an application that lends itself well to parallel processing.
Re:"current computers" (Score:5, Informative)
No. To crack AES-128 the attack still requires work of the order of 2^126.1. A machine capable of cracking a 56-bit DES key in a second might be built for about US$5B, going by the price of the COPACABANA FPGA-based DES cracker (US$10,000 for a machine that can crack 56-bit keys in 6 days). Such a machine would take 140 trillion years to crack AES-128 by brute force, or 38 trillion years to crack AES-128 using the algorithm. If you had 38 trillion of these machines you could conceivably crack an AES-128 password in a year. But to give you some idea of how big 38 trillion is, if each of these 38 trillion machines could be made to fit in a 1U server box, the rack would be just over 1.672e8 km high, just a bit over one astronomical unit. You could build a bridge from the earth to the sun with that. If you spread that many machines out, they'd cover 8,892,000 square kilometers, which is more than the total area of the lower 48 states of the US, and you'd have enough machines left over to pave over just about half of Alaska. If they ran at 100 W each, the project would require 3.3288e16 kWh of energy, or 1.2e23 joules, about a thousand times more than the world's annual energy consumption.
For 256-bit keys the problem is even worse. The algorithm has a complexity of 2^254.4. The energy requirement of that staggering number, assuming a computer able to operate at the von Neumann-Landauer limit of ln(2)kT energy per bit flip, running at a temperature of 2.7 K, would require a staggering 1.24e54 J of energy, about the equivalent of 10 billion supernovas, or about a thousandth of the total mass-energy of the Milky Way Galaxy.
Broken by Microsoft?? (Score:4, Informative)
If you choose to believe some of the articles [computerworld.com], it was Microsoft who "broke" this encryption algorithm.
However, if you read the actual research paper [microsoft.com] the first page explicitly explains the relation between Microsoft and the researchers as "The authors were visiting Microsoft Research Redmond while working on these results."