4 ms·

Like much of Peter Gutmann’s writing this is a mixture of good points and things that are downright incorrect or at least misleading. For example, he criticises

Like much of Peter Gutmann’s writing this is a mixture of good points and things that are downright incorrect or at least misleading. For example, he criticises GCM for losing confidentiality when a nonce is reused. True, but ChaPoly has exactly the same issue. And although CBC+HMAC is somewhat better in that regard, it doesn’t “drop back to ECB mode”, and it still loses CPA security. HMAC is far more robust than any polynomial MAC, but the persistent idea that there is any meaningful difference in robustness between any of the traditional cipher modes under nonce/IV misuse is nonsense. If you need misuse resistance then use a mode that actually provides it, like SIV.

tptacek 3y ago
I mean, he hasn't nailed the reason ChaPoly is favored over GCM, and it's not a good paragraph, but he's not wrong that GCM is ill-loved by cryptography engineers, despite its ubiquity. Really though, it's just missing an important bit of the history, which is that there was a decent stretch of years where it was basically impossible to implement GCM securely on architectures that didn't have something like the CLMUL instruction. I don't agree with you at all about the equivalent of IV misuse under CBC+HMAC and nonce reuse under ChaPoly. It's a bug either way, and bugs in cryptosystems are bad, but it's much less bad in CBC+HMAC. That is in fact a good reason to use it.
- nmadden 3y ago
  But it’s less bad because of HMAC, not because of CBC. Hand waving arguments that CBC is meaningfully better than CTR mode under IV reuse are silly. There are cases where a nonce reuse in CTR mode reveals very little (eg key wrapping) and cases where the same in CBC mode reveals everything. The worst case for both is equally bad.
  - tptacek 3y ago
    I still disagree with you even given this refinement. A repeated CBC IV is a second-order vulnerability that still requires you to set up the conditions for an ECB-style attack on the system, which isn't always possible. A repeated CTR nonce immediately sacrifices confidentiality.
    - nmadden 3y ago
      That’s not true. CBC mode with a repeated IV immediately reveals equality of plaintexts or any common prefix (modulo block size).
      - tptacek 3y ago
        And my claim is that is not always valuable to an attacker, whereas I can't think of an instance where a repeated CTR nonce wasn't game-over. It's always bad. I don't want to get into a semantic argument about whether or not a repeated IV is a vulnerability. It is. But it's not as severe a vulnerability as a repeated CTR nonce, which repeats the entire keystream.
        nmadden 3y ago
        > whereas I can’t think of an instance where a repeated CTR nonce wasn’t game-over. The fact that you can’t think of an example is not a serious security argument. This is why we have rigorous security definitions rather than hand waving “I can’t think of anything” arguments, which should have died in the 90s. I already gave you one example: key-wrapping. JOSE (of course) has a key-wrapping mode based on GCM, and at least one recent article advocates for its widespread use [1] (see recommendations at end). Despite me not agreeing with that advice, it is an example of where CTR loses no information at all under nonce reuse: the XOR of two random keys is itself indistinguishable from random. I can certainly think of examples based on encrypting binary data streams where the XOR of plaintexts may also reveal very little. To decide whether CBC or CTR leaks more you have to consider the specifics of the application, or you have to make shaky assumptions about “typical” data. IMO those assumptions are not a good foundation for security and we should move past them. [1]: https://scottarc.blog/2023/09/06/how-to-write-a-secure-jwt-library-if-you-absolutely-must/ https://scottarc.blog/2023/09/06/how-to-write-a-secure-jwt-l...
        tptacek 3y ago
        You're responding to an argument I didn't make. Obviously I don't believe that repeated CBC IVs are never an exploitable vulnerability. There are famously exploitable instances; one broke TLS. I'm arguing that a repeated CBC IV is less likely to be practically exploitable than a repeated CTR nonce, which is virtually always exploitable.
marcosdumay 3y ago
Why are we so concerned with nonce misuse anyway? I understood it at the time when nonces had complex rules, and when they were created deterministically. But nowadays it's pretty standard that modern algorithms work jut fine with completely random nonces, and it's pretty standard that you make them this way. It being standard, they just come packed with the algorithm. IMO, worrying about bugs there makes exactly as much sense as worrying about bugs on the main algorithm. There's no reason to single them out.
- nmadden 3y ago
  There are several reasons. Off the top of my head: 1. People use bad PRNGs or otherwise mess this up so the nonces aren’t as random as they should be, or they use ciphers with small nonce spaces (eg original ChaCha with 64-bit nonces) and generate enough nonces that collisions become likely. 2. Even if you use a larger nonce space, like GCM’s usual 96-bits, you may be Google and generate so many nonces so quickly that collisions even then become likely. (This is generally not a problem for >128 bit nonces though). See the rationale for the development of AES-GCM-SIV for an example. 3. If you generate a random nonce then you have to send that nonce on the wire, which adds overhead (e.g. 16 bytes per message). If you send a lot of small messages or have strict space limits then you might not want this overhead, leading back to deterministic nonce generation. 4. There are a lot of existing crypto protocols in use, and almost all of them use deterministic nonces. We’re not going to just replace them all overnight with random nonce variants.
  - panax 3y ago
    Also nonce misuse is a common failure mode among novices who might not understand what a nonce is supposed to be. People do all kinds of mistakes including using hardcoded static nonces. Its also fairly easy to come up with a bad protocol where someone can trick you into nonce reuse. Or there is a complicated error path that might involve a device going through reset where a nonce reuse might occur. Some of these are not so trivial to identify either.
- tptacek 3y ago
  This is a question with a simple answer. The most popular nonce-based AEAD is GCM, which has only the AES block size to fit both a nonce and a counter, which doesn't leave enough headroom to comfortably use random nonces. As a result, people build elaborate schemes to generate deterministic fresh nonces, and when those break, GCM breaks.

tptacek 3y ago

I mean, he hasn't nailed the reason ChaPoly is favored over GCM, and it's not a good paragraph, but he's not wrong that GCM is ill-loved by cryptography engineers, despite its ubiquity. Really though, it's just missing an important bit of the history, which is that there was a decent stretch of years where it was basically impossible to implement GCM securely on architectures that didn't have something like the CLMUL instruction. I don't agree with you at all about the equivalent of IV misuse under CBC+HMAC and nonce reuse under ChaPoly. It's a bug either way, and bugs in cryptosystems are bad, but it's much less bad in CBC+HMAC. That is in fact a good reason to use it.

nmadden 3y ago
But it’s less bad because of HMAC, not because of CBC. Hand waving arguments that CBC is meaningfully better than CTR mode under IV reuse are silly. There are cases where a nonce reuse in CTR mode reveals very little (eg key wrapping) and cases where the same in CBC mode reveals everything. The worst case for both is equally bad.
- tptacek 3y ago
  I still disagree with you even given this refinement. A repeated CBC IV is a second-order vulnerability that still requires you to set up the conditions for an ECB-style attack on the system, which isn't always possible. A repeated CTR nonce immediately sacrifices confidentiality.
  - nmadden 3y ago
    That’s not true. CBC mode with a repeated IV immediately reveals equality of plaintexts or any common prefix (modulo block size).
    - tptacek 3y ago
      And my claim is that is not always valuable to an attacker, whereas I can't think of an instance where a repeated CTR nonce wasn't game-over. It's always bad. I don't want to get into a semantic argument about whether or not a repeated IV is a vulnerability. It is. But it's not as severe a vulnerability as a repeated CTR nonce, which repeats the entire keystream.
      - nmadden 3y ago
        > whereas I can’t think of an instance where a repeated CTR nonce wasn’t game-over. The fact that you can’t think of an example is not a serious security argument. This is why we have rigorous security definitions rather than hand waving “I can’t think of anything” arguments, which should have died in the 90s. I already gave you one example: key-wrapping. JOSE (of course) has a key-wrapping mode based on GCM, and at least one recent article advocates for its widespread use [1] (see recommendations at end). Despite me not agreeing with that advice, it is an example of where CTR loses no information at all under nonce reuse: the XOR of two random keys is itself indistinguishable from random. I can certainly think of examples based on encrypting binary data streams where the XOR of plaintexts may also reveal very little. To decide whether CBC or CTR leaks more you have to consider the specifics of the application, or you have to make shaky assumptions about “typical” data. IMO those assumptions are not a good foundation for security and we should move past them. [1]: https://scottarc.blog/2023/09/06/how-to-write-a-secure-jwt-library-if-you-absolutely-must/ https://scottarc.blog/2023/09/06/how-to-write-a-secure-jwt-l...
        tptacek 3y ago
        You're responding to an argument I didn't make. Obviously I don't believe that repeated CBC IVs are never an exploitable vulnerability. There are famously exploitable instances; one broke TLS. I'm arguing that a repeated CBC IV is less likely to be practically exploitable than a repeated CTR nonce, which is virtually always exploitable.

marcosdumay 3y ago

Why are we so concerned with nonce misuse anyway? I understood it at the time when nonces had complex rules, and when they were created deterministically. But nowadays it's pretty standard that modern algorithms work jut fine with completely random nonces, and it's pretty standard that you make them this way. It being standard, they just come packed with the algorithm. IMO, worrying about bugs there makes exactly as much sense as worrying about bugs on the main algorithm. There's no reason to single them out.

nmadden 3y ago
There are several reasons. Off the top of my head: 1. People use bad PRNGs or otherwise mess this up so the nonces aren’t as random as they should be, or they use ciphers with small nonce spaces (eg original ChaCha with 64-bit nonces) and generate enough nonces that collisions become likely. 2. Even if you use a larger nonce space, like GCM’s usual 96-bits, you may be Google and generate so many nonces so quickly that collisions even then become likely. (This is generally not a problem for >128 bit nonces though). See the rationale for the development of AES-GCM-SIV for an example. 3. If you generate a random nonce then you have to send that nonce on the wire, which adds overhead (e.g. 16 bytes per message). If you send a lot of small messages or have strict space limits then you might not want this overhead, leading back to deterministic nonce generation. 4. There are a lot of existing crypto protocols in use, and almost all of them use deterministic nonces. We’re not going to just replace them all overnight with random nonce variants.
- panax 3y ago
  Also nonce misuse is a common failure mode among novices who might not understand what a nonce is supposed to be. People do all kinds of mistakes including using hardcoded static nonces. Its also fairly easy to come up with a bad protocol where someone can trick you into nonce reuse. Or there is a complicated error path that might involve a device going through reset where a nonce reuse might occur. Some of these are not so trivial to identify either.
tptacek 3y ago
This is a question with a simple answer. The most popular nonce-based AEAD is GCM, which has only the AES block size to fit both a nonce and a counter, which doesn't leave enough headroom to comfortably use random nonces. As a result, people build elaborate schemes to generate deterministic fresh nonces, and when those break, GCM breaks.