Brute Force Key Attacks Are for Dummies

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:

This is a companion discussion topic for the original blog entry at: http://www.codinghorror.com/blog/2006/07/brute-force-key-attacks-are-for-dummies.html

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.

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.

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.

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.

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.

“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) ?

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.

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

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.

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.

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…

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?

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.

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.

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.

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…

INSTRUCTIONS:

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.

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!

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.