7 ms·

AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption

120 points by conductor 7y ago

wolf550e 7y ago
is XChaCha20-Poly1305 better if I don't need the performance of hardware accelerated AES GCM or am not guaranteed to always run on a device that has that hardware acceleration (AESNI, CLMUL)?
- FiloSottile 7y ago
  If you trust your CSPRNG and you wanted AES-GCM-SIV just to be allowed to use random nonces, yeah. If there is any reason you might still repeat a nonce, XChaCha will break.
  - metalliqaz 7y ago
    Presumably you could form a similar IV construction with Poly1305 as your hash, no?
    - CiPHPerCoder 7y ago
      S2V for XChaCha20-Poly1305 has actually been discussed on the CFRG mailing list (and a little bit off-list between myself and others interested in this topic). The only question that hasn't been addressed at the time of the last email was, where does it fit? XChaCha20 uses HChaCha20 to derive a 256-bit subkey between the 256-bit key and first 128 bits of the nonce. Then it uses ChaCha20 with the subkey and the remaining 64 bits of the nonce. ChaCha20 has an internal counter that goes between 0 and 2^64 - 1. AEAD_XChaCha20_Poly1305 uses the first 32 bytes of the XChaCha20 keystream to determine the Poly1305 key for that message, then begins the encryption starting at the next block. (The remaining 32 bytes of block_counter = 0 are discarded in XChaCha20, but not in XSalsa20; this is a subtle difference that probably only makes streaming APIs easier to design and has no significant security considerations.) With that in mind: XChaCha20 is already deriving a key from the key and (extended) nonce. And it already has an internal block counter (which side-steps counter/nonce wrapping issue that was addressed with AES-CTR in the AES-GCM-SIV design). The simplest solution is to, instead of just trusting your CSPRNG, do this: function crypto_aead_xchacha20poly1305siv_encrypt(msg, key) { let nonce = Buffer.alloc(24); sodium.randombytes_buf(nonce); // Synthetic nonce here: s2v(nonce, msg); let cipher = Buffer.alloc(msg.length + 16); sodium.crypt_aead_xchacha20poly1305_ietf_encrypt(cipher, msg, nonce, key); return [nonce, cipher]; } But this would be, strictly speaking, indistinguishable from XChaCha20-Poly1305 without SIV. For context: I authored the XChaCha20 RFC draft, implemented it in pure-PHP (twice; the second time was to support 32-bit systems).
colmmacc 7y ago
Here's a TLDR in case you're curious: AES-GCM is an API that takes 4 inputs. AES-GCM(key, nonce, additional_data, plaintext). The nonce is also called an initialization vector (IV). The key and nonce/IV are used to encrypt the plaintext using AES-CTR. A keyed hash, GHASH, is then computed over the additional data and the cipher text. That hash is encrypted with AES too, and you get an authentication tag. AES-GCM-SIV has two big differences. Firstly, GHASH is replaced with POLYVAL, a hash that is almost exactly the same but reverses the order of some bytes because it turns out that's more efficient on most platforms. Secondly, rather than using the key and a nonce to initialize the AES-CTR encryption, a synthetic IV is computed from the nonce that the caller provides and an encrypted POLYVAL hash of the plaintext. This difference means that even if the caller uses the same nonce twice, which is bad, that the synthetic IV will still be different as long as the plaintext messages are different. This is what makes the nonce resistance. This is great for cases where we're using the same key over and over in a distributed way, and all of the senders can't guarantee not to use the same nonces, they might collide. TLS session tickets and cookies are good examples of that. Two small gotchas: the biggest is that when encrypting the message, we have to pass over it twice, once to compute the hash, and once to encrypt it. The second is that it's still possible to screw things up on the caller side, SIV doesn't magically make it ok not to make an attempt at setting a random nonce. For example if you use the null/all-zeroes nonce over and over, identical messages are going to be trivially finger-printable.
- metalliqaz 7y ago
  Related to gotcha #1 - it also means that you have to have the entire message available when you start encryption. Lightweight embedded systems may not be able to meet that requirement.
  - olliej 7y ago
    the problem with gcm’s nonce reuse weakness is that the best way to generate a unique nonce is as a hash of the input message - otherwise you technically have to record every nonce you’ve ever used. I guess an alternative would be to have a secret key and a counter and then have the nonce be something like aes(key, counter++) but obviously that has scalability issues I’m sure @tqpf/@tqbf (I cant recall) has opinions :)
jwilk 7y ago
HTML version: https://tools.ietf.org/html/rfc8452 https://tools.ietf.org/html/rfc8452
- sctb 7y ago
  Thanks! The RFC markup is so respectful of text I don't feel bad for updating it from https://www.rfc-editor.org/rfc/rfc8452.txt https://www.rfc-editor.org/rfc/rfc8452.txt.
praseodym 7y ago
> some AEADs (including AES-GCM) suffer catastrophic failures of confidentiality and/or integrity when two distinct messages are encrypted with the same key and nonce. While the requirements for AEADs specify that the pair of (key, nonce) shall only ever be used once, and thus prohibit this, this is a worry in practice. Could anyone explain what this catastrophic failure entails? Do both messages suddenly get decryptable, or is the entire AES key compromised?
- deleted 7y ago
  [deleted]
- CiPHPerCoder 7y ago
  You immediately lose your integrity protections, which allows you to launch attacks against AES-CTR as if it had no authentication tag. https://cryptologie.net/article/361/breaking-https-aes-gcm-or-a-part-of-it/ https://cryptologie.net/article/361/breaking-https-aes-gcm-o...
  - amluto 7y ago
    You also learn the XOR or the two plaintexts, which can be a catastrophic loss of confidentiality.
    - joe_xyz 7y ago
      You can also determine the keyed hash function key if you collect enough plaintexts, which would let you forge authentication tags https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/800-38-series-drafts/gcm/joux_comments.pdf https://csrc.nist.gov/csrc/media/projects/block-cipher-techn...
  - throwaway2048 7y ago
    Its worse than that with AES-GCM, nonce reuse reveals the AES private key.
- wolf550e 7y ago
AnaniasAnanas 7y ago
There is also HS1-SIV which uses Chacha20.
jopsen 7y ago
Why is it that most implementation require me to specify the nonce/IV, and why not include it in the cipher text? Most implementations could easily call an internal RNG and harvest an IV on my behalf, preventing me from being stupid. So why not? Similarly, if the specification said that the IV must be prepended to the cipher text, then I would never need to specify the IV when decrypting. (Is it wrong to send the IV in plaintext?)
- regecks 7y ago
  It's interesting that even libsodium's box/secretbox have nonce as a separate part of its 'easy to use' interface. I also would like to know why it isn't just an opaque part of the ciphertext. I'm aware that nonces are not always random but sometimes a counter, which creates an easy way to track nonce re-use. Is that the only reason?
  - jopsen 7y ago
    Also because it's not part of the cipher text I always end up wondering if I can transmit it in plaintext -- thus, I search stackoverflow for some sketchy answer that says it can -- because nobody every documents this in a library..
  - jedisct1 7y ago
    This is a historic API. libhydrogen's API is different: https://github.com/jedisct1/libhydrogen/wiki/Secret-key-encryption https://github.com/jedisct1/libhydrogen/wiki/Secret-key-encr...
- ilammy 7y ago
  Because these are cryptographic primitives and you're supposed to be educated enough for using them correctly. If you do not want to think about that, use a higher-level cryptographic libraries that make all these decisions for you: how IV is generated, how it is stored together with the ciphertext, how do you compute authentication token, how to you compute the encryption key, what algorithm you use, etc.
  - 7y ago
bondolo 7y ago
Thank you to the authors for being entirely explicit about the implementation to the point of providing pseudo code and not having any expectation that implementors or users will know anything about cryptography.

120 points by conductor 7y ago

is XChaCha20-Poly1305 better if I don't need the performance of hardware accelerated AES GCM or am not guaranteed to always run on a device that has that hardware acceleration (AESNI, CLMUL)?

FiloSottile 7y ago
If you trust your CSPRNG and you wanted AES-GCM-SIV just to be allowed to use random nonces, yeah. If there is any reason you might still repeat a nonce, XChaCha will break.
- metalliqaz 7y ago
  Presumably you could form a similar IV construction with Poly1305 as your hash, no?
  - CiPHPerCoder 7y ago
    S2V for XChaCha20-Poly1305 has actually been discussed on the CFRG mailing list (and a little bit off-list between myself and others interested in this topic). The only question that hasn't been addressed at the time of the last email was, where does it fit? XChaCha20 uses HChaCha20 to derive a 256-bit subkey between the 256-bit key and first 128 bits of the nonce. Then it uses ChaCha20 with the subkey and the remaining 64 bits of the nonce. ChaCha20 has an internal counter that goes between 0 and 2^64 - 1. AEAD_XChaCha20_Poly1305 uses the first 32 bytes of the XChaCha20 keystream to determine the Poly1305 key for that message, then begins the encryption starting at the next block. (The remaining 32 bytes of block_counter = 0 are discarded in XChaCha20, but not in XSalsa20; this is a subtle difference that probably only makes streaming APIs easier to design and has no significant security considerations.) With that in mind: XChaCha20 is already deriving a key from the key and (extended) nonce. And it already has an internal block counter (which side-steps counter/nonce wrapping issue that was addressed with AES-CTR in the AES-GCM-SIV design). The simplest solution is to, instead of just trusting your CSPRNG, do this: function crypto_aead_xchacha20poly1305siv_encrypt(msg, key) { let nonce = Buffer.alloc(24); sodium.randombytes_buf(nonce); // Synthetic nonce here: s2v(nonce, msg); let cipher = Buffer.alloc(msg.length + 16); sodium.crypt_aead_xchacha20poly1305_ietf_encrypt(cipher, msg, nonce, key); return [nonce, cipher]; } But this would be, strictly speaking, indistinguishable from XChaCha20-Poly1305 without SIV. For context: I authored the XChaCha20 RFC draft, implemented it in pure-PHP (twice; the second time was to support 32-bit systems).

colmmacc 7y ago

Here's a TLDR in case you're curious: AES-GCM is an API that takes 4 inputs. AES-GCM(key, nonce, additional_data, plaintext). The nonce is also called an initialization vector (IV). The key and nonce/IV are used to encrypt the plaintext using AES-CTR. A keyed hash, GHASH, is then computed over the additional data and the cipher text. That hash is encrypted with AES too, and you get an authentication tag. AES-GCM-SIV has two big differences. Firstly, GHASH is replaced with POLYVAL, a hash that is almost exactly the same but reverses the order of some bytes because it turns out that's more efficient on most platforms. Secondly, rather than using the key and a nonce to initialize the AES-CTR encryption, a synthetic IV is computed from the nonce that the caller provides and an encrypted POLYVAL hash of the plaintext. This difference means that even if the caller uses the same nonce twice, which is bad, that the synthetic IV will still be different as long as the plaintext messages are different. This is what makes the nonce resistance. This is great for cases where we're using the same key over and over in a distributed way, and all of the senders can't guarantee not to use the same nonces, they might collide. TLS session tickets and cookies are good examples of that. Two small gotchas: the biggest is that when encrypting the message, we have to pass over it twice, once to compute the hash, and once to encrypt it. The second is that it's still possible to screw things up on the caller side, SIV doesn't magically make it ok not to make an attempt at setting a random nonce. For example if you use the null/all-zeroes nonce over and over, identical messages are going to be trivially finger-printable.

metalliqaz 7y ago
Related to gotcha #1 - it also means that you have to have the entire message available when you start encryption. Lightweight embedded systems may not be able to meet that requirement.
- olliej 7y ago
  the problem with gcm’s nonce reuse weakness is that the best way to generate a unique nonce is as a hash of the input message - otherwise you technically have to record every nonce you’ve ever used. I guess an alternative would be to have a secret key and a counter and then have the nonce be something like aes(key, counter++) but obviously that has scalability issues I’m sure @tqpf/@tqbf (I cant recall) has opinions :)

jwilk 7y ago

HTML version: https://tools.ietf.org/html/rfc8452 https://tools.ietf.org/html/rfc8452

sctb 7y ago
Thanks! The RFC markup is so respectful of text I don't feel bad for updating it from https://www.rfc-editor.org/rfc/rfc8452.txt https://www.rfc-editor.org/rfc/rfc8452.txt.

praseodym 7y ago

> some AEADs (including AES-GCM) suffer catastrophic failures of confidentiality and/or integrity when two distinct messages are encrypted with the same key and nonce. While the requirements for AEADs specify that the pair of (key, nonce) shall only ever be used once, and thus prohibit this, this is a worry in practice. Could anyone explain what this catastrophic failure entails? Do both messages suddenly get decryptable, or is the entire AES key compromised?

deleted 7y ago
[deleted]
CiPHPerCoder 7y ago
You immediately lose your integrity protections, which allows you to launch attacks against AES-CTR as if it had no authentication tag. https://cryptologie.net/article/361/breaking-https-aes-gcm-or-a-part-of-it/ https://cryptologie.net/article/361/breaking-https-aes-gcm-o...
- amluto 7y ago
  You also learn the XOR or the two plaintexts, which can be a catastrophic loss of confidentiality.
  - joe_xyz 7y ago
    You can also determine the keyed hash function key if you collect enough plaintexts, which would let you forge authentication tags https://csrc.nist.gov/csrc/media/projects/block-cipher-techniques/documents/bcm/comments/800-38-series-drafts/gcm/joux_comments.pdf https://csrc.nist.gov/csrc/media/projects/block-cipher-techn...
- throwaway2048 7y ago
  Its worse than that with AES-GCM, nonce reuse reveals the AES private key.
wolf550e 7y ago

AnaniasAnanas 7y ago

There is also HS1-SIV which uses Chacha20.

jopsen 7y ago

Why is it that most implementation require me to specify the nonce/IV, and why not include it in the cipher text? Most implementations could easily call an internal RNG and harvest an IV on my behalf, preventing me from being stupid. So why not? Similarly, if the specification said that the IV must be prepended to the cipher text, then I would never need to specify the IV when decrypting. (Is it wrong to send the IV in plaintext?)

regecks 7y ago
It's interesting that even libsodium's box/secretbox have nonce as a separate part of its 'easy to use' interface. I also would like to know why it isn't just an opaque part of the ciphertext. I'm aware that nonces are not always random but sometimes a counter, which creates an easy way to track nonce re-use. Is that the only reason?
- jopsen 7y ago
  Also because it's not part of the cipher text I always end up wondering if I can transmit it in plaintext -- thus, I search stackoverflow for some sketchy answer that says it can -- because nobody every documents this in a library..
- jedisct1 7y ago
  This is a historic API. libhydrogen's API is different: https://github.com/jedisct1/libhydrogen/wiki/Secret-key-encryption https://github.com/jedisct1/libhydrogen/wiki/Secret-key-encr...
ilammy 7y ago
Because these are cryptographic primitives and you're supposed to be educated enough for using them correctly. If you do not want to think about that, use a higher-level cryptographic libraries that make all these decisions for you: how IV is generated, how it is stored together with the ciphertext, how do you compute authentication token, how to you compute the encryption key, what algorithm you use, etc.
- 7y ago

bondolo 7y ago

Thank you to the authors for being entirely explicit about the implementation to the point of providing pseudo code and not having any expectation that implementors or users will know anything about cryptography.