Matching cryptographic primitive strengths (opens in new tab)

The thermodynamic limit cited (Landauer's cost of erasure) to show that 128 bits is enough (barring algorithmic advances) doesn't strictly apply. Charles Bennett[1] pointed out that any irreversible computation (i.e. one that involves erasure) can be made reversible by saving all the intermediate results (rather than erasing them), printing the result, then running the computation backward and letting it eat up all of the saved intermediate results. While this approach to computation isn't directly applicable here, it does show that you can't count on the thermodymanic cost to keep you safe.

[1] C. H. Bennett, "Logical Reversibility of Computation" _IBM Journal of Research and Development_ 17:525-532 (November, 1973), http://www.cs.princeton.edu/courses/archive/fall04/cos576/pa...

Another point on the "2 bits per increment", you can only flip one bit at a time to get through all possible 128-bit states using Gray code.

The argument that 128 bits of security are enough is quite reasonable [3]. There are, however, a couple technicalities with using 128-bit security primitives and/or keys:

- Multi-target attacks. In the case of symmetric ciphers, one has to take into account that the attacker may have many messages encrypted under many keys, and that success is achieved once at least one of them is broken. [1] exemplifies this effect with AES-128: with 2^86 time, a machine of size 2^32 has near certainty of breaking at least one out of 2^10 keys. Larger key sizes effectively render such tradeoffs moot. Note that multi-target attacks do not affect the speed of elliptic curve discrete logarithm computation: while it is possible to speed up a discrete logarithm after a previous one (by a factor of ~sqrt(2)), you still need to go through a full 2^128 computation first. So pairing (say) a 256-bit elliptic curve with AES-256 is not entirely unreasonable.

- Quantum computers. The last paragraph mentions pairing AES-256, SHA-384, and 128-bit McEliece as a balanced choice. Quantum computers clearly affected this choice, with the AES key size chosen to thwart Grover search, SHA-384 being chosen to thwart the Brassard-Hoyer-Tapp collision-finding algorithm (although it is no better than classical search due to crazy memory requirements), and McEliece for its well-known post-quantumness. A little-known fact is that Grover also speeds McEliece breaking considerably [2]. Thus, in a quantum world the McEliece key size would have to be increased to get quantum balance (McBits's parametrization achieves 128 bits of classical security).

- Security margin and operational costs. This is covered well already by Adam, but is worth emphasizing. With AES, the cost of going 256-bit instead of 128 is 4 more rounds. In the case of SHA-256, upgrading to SHA-512 actually speeds things up in typical 64-bit CPUs. Except in the most extreme of cases, this is a very acceptable cost to get a comfortable 128 extra bits of security in case AES or SHA-256 gets wounded. In the case of RSA or Diffie-Hellman, going from 128 to 256 bits of security gives us an approximate 25x slowdown, not to mention the increase in key sizes: 128 bits of security margin in this case is hardly acceptable. The case of elliptic curves is more murky: the cost of an extra 128 bits of security margin is around 4x, which may or may not be acceptable depending on the application.

[1] http://cr.yp.to/papers.html#bruteforce

[2] http://cr.yp.to/papers.html#grovercode

[3] I made a similar argument not too long ago, on the specific case of SHA-256's collision-resistance: https://news.ycombinator.com/item?id=7747545