Slashdot Mirror
New Research Cracks AES Keys 3-5x Faster
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.
Note that it would still take a few billion years with current computers
That's about... oh... 20 minutes using NSA equipment.
n/t
The Katholieke Universiteit Leuven (KUL) is a Belgian, specifically Flemish, university not Dutch.
If all else fails, immortality can always be assured by spectacular error.
"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.."
linky...
Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
Who writes this stuff? Anyway, it surely is a long time. But should we be concerned? Read on http://csharptest.net/?p=523
Surely a few billion years is the time it takes to try all the possible passwords. Although the chances are slim is it not entirely possible that a file could be cracked in seconds if you got lucky?
(sic) "Dutch Katholieke Universiteit Leuven."
Leuven/Louvain is in Belgium, not the Netherlands.
Don't blame me, I voted for Baltar.
To put that number in perspective, it would take a stack of 4GB hard drives extending past the orbit of Saturn...
How many libraries of congress?
From the article:
"But the work, the result of a long-term cryptanalysis project, could be the first chink in the armor of the AES standard, previously considered unbreakable."
I would love to know who considered AES, or any from crypto for that matter, "unbreakable". In the olden days, when the Earth was young, crypto/security experts were naive and were ego driven into thinking they could be the one to produce the unbreakable crypto solution. However, after a few decades of failure, now anybody and everybody in the industry understands that "unbreakable" is just a fantasy.
No security expert, especially a crypto expert, worth their salt would believe any solution is unbreakable. There may be some solutions that have not been broken yet, some not worth the effort, and some because the effort has not gone on long enough. In the end, any crypto solution is breakable, and if it hasn't been broken yet, it will be; it's just a matter of time.
While any crypto will eventually be broken, what matters is, can it be broken in time to do anything useful; for an attacker to leverage the data attained and undermine the vested parties. If an attacker attempts to hook into a financial transaction, can the crypto solution secure the transaction long enough to prevent the attacker from leveraging the data in the transaction. Or, if a user needs to secure the confidentiality of data, can the crypto solution assure effectiveness until the data is either destroyed by the user, or until a new confidentiality solution is implemented, or until the user decides it no longer requires confidentiality. Just some examples.
Any time someone publishes an algorithm that requires such insane space requirements, I have to question their analysis. Often they assume O(1) random lookup when any real implementation would be O(log(n)). Such a difference could easily cause this "5x" crack to have worse performance than brute-force.
p.s. Who the hell still uses 4GB drives? Saying 1/500th of the way to Saturn with 2TB drives doesn't sound as cool I guess.
or it didn't happen.
As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.
As always, all IMO. Insert "I think" everywhere grammatically possible.
liar
This is not a signature.
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?
Why OpalCalc is the best Windows calc
I've done better attacks on RSA - I've reduced the area of attack primes by many orders of magnitude. AES is a very complex algorithm however.
My porn collection would require a stack 3.5" floppy disks at -least- 12 or 15 feet high.
4GB hard drives? Is this 2001 or did you mean 4TB drives?
Well, here's a better visual. Using 2TB (2^41 bits), you would need 2^47 drives. Using 3.5" (1" x 4" x 5.25") drives, arranged into cubes 24 high x 6 wide x 4 deep (allowing ~1/4" for power and data cables on the depth), you get 476 drives in a 24" cube (2'). For simplicity, let's call it 256 (2^8) drives in a 2' cube, allowing some space for cooling and mounting hardware. That means you need 2^39 such cubes. That's a cube 2^13 (8192) x 2' on each side. 8192 x 2 = 16384' = ~ 3.1mi (~5km) per side. That's 4x as high as the tallest building in the world and larger than the largest "downtown" in the world. Alter the shape into a more conical structure and you have a literal mountain of hard drives.
make imaginary.friends COUNT=100 VISIBLE=false
How would it be log(n)? They are just precomputing a bunch of plaintext-ciphertext pairs and storing them in a hash table. Hash tables are constant time access.
And on the power consumption side, these will consume about 1 million TW.
Achille Talon
Hop!
can you even buy 4gb harddrives?
135TB in a 4U Blackblaze storage pod, 280 rack units in a 20' x 8' [ ... x 8' high? ] shipping container, 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.
09F91102 no, 455FE104 nope, F190A1E8 uh-uh, 7A5F8A09 that's not it, C87294CE no. Ah! 452F6E403CDF10714E41DFAA257D313F.
The NSA called. They deny that any such data center exists.
It seems that those who know that in a Universe containing Humans who have Free Will and Choice, P actually equals NP since the Human Mind is a Nondeterministic Universal Machine which permeates Universal Computability. A functional NDTM chooses by irreducible free will. A computer can harness this by taking input from its user. Without human users, AI is weak, but together WE ARE STRONG! Hoom.
-- The Grand Teddy Bear has Spoken: "Windows 8 Source Code Available NOW! more disgusting than your pr..."
Is my math wrong but i come to different numbers:
20'x8'
135TB * 280 = 36.9 PB
2^88 Bytes = 274 877 906 944 PB
=> ~ 7.5 Billion shipping containers
1 container = 160 ft => 1miles = ~174240 containers => ~43000miles
=> stack 8 high => 5380miles => 73 miles to each side
40'x8'
135TB * 1400 = 184.6PB
=> ~ 1.5 Billion shipping containers
1 container = 320ft => 1 miles = ~87120 containers => ~17220miles
=> stack 8 high => 2152miles => 47 miles to each side
maybe there is some space left beneath area 51
If you choose to believe some of the articles, it was Microsoft who "broke" this encryption algorithm.
However, if you read the actual research paper 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."
echo '[q]sa[ln0=aln80~Psnlbx]16isb572CCB9AE9DB03273snlbxq' |dc
Hash tables are constant time access.
That's true in your PC, but it's not true on the scale we're talking about. ;)
Once you leave the confines of the PC, it's a bit more obvious that memory access is O(memory-bits). Imagine that you're doing memory-mapped IO across a serial bus (e.g. USB or SATA). Keep doubling the number of external hard drives until you get it.
---
p.s. Now imagine an array of memory units (DRAM modules or hard drives) too large to fit on the planet. Suddenly the speed of light delays are going to start eating your lunch, and you'll have to start worrying about O(cube-root(bits)) average speed-of-light propagation delay. Keep multiplying the number of memory units by 8 until you get it.
p.p.s. No fair imagining that the array is so massive that it becomes a black hole.
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.
09F91102 no, 455FE104 nope, F190A1E8 uh-uh, 7A5F8A09 that's not it, C87294CE no. Ah! 452F6E403CDF10714E41DFAA257D313F.
Every single attack against AES that I have heard of until this date has taken advantage of some weaknesses in the key schedule. This one is no different. It seems like it is about time to design a new key schedule for AES while keeping the main cipher the same. The new key schedule should be a pseudorandom function generated from the key to avoid those attacks that reconstruct the key schedule after memory has been turned off for a little while and some of the bits in the schedule has been corrupted. If the key schedule wasn't so regular it would only take very few corrupted bits in the schedule before it is faster to brute force the key than to figure out which of the bits in the schedule are corrupted.
Obviously a pseudorandom key schedule would be much slower than the current key schedule. But for most uses you will encrypt a lot of data once you have set up the schedule, so a more expensive schedule is an acceptable price. Personally I'd look a little bit on blowfish for inspiration on how to make a strong key schedule.
If a new key schedule is defined, I think it might be worthwhile to increase the number of rounds a little bit. It seems the initial safety margin was a bit on the small side. This of course will not just slow down generation of the key schedule but also slow down the main cipher. But that may be a price worth paying.
Hopefully hardware to compute AES was designed in a way that you can give it a key schedule generated in a different way, and tell it how many rounds to use. If hardware was limited to exactly the three numbers used by the original AES, that would be unfortunate. If such hardware is known to exist the new number of rounds could be decided as follows. 128 bit key, 14 rounds. 192 bit key, 14 rounds. 256 bit key 20 rounds. That way hardware that is able to do 14 rounds (currently used with 256 bit keys) will work for 128 and 192 bit keys, and hardware that is able to do 10 rounds (currently used with 128 bit keys) will work for the 256 bit keys by using it twice.
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.
make imaginary.friends COUNT=100 VISIBLE=false
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 useful thing to have than a larger key. That was one of the criticisms of AES is that it doesn't have a lot of rounds. What is has was determined to be sufficient, and history has bore that out (it is the most analyzed cryptosystem in history and is still strong) but there wasn't the margin that some like Schiner would have liked.
Now in either case the problem you run in to is processor power. Remember that for real world use, you want to be able to do encryption as part of other tasks. I don't want to have my computer sit and do nothing but encryption, I want it to work in the background. Like say I want to use full disk encryption. Ok well that means that the encryption has to run in realtime, in the background. So not only does it need to be able to stream at like 500MB/sec so as to not slow things down, but it really needs to be able to do that without taking up too much of my CPU so my system doesn't bog down.
The more complex the encryption, the harder it is to do that. Get massive key sizes, hundreds of rounds, and you've built some great security margins in, but at what cost? Maybe nobody uses it because it is too damn slow.
In terms of complexity, that is actually a criticism of AES. It is one of the few that has a rather simple and elegant mathematical definition. That worries some cryptographers as it may mean there is a simple mathematical method to reduce the complexity of solving it.
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.
Um, yeah it does. Haven't you heard of Area 51?
tia
The Admin and the Engineer
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 :)
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.
If this was China, you'd all be up in arms, firearms, probably.
Max.
You didn't paraphrase them correctly.
The NSA neither denies nor confirms that any such data center or data centers do exist or do not exist.
Twenty years ago hard drives were 100 MB. Now they are 2 TB, that's a x20000 increase roughly 2^14 increase. If the trend continues (I have no idea when we will hit a hard wall in storage space) it will probably fit into something the size of a thumb drive in 60 years.
That's not very far. I can see Saturn from my house.
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.
Nothing amazes me more about the human condition than the pornographic attraction of not having to think. It's as if our giant brain achieves maximal jizz by turning itself off.
Transmutation of lead into gold has been pondered for at least 300 decades. But it's good to know that in 300+epsilon, mission accomplished. I've never understood the attraction of reverse inference from hubris: find a bunch of stuffed shirts with jumbo pocket protectors yammering as if they had a giant brain (long after they have switched it off), write down all the things they got wrong, conclude the opposite, Bob's your uncle. Genius without effort. Don't add water, lather, rinse, or repeat.
This kind of thing is people who have switched their brain off drawing inference over larger pools of people who switched their brains off. What could go wrong? Nearly every principle of robust statistics is violated by inference on low-hanging counter-examples of hubris pricked.
A few examples higher up the tree: chemical process to transmute lead into gold, faster than light space travel, anti-gravity machine, perpetual motion yielding exploitable work.
If the Babylonians had discovered the fountain of youth, there would be some sprightly poster here with a six digit negative slashdot ID crying out "but I said it could never be done 3000! years ago!! and it still!!! hasn't!!!!" supposing Babylonians are prone to excess with chisel marks.
Suppose I could offer you the wager that if you go without until AES is broken, the gods of well-earned entitlement will deliver 700 air-brushed virgins (of your preference gender) for your eternal pleasure. Would that be enough to turn your brain back on? Or would you grab for a pair of decades and roll the dice?
Of perhaps among the exponential sample space of ridiculous things we haven't invented yet (and never will) some of the problems are impossibly hard independent of our impatience level or proneness to jump to conclusions.
All Turing machines halt if you wait long enough, supposing waiting until it doesn't is the only falsification that meets brain-on-dialtone acceptance standards.
Since breaking AES by brute force is about as respectable as pursuit of the fountain of youth, it made me think about my proposal of 700 virgins, assuming they behave like women scorned as you advance through the starving ranks. Since we're in the business of breaking AES by brute force, let's assume we've already solved the problem of living forever. This is a true proposition for testing your faith in the stopping algorithm.
Secretary problem
The probability here is 1-1/e that you'll wind up spending forever-1 nights with the 700'th virgin as not delivered on xmas morning, with a mean memory of 350 other xmas packages who would brighten eternity oh so much better.
Think hard, you're playing for keeps.