Subject: [Cfrg] AES-PMAC-SIV

From: Yehuda Lindell <[email-masked]>
Date: Wed, 8 Nov 2017 21:02:43 +0000

Regarding PMAC-SIV versus AES-GCM-SIV: it may be the case that some people do not want to implement GMAC based modes on embedded devices; I’m not sure, and there is some psychology here.

In any case, I do not want to relate to the question of standardizing PMAC-SIV. But, I feel I must respond to some comments made regarding AES-GCM-SIV, since there are some significant inaccuracies.

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).

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.

(GCM indeed has a 2^32 bound on the NUMBER OF MESSAGES when using a random IV, in order to keep the adversary advantage below 2^-32. However, in the setting with random nonces, AES-GCM-SIV can encrypt 2^48 messages of length 2^21 each, or 2^64 messages of length 2^13 each, and still have an adversarial advantage of only 2^-32.)

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 8 Nov 2017 17:29:18 -0800

On Wed, Nov 8, 2017 at 1:02 PM, Yehuda Lindell <[email-masked]>
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

---

From: Yehuda Lindell <[email-masked]>
Date: Thu, 9 Nov 2017 08:54:01 +0000

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 <[email-masked]> wrote:
> 
> On Wed, Nov 8, 2017 at 1:02 PM, Yehuda Lindell <[email-masked] <mailto:[email-masked]>> wrote:
> 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