5 ms·

What's the feeling on them preferring 256-bit AES over 128-bit AES? I was under the impression there is no theoretical nor practical justification for it.

by gcp 10y ago

agwa 10y ago
Batch attacks: https://blog.cr.yp.to/20151120-batchattacks.html https://blog.cr.yp.to/20151120-batchattacks.html
- tptacek 10y ago
  How is this attack meaningful with the random AES keys generated by the TLS KDF?
  - agwa 10y ago
    Huh? That attack works with random keys. Are you confusing it with a related-key attack?
    - tptacek 10y ago
      Look again. I think the meaningful attacks here are against public key algorithms (and, I suppose, maybe, MAC algorithms). See, for instance, the hypothesized 2^64 ECC attack.
      - agwa 10y ago
        I think this is the essential paragraph: > What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2^128 of matching any particular user key, but the attack ends up merging costs across a batch of 2^40 user keys, amplifying the effectiveness of each guess by a factor 2^40 If the attacker has collected 2^40 instances of some known plaintext, such as "GET / HTTP/1.1\r\n", encrypted under 2^40 unknown AES-128 keys (and it doesn't matter how those keys were generated), then the attacker can generate a key randomly, encrypt the known plaintext under that key, and see if it matches any of the target ciphertexts. The chance of guessing one of the 2^40 keys successfully this way is 1/2^(128-40) = 1/2^88. This means that attacking one of the keys requires far less than the 2^128 operations that one might expect would be required to attack AES-128. DJB argues that this makes AES-128 ill-matched with elliptic curves that provide a 128-bit security level, thus motivating a cipher with 256 bit keys instead, such as AES-256 or ChaCha20. In practice, the first 32 bits of the GCM nonce used by TLS are derived during the handshake, so the attacker has to do 2^32 more computations (since there are 2^32 different ways a known plaintext could be encrypted with a given key). So perhaps AES-128 is actually fine with TLS. But the point still stands that there is a justification for preferring AES-256 over AES-128.
        tptacek 10y ago
        My undertstanding is that's the basic, very impractical attack illustration the article opens up with, so that the reader groks how batch attacks work. But most of the article is about the surprising ways in which public key algorithms take that attack into the realm of practicality.
        agwa 10y ago
        DJB has espoused this point repeatedly - it's more than a motivator for the rest of the article.
        tptacek 10y ago
        I guess we can agree to disagree about whether this attack is an illustration of how treacherous it is to reason about key sizes or a practical attack on TLS.
        caf 10y ago
        DJBs point is summarised by the last point from the slides: "Bottom line: 128-bit AES keys are not comparable in security to 255-bit elliptic-curve keys. Is 2²⁵⁵−19 big enough? Yes. Is 128-bit AES safe? Unclear."
      - pbsd 10y ago
        The 2^64 attack there is for 128-bit ECC, which is not hypothesis---it's a standard Pollard rho attack. That is, the entire purpose of rho is to find a "key collision" aP + bQ = cP + dQ, from which we can immediately derive the secret key. The point there is that batching helps the attacker finding the first AES key by a factor of m, m being the number of keys being attacked, but it doesn't really help finding the first ECC key---although it does help with the cost of finding the second, third, etc a bit. So for example, the effective multi-key security of AES-128, given 2^32 different keys (read: sessions), is 2^96. See for example [1] for a formalization of multi-key security in the symmetric encryption setting. [1] https://eprint.iacr.org/2015/101 https://eprint.iacr.org/2015/101
meta_AU 10y ago
From memory there is a related key attack on AES256 with complexity 2^99. So in that regard AES128 is more secure than AES256.
- gcp 10y ago
  That's exactly what I mean by the lack of theoretical justification for their grading.
- CiPHPerCoder 10y ago
  The related key attack is only really relevant if you're using the AES internals to construct, say, a hash function. With random keys (generated via /dev/urandom), you don't need to worry about that.
- xoa 10y ago
  Someone who knows more correct me if I wrong, but my recollection is that the AES256/192 related key attack presented by Alex Biryukov and Dmitry Khovratovich (assuming that's what you're referring to) was seriously, seriously theoretical. Like, for real. Performing it required somehow getting the owner of the targeted key (K1) to use a specific derivation algorithm to derive 3 other keys from K1, then get the owner to perform encryption/decryption operations of the attacker's choosing using all 4 keys on up to 2^99.5 16-byte blocks, THEN the attacker uses ridiculous amounts of storage to to finish, I can't remember exactly how big but multiple exabytes of storage big. I know how sometimes weaknesses are found that seem impossible at first but can somehow be improved, but unless something fundamental has changed in the years since that attack did not appear to have any actual significance beyond academics (which is why no one in the industry worried about it). Beyond any efficiency requirements is the basic least-common denominator actor issue: if an attacker can get a key owner (person or machine) to perform that level of arbitrary action, there are much much easier ways to subvert the entire system. As a symmetric block cipher I suppose being in the habit of AES-256 usage is at least some gesture towards any future attacks by scalable general purpose quantum computers should they appear, since Grover's means it'd still be decent while 128 would drop to 64, though given the generally usage of asymmetric ciphers for initial exchange I don't know if it actually matters at all in the specific instance of the web. But whatever its benefits or downsides I don't think the related key attack makes it worse then AES-128.
tptacek 10y ago
I think it's a bit silly to demand 256 bit security from your bulk cipher but only 128 bit security from your key exchange. Quantum does affect this, but obviously the implications of quantum are way bigger than your block cipher choice.
- amluto 10y ago
  Talking about "128 bits" security is meaningless. DJB pointed out, correctly, that generic attacks against ciphers with 128-bit keys are distressingly close to being practical. Generic attacks against 256-bit ECDHE are wildly impractical. If you want to make it take comparable effort to break the key exchange as it takes to break the cipher, the cipher key needs to be bigger.
  - baby 10y ago
    > DJB pointed out, correctly, that generic attacks against ciphers with 128-bit keys are distressingly close to being practical Not he didn't. And 256-bit ECDHE has 128 bits of security.
    - amluto 10y ago
      Look at his paper "Understanding Brute Force". > And 256-bit ECDHE has 128 bits of security. Can you give that a meaningful definition? I suspect you mean that it takes ~2^128 operations to break a single target ECDHE exchange. If so, that is both true and completely irrelevant to anything I said. The key point here is that it does not take anywhere near 2^128 operations before you can decrypt a single AES-128 block out of a large corpus of captured ciphertexts. For that type of attack, 128 bit ciphers offer vastly less security than ECDHE on a 256-bit field.
      - baby 10y ago
        If you're talking about batch attacks. They're a completely theoretical kind of attack, it does not apply to normal usages of AES. Sure, TLS makes it possible to theorize about them. Let me try: Imagine that the NSA has collected 2^40 sessions using AES-128 on the internet. Let's imagine that they only want to steal session IDs being sent (if they want to eavesdrop on more data, it will be worse). From burp, I get that a simple GET request to Gmail is 2319 bytes, that's around 144 blocks of AES. Let's say a 100. So in total, the NSA would have to store 2^40 * 128 * 100 bits, let's say around 2 petabytes. Also I forgot, let's imagine that the first block of any of these sessions' first message is always the same thing. A GET request to the same address. We got extra lucky! Now they have to perform 2^88 AES operations for each key guess, and hopefully they will start finding keys at this point. (It's more than all of the computing power of bitcoin btw.). And for each of these AES operations they also have to check in their 2 petabytes corpus for a match (I hope you way to do that). Let's imagine that the NSA wants to do less computations of AES. They could have stored 2^50 sessions instead! And now they only have to perform 2^78 AES operations. For this they would have to store around 2 exabytes. In 2010 the whole traffic of internet was estimated to be around 21 exabytes per month. So if the NSA would be to record sessions for a month, they would need to store 10% of the internet hopping that they would also be GET requests to Gmail. Now we can theorize about the evolution of storage space, and computing power, and ... quantum computer. In which case ECDHE will fall before AES-128 does.
ivanr 10y ago
I should have fixed that a long time ago and I apologise that I haven't yet. But I will! At the moment, sites with "too strong" security (e.g., 4096-bit RSA, 4096-bit DH, etc) are still rewarded for it, but they shouldn't be.

What's the feeling on them preferring 256-bit AES over 128-bit AES? I was under the impression there is no theoretical nor practical justification for it.

by gcp 10y ago

What's the feeling on them preferring 256-bit AES over 128-bit AES? I was under the impression there is no theoretical nor practical justification for it.

agwa 10y ago

Batch attacks: https://blog.cr.yp.to/20151120-batchattacks.html https://blog.cr.yp.to/20151120-batchattacks.html

tptacek 10y ago
How is this attack meaningful with the random AES keys generated by the TLS KDF?
- agwa 10y ago
  Huh? That attack works with random keys. Are you confusing it with a related-key attack?
  - tptacek 10y ago
    Look again. I think the meaningful attacks here are against public key algorithms (and, I suppose, maybe, MAC algorithms). See, for instance, the hypothesized 2^64 ECC attack.
    - agwa 10y ago
      I think this is the essential paragraph: > What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2^128 of matching any particular user key, but the attack ends up merging costs across a batch of 2^40 user keys, amplifying the effectiveness of each guess by a factor 2^40 If the attacker has collected 2^40 instances of some known plaintext, such as "GET / HTTP/1.1\r\n", encrypted under 2^40 unknown AES-128 keys (and it doesn't matter how those keys were generated), then the attacker can generate a key randomly, encrypt the known plaintext under that key, and see if it matches any of the target ciphertexts. The chance of guessing one of the 2^40 keys successfully this way is 1/2^(128-40) = 1/2^88. This means that attacking one of the keys requires far less than the 2^128 operations that one might expect would be required to attack AES-128. DJB argues that this makes AES-128 ill-matched with elliptic curves that provide a 128-bit security level, thus motivating a cipher with 256 bit keys instead, such as AES-256 or ChaCha20. In practice, the first 32 bits of the GCM nonce used by TLS are derived during the handshake, so the attacker has to do 2^32 more computations (since there are 2^32 different ways a known plaintext could be encrypted with a given key). So perhaps AES-128 is actually fine with TLS. But the point still stands that there is a justification for preferring AES-256 over AES-128.
      - tptacek 10y ago
        My undertstanding is that's the basic, very impractical attack illustration the article opens up with, so that the reader groks how batch attacks work. But most of the article is about the surprising ways in which public key algorithms take that attack into the realm of practicality.
        agwa 10y ago
        DJB has espoused this point repeatedly - it's more than a motivator for the rest of the article.
        tptacek 10y ago
        I guess we can agree to disagree about whether this attack is an illustration of how treacherous it is to reason about key sizes or a practical attack on TLS.
        caf 10y ago
        DJBs point is summarised by the last point from the slides: "Bottom line: 128-bit AES keys are not comparable in security to 255-bit elliptic-curve keys. Is 2²⁵⁵−19 big enough? Yes. Is 128-bit AES safe? Unclear."
    - pbsd 10y ago
      The 2^64 attack there is for 128-bit ECC, which is not hypothesis---it's a standard Pollard rho attack. That is, the entire purpose of rho is to find a "key collision" aP + bQ = cP + dQ, from which we can immediately derive the secret key. The point there is that batching helps the attacker finding the first AES key by a factor of m, m being the number of keys being attacked, but it doesn't really help finding the first ECC key---although it does help with the cost of finding the second, third, etc a bit. So for example, the effective multi-key security of AES-128, given 2^32 different keys (read: sessions), is 2^96. See for example [1] for a formalization of multi-key security in the symmetric encryption setting. [1] https://eprint.iacr.org/2015/101 https://eprint.iacr.org/2015/101

meta_AU 10y ago

From memory there is a related key attack on AES256 with complexity 2^99. So in that regard AES128 is more secure than AES256.

gcp 10y ago
That's exactly what I mean by the lack of theoretical justification for their grading.
CiPHPerCoder 10y ago
The related key attack is only really relevant if you're using the AES internals to construct, say, a hash function. With random keys (generated via /dev/urandom), you don't need to worry about that.
xoa 10y ago
Someone who knows more correct me if I wrong, but my recollection is that the AES256/192 related key attack presented by Alex Biryukov and Dmitry Khovratovich (assuming that's what you're referring to) was seriously, seriously theoretical. Like, for real. Performing it required somehow getting the owner of the targeted key (K1) to use a specific derivation algorithm to derive 3 other keys from K1, then get the owner to perform encryption/decryption operations of the attacker's choosing using all 4 keys on up to 2^99.5 16-byte blocks, THEN the attacker uses ridiculous amounts of storage to to finish, I can't remember exactly how big but multiple exabytes of storage big. I know how sometimes weaknesses are found that seem impossible at first but can somehow be improved, but unless something fundamental has changed in the years since that attack did not appear to have any actual significance beyond academics (which is why no one in the industry worried about it). Beyond any efficiency requirements is the basic least-common denominator actor issue: if an attacker can get a key owner (person or machine) to perform that level of arbitrary action, there are much much easier ways to subvert the entire system. As a symmetric block cipher I suppose being in the habit of AES-256 usage is at least some gesture towards any future attacks by scalable general purpose quantum computers should they appear, since Grover's means it'd still be decent while 128 would drop to 64, though given the generally usage of asymmetric ciphers for initial exchange I don't know if it actually matters at all in the specific instance of the web. But whatever its benefits or downsides I don't think the related key attack makes it worse then AES-128.

tptacek 10y ago

I think it's a bit silly to demand 256 bit security from your bulk cipher but only 128 bit security from your key exchange. Quantum does affect this, but obviously the implications of quantum are way bigger than your block cipher choice.

amluto 10y ago
Talking about "128 bits" security is meaningless. DJB pointed out, correctly, that generic attacks against ciphers with 128-bit keys are distressingly close to being practical. Generic attacks against 256-bit ECDHE are wildly impractical. If you want to make it take comparable effort to break the key exchange as it takes to break the cipher, the cipher key needs to be bigger.
- baby 10y ago
  > DJB pointed out, correctly, that generic attacks against ciphers with 128-bit keys are distressingly close to being practical Not he didn't. And 256-bit ECDHE has 128 bits of security.
  - amluto 10y ago
    Look at his paper "Understanding Brute Force". > And 256-bit ECDHE has 128 bits of security. Can you give that a meaningful definition? I suspect you mean that it takes ~2^128 operations to break a single target ECDHE exchange. If so, that is both true and completely irrelevant to anything I said. The key point here is that it does not take anywhere near 2^128 operations before you can decrypt a single AES-128 block out of a large corpus of captured ciphertexts. For that type of attack, 128 bit ciphers offer vastly less security than ECDHE on a 256-bit field.
    - baby 10y ago
      If you're talking about batch attacks. They're a completely theoretical kind of attack, it does not apply to normal usages of AES. Sure, TLS makes it possible to theorize about them. Let me try: Imagine that the NSA has collected 2^40 sessions using AES-128 on the internet. Let's imagine that they only want to steal session IDs being sent (if they want to eavesdrop on more data, it will be worse). From burp, I get that a simple GET request to Gmail is 2319 bytes, that's around 144 blocks of AES. Let's say a 100. So in total, the NSA would have to store 2^40 * 128 * 100 bits, let's say around 2 petabytes. Also I forgot, let's imagine that the first block of any of these sessions' first message is always the same thing. A GET request to the same address. We got extra lucky! Now they have to perform 2^88 AES operations for each key guess, and hopefully they will start finding keys at this point. (It's more than all of the computing power of bitcoin btw.). And for each of these AES operations they also have to check in their 2 petabytes corpus for a match (I hope you way to do that). Let's imagine that the NSA wants to do less computations of AES. They could have stored 2^50 sessions instead! And now they only have to perform 2^78 AES operations. For this they would have to store around 2 exabytes. In 2010 the whole traffic of internet was estimated to be around 21 exabytes per month. So if the NSA would be to record sessions for a month, they would need to store 10% of the internet hopping that they would also be GET requests to Gmail. Now we can theorize about the evolution of storage space, and computing power, and ... quantum computer. In which case ECDHE will fall before AES-128 does.

ivanr 10y ago

I should have fixed that a long time ago and I apologise that I haven't yet. But I will! At the moment, sites with "too strong" security (e.g., 4096-bit RSA, 4096-bit DH, etc) are still rewarded for it, but they shouldn't be.