I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at the current time. Can someone provide some information on this subject with quotable reference?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you need sentences/phrases to quote, or could you quote this? $\endgroup$– user991Commented Apr 10, 2012 at 0:17
-
$\begingroup$ @RickyDemer Some paper would be ideal, but probably the website will do. $\endgroup$– ThePiachuCommented Apr 10, 2012 at 0:36
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
The last major effort I know of for cracking keys was the Distributed.net effort.
You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP machines or (to use some rc5-56 numbers) nearly a half million Pentium Pro 200s." as it said in their press release.
At the time, they moved on to doing a 72-bit key, which would be 256 times harder.
If we do some Moore-Law-type hand waving, we'd see a $2^7$ (128×) increase in compute power in ten years. That means that if you started today, it would only be twice as hard as breaking 64-bits was a decade ago. Doable, but not many people would actually want to bother.
Even if you're a government, buying a zero-day exploit and tailoring your own malware would be cheaper.
$\begingroup$
$\endgroup$
Any symmetric crypto with key length of 64 bits or less can be brute forced with the relatively cheap copacobana hardware.
If a major player built special purpose hardware like this filling racks with $256$ copacobanas in parallel, they would in theory be able to brute force keys of $2 ^ {64 + 8} = 2 ^ {72}$ bits. But that is still a long way from 128 bits. To brute force 128 bits, you would have to connect $2 ^ {128-64} = 2 ^{64}$ copacobanas. That is just too many to be practically doable. Maybe it will be possible in 10 to 20 years or so, who knows. By then everybody has surely switched to 256 bit keys or longer anyway.
$\begingroup$
$\endgroup$
I am currently enrolled in an online course of cryptography by Prof. Dan Boneh of Stanford University. In one of the lectures, he told that currently algorithms where the brute force attack requires less than $2^{90}$ trials are weak and anything above that is safe. So, 128-bit is currently out of reach of the fastest machine present on earth, as it requires $2^{128}$ trials to crack it.
$\begingroup$
$\endgroup$
For RSA, the factoring challenge for 768 bit RSA modulus was met in December 2009. Authors published their procedure here. What this means is that if you have a RSA private key of 768 bit, you are potentially vulnerable to practical factoring attack with hardware available today.
