Brute Force Key Attacks Are for Dummies

July 10, 2006

Cory Doctorow recently linked to this fascinating email from Jon Callas, the CTO of PGP corporation. In it, Jon describes the impossibility of brute force attacks on modern cryptography:

Modern cryptographic systems are essentially unbreakable, particularly if an adversary is restricted to intercepts. We have argued for, designed, and built systems with 128 bits of security precisely because they are essentially unbreakable. It is very easy to underestimate the power of exponentials. 2^128 is a very big number. Burt Kaliski first came up with this characterization, and if he had a nickel for every time I tell it, he could buy a latte or three.

Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.

If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking.

Each additonal bit doubles the number of keys you have to test in a brute force attack, so by the time you get to 128 or 256 bits, you have a staggeringly large number of potential keys to test. The classic illustration of this exponential growth is the fable of the mathematician, the king, and the chess board:

There is an old Persian legend about a clever courtier who presented a beautiful chessboard to his king and requested that the king give him in return 1 grain of rice for the first square on the board, 2 grains of rice for the second square, 4 grains for the third, and so forth. The king readily agreed and ordered rice to be brought from his stores. By the fortieth square a million million rice grains had to be brought from the storerooms. The king's entire rice supply was exhausted long before he reached the sixty-fourth square. Exponential increase is deceptive because it generates immense numbers very quickly.

By the time you get to that 32nd chessboard square, you're facing a very large number indeed.

chessboard illustration of exponential growth

However, 2^32 isn't necessarily a very large set of keys when you're performing a brute force attack with a worldwide distributed network of computers. Such as the RC5 distributed computing project. Here's what they've done so far:

The earliest 56-bit challenge, which ended in 1997, tested keys at a rate of 1.6 million per second. The ongoing 72-bit challenge is currently testing keys at the rate of 139.2 million per second. We're testing keys 88 times faster than we were 10 years ago, through natural increases in computing power and additional computers added to the distributed computing network.

And yet the RC5-72 project still has 1,040 years to go before they test the entire keyspace. Remember, that's for a lousy 72-bit key! If we want to double the amount of time the brute force attack will take, all we need to do is tack on one teeny, tiny little bit to our key. 73-bit key? 2,080 years. 74-bit key? 4,160 years.

It's painfully clear that a brute force attack on even a 128 bit key is a fool's errand. Even if you're using a planet covered with computers that crack keys at the speed of light.

If you're a smart attacker, you already know that brute force key attacks are strictly for dummies with no grasp of math or time. There are so many other vulnerabilities that are much, much easier to attack:

  • Rootkits
  • Social engineering
  • Keyloggers
  • Obtain the private key file and attack the password on it

Of course, beyond ruling out brute force attacks, I'm barely scratching the surface here. Jon Callas' Black Hat conference presentation Hacking PGP (pdf) goes into much more detail, if you're interested.

Posted by Jeff Atwood
21 Comments

There is an excellent UW course online about this very topic:

http://www.cs.washington.edu/education/courses/csep590/06wi/

The introductory lesson already touches on the enormous size of the number space that is the root of the security of modern cryptography.

But then again, as further lessons show, security by size alone may be deceptive as long as tricky mathematics allows to significantly reduce the search space.

Henry Boehlert on July 11, 2006 4:31 AM

At least, until quantum computers become a reality :)

"fact a quantum computer capable of performing Shor's algorithm would be able to break current cryptography techniques in a matter of seconds"

http://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/spb3/

Also let's not forget Deep Crack (http://en.wikipedia.org/wiki/Deep_Crack ) which can break a 56bit DES message in 22 hours.

Peter Bridger on July 11, 2006 9:17 AM

Thinking about SSL connections with bank. Which is a much large problem than secure email(who cares). It is a classic case of using an Armoured Truck to go from cardboard box to cardboard box. The local workstation will always be the weakest point.

You also have not mentioned MITM attacks.

I do not see this changing in the future either. Amoured trucks will still go from cardboard box to cardboard box. And networks will always be soft and goey on inside.


rid00z on July 11, 2006 9:22 AM

We're testing keys 88 times faster than we were 10 years ago

Math error here, or typo?

139.2 billion / 1.6 million = 87,000.

Not to say 88 times faster isn't impressive. But it's nowhere near as impressive an illustration of futility as 87,000.

WaterBreath on July 11, 2006 9:27 AM

It's a typo on my part.

RC-72 rate: 139,270,116,320 keys/sec (currently..)
RC-56 rate: 1,578,699,548 keys/sec

Thanks for the correction.

Jeff Atwood on July 11, 2006 10:43 AM

"Chessboards don't have red squares, but an interesting post nonetheless. :-)"

trivia: yes, they can have any contrasting colors and , over the years, I've used many variants, including red and black. Now back to important stuff.

I doubt if Kevin Mitnick ever tried to hack a password, even with a reduced search space. The real dangers are as mentioned above. Can we ever get "everybody" to avoid typing personal data when answering an email (phishing) ?

barry on July 11, 2006 10:56 AM

Also let's not forget Deep Crack

OK, so Deep Crack is a 1998 vintage massively parallel bit of hardware dedicated to keycracking. It tests 90 billion keys per second. Let's assume you could build a machine like that today which is 100 times faster. So the 2007 version can test 9 quadrillion (9 x 10^12) keys per second.

http://www.jimloy.com/math/billion.htm

The 128 bit keyspace is 2^128 or..

3.40 e+38

dividing that by

9,000,000,000,000 keys/sec

I get

37,809,151,880,104,273,718,152,734 seconds

which is..

1,198,920,341,200,668,243 years

A 128-bit key seems quite safe from a modern Deep Crack; it's also safe from an array of them. At any rate, I think governments and other truly paranoid organizations use 1,024 bit keys, just to be sure.

Jeff Atwood on July 11, 2006 11:07 AM

On the chessboard s/32868/32768/ (Pedantic, but someone may use it as a reference.)

hgs on July 11, 2006 11:45 AM

Just a comment on 1,024 bit keys (vs. 128 bit): don't confuse symmetric cryptography with public-key cryptography (where 1,024 bit keys are commonly used with e.g. RSA). You cannot compare the two.

C-J Berg on July 11, 2006 12:31 PM

1024 vs 128 is different; public key encryption has significant key-reduction algorithms applicable, so the bitlength has to be much higher to compensate (1024 is standard now, the paranoid go with 2048+).

The US uses 128 AES for most normal communications, or 192-256 for secret/top secret stuff. It doesn't even bother to support keys over 256 because it's already so insanely high for the foreseeable future.

Foxyshadis on July 11, 2006 12:49 PM

Finally, I know the reason why the US are trying to get to Mars ;)

They want to build a sand-grain computer factory there and cover the planet with them...

Daniel on July 11, 2006 1:13 PM

Key cracking remains (as it has been for years) primarily of interest to mathematicians and statisticians; real security has long since left the realm of key bitcounts and complicated algorithms. Talking about cracking PGP is a fascinating mental exercise, but it just simply isn't relevant to *security* anymore.

The biggest security threat - social engineering - is still just as big as it ever has been. Actually, it may even be bigger, because technology is now in the hands of more people - and yet the average understanding of that technology remains fairly poor.


What worries me personally is that I see these articles about how impossible it is to crack n-bit keys on a fairly regular basis, but I honestly can't recall having seen any articles about defending against genuine security vulnerabilities outside of dedicated security interest groups. The "256 bits is really secure" discussion has certainly captured the imagination of the public at large, but personally I think that in so doing its primarily lasting effect is to create a false sense of security.


Oh, hell... 512 bits ought to be enough for anybody, right?

Apoch on July 12, 2006 9:05 AM

Although, if it was set up so that computer 1 would test all combinations 0-Z, then the second 00-0Z, the third 10-1Z, etc, it could prove very effective (ie setting a small area or each one to test.

Gold Blade on March 21, 2007 4:15 AM

Sory about this. I figure that the ultimate defense against brute-force attacks would be to have a waiting period after some number of failed attempts. So no matter how fast it goes, there's gonna be a loooong wait.
If it does 100 million keys a second with 256 bit and a 1 minute wait in between every 10 failed attempts:
(2^256+((2^256/10)*1))/100000000=6.947525354238971... e+69 seconds, or 2.2030458.. e+62 years at most. Your power bill would be pretty high by the time it did every possible one with those factored in.

Gold Blade on March 21, 2007 4:39 AM

Sorry but I think the original e-mail is wrong. I've done my own calculation and I come up with an average time to crack a key of around 1000 seconds, not 1000 years. Has no one else checked it? If you're in the cryptography field then surely you don't trust without proof?

My assumptions:

Distance across grain: 1e-3 m
Space occupied by grain of sand: 1e-9 m^3
Speed of light: 3e8 m/s
Surface area of earth: 5.1E14 m^2
Volume of covering earth to 1m depth: 5.1e14 m^3
Average number of guesses required: 1.7e38

Which gives:
5.1e23 Grains
3.3e-12 Seconds for light to traverse a grain
3e11 guesses per grain per second
1.5e35 Total guesses per second
1.1e3 seconds per successful guess.

I agree with the sentiment though - 128 bit brute force attacks are currently unthinkable.

Ross on May 10, 2007 9:17 AM

Think of a so called quantum computer. With a nice trick by using the nature of quantummechanics research is trying to build a computer which can do only one thing, better than a normal computer: cut numbers into prim-numbers...and this it what it's needed to break crypthografic keys...
theoretically it works, but in practice the best quantum computer in the world can calculate at the moment 15 = 5 * 3; the highest refactoring to primnumbers...the technical equiment needs like in anicent time of the normal computer rooms and halls for place...
I am sixty now, and i hope i can see a quantum computer working in about five or ten years. We here in Canada are the best in the materie of quantum computers...

Plunga on May 10, 2007 12:33 PM


INSTRUCTIONS:
1) Name your brute
2) Pick your brutes colors
3) Click Arena
4) Pick another brute to fight
5) Watch your brute fight someone elses brute and have absolutely no control over what happens.
6) Go back to your brutes cell, look at his experience and weapons gained, then rinse and repeat.

alucard on June 5, 2009 1:10 PM

Chessboards don't have red squares, but an interesting post nonetheless. :-)

I think the great irony is that despite our practically unbreakable security, there's *always* going to be some idiot who will happily type their PayPal password into a phishing page.

Key's under the welcome mat, let yourself in!

Aaron G on February 6, 2010 9:47 PM

I've seen chessboards with various shades of off-white and any dark alternating colour, but never red and black... that's a checkerboard. Maybe I just haven't looked hard enough, but being a n3rd in childhood I saw my fair share of chess boards.

And yes, quantum computers will be able to solve arbitrary-length encryption in mere slivers of a second, and they will also run on sunshine, lollipops and rainbows.

Aaron G on February 6, 2010 9:47 PM

I use 256-bit keys to defend against possible future weaknesses discovered in the algorithm that allow better than brute-force attacks. I know full well that given a theoretically ideal computer (in terms of energy use for computation achieved) and extremely optimistic assumptions about the amount of computation required to check a key, it would still take the energy output of a supernova to crack the key if brute force were required.

Also, from what I know, quantum computers will have only a very limited effect on symmetric key cryptography. From what I know, the search algorithms possible using a quantum computer effectively halve the key-length of a symmetric key, which makes symmetric keys still pretty darn good, even with quantum computers.

Lastly, all known asymmetric algorithms completely fail in the face of a working quantum computer with a sufficient number of gates. These are the algorithms that typically require key lengths of (at the very least) 1024 to be secure. In fact, in order to achieve a level of security equivalent to a 256-bit symmetric block cipher key, you currently need something like an 8192 bit asymmetric key. But, for a 30 year time window, 3072 bits is probably enough.

The exponential increase relation does not hold for asymmetric keys. The increase in computation required to break per added bit goes up by more than a polynomial factor, but by less than an exponential one.

Of course, once again, with quantum computers with a sufficient number of gates, adding a bit just gets you a linear increase in computational complexity to break, which is exactly the same order of increase as it takes to use. But this is _only_ with asymmetric key cryptography, not with symmetric key.

Omnifarious on March 14, 2011 3:15 PM

Sorry if I am posting it at the wrong place. It will be very appreciated if someone can help.
How can I build a hardware device for brute force attack?
It's an electronics project. I have to develop a prototype for a device to perform a 'brute-force' attack upon a keypad entry system. The device may assume a keypad of 3 columns and 4 rows. It may also assume a pass-code of 4-6 key-presses. The device will be required to press the keys and record (sound) the result - to differentiate valid guesses from invalid. The device may sequentially try various keystrokes in order to determine the correct 'combination'. It is this guessing (trial-and-error) which makes it a 'brute force' technique. Can someone help us?

G on September 20, 2011 3:13 AM

The comments to this entry are closed.