[Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document ---- Some clarifications

["Gueron, Shay" <[e-mail]>]

Hello –



After we posted the AES-GCM-SIV draft, we saw several questions. We are 
trying to address the points that were raised, hence the lengthy mail.


Firstly, we’re sensitive to the concern that we’re pre-empting CAESAR 
here but we think that this is significantly smaller in scope than what 
CAESAR is attempting. AES-GCM-SIV just reformulates AES-GCM in a 
different order so that we can address some situations where the nonce 
requirements of AES-GCM are troubling.



AES-GCM-SIV has roughly the same cost as AES-GCM, which is already 
widely used on various platforms, both with and without AES hardware 
support. But, from an engineering point of view, there are a lot of 
machine with AES-GCM hardware support, which is driving the use of 
AES-GCM because of its performance on those machines. And it’s driving 
use of AES-GCM even in cases where the nonce can’t be a simple counter. 
Thus the motivation for a tweak to AES-GCM that avoids this problem.


We gladly offer it for free, for anyone to enjoy and use.

The code (reference, performance code, and performance numbers) is 
available in the github repository at 
https://github.com/Shay-Gueron/AES-GCM-SIV. BoringSSL will integrate it 
as well, so it could be used directly from that library.

The (ACM CCS) paper described a GCM-SIV implementation with 128-bit 
keys. The CFRG submission is different in two respects:
1. A 256-bit version that is added.
2. There is key derivation added (based on the nonce) to refresh the 
encryption key for each record.

The purpose of #2 is to allow AES-GCM-SIV to use a single key multiple 
times. In the original paper version, an IV is derived from the 
universal hash function (and the nonce) over the message, and occupies 
95 bits of the counter block during the encryption. Collisions are 
imminent after 2^48 uses, and to maintain safety margins, we would need 
to restrict the usage of one key to 2^32 messages. This could seem like 
a real constraint for a real AE scheme. With a differently derived key 
(derived from the nonce), the lifetime of one key can be extended.

The cost of extending the lifetime of the key is that of computing a key 
schedule, but this overhead is small on the target platforms that have 
AES hardware support.

To clarify a possible confusion about the 256-bit variant: no 256-bit 
key is ever derived from a 128-bit key. A 256-bit encryption key is 
derived from the 256-bit master key and a (128-bit) nonce but two 
encryptions. The authentication key has 128 bits, and so does the 
authentication tag.



Regarding the 256-bit key variant, and the key derivation in general, we 
are currently working on a full proof of security to show the exact 
bounds. However, for now, we would like to point you to this sketch of a 
proof, showing that obtaining a key by applying AES-256 to the nonce 
(twice) as we do, does not harm security (the full proof later will show 
that it significantly increases the security).



PROOF SKETCH:

Let \Pi=(Gen,Enc,Dec) be an encryption scheme (including mode of 
operation) that uses AES256 directly and is (t,q,e)-indistinguishable 
(time t, with q queries to encryption oracle, advantage e). Now, modify 
to \Pi’=(Gen’,Enc’,Dec’) where the only difference is that Enc’ begins 
by deriving a 256 bit key by applying AES256 to the nonce with 0 and 
then to the nonce with 1.



Then, the distinguishing probability for \Pi’ is at most (t,q,e) PLUS 
what can be gained by distinguishing AES256 from a PRP with the number 
of queries equalling twice the number of different nonces queried PLUS 
2^{-128}. This follows since a distinguisher D for AES256 can derive the 
keys using its oracle. We have the following observations:

1) If the function being accessed by D is random, then the key is truly 
random EXCEPT that it cannot be of the form k'||k’. Thus, with 
probability 2^{-128} the key will be of this form and it won’t be the 
same as the original encryption scheme. Otherwise, it’s identical to the 
original encryption scheme.

2) If the function being accessed by D is AES256, then this is exactly 
the modified encryption scheme.

Note that the number of queries made by D to its oracle is twice the 
number of different nonces. Thus, this is the only difference.



We stress that the above just shows that nothing is lost by doing this 
derivation. However, we do it in order to gain inside \Pi. The bounds 
will be published soon.


Thank you,
Shay, Adam, Yehuda