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.
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.
Or it would only take a year with a few billion computers.
No, they just use Keyloggers.
"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.
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?
That's about... oh... 20 minutes using NSA equipment In order for this sort of thing to be cracked quickly one would need either ridiculously fast computers even by the standards of something like the NSA. It is more plausible that the NSA is aware of improved algorithms that would allow much faster key recovery. In that case, this improvement is likely irrelevant. It is more likely that they will be able to break things due to implementational problems such rather than direct key retreivable. So I'd be more concerned about side-channel attacks and the like. Also, obligatory xkcd: http://xkcd.com/538/.
(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...
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.
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?)
They're using their grammar skills there.
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.
May I interest you in one of my premium tin foil hats?
Not necessarily. Some problems are not solved faster by parallel computing. ie. If it take 9 months for a 1 woman to have baby, you can't get 9 women to have a baby in one month.
Well, there's spam egg sausage and spam, that's not got much spam in it.
OTP is unbreakable, but you could argue that it isn't a "solution". :^)
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.
If I steal your hard drive, you can't destroy the data anymore, or replace the solution on that hard drive. Even if I don't steal it, you're relying on having a secure way to destroy the data. OTOH, how much is a few bad sectors of old data worth?
If you can count on detecting the breach, and can take steps to make the data unimportant more quickly (change passwords, report card numbers stolen), then you just need enough time to react. If you can't do something like that, then the crypto needs to last until the data isn't sensitive anymore.
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
*coughcough*proveit*cough*
You're not doing it right.
*cough*whoosh*cough*
My porn collection would require a stack 3.5" floppy disks at -least- 12 or 15 feet high.
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.
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
And on the power consumption side, these will consume about 1 million TW.
Achille Talon
Hop!
No, but you can pipeline it and have one baby per month if you wait one month between creating each baby. This gives you a throughput of one per month after the initial setup time.
"Civis Europaeus sum!"
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.
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..."
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.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
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
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.
And if you order now, you'll receive not one, but TWO, free bath robes, and a children's bible for junior. Call now, because this offer won't last long.
vos nescitis quicquam, nec cogitatis quia expedit nobis ut unus moriatur homo pro populo et non tota gens pereat.
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
So, you're saying we might have to work weekends?
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?
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 they have quite that much advanced knowledge about cryptography. These people are there to spy and coerce, so they are also as Machiavellian and manipulative as they can get.
http://www.moonlight3d.eu/
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.
Which is great and all until they use them quantum backscatter thingamabobs to read your login from your noggin while your noddin'. Then they get your password and decrypt in a matter of seconds.
Get a web developer
Is that why customers always tell me their computer feels slow after a while and the only way to fix it is to reinstall the OS? I just thought it was malware ridden and the "registry fixer" they ran (that was also coercion-ware) borked it beyond all chance of repair.
Get a web developer
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 zero implications the NSA today.
So you move the embryos/foetuses to another uterus every month? I don't think you grasped either pregancy or pipelines completly...
Ooh Ooh Can we pave over the half that Sarah Palin comes from?
I think you've been read too many times
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?
http://www.moonlight3d.eu/
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.
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.
No sig today...
Seriously?
The one-time pad 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 sufficiently long, then so is the key, and then even brute force is infeasible.
Obviously, this method is not practical for general use, but it is useful where there is an accessible and secure side channel (secure wire, military courier, etc.) through which to distribute the one-time key. It is vulnerable to side-channel attacks, but only complete ones. Knowing part of the key will only allow you to decrypt the equivalent part of the message; assuming the key was truly random, there is no way to derive the remaining parts.
OK, so it's difficult, but theoreically possible?!
To have a right to do a thing is not at all the same as to be right in doing it
So, by analogy, in the time it takes to crack one encryption code, we can crack them all?
Even more plausibly: NSA knows your password and private key already, even if they don't have backdoors into your encryption software.
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.
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)
No sig today...
It's much easier to add a couple more rounds of encryption.
No sig today...
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.
Yes, well, this just so happens to be one of those problems that is suited very well for parallel computation.
Everyone gets a chunk of ciphertext and an assignment of keyspace to chew through. Whoever wins the lottery and gets meaningful cleartext out of it reports back to "dispatch."
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...
The operative word being "theoretically" - meaning "Possible in theory" which in no way means "Possible in practicality"
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...
No, it wasn't. NIST did that, and they did it mostly because:
1. Most finalists voted for themselves as first place
2. Most finalists voted for Rijndael
It is worth noting however that Rijndael was voted over Serpent primarily because Rijndael was significantly faster, where Serpent was significantly stronger!
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...
Er, make 2 read:
2. Most finalists voted for Rijndael as runner-up
(new slashdot + network service trouble = fail)
For large sets, this will be our guide even unto death, for the LORD will work for each type of data it is applied to...