5 ms·

Towards a Safer Footgun

62 points by cpach 9y ago

twoodfin 9y ago
If we had access to a time machine, would we want to suggest to the IETF standards-makers that they specify a longer nonce than 96 bits?
- dchest 9y ago
  You'll need a time machine that can go back to the AES selection process to ask for a larger block size than 128 bits and/or faster key schedule. 96 bit nonce is so short because in counter mode you encrypt 128-bit block representing the nonce+counter and XOR the result with the message. In IETF/NIST standards, the block is split into 96 bits of nonce and 32 bits of counter, thus with one nonce you can generate up to 2^32 blocks of key stream without repeating it. Some other standards split 128-bits into 64-bit nonce and 64-bit counter. As you can see, there's not much you can do to make it larger. Salsa20/ChaCha is built with a 512-bit permutation (with initial word additions at the end to make it into PRF), which processes 256-bit key, 128-bit nonce+block counter and 128-bit constant. Similar situation here: we can split 128-bit nonce/counter into 64-bit nonce and 64-bit block counter (original DJB version) or 96-bit nonce and 32-bit block counter (IETF version, used in TLS). However, since there's no key schedule — key bytes are directly fed into the permutation, it's not expensive to change key for each message, unlike with AES that has to run key schedule for every key change. This neat property is what allows XSalsa20 (Salsa20 with 192-bit "expanded" nonce), to be quite inexpensive: basically it "hashes" 128 bits of the expanded nonce and original key with the same permutation, truncating it, into a new key, and then uses this new key along with the other 64 bits of the expanded nonce with Salsa20.
ivm83 9y ago
Article doesn't mention that with AES-GCM-SIV you lose indistinguishability - an attacker observing encrypted messages passing by can see when two copies of the same message are sent, since they will use the same IV. This might not matter for some cases, but could be a big deal for others.
- stouset 9y ago
  Yes, but only when nonces are reused. In this way, it's at least strictly better than AES-GCM which fails catastrophically. I'm not positive, but I think the GHASH authenticator used might even allow key recovery in this scenario.
  - unscaled 9y ago
    Yes. If nonce reuse is expected and distinguishable messages are considered to be a problem, then you really need a larger nonce. AES-GCM-SIV was designed to be nonce misuse resistant while still supporting short nonces. That's why Coda Hale called it a safer footgun. It's much safer, but still a footgun. An AEAD construction based on XChaCha20/XSalsa20-Poly1305 will solve this problem, as would be deriving a per-message key from your master key + a random salt. I'm not an expert, but this seems to me like a safer method if you want to positively eliminate the possibility of nonce reuse, and don't care about the extra overhead from larger nonces and lack of standardization.
    - stouset 9y ago
      Nonce reuse is only expected in the sense that cryptographers have begun to accept that developers will always find a way to misuse primitives. That's why these are called "nonce misuse-resistant" ciphers. Cryptographers are not encouraging people to use this type of cipher where nonce reuse is expected. Nonce reuse should never be expected, and always be avoided. But people being people will wrongly use these constructions, so we do our best to try and limit the worst downsides of the footgun. XChaCha20-Poly1305 will not solve this problem, as you seemt o believe. It is more of a footgun, in that it too catastrophically fails under nonce reuse. Yes, it's less likely to suffer reuse in the first place due to a larger nonce size, but that ignores the context driving the creation of SIV schemes: developers who choose nonces poorly, not developers who encrypt too many messages given the likelihood of collision of a random nonce.
- MichaelGG 9y ago
  Shouldn't it have incorporated some random bits or a counter?
unscaled 9y ago
It's too bad IETF didn't at least specify a standard way to use XChacha20/XSalsa20 with Poly1305 for AEAD. As it is you have to rely on all implementations to: 1. Split the nonce and counter the same way. libsodium uses a 64-bit nonce, 32-bit counter and 32-bit wasted zero bytes for IETF compatibility ;). (You could also say it's a 64-bit counter that never counts past 2^32-1). 2. Feed the AEAD into Poly1305 in the same way. IIRC libsodium hashes everything in this order: AEAD padded with zeros, so length will be a multiple of 16 message padded with zeros in the same way AEAD length message length This is the same as the scheme IETF defined for ChaCha20Poly1305, but it's not defined in any standard XChacha20Poly1305, so nobody can guarantee that the library you're using will do the same (if it supports XChaCha20 at all).

62 points by cpach 9y ago

If we had access to a time machine, would we want to suggest to the IETF standards-makers that they specify a longer nonce than 96 bits?

dchest 9y ago
You'll need a time machine that can go back to the AES selection process to ask for a larger block size than 128 bits and/or faster key schedule. 96 bit nonce is so short because in counter mode you encrypt 128-bit block representing the nonce+counter and XOR the result with the message. In IETF/NIST standards, the block is split into 96 bits of nonce and 32 bits of counter, thus with one nonce you can generate up to 2^32 blocks of key stream without repeating it. Some other standards split 128-bits into 64-bit nonce and 64-bit counter. As you can see, there's not much you can do to make it larger. Salsa20/ChaCha is built with a 512-bit permutation (with initial word additions at the end to make it into PRF), which processes 256-bit key, 128-bit nonce+block counter and 128-bit constant. Similar situation here: we can split 128-bit nonce/counter into 64-bit nonce and 64-bit block counter (original DJB version) or 96-bit nonce and 32-bit block counter (IETF version, used in TLS). However, since there's no key schedule — key bytes are directly fed into the permutation, it's not expensive to change key for each message, unlike with AES that has to run key schedule for every key change. This neat property is what allows XSalsa20 (Salsa20 with 192-bit "expanded" nonce), to be quite inexpensive: basically it "hashes" 128 bits of the expanded nonce and original key with the same permutation, truncating it, into a new key, and then uses this new key along with the other 64 bits of the expanded nonce with Salsa20.

ivm83 9y ago

Article doesn't mention that with AES-GCM-SIV you lose indistinguishability - an attacker observing encrypted messages passing by can see when two copies of the same message are sent, since they will use the same IV. This might not matter for some cases, but could be a big deal for others.

stouset 9y ago
Yes, but only when nonces are reused. In this way, it's at least strictly better than AES-GCM which fails catastrophically. I'm not positive, but I think the GHASH authenticator used might even allow key recovery in this scenario.
- unscaled 9y ago
  Yes. If nonce reuse is expected and distinguishable messages are considered to be a problem, then you really need a larger nonce. AES-GCM-SIV was designed to be nonce misuse resistant while still supporting short nonces. That's why Coda Hale called it a safer footgun. It's much safer, but still a footgun. An AEAD construction based on XChaCha20/XSalsa20-Poly1305 will solve this problem, as would be deriving a per-message key from your master key + a random salt. I'm not an expert, but this seems to me like a safer method if you want to positively eliminate the possibility of nonce reuse, and don't care about the extra overhead from larger nonces and lack of standardization.
  - stouset 9y ago
    Nonce reuse is only expected in the sense that cryptographers have begun to accept that developers will always find a way to misuse primitives. That's why these are called "nonce misuse-resistant" ciphers. Cryptographers are not encouraging people to use this type of cipher where nonce reuse is expected. Nonce reuse should never be expected, and always be avoided. But people being people will wrongly use these constructions, so we do our best to try and limit the worst downsides of the footgun. XChaCha20-Poly1305 will not solve this problem, as you seemt o believe. It is more of a footgun, in that it too catastrophically fails under nonce reuse. Yes, it's less likely to suffer reuse in the first place due to a larger nonce size, but that ignores the context driving the creation of SIV schemes: developers who choose nonces poorly, not developers who encrypt too many messages given the likelihood of collision of a random nonce.
MichaelGG 9y ago
Shouldn't it have incorporated some random bits or a counter?

unscaled 9y ago

It's too bad IETF didn't at least specify a standard way to use XChacha20/XSalsa20 with Poly1305 for AEAD. As it is you have to rely on all implementations to: 1. Split the nonce and counter the same way. libsodium uses a 64-bit nonce, 32-bit counter and 32-bit wasted zero bytes for IETF compatibility ;). (You could also say it's a 64-bit counter that never counts past 2^32-1). 2. Feed the AEAD into Poly1305 in the same way. IIRC libsodium hashes everything in this order: AEAD padded with zeros, so length will be a multiple of 16 message padded with zeros in the same way AEAD length message length This is the same as the scheme IETF defined for ChaCha20Poly1305, but it's not defined in any standard XChacha20Poly1305, so nobody can guarantee that the library you're using will do the same (if it supports XChaCha20 at all).