5 ms·
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 initi
by colmmacc 8y 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 8y agoRelated 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 8y agothe 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 :)
- metalliqaz 8y agoCounters are already used in the generation of the keystream
- admax88q 8y ago> 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 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.
- metalliqaz 8y agoYou are supposed to combine the hash with the user-provided nonce. It's not purely a hash, that's not good enough. The purpose is to protect against the user-provided nonce being weak. Still expect a proper nonce if it can be done.
- olliej 8y agoThe problem with gcm is that you absolutely cannot ever reuse a nonce, hence gcm-siv using a hash of the message - assuming a cryptographically strong hash the hash collision rate should theoretically have lower odds than a pure ring (sqrt(hashsize) vs likelihood of non-random different data colliding in practice) 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
- admax88q 8y agoI get why 'SIV' used a hash of the message in addition to the user provided nonce. 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.
- shinigami 8y agoFor that you need to divide the message in chunks and encrypt&authenticate each chunk. It's what GPG is going to do soon. There are some ad-hoc approaches for that procedure, but two interesting and well-constructed are STREAM and CHAIN: https://eprint.iacr.org/2015/189.pdf https://eprint.iacr.org/2015/189.pdf
- jetrink 8y ago> 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. 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.
- lvh 8y agoThis is playing a little fast and loose but just to get an idea: the keyed hash is fast but only secure once. By encrypting it, you get most of the perf benefit (the tag is much smaller than the entire message), and you get multi-message security. 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.
- colmmacc 8y agoThe later iterations of Poly1305 removed the need for AES by using a synthetic Salsa20 derived key that is unique per key-nonce input pair.
- lvh 8y agoWhoops; you're right of course, but same idea with fewer primitives -- either way, obscure the output of the polynomial MAC with the output of a cipher, so you get the fast MAC that you can reuse multiple times.
- colmmacc 8y agoA naked GHASH is not a secure MAC; the key can be reverse engineered from the value. So it's encrypted to make the tag.
- lvh 8y agoYou mean for 2 values under the same (key, nonce), right?
- zimmerfrei 8y ago>> 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. 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.pdf https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pd... [2] https://blog.quarkslab.com/reversing-a-finite-field-multiplication-optimization.html https://blog.quarkslab.com/reversing-a-finite-field-multipli...
- tptacek 8y agoIsn't the Shay Gueron presentation you're citing talking about cleverly using the CLMUL extensions that Intel basically added as hardware support for GCM? I feel like Intel did a pretty good job documenting how to use PCLMULQDQ to implement GHASH.