4 ms·

Huh? That attack works with random keys. Are you confusing it with a related-key attack?

by agwa 10y ago

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

Huh? That attack works with random keys. Are you confusing it with a related-key attack?

by agwa 10y ago

Huh? That attack works with random keys. Are you confusing it with a related-key attack?

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