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

From: "Gueron, Shay" <[email-masked]>
Date: Fri, 15 Apr 2016 16:13:22 +0000

Hi Aaron,

Thanks for the comment, but I believe your conclusion is not correct.

AES-GCM-SIV (128/256 bit key) which is proposed for CFRG is a fully 
nonce misuse resistant authenticated encryption scheme.

This means the following: repeating a nonce will not leak any 
information except if the same nonce and the same message is encrypted. 
In that case, an adversary could only know that the two identical 
message were encrypted (this cannot be avoided in any deterministic 
scheme).

Of course, there are limits to the number of times messaged can be 
encrypted with the same key. The security margins of the CCS2015 paper 
(original scheme) were proven there.

The CFRG submission extends the number of times that a single key 
(either 128 or 256 bits) can be used - and gets better bounds - at the 
cost of extra key expansion, as specified (we will publish the improved 
bounds).

However, if a user chooses to use the scheme to send many (e.g., ~2^48) 
messages while always repeating the same nonce, then AES-GCM-SIV simply 
reduces to the GCM-SIV of the CCS2015 paper (and the synthetic IV's 
will, at high probability, collide). This is inevitable under such a 
"nonce abuse" scenario. Basically, this case would behave similarly to 
AES-GCM with a random 96-bit nonce, used ~2^48 with the same key.

What else can be expected?

I hope this clarifies the situation.

Thanks, Shay

------ Original Message ------
From: "Aaron Zauner" <[email-masked]>
To:
Cc: "Yehuda Lindell" <[email-masked]>; "[email-masked]" 
<[email-masked]>; "Adam Langley" <[email-masked]>
Sent: 4/15/2016 8:48:07 AM
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant 
Authenticated Encryption" as a CFRG document ---- Some clarifications

>Hi,
>
>Went through past discussion on the proposal, the draft and (also) 
>noticed the security considerations section and Adam's reply over here: 
>https://www.ietf.org/mail-archive/web/cfrg/current/msg08030.html
>
>So I think it's worth noting in the document that this proposal isn't 
>"as" nonce misuse resistant to the extent that some people may assume 
>it is by the title/abstract. i.e. GCM-SIV speaks of "Fully nonce misuse 
>resistance" while AES-GCM-SIV uses the term "Nonce misuse resistance" - 
>it may be well worth going into more detail in the draft on the matter 
>and clarifying. Please correct me if I'm completely off-course here.
>
>Aaron

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 15 Apr 2016 23:46:21 +0700

Hi,

> On 15 Apr 2016, at 23:13, Gueron, Shay <[email-masked]> wrote:
> This means the following: repeating a nonce will not leak any information except if the same nonce and the same message is encrypted. In that case, an adversary could only know that the two identical message were encrypted (this cannot be avoided in any deterministic scheme).
> 
> Of course, there are limits to the number of times messaged can be encrypted with the same key. The security margins of the CCS2015 paper (original scheme) were proven there.
> 
> The CFRG submission extends the number of times that a single key (either 128 or 256 bits) can be used - and gets better bounds - at the cost of extra key expansion, as specified (we will publish the improved bounds).

Thanks for the clarification on that part.

> However, if a user chooses to use the scheme to send many (e.g., ~2^48) messages while always repeating the same nonce, then AES-GCM-SIV simply reduces to the GCM-SIV of the CCS2015 paper (and the synthetic IV's will, at high probability, collide). This is inevitable under such a "nonce abuse" scenario. Basically, this case would behave similarly to AES-GCM with a random 96-bit nonce, used ~2^48 with the same key.

Ok, so I did understand this correctly in the first place. That's actually of some concern to me, we've seen some implementations (most Cavium based, AFAICT) in the wild that use random 96-bit nonces with AES-GCM [0], some actually repeat them [1]. Likewise it's probable that implementers may err with AES-GCM-SIV and repeat messages under the same nonce ~2^48 times in some scenarios.

> What else can be expected?

The explanation you provided above (w.r.t. repeating messages under a single nonce ~2^48 times) is quite sufficient, may I suggest it gets added to the security consideration section so implementers might not repeat the same mistake with this particular design?

Thanks for your time & feedback,
Aaron

[0] https://www-01.ibm.com/support/docview.wss?uid=swg21979604
[1] https://kb.radware.com/Questions/SecurityAdvisory/Public/Security-Advisory-Explicit-Initialization-Vector-f

---

From: "Gueron, Shay" <[email-masked]>
Date: Fri, 15 Apr 2016 17:04:53 +0000

Hi -

Sure, we can add the comment to the next revision.

(In any case, this follows from the security bounds, but spelling this 
out in the CFRG document would not hurt)

[ About using AES-GCM with a random IV 2^48 times: this violates the 
guidelines of AES-GCM spec ( 
http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf, 
section 8.3). ]

Regards, Shay

------ Original Message ------
From: "Aaron Zauner" <[email-masked]>
To: "Gueron, Shay" <[email-masked]>
Cc: "Yehuda Lindell" <[email-masked]>; "[email-masked]" 
<[email-masked]>; "Adam Langley" <[email-masked]>
Sent: 4/15/2016 9:46:21 AM
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant 
Authenticated Encryption" as a CFRG document ---- Some clarifications

>>information except if the same nonce and the same message is 
>>encrypted. In that case, an adversary could only know that the two 
>>identical message were encrypted (this cannot be avoided in any 
>>deterministic scheme).
>>
>>cost of extra key expansion, as specified (we will publish the 
>>improved bounds).
>
>>  However, if a user chooses to use the scheme to send many (e.g., 
>>~2^48) messages while always repeating the same nonce, then 
>>AES-GCM-SIV simply reduces to the GCM-SIV of the CCS2015 paper (and 
>>the synthetic IV's will, at high probability, collide). This is 
>>inevitable under such a "nonce abuse" scenario. Basically, this case 
>>would behave similarly to AES-GCM with a random 96-bit nonce, used 
>>~2^48 with the same key.
>
>Ok, so I did understand this correctly in the first place. That's 
>actually of some concern to me, we've seen some implementations (most 
>Cavium based, AFAICT) in the wild that use random 96-bit nonces with 
>AES-GCM [0], some actually repeat them [1]. Likewise it's probable that 
>implementers may err with AES-GCM-SIV and repeat messages under the 
>same nonce ~2^48 times in some scenarios.
>
>The explanation you provided above (w.r.t. repeating messages under a 
>single nonce ~2^48 times) is quite sufficient, may I suggest it gets 
>added to the security consideration section so implementers might not 
>repeat the same mistake with this particular design?
>
>[1] 
>https://kb.radware.com/Questions/SecurityAdvisory/Public/Security-Advisory-Explicit-Initialization-Vector-f

---

From: Aaron Zauner <[email-masked]>
Date: Sat, 16 Apr 2016 00:22:05 +0700

Hi,

> On 16 Apr 2016, at 00:04, Gueron, Shay <[email-masked]> wrote:
> 
> Hi -
> 
> (In any case, this follows from the security bounds, but spelling this out in the CFRG document would not hurt)

I think the clearer the wording here, the better the outcome in the understanding of implementers, not all are mathematicians or cryptographers themselves.

> [ About using AES-GCM with a random IV 2^48 times: this violates the guidelines of AES-GCM spec ( http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf, section 8.3). ]

I am aware of that. Joux provided a comment on the matter during the NIST specification phase: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-38_Series-Drafts/GCM/Joux_comments.pdf (section 3)

The problem here is not the spec itself - it's human error and misunderstanding during implementation phase. I feel nonce-misuse resistant modes should effectively prevent such scenarios in the first place. At least that was my understanding until today.

Aaron