Re: [Cfrg] AES-PMAC-SIV

[Yehuda Lindell <[e-mail]>]

Hi,

The intention in the spec text is that if the nonce is fixed then AES-GCM-SIV has a birthday bound on the overall number of blocks (like AES-GCM, AES-CCM, AES-SIV, etc.), even if the adversary is nonce-respecting. This means that you can encrypt up to 2^48 blocks overall with the same nonce in AES-GCM-SIV, with the adversarial advantage of only 2^-32.

The detailed analysis of all of these security considerations appear in the series of papers referred to. I suggest looking at https://eprint.iacr.org/2017/168.pdf <https://eprint.iacr.org/2017/168.pdf> and https://eprint.iacr.org/2017/702.pdf <https://eprint.iacr.org/2017/702.pdf>.

We have also put up a webpage with information and FAQs. See: http://cyber.biu.ac.il/aes-gcm-siv <http://cyber.biu.ac.il/aes-gcm-siv>

Yehuda


> On 9 Nov 2017, at 3:29, Tony Arcieri <[e-mail]> wrote:
> 
> On Wed, Nov 8, 2017 at 1:02 PM, Yehuda Lindell <[e-mail] <mailto:[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 <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