3
$\begingroup$

In brute-force attack calculations cryptographers say we should assume an attacker will find the key after $2^{(n/2)}$ tries. If n=128, then n/2=64. We know that this is practical (A 64 bit key is already found via brute-force by distributed.net). Then why 128 bit encryption is considered practically secure at present?

BTW, is birthday attack somehow relevant here? I think it is believed that 128 bit hashes are really not secure enough because of the birthday attack. So isn't that fact extendable to encryption too?

$\endgroup$
  • $\begingroup$ $2^{n}/2$ not $2^{(n/2)}$ surely? Or am I missing something here? $\endgroup$ – Dave Howe Mar 27 '15 at 15:08
  • 1
    $\begingroup$ Just to add to the confusion: your 2^(n/2) number is reasonably close to correct for symetric keys if quantum computing becomes a useful thing and is also correct or at least a bound for public cryptography built around the discrete log problem [DL over elliptic curves for example; discrete log over finite fields is basically the same as RSA factoring, which requires substantially larger key sizes for the equivalent strength] $\endgroup$ – Foon Mar 27 '15 at 18:04
15
$\begingroup$

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$).

It is required to only search half of the key space on average (if average is the correct term here, this is not something you are likely to repeat), but that means that the search should cover $2^{128}/2 = 2^{128-1} = 2^{127}$ on average.

So in the end it comes down to the difference between $2^{128/2}$ as used by the birthday attack (which is not applicable) and $2^{128} / 2$ which is the average amount of tries required by a brute force attack.

For an indication how the time scales with the number of bits, take a look at the stats of the RC5 72 bit challenge and compare it with the stats of the RC5 64 bit challenge that you probably referred to.


Birthday attacks are indeed not applicable to encryption. Collision finding - for which the Birthday attacks are used - are in itself not directly applicable to attacks on ciphers.

$\endgroup$
  • $\begingroup$ But cryptographers say we should assume that an attacker will find the key after trying half of the key space. so we for 128 bit keys we should assume $2^{64}$ tries is sufficient to assume finding the key is possible. Isn't that right? $\endgroup$ – user40602 Mar 27 '15 at 12:33
  • 10
    $\begingroup$ @user40602 Half of $2^{128}$ is $2^{127}$, not $2^{64}$, just like half of $2^{16}$ (65536) is $2^{15}$ (32768), not $2^8$ (256). Hopefully that clears it up. $\endgroup$ – Thomas Mar 27 '15 at 12:36
  • $\begingroup$ Oh sorry, I apologize! Apparently I forgot my math lessons!! Bad for cryptography :( Maybe the materials about birthday attack somewhat confused me. $\endgroup$ – user40602 Mar 27 '15 at 12:40
  • 1
    $\begingroup$ Because KeySpace/2 is the average amount of tries required? $\endgroup$ – Maarten Bodewes Mar 27 '15 at 12:48
  • 1
    $\begingroup$ @user40602 If I randomly pick a number between 1 and 10 and ask you to guess it, it will take you 10/2 = 5 tries on average to guess it. $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 27 '15 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.