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.
Re:Correction (Score:4, Funny)
Cool, the mods changed the summary. Since the error was in TFA this means we are in the historically nearly unprecedented situation of having a summary that's more correct than TFA ;-)
(What I meant to say is, good job.)
Re: (Score:2)
Cool, the mods changed the summary. Since the error was in TFA this means we are in the historically nearly unprecedented situation of having a summary that's more correct than TFA ;-)
(What I meant to say is, good job.)
Er, hopefully it was the near legendary "slashdot editors" who changed the summary.
Re: (Score:2)
Funny thing is, Joan Daemen and Vincent Rijmen - the ones who developed the Rijndael which later became AES, both worked at the KUL...
That's some mighty fine print you got there... (Score:5, Interesting)
"New Research Cracks AES Keys 3-5x Faster"
(the fine print)
"it would still take a few billion years with current computers to actually break anything.."
Re: (Score:2)
Given Moores law a crypto attack will get double the speed about every 2 years so it was known from the start
that AES had a limited time to be secure. It was just a matter of time until the crypte lenght become too short given the CPU power you can add to break it.
So this means that we just have to upgrade to a new krypto about 4 years earlier then if it had not been found for it to still be safe.
Re: (Score:2)
Re: (Score:3)
Yeah, my cousin took an advanced cryptography class for CS, and his teacher ran the math on brute forcing a 256bit key with the theoretical physical minimum amount of energy required with ultra-advanced technology, on average would consume more usable energy than there is in the MilkyWay.
Brute forcing is out of the question for sure, unless we start to consume galaxies for energy.
Unfortunately, AES isn't perfect, and it's effective strength is much lower than 256bit. The 3-5x reduction might be enough to br
Re: (Score:2)
Brute forcing is out of the question for sure, unless we start to consume galaxies for energy.
It's OK as long as it's other people's galaxies and not our own though isn't it?
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: (Score:2)
Re: (Score:2)
Which is why I said "brute force"
From one of the links going around:
"...having an ideal computer, working at the freezing temperature of 3.2 Kelvin...
Even sucking all the energy from a supernova would be just enough to pass through all states of a 219-bit counter... So, it is clear that a 256-bit key (which, just to be represented while we brute-force it on our ideal computer, would require the energy that 400.000.000.000.000.000.000 suns like our sun radiate in a year...) seems errrr... kinda difficult to
Re: (Score:3)
I learned from *MY* CS teachers back in the 90s that all cryptography is crackable given enough time.
Well, they forgot to teach you about the one-time pad.
Re: (Score:2)
As stated elsewhere, there are various ways around this limitation, including the use of reversible computing which works by "borrowing" entropy resulting in an extremely low entropy computation mechanism.
Re: (Score:2)
Re: (Score:2)
Doesn't matter: Do the math with a single electron transition per key and you still need to capture the entire energy output of the Sun to brute force a 128-bit key in a useful time. Not going to happen.
Re:That's some mighty fine print you got there... (Score:4, Informative)
E=MC^2 you fucking retard
Re: (Score:2)
And the energy of every atom corresponds to cracking a cipher in what way exactly, you fucking retard?
Someone above calculated how much energy would be used by 38 trillion computers in parallel working to brute force AES encryyption.
Executive summary: a lot.
Re: (Score:2)
Given Moores law a crypto attack will get double the speed about every 2 years so it was known from the start
that AES had a limited time to be secure. It was just a matter of time until the crypte lenght become too short given the CPU power you can add to break it.
I don't think you quite grasp the scale of the numbers here. It's easy to say "just use a million PCs" but setting up that many PCs, powering them all and just plain keeping them all running is way harder than you think. Numbers in the tens of thousands is probably more realistic (even for the NSA).
Quoting Moore's Law doesn't work either: A better way to think of it is to figure out how much energy you'd need to brute force a 128-bit crypto key. Assuming the lowest power unit possible to check a key, ie. on
Re: (Score:2)
Umm.. It's close enough. Moores laws states that you can place twice the number of transistors in the same space every 2 years. This is roughly the same as twice the speed every two years, and it would be assuming you are just adding more cores and producing the same die size.
Re: (Score:2)
Re: (Score:2)
Re:That's some mighty fine print you got there... (Score:5, Interesting)
Re: (Score:2)
Or "New attack reduces 256 bit key strength by two bits"
I'm not too worried about it, as i've already switched to Triple-Rjindeal scheme, eg 3AES256 with a keying analogous to 3DES keying option 1
So they're reducing a 768 bit key strength by what, 0.2% ?
Re: (Score:3)
Re: (Score:3)
I use 1.21 jiga-bit flux encryption.
As soon as I think up something that I need to encrypt, I bang my head into the sink until I forget it, confident that I'll come back in time from the future (or send a suitable representative in a life vest) to remind myself what it is I wanted encrypted when I need the information.
Re: (Score:2)
Re: (Score:2)
i've already switched to Triple-Rjindeal scheme, eg 3AES256
with a keying analogous to 3DES keying option 1
You're doing it wrong:
a) There's no proof that this will increase the strength, it might weaken it.
b) You'd be better off adding whitening (ie. AESX, analogous to DESX)
c) Much better to just increase the number of rounds in standard AES.
(Yeah, I know you were being facetious, but...)
Re: (Score:3)
There is an existing key schedule attack [schneier.com] against AES-256 (attack complexity 2^119) and AES-192 (complexity 2^176). The existing attack is a related-key attack, and some modes of operation (e.g. XTS as used by TrueCrypt) are not vulnerable to it.
The big deal about this paper is that it (a) operates in a single-key model, rather than requiring a related-key; and (b) is the first attack against full round AES-128.
The reason that AES remains a better choice than serpent or twofish is precisely because this sor
Re: (Score:2)
Ah. So it might be enough time to develop a new standard.
Incidentally, do any of these calculations of "a billion years" take into account Moore's Law? Has anyone developed an actual calculation taking into account the rate of computer advancement? (It'd still be secure enough for daily use, but still.) Some quick math shows that if computers double in power every 2 years, then the time to break it halves every 2 years. Or, in 60 (2*2^30=~ 1 billion) years computers will be 1 billion times more powerful an
Re: (Score:3)
http://everything2.com/user/dogganos/writeups/Thermodynamics+limits+on+cryptanalysis [everything2.com]
Who cares about Moore's law. Read that.
Now it STILL might get broken. Attacks better than brute force are always the largest threat. However nobody need worry about the brute force computer to break their codes. Not even quantum computers help here, by the way. See Grovers Algorithm. Preview: "Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storag
Re: (Score:3)
Reversible Computing [wikipedia.org]
It could theoretically overcome the limits of thermodynamics on computers. Basically, AFAICT it requires us to (nearly) perfectly observe the computer so that we could reverse any changes that take place in the system, so they would generate very, very little entropy (limited by how well we could build them.) Essentially, they can reuse any energy already used in computation with a very low degree of loss. Also, you might want to look at "Adiabatic quantum computation". Essentially thi
Re: (Score:2)
Nor, for that matter, that P!=NP, which is a more or less essential assumption in public-key cryptography. If it isn't, then as the key size grows, time to brute-force increases linearly, not exponentially as we think it does.
Not necessarily. Even assuming P = NP, the conversion from the NP problem to the equivalent P problem doesn't necessarily take linear time. And it doesn't mean that the P solution itself can run in linear time. If it turns out that both the conversion and the P solution are O(n^10^10^10^10^10), they would be practically worthless for anything.
Re: (Score:2)
Look. Brute force: Division... divide a million by three, by subtracting three from the dividend and counting how many times it happens before the dividend rolls past zero. 333k cycles. Now do long division. 8 cycles. Snap, it's done.
Now jump forward a decade or two... quantum computing... probabilistic algorithms... Snap, AES is cracked. Never assume that today's technology will be applied to tomorrow's problems. If you do -- everything you come up with is very likely to be wrong.
Finally -- never assume th
Re: (Score:2)
Re: (Score:2)
ECRYPT II specifically lists AES-256 as protected against analysis by quantum computer (unless Shor's algorithim applies), People should be more worried about asymmetric crypto, although even there alternatives have been developed. As a fully capable quantum computer won't spring into existence suddenly, I presume we would have a few years to switch.
"Both of the fundamental intractability assumptions on integer factoring and discrete loga-
rithms break down if a (large) quantum computer could be built as dem
Re: (Score:2)
The fine print from the summary isn't even quite accurate -- the attack complexity is slightly more than 2^125. If you assume computers can check about a billion (2^30) keys per second, and given that you have about 2^25 seconds in a year, you would need about a trillion (2^40) computers to guarantee success in a billion years. (125=30+25+40+30.)
Re: (Score:2)
"New Research Cracks AES Keys 3-5x Faster"
(the fine print)
"it would still take a few billion years with current computers to actually break anything.."
Yeah, but that still means were down to 5 billion years from the previous 25 billion years, right?
Bruce Schneier's take (Score:5, Informative)
Re: (Score:2)
Re: (Score:2)
Has anyone come up with better attacks on ROT13 lately?
There are also putatively strong cryptosystems that have simply not been the focus of much recent study, and so nobody has devised better attacks on them, even though better attacks probably exist.
Re: (Score:2)
Camera. Keylogger. Drugs. A dull, but ragged edged knife. Waterboarding. Possession of your daughter. Need I go on? There are always new attacks. Security is not what you think it is; consequently, neither is encryption, from ROT13 to the most advanced thing you're aware of (which is unlikely to be the most advanced thing the government is aware of, btw.)
All encryption does is secure one avenue. There are always others.
Re: (Score:2)
Except for waterboarding and maybe keyloggers, none of those are new. They are also not attacks in the sense that everyone else is talking about.
Re: (Score:2)
Re: (Score:3)
We get all those little countries confused. (Score:2)
(sic) "Dutch Katholieke Universiteit Leuven."
Leuven/Louvain is in Belgium, not the Netherlands.
The AES-128 "crack" requires 2^88 bytes of storage (Score:3)
To put that number in perspective, it would take a stack of 4GB hard drives extending past the orbit of Saturn...
Re: (Score:2)
135TB in a 4U Blackblaze storage pod [backblaze.com], 280 rack units in a 20' x 8' [ ... x 8' high? ] shipping container [pingdom.com], gives 9.5PB or log2(135 * 8 * 10^12 * 280 / 4) 2^56 bits of raw online storage.
So now you *only* need 4 billion (2^32) shipping containers... yeah right. Stacking them 8 high, with no space for walkways or roads, would cover an area at least 55 miles on each side.
Re:The AES-128 "crack" requires 2^88 bytes of stor (Score:5, Funny)
The NSA called. They deny that any such data center exists.
Re: (Score:2)
In the time it would take to create such a thing efficiently, it would probably be possible to do it in 1/4th of the size :)
Re: (Score:2)
In the time it would take to create such a thing efficiently, it would probably be possible to do it in 1/4th of the size :)
And in the time it would take the government to build such a thing, it will have become commodity desktop hardware.
Re: (Score:2)
Re: (Score:2)
That's a 135TB, *4U* server. And I was counting 2^88 data storage as bits not bytes, though I'm not sure if the paper specifies the size of a data object anywhere. So (( 2^32 / 8 ) * 20' * 8' )^1/2 = 293K feet per side.
The blackblaze is a full length server case, so you wouldn't fit 1400 of them into the 40' container.
Re: (Score:2)
My porn collection would require a stack 3.5" floppy disks at -least- 12 or 15 feet high.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Some minor corrections to my post above. 2TB is 2^41 bytes (not bits). 3.5" form factor is 1" x 4" x 5.75" (not 5.25").
Someone mentioned power usage. Assuming 5W/drive typical/average power, 5 x 2^47 = ~700TW. This is approximately 47x the 2008 worldwide energy consumption rate [wikipedia.org].
And what do its authors say about this method? (Score:2)
As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.
512 bit or more? (Score:2)
As someone who knows next to nothing about encryption, here's a question. If this ever becomes a problem, can't one VERY easily increase the bit count from 256 to 512 or more for an exponentially stronger encryption?
And more generally, I've heard these algorithms are very complicated. Rather than having this enormous complexity, can't you use a simpler, more elegant math algorithm, and again, just increase the bit count say from 256 to 512bit or more? Or does math not support that?
In this age of terabytes,
Re: (Score:3)
It is usually not practical to pick "a simpler, more elegant math algorithm" because those are easy -- or at least easier -- to break. As someone mentioned up-thread, and as Bruce Schneier likes to remind us, attacks tend to get better over time -- they never get worse.
Modern cryptosystems are carefully tuned to resist a lot of clever attacks. Probably every stage in every (credibly) proposed encryption scheme has been closely examined by very smart people to understand its behavior and look for weaknesse
Re: (Score:2)
The reason the algorithms are complex is because they can't be easily reversible. It can't be obvious from the encrypted text as to what the key is, or what the decrypted message is, otherwise your encryption is useless. These algorithm
Re: (Score:2)
Increasing key size is not simply a matter of encoding things twice, as there may be an attack where they can take a shortcut, reducing the practical key strength.
Some additional reading:
http://x5.net/faqs/crypto/q61.html [x5.net]
http://x5.net/faqs/crypto/q85.html [x5.net]
Re: (Score:2)
As someone who knows next to nothing about encryption, here's a question. If this ever becomes a problem, can't one VERY easily increase the bit count from 256 to 512 or more for an exponentially stronger encryption?
And more generally, I've heard these algorithms are very complicated. Rather than having this enormous complexity, can't you use a simpler, more elegant math algorithm, and again, just increase the bit count say from 256 to 512bit or more? Or does math not support that?
In this age of terabytes, does it really matter if we all save a few bits?
Cipher design is pretty complicated, but with a little bit of hand-waving, it might be able to explain the problem.
The task of creating a cipher (encryption algorithm) is basically the same problem as creating set of algorithms for shuffling a deck of cards a certain way. The deck of cards starts in order and the data you want to encrypt is where the deck is "cut". Then you shuffle the cards using some instructions (set by the key) and then you figure out where in the deck that card ended up. You decrypt
Bits aren't really the issue (Score:2)
I don't know that you'll ever be able to brute force a 256-bit key, presuming that there are no weaknesses and you get all 256-bits of entropy. I mean the energy levels involved would be, like, galactic (as in the energy contained in a galaxy) in scale. So until we develop a completely different method of computing, that isn't a problem.
The problem comes in when you are able to find weaknesses in the algorithm and break rounds of it, and thus decrease the complexity. So really, more rounds are the more usef
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."
Re: (Score:2)
Science Daily correctly summarizes the true meaning of this research: First Flaws in the Advanced Encryption Standard Used for Internet Banking Identified [sciencedaily.com]
Re: (Score:2)
Yeah, I didn't expect they were looking at Windows 7 search to find anything. I expect they were just visiting Niels Ferguson and got talked over to include Microsoft in the paper.
I have a method... (Score:2)
I have a method to crack them 10 times faster.
Its called using 10 machines.
That said its not going to make much of a difference if you're pressed for time because the universe is going to die of death-heat before you finished.
REQ: obligatory and germane XKCD plz (Score:2)
Paranoid take (Score:2)
They build in this weakness to be able to present the paper - one more paper to let your research institute exist! AES is (mostly/partly?) from Leuven.
Nah, just joking, Leuven is pretty well respected, I don't think it will disappear overnight.
Not China? (Score:2)
If this was China, you'd all be up in arms, firearms, probably.
Re: (Score:3, Insightful)
Re: (Score:2, Insightful)
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: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
So, you're saying we might have to work weekends?
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re:"current computers" (Score:5, Funny)
Re: (Score:2)
Re: (Score:2)
But wasn't AES chosen from a hos of candidates by the NSA? As far as I remember, they had external cryptography experts on that.
If you are a guy who thinks tinfoil hats are fashionable, you might come to think that the NSA might have chosen AES because they knew how to break it all along, but none of the civilian experts saw flaws in it. Now, the first one of the deliberate flaws actually showed up. While I believe that any such organization would pull that kind of stunt in an instant, I do not believe that
Re: (Score:2)
The algorithm is known to be secure. Even with this compromise, according to several crypto guys I've read responses from, even by today's standard AES is very much secure. They did saw if you apply the current computing trends, likely it won't be, on the upper end, in another decade or two.
So even with this weakness, assuming the NSA has vastly more massive computing power available than anyone things, it would require ALL of their computing power for a considerable duration. So pragmatically, this has zer
Re: (Score:3)
What do you mean by "known to be secure"? Do you mean that nobody knows how to break it or that there is a formal proof that no shortcuts for brute force attacks exist?
Re: (Score:2)
All this attack shows is that AES should have had a couple more rounds built into it, ie. the number of rounds wasn't sufficient to remove all trace of the key. You can recover 2 or 3 key bits with less work than a brute force search.
I'm not sure how they chose the number of rounds for AES but it doesn't seem like there was much of a safety margin (only ten loops with a 128 bit key??)
Short version: The algorithm is still secure, we just need to increase the loop count a bit.
Re: (Score:2)
Re:"current computers" (Score:5, Funny)
you mean our equipment?
it's widely known that the NSA uses all known operating systems for distributing computing tasks.
So every windows computer connected to the Internet will accept NSA task packets and compute them and send them back. It does this seamlessly though so the user never sees anything. They built it into the TCP/IP stack. It just becomes easier with windows and even Linux. (SELinux anyone?)
Re: (Score:2)
Re: (Score:2)
*cough*whoosh*cough*
Re: (Score:2)
Re: (Score:2)
Yes, that's what probability and statistics are all about. The time quoted to break an encryption method generally is either worst case or worst case/2
Re: (Score:2)
Re: (Score:2)
Some RealDolls(tm) would tell you otherwise. If they could.
Re: (Score:2)
I would love to know who considered AES, or any from crypto for that matter, "unbreakable".
Dan Brown.
Read digital fortress. It's actually quite an enjoyable ride, as long as you note right up front that Dan Brown's version of reality read like James Bond's version of international relations.
Re: (Score:2)
The one-time pad [wikipedia.org] is, from an information theoretic perspective, perfectly secure. Essentially, you take a randomly generated key of the same length as your message and perform some operation between the two (it needn't be any more complicated than a bitwise XOR) that completely obscures the message and the key. Provided that you never use the same key twice, there is no way for someone else, knowing only the ciphertext, to obtain either the message or the key, apart from brute force. If the message is su
Re: (Score:2)
However, after a few decades of failure, now anybody and everybody in the industry understands that "unbreakable" is just a fantasy.
a) DES has never been broken, nor is it likely to be. The best known attack against DES is brute force (discarding the impractical attacks...)
b) There's no reason to believe we can't make a 128-bit cypher which is as secure as DES.
(in fact AES with more rounds is probably as secure as DES, the only thing this new attack has shown is that AES needs more rounds)
Re: (Score:2)
It's much easier to add a couple more rounds of encryption.