Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

New Research Cracks AES Keys 3-5x Faster

Unknown Lamer posted more than 2 years ago | from the before-the-heat-death-of-the-universe dept.

Encryption 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.

cancel ×

176 comments

"current computers" (0, Troll)

Anonymous Coward | more than 2 years ago | (#37137030)

  Note that it would still take a few billion years with current computers
 
That's about... oh... 20 minutes using NSA equipment.

Re:"current computers" (3, Insightful)

SquirrelDeth (1972694) | more than 2 years ago | (#37137096)

Or it would only take a year with a few billion computers.

Re:"current computers" (1, Insightful)

UnknowingFool (672806) | more than 2 years ago | (#37137692)

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.

Re:"current computers" (1)

calgar99 (856142) | more than 2 years ago | (#37137814)

You're not doing it right.

Re:"current computers" (1)

lordholm (649770) | more than 2 years ago | (#37138454)

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.

Re:"current computers" (3, Informative)

shaitand (626655) | more than 2 years ago | (#37138468)

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" (4, Informative)

dido (9125) | more than 2 years ago | (#37138904)

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:"current computers" (5, Funny)

Nialin (570647) | more than 2 years ago | (#37137100)

No, they just use Keyloggers.

Re:"current computers" (0)

CharlyFoxtrot (1607527) | more than 2 years ago | (#37137172)

That's about... oh... 20 minutes using NSA equipment.

The equipment in question being the large wrench they use to knock the password out of you.
Well to be fair it's actually more like 12 hours to whisk you away to an undisclosed middle eastern location, then 20 minutes of "cracking", but still.

Re:"current computers" (1)

JoshuaZ (1134087) | more than 2 years ago | (#37137268)

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/ [xkcd.com] .

Re:"current computers" (4, Funny)

DragonTHC (208439) | more than 2 years ago | (#37137516)

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:"current computers" (1)

Anonymous Coward | more than 2 years ago | (#37137594)

May I interest you in one of my premium tin foil hats?

Re:"current computers" (1)

intellitech (1912116) | more than 2 years ago | (#37139398)

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.

Re:"current computers" (1)

Pete Venkman (1659965) | more than 2 years ago | (#37137806)

*coughcough*proveit*cough*

Re:"current computers" (1)

lorenlal (164133) | more than 2 years ago | (#37137846)

*cough*whoosh*cough*

Insert crack joke here (0)

Osgeld (1900440) | more than 2 years ago | (#37137034)

n/t

Correction (5, Informative)

CharlyFoxtrot (1607527) | more than 2 years ago | (#37137060)

The Katholieke Universiteit Leuven (KUL) is a Belgian, specifically Flemish, university not Dutch.

Re:Correction (0)

Anonymous Coward | more than 2 years ago | (#37137424)

not Dutch yet

FTFY

Re:Correction (0)

Anonymous Coward | more than 2 years ago | (#37138860)

Seems like they teach Ingleesh, specifically Noparsingleesh, language not English.

That's some mighty fine print you got there... (4, Interesting)

geekmux (1040042) | more than 2 years ago | (#37137136)

"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:That's some mighty fine print you got there... (1)

a_n_d_e_r_s (136412) | more than 2 years ago | (#37137200)

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:That's some mighty fine print you got there... (0)

Anonymous Coward | more than 2 years ago | (#37137276)

That's not what Moore's law says.

Re:That's some mighty fine print you got there... (0)

Anonymous Coward | more than 2 years ago | (#37137318)

Right, but it's a trivial consequence of Moore's Law.

Assume that you have an integrated circuit (e.g a computer) which cracks AES keys. Moore's law says that every 2 years the density of an integrated circuit doubles. So in 2 years, you will be able to put two crackers on one circuit of the same size, thus cracking AES twice as fast.

Re:That's some mighty fine print you got there... (1)

AchilleTalon (540925) | more than 2 years ago | (#37138134)

Moore's Law maybe violated as soon as you reached the atomic scale. Soon or later, Moore's law will be violated. You cannot project it in the future ad infinitum.

Re:That's some mighty fine print you got there... (1)

KingMotley (944240) | more than 2 years ago | (#37137384)

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:That's some mighty fine print you got there... (1)

afidel (530433) | more than 2 years ago | (#37137354)

No, AES-256 would take the energy of every atom in the earth to brute force using known methods (it was in the same order of magnitude anyway, saw the calculations once).

Re:That's some mighty fine print you got there... (2)

Bengie (1121981) | more than 2 years ago | (#37137588)

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 bring it near the realm of practical with enough money.

Re:That's some mighty fine print you got there... (-1)

Anonymous Coward | more than 2 years ago | (#37137682)

Rubbish. I learned from *MY* CS teachers back in the 90s that all cryptography is crackable given enough time. At *current* hardware it is infeasible. 10 years from now? Think about the computers we had around 2000. Think about what we have now. 8 core, at 2-4ghz, 8 gig of memory are fairly common usually with a decent GPU attached to it with 100-500 cores available. The nice thing about cryptography works pretty good with parallelism.

Lets say it takes 2 billion years to crack 1 key.

Computational power doubles about every 2 years (faster if you use dedicated hw and more 'exotic' methods) for the about 1/3-2/3rds less amount of power.

So in a mere 62 years you would be able to crack it in a year. Hours if you wait 10-20 more years.

Things like what they just found means it will be feasible in 30 or so years.

AES was always known to eventually be crackable. It has an expiration date. Just like the DES40 it replaced. Hence the look for a new one. If it was actually 'perfect' and provably so they wouldnt bother.

Re:That's some mighty fine print you got there... (3, Informative)

0123456 (636235) | more than 2 years ago | (#37137730)

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:That's some mighty fine print you got there... (1)

afidel (530433) | more than 2 years ago | (#37137758)

Ahem [everything2.com]

Re:That's some mighty fine print you got there... (1)

Bengie (1121981) | more than 2 years ago | (#37137864)

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 brute-force..."

Its "effective" key size is smaller because of logic flaws.

Re:That's some mighty fine print you got there... (2)

zebslash (1107957) | more than 2 years ago | (#37139076)

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:That's some mighty fine print you got there... (-1)

Anonymous Coward | more than 2 years ago | (#37137644)

No, AES-256 would take the energy of every atom in the earth to brute force using known methods

What does that even mean? The 'energy of every atom'?! Fucking hell. Just when you think Slashdot comments can't get any fucking dumber...

Re:That's some mighty fine print you got there... (4, Informative)

Anonymous Coward | more than 2 years ago | (#37137714)

E=MC^2 you fucking retard

Re:That's some mighty fine print you got there... (-1)

Anonymous Coward | more than 2 years ago | (#37138220)

And the energy of every atom corresponds to cracking a cipher in what way exactly, you fucking retard?

Re:That's some mighty fine print you got there... (1)

mcrbids (148650) | more than 2 years ago | (#37138654)

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:That's some mighty fine print you got there... (4, Interesting)

FuzzyDaddy (584528) | more than 2 years ago | (#37137212)

Or "New attack reduces 256 bit key strength by two bits"

Re:That's some mighty fine print you got there... (1)

mysidia (191772) | more than 2 years ago | (#37137370)

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:That's some mighty fine print you got there... (2)

kelemvor4 (1980226) | more than 2 years ago | (#37137614)

That's weak, you need at least 1Gigabit key strength to protect your emails. Man up.

Re:That's some mighty fine print you got there... (0)

Anonymous Coward | more than 2 years ago | (#37137700)

Ewscray atthay, Iway ustjay useway igpay atinlay. Ytray
ackingcray atthay!

Re:That's some mighty fine print you got there... (2)

Skarecrow77 (1714214) | more than 2 years ago | (#37137966)

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:That's some mighty fine print you got there... (0)

Anonymous Coward | more than 2 years ago | (#37137668)

There is no evidence that 3 rounds of AES is any more secure than plain AES. Double DES is actually weaker than single DES; there is the possibility that a single decryption step can decrypt multiple AES passes. Nobody actually bothered to invest too much time analyzing multiple AES passes, so by using triple AES you are just using security by obscurity.

Re:That's some mighty fine print you got there... (1)

Baloroth (2370816) | more than 2 years ago | (#37137356)

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 and will be able to break AES in a few years, instead of a few billion. Assuming Moore's law continues, and that we don't switch to an entirely new computational system (i.e. quantum computers) in the mean time. .

Of course, you can always increase the key length (8196-bit encryption, anyone?)...

Re:That's some mighty fine print you got there... (2)

doublebackslash (702979) | more than 2 years ago | (#37137408)

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) storage space" Not so good.

Re:That's some mighty fine print you got there... (2)

Baloroth (2370816) | more than 2 years ago | (#37137828)

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 this low-entropy system, but with quantum computers (so faster at brute-forcing).

Regardless, the point of TFA is that AES isn't perfectly secure, so strict brute-forcing isn't necessary. And we have no real evidence that the construction of a perfect system is possible. 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. It might be entirely possible that a new mathematical system could calculate a 256-bit key in hours, instead of billions of years. Doubtful, but no one really knows.

Re:That's some mighty fine print you got there... (1)

bondsbw (888959) | more than 2 years ago | (#37138316)

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:That's some mighty fine print you got there... (1)

maxwell demon (590494) | more than 2 years ago | (#37139284)

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.

You don't have to go to such ridiculously large numbers. Even O(n^100) is basically unmanageable. It would mean that if the 64-bit case can be solved in a nanosecond (i.e. about 3 clock cycles on a current processor), the 128 bit case will need about 4*10^13 years, or close to 3000 times the age of the universe. I'd say that's pretty secure.

Re:That's some mighty fine print you got there... (1)

fyngyrz (762201) | more than 2 years ago | (#37139328)

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 the NSA and it's sibling agencies are using what YOU consider to be today's technology. Also very likely to be wrong.

Re:That's some mighty fine print you got there... (0)

Anonymous Coward | more than 2 years ago | (#37138228)

Your notation is a little unclear but Grover's algorithm actually runs in sqrt(n) time which would effectively halve the number of bits in a cipher, bringing AES 128 well within reach (similar to cracking DES now).

Re:That's some mighty fine print you got there... (1)

Entrope (68843) | more than 2 years ago | (#37137366)

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:That's some mighty fine print you got there... (1)

frozentier (1542099) | more than 2 years ago | (#37138292)

"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 (4, Informative)

condition-label-red (657497) | more than 2 years ago | (#37137144)

linky [schneier.com] ...

Re:Bruce Schneier's take (0)

Anonymous Coward | more than 2 years ago | (#37137214)

The quote he gives at the bottom of the link is a bit too pessimistic (or optimistic if you're a cracker):

Again, I repeat the saying I've heard came from inside the NSA: "Attacks always get better; they never get worse."

"Attacks might get better, but they never get worse."

(Fixed that For Bruce Schneier)

Re:Bruce Schneier's take (1)

ThatsMyNick (2004126) | more than 2 years ago | (#37137488)

Nope, they always do! (Unless you can provide an example where they havent, the statement stands)

Re:Bruce Schneier's take (0)

Anonymous Coward | more than 2 years ago | (#37137802)

Ahem. It's easy to prove that cracks don't always get better.

Let X be the fastest crack possible for a given encoding.

Try to improve upon X.

Fail. (Hint: By its definition, X cannot be improved upon.)

Q.E.D.

p.s. It may be decades/centuries before anyone can prove that X is actually the fastest, but that doesn't change the fact that X cannot be improved upon.

Re:Bruce Schneier's take (1)

Entrope (68843) | more than 2 years ago | (#37138000)

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:Bruce Schneier's take (1)

fyngyrz (762201) | more than 2 years ago | (#37139344)

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:Bruce Schneier's take (2)

Yaur (1069446) | more than 2 years ago | (#37138182)

one time pad

mod parent down! (-1)

Anonymous Coward | more than 2 years ago | (#37137248)

goatse warning

Re:mod parent down! (1)

CamoCoatJoe (972244) | more than 2 years ago | (#37137582)

liar

A billion years? (0)

Anonymous Coward | more than 2 years ago | (#37137204)

Who writes this stuff? Anyway, it surely is a long time. But should we be concerned? Read on http://csharptest.net/?p=523

A few billion years (1)

Doodlesmcpooh (1981178) | more than 2 years ago | (#37137242)

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?

Re:A few billion years (0)

Anonymous Coward | more than 2 years ago | (#37137386)

"The password is 12345..."
"12345, thats the combination on my luggage!"

Re:A few billion years (0)

Anonymous Coward | more than 2 years ago | (#37137442)

Given the sloppy way in which most people choose their passwords, the change of getting lucky is almost 100%.

Re:A few billion years (1)

AK Marc (707885) | more than 2 years ago | (#37137564)

A slashdotter never has a 100% chance of getting lucky.

Re:A few billion years (1)

fyngyrz (762201) | more than 2 years ago | (#37139354)

Some RealDolls(tm) would tell you otherwise. If they could.

Re:A few billion years (1)

maxwell demon (590494) | more than 2 years ago | (#37139380)

A slashdotter never has a 100% chance of getting lucky.

That's wrong. All you have to do is to start up nethack at full moon.

Re:A few billion years (1)

CamoCoatJoe (972244) | more than 2 years ago | (#37137600)

Surely a few billion years is the time it takes to try all the possible passwords.

Not at all. Sell your supercomputer, buy savings bonds from various governments (or gold if you insist), buy a better supercomputer in 90 years, crack in 10 years after that.

YMMV

Re:A few billion years (1)

PhunkySchtuff (208108) | more than 2 years ago | (#37139308)

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

We get all those little countries confused. (1)

iluvcapra (782887) | more than 2 years ago | (#37137362)

(sic) "Dutch Katholieke Universiteit Leuven."

Leuven/Louvain is in Belgium, not the Netherlands.

Re:We get all those little countries confused. (0)

Anonymous Coward | more than 2 years ago | (#37138992)

Hell, I'm Luxemburgish (really), and I can't tell them apart!

Belge an Holland, firwaat musst dir äech* esou ähnlech sin?? [cheezburger.com]

___
* No, that's not wrong. That's a dialect! Yes, this country of 400,000 people actually has many dialects!

The AES-128 "crack" requires 2^88 bytes of storage (2)

yeremein (678037) | more than 2 years ago | (#37137416)

To put that number in perspective, it would take a stack of 4GB hard drives extending past the orbit of Saturn...

Re:The AES-128 "crack" requires 2^88 bytes of stor (0)

Anonymous Coward | more than 2 years ago | (#37137430)

How many libraries of congress?

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

Anonymous Coward | more than 2 years ago | (#37137464)

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.

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

Skarecrow77 (1714214) | more than 2 years ago | (#37137978)

My porn collection would require a stack 3.5" floppy disks at -least- 12 or 15 feet high.

Re:The AES-128 "crack" requires 2^88 bytes of stor (0)

Anonymous Coward | more than 2 years ago | (#37138336)

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.

Re:The AES-128 "crack" requires 2^88 bytes of stor (0)

Anonymous Coward | more than 2 years ago | (#37139130)

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.

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

lbates_35476 (901961) | more than 2 years ago | (#37138022)

4GB hard drives? Is this 2001 or did you mean 4TB drives?

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

gstrickler (920733) | more than 2 years ago | (#37138244)

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.

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

AchilleTalon (540925) | more than 2 years ago | (#37138430)

And on the power consumption side, these will consume about 1 million TW.

Re:The AES-128 "crack" requires 2^88 bytes of stor (0)

Anonymous Coward | more than 2 years ago | (#37138446)

can you even buy 4gb harddrives?

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

complete loony (663508) | more than 2 years ago | (#37138492)

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 (4, Funny)

flonker (526111) | more than 2 years ago | (#37138714)

The NSA called. They deny that any such data center exists.

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

Psilax (1297141) | more than 2 years ago | (#37138962)

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

Re:The AES-128 "crack" requires 2^88 bytes of stor (1)

complete loony (663508) | more than 2 years ago | (#37139366)

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.

Unbreakable? (0)

Anonymous Coward | more than 2 years ago | (#37137456)

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.

Re:Unbreakable? (1)

CamoCoatJoe (972244) | more than 2 years ago | (#37137750)

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.

Re:Unbreakable? (1)

Skarecrow77 (1714214) | more than 2 years ago | (#37137994)

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.

Algorithm (0)

Anonymous Coward | more than 2 years ago | (#37137520)

or it didn't happen.

And what do its authors say about this method? (1)

jthill (303417) | more than 2 years ago | (#37137542)

They say, as the payload sentence of the abstract,

As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

Oblig xkcd (-1, Redundant)

Fnord666 (889225) | more than 2 years ago | (#37137662)

Olbigatory xkcd [xkcd.com] reference.

512 bit or more? (1)

Twinbee (767046) | more than 2 years ago | (#37137766)

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?

Re:512 bit or more? (2)

Entrope (68843) | more than 2 years ago | (#37137974)

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 weaknesses. Existing systems have very elegant structures that are simple in most respects, but they are complicated in certain ways because consistently simple designs are much easier to exploit.

(As a further complicating factor, using a longer key generally requires using more internal state and more rounds. You might -- or might not -- be able to double the block size, but to move from 128-bit to 256-bit keys, you are very likely to need to increase your cipher from [say] 8 rounds to 12. This means at least a 50% increase in execution time for the same amount of data, and possibly more. If the increased size bumps your S-boxes, state and code out of L1 cache, it will be much worse. If you cannot double the block size, but need to double your internal state size for the larger key, that will add another doubling of execution time.)

Re:512 bit or more? (1)

The Dancing Panda (1321121) | more than 2 years ago | (#37138018)

To try to answer your question as simply as possible: Yes, and No. It is generally fairly easy to increase the bit count, but then you have to go through and reencrypt all your data, which takes time, and energy, and depending on the attack, you still might be susceptible.

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's are elegant, they are just complex and take a lot of processor power to run.

Re:512 bit or more? (1)

flonker (526111) | more than 2 years ago | (#37138774)

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:512 bit or more? (1)

slew (2918) | more than 2 years ago | (#37138782)

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 by just doing the steps in reverse (effectively unshuffling the cards).

Now the trick of making an encryption algorithm is to have a set of algorithm where every possible key describes scrambling instructions that results in a completely different shuffle such that they aren't really related in any easy to crack way. The problem is that we don't really know how to do that effectively (this random permutation construction problem is related to one of the open problems of group theory).

If you describe your set of shuffling algorithm with very simple math, it is generally actually easier to attack mathematically. It takes lots of scrambling instructions to make up for the simple math (which makes your encryption complicated by length). With more complicated math it makes it harder to attack mathematically (in the case of AES and other modern ciphers, substitution tables are used to implement the complicated math).

So given we don't know how to simply construct sets of these random shuffling algorithms, how would we know that the design we came up with there is a "weakness" where for a sub-set of keys a certain sub-set of plaintext values map to some sub-set of cipher-text values (a sub-group/ideal or some other group-theoretic structure that can be easily analyzed and defeated). That's a big problem which nobody has an answer for yet, but if the sets are small enough that humans can analyze them, it's easier to see if they *might* have some weakness. If it's a huge set, no human could probably analyze them.

Actually if you really look at the guts of AES and other modern ciphers, they are actually constructed with very elegant math which is iterated (over several rounds). As an example, AES is a very straight forward iterations of two different SP (Substitution/Permutation) networks (one for the key schedule and another for the data). AES-128 runs this iteration 10 times, and AES-256 runs this iteration 14 times. The key and the data enter different SP networks and after each S and P stage the data stage is xored with the output of the corresponding key stage before heading into the next data S and P stage.

The AES permutation stages are basically just row shifts and small column "multiplications" (in a Galois field). This is a very simple "shuffle" of the data across the 128-bit data width. The AES substitution tables are sets of 8bit to 8bit tables which were constructed mathematically (to avoid any fears that they were created with back-doors which was a concern with the original DES substitution tables). This is basically a complicated 256 card random deck shuffle. All the operations can be implemented fairly easily on things as simple as a 8-bit microprocessor (8-bit lookup tables is the most complicated thing, the rest are just shifts and xors).

W/o the substitution table, all the shuffling would be really easy to invert mathematically. The set of AES substitution tables were actually selected to defend against two known mathematical attacks (linear and differential attacks) which were commonly used to attack other "simple" ciphers. In fact during the AES design analysis, there was some concern that since the substitution tables was constructed mathematically, it might not be "random" enough and perhaps the math that was used to create it could be used to somehow to create a weakness in the cipher. So far that hasn't turned out to be true, but there are some probabilistic attacks that claim this is a problem (e.g, the XSL attack).

But to answer your original question, even though AES and other modern ciphers are iterations over fairly simple math, it isn't that easy to increase the key size and add iterations and still be sure the cipher is certifiable (i.e, it has the property that there's no easier way to get the key than to guess it). For example, AES has 3 standard variants (128-bit key, 192-bit key, and 256-bit key) which were straightforward increases in the seeding of the key schedule and iteration counts. It was later discovered that there was a flaw in the way that AES initializes and runs the key schedule so that a 256-bit key wasn't exponentially more complicated to guess than the 128-bit key. This flaw wasn't obvious when the cipher was originally designed, but only came out later when the so-called boomerang attack was discovered. No free lunch. Basically we don't know what we are doing yet in this area of math, we are just scratching the surface.

Breaking Crypto... (0)

Anonymous Coward | more than 2 years ago | (#37137866)

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.

Yet more milking of the GreatCow (TM) (1)

GrandTeddyBearOfDoom (1483117) | more than 2 years ago | (#37138902)

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.

Broken by Microsoft?? (3, Informative)

AftanGustur (7715) | more than 2 years ago | (#37138990)

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."

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...