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?

Improve this question
$\endgroup$
2
  • $\begingroup$ $2^{n}/2$ not $2^{(n/2)}$ surely? Or am I missing something here? $\endgroup$
    – Dave Howe
    Mar 27, 2015 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, 2015 at 18:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 at 12:40
  • 1
    $\begingroup$ Because KeySpace/2 is the average amount of tries required? $\endgroup$
    – Maarten Bodewes ♦
    Mar 27, 2015 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, 2015 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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