2
$\begingroup$

The likelihood of breaking, for instance, an AES-128 cipher is 100% after $2^{128}$ tries in brute force, meaning that I've got to try $2^{128}$ keys to certainly break it.

What if I (hypothetically) had recorded $2^{128}$ bits of data encrypted with the same AES-128 key? How does this help in cryptoanalysis?

And how is the situation differently if or if not a part of this data (e.g. word file headers, specific telnet handshakes, whatever) was known plaintext?

|improve this question|||||
$\endgroup$
  • 4
    $\begingroup$ It will take $2^{127}$ tries on average, not $2^{64}$. If the probability of each guess being correct is $1/2^n$, it takes $2^n / 2 = 2^{n-1}$ guesses to have a 50% chance of success. $\endgroup$ – Reid Mar 12 '14 at 23:34
  • $\begingroup$ What Maraste may be thinking of is how most modes of operation can be broken with $2^64$ blocks. $\hspace{.46 in}$ $\endgroup$ – user991 Mar 13 '14 at 1:18
  • $\begingroup$ You're, of course, right. In my defense: it was 1 a.m. local time after a very tiring day. :( I corrected it to full 2¹²⁸ tries, as it is maybe more straight forward and doesn't influence the question itself. $\endgroup$ – Marste Mar 13 '14 at 9:26
  • $\begingroup$ In your 2nd sentence: Just having "bits of ancrypted data with the same key" is looking at the wrong level. First, single bits don't matter, but we always have to look at full blocks. And then: ciphertext only is a very very weak attack scenario. Even for a weak block cipher like DES, this amount of data wouldn't be usefull (for DES, brute force is the way to go nowadays anyway). AES is designed in a way to resist chosen plaintext attacks, which you didn't even mention, but it that is the targeted goal for recent block ciphers. $\endgroup$ – tylo Mar 13 '14 at 12:55
5
$\begingroup$

Quite apart from the correction that Reid made (it takes $2^{127}$ attempts to achieve a probability of 50% of finding the right key; with $2^{64}$ attempts, the probability of success is $2^{-64}$), with AES, there is no known way to take advantage of known (or even chosen) plaintext to speed up any brute force search; even with $2^{64}$ chosen plaintext/ciphertext pairs, the best known attack is to pick one pair, and apply a brute force search on that pair.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ I re-using a key in block ciphers doesn't influence cryptanalysis, then why bother with key changes in security protocols (like TLS or IPsec)? $\endgroup$ – Marste Mar 13 '14 at 9:32
  • 2
    $\begingroup$ @Marste 1) TLS in its typical use doesn't bother changing the key during the lifetime of a connection 2) Changing the key within a connection strengthens forward secrecy 3) More samples don't help brute-force, but might aid cryptoanalysis. There is also a block size dependent limit, which is only a couple of GB for 64 bit blocks. Older protocols worry about these issues since we didn't have AES yet. Nowadays it's less of a concern. $\endgroup$ – CodesInChaos Mar 13 '14 at 10:06

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.