How does the key size per data bit influence the security?

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?

• 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. – Reid Mar 12 '14 at 23:34
• What Maraste may be thinking of is how most modes of operation can be broken with $2^64$ blocks. $\hspace{.46 in}$ – user991 Mar 13 '14 at 1:18
• 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. – Marste Mar 13 '14 at 9:26
• 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. – tylo Mar 13 '14 at 12:55

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.