AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption
tools.ietf.org
tools.ietf.org
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.
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 :)
That doesn't sound right.
I would wager that using a cryptographically secure RNG is less likely to produce the same number twice, or at the very least equally as likely. If you have a very strong hash, then the hash algorithm should act the same as an RNG.
Of course all of this is on the assumption that any hashes and rngs you use are secure :)
In practice: many sites using gcm were using rng based nonces that end up colliding
My point was I disagree on your sentence "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."
That implies that a hash is strong enough that you don't need to track messages. If you believe that to be the case then a CSRNG would be equally as strong of not stronger and less complex. Still sqrt(n) chance of collision.
Bigger services, such as Public Cloud providers (I work at AWS, and it's a factor for us) actually end up running up on these limits.
What is the purpose of encrypting the keyed hash? I'm assuming there's something clever that an attacker could do with it if it were not encrypted, but I can't figure out what that might be.
FWIW, Poly1305 in e.g. secretbox works the same way: it's really Poly1305-AES. The Poly1305 is equivalent to GHASH here; AES encrypts in both cases.
The GHASH/GCM bit twiddling is so awful and slow and side-channel insecure to do in software, that most people just blindly copy the obscure code full of clever optimization that smart specialists come up with [1].
Then other smart specialists [2] have to reverse engineer said clever tricks (now widely used everywhere), because no explanation exists and it is not clear why they work in the first place.
Once done, a third group of smart specialists tweak the algorithm in an incompatible way to gain 10% speed on specific platforms and forcing people to pull in even more obscure code.
Simply put, I wish AES-GCM-SIV had just used GHASH as GCM and helped keeping complexity of crypto libraries down...
[1] https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pd... [2] https://blog.quarkslab.com/reversing-a-finite-field-multipli...
Could anyone explain what this catastrophic failure entails? Do both messages suddenly get decryptable, or is the entire AES key compromised?
https://cryptologie.net/article/361/breaking-https-aes-gcm-o...
https://csrc.nist.gov/csrc/media/projects/block-cipher-techn...
The same caveats thus apply to e.g. Chacha20-Poly1305 (keystream out of counter mode XOR plaintext for encryption, Carter-Wegman MAC).
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?)
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?
libhydrogen's API is different: https://github.com/jedisct1/libhydrogen/wiki/Secret-key-encr...
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.
The nonce could be stored as an internal counter, but that would require the encryption operation to modify internal state, which would then require locking in order to be thread safe. That would introduce more complexity than requiring the caller to supply the nonce.
To me that seems like premature optimization.
Moreover, RNGs require internal state to prevent giving the same random numbers twice, so in this context it's just a slower counter that would still introduce locking.
I was more talking about a case where a developer would like to add crypto to their chat application or whatever where the amount of crypto being done is so low it shouldn't really matter.
Particularly in a case like this, you would end up with two APIs, one that takes an immutable state plus a nonce and the other that takes a mutable state that is really the immutable state plus the nonce which it increments for you, with the separate question of whether it handles the locking for you or not (note that not all platforms even have threads). They're so similar that having both is confusing, but if you're to have only one then the applications that need good performance (which are common) want the one where the caller supplies the nonce, as does anything else that may need visibility into that, e.g. if messages are sent from more than one process or device.
Moreover, the performance implications creep up on you. You don't expect it to matter for your chat app until you start letting users attach files to messages and suddenly you're encrypting 10GB files instead of 10 byte messages. Then you start losing users to apps that use faster encryption, or worse, no encryption.
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];
}
For context: I authored the XChaCha20 RFC draft, implemented it in pure-PHP (twice; the second time was to support 32-bit systems).