Re: [Cfrg] AES-PMAC-SIV

[Tony Arcieri <[e-mail]>]

On Wed, Nov 8, 2017 at 1:02 PM, Yehuda Lindell <[e-mail]>
wrote:

> 1) I don’t know how it can be hard to find implementations of AES-GCM-SIV
> to benchmark against. In addition to reporting measurements in the papers,
> we have also explicitly referenced both the github AES-NI implementation at
> https://github.com/Shay-Gueron/AES-GCM-SIV, and the BoringSSL
> implementation. Note that BoringSSL can be compiled both with AES-NI +
> CLMUL and without AES-NI (and CLMUL). So, you can compare easily on
> modern x86 processors and also on ARM v7 (which does not have AES-NI and
> CLMUL).
>

Thank you. I'm not sure how I didn't find this. I assure you I looked!


> 2) The statement about bounds is blatantly false. Indeed, AES-SIV has a
> birthday limit on the number of blocks. After encrypting 2^64 blocks, the
> adversary has an advantage of 1/2. Thus, in order to limit the adversary’s
> advantage to 2^-32, you can encrypt at most 2^48 blocks. In contrast,
> AES-GCM-SIV comes with BEYOND BIRTHDAY BOUNDS. This is described explicitly
> in the AES-GCM-SIV papers. In fact, if the same nonce is always used, then
> AES-GCM-SIV has the same bounds as AES-SIV, but when nonces repeat a
> bounded amount, AES-GCM-SIV’s bounds are way beyond AES-SIV.
>

The specific bounds I am referring to are the ones referred to in section 9
(Security Considerations) of draft-irtf-cfrg-gcmsiv-06:

If the nonce is fixed then AES-GCM-SIV acts like AES-GCM with a random
> nonce, with the caveat that identical plaintexts will produce identical
> ciphertexts. However, we feel that the 2^32 limit for AES- GCM is too risky
> in a multi-key setting. Thus with AES-GCM-SIV we recommend that, for a
> specific key, a nonce not be repeated more than 2^8 times.


I apologize if this is a mischaracterization. I actually asked a number of
people about this particular bound prior to posting, and at one point was
of the opinion I shouldn't even mention it. I would definitely appreciate
any clarifications you can provide to these bounds and how these relate to
the corresponding ones in AES-SIV.

-- 
Tony Arcieri