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

From: Adam Langley <[email-masked]>
Date: Sun, 3 Apr 2016 06:57:29 +0700

On Thu, Mar 31, 2016 at 3:22 PM, Andy Lutomirski <[email-masked]> wrote:
> 4. Since this claims nonce-MR, setting nonce=0 is valid.  If someone does
> this, then I think they are vulnerable to the extra-easy parallel attack.

Ah, do you mean when the AES-GCM-SIV is used with a fixed nonce?

In that case, it breaks down in the same way as AES-GCM with random
nonces. We note that in the Security Considerations
(https://tools.ietf.org/html/draft-gueron-gcmsiv-02#section-9):

"It's worth noting that the 2^32 limit still applies as the number of
distinct messages that can be encrypted under a fixed nonce. Nonces
should be unique and the misuse-resistance of these AEADs should not
be depended on to the extent that 2^32 duplicates may occur.  (Or 2^31
duplicates in the case of AEAD_AES_256_GCM_SIV.)"

Basically our "misuse" resistance doesn't stretch to that kind of
abuse. That might not meet some definitions of nonce-MR but
AES-GCM-SIV is very strongly related to AES-GCM and so acts like it in
some cases.

Cheers

AGL

---

From: Andy Lutomirski <[email-masked]>
Date: Sat, 2 Apr 2016 17:49:15 -0700

> (https://tools.ietf.org/html/draft-gueron-gcmsiv-02#section-9):

I mean something different, but I read it a bit wrong.  If I understand
correctly, if AES256-GCM-SIV is used 128-bit keys, then you can only
encrypt with ~2^64 (key, nonce) pairs, even with different keys, before a
work factor ~2^64 attacker can decrypt one of them (which one is not under
their control).  This may not work if something prevents DJB's efficient
parallel attack from working.

With fixed nonce, the key derivation has no practical effect (as I said, I
read it wrong at first).  With *variable* nonce, the protocol no longer
works like the paper, so I don't believe the security proof works as is.

---

From: "Gueron, Shay" <[email-masked]>
Date: Tue, 05 Apr 2016 13:14:05 +0000

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

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 7 Apr 2016 16:16:07 -0700

On Tue, Apr 5, 2016 at 6:14 AM, Gueron, Shay <[email-masked]> wrote:
> The (ACM CCS) paper described a GCM-SIV implementation with 128-bit keys.
> The CFRG submission is different in two respects:
> 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.
>
> 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.

The only relevant text I can find in the draft is:

   If the AES key is 16 bytes long then define the _record-encryption
   key_ as the encryption of the nonce using the AES key.  If AES-256 is
   being used then this is insufficient as 256 bits of key material are
   needed.  Therefore the record-encryption key in this case is the
   concatenation of the result of encrypting, using the AES key, the
   nonce with the least-significant bit of the first byte set to zero
   and then to one.

This very much sounds to be like (a) a 256-bit key is derived from a
128-bit key and (b) the draft doesn't actually specify what the record
key is in any other case.  I interpreted the vague text to mean that
the record key is the AES key in all other cases.

Can you clarify the draft?

--Andy

---

From: Adam Langley <[email-masked]>
Date: Fri, 8 Apr 2016 08:55:17 +0900

> Can you clarify the draft?

Will do as soon as I'm able (which should be next week).

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

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

Regarding:

****

--Andy
****

Yes, of course. Here is the paragraph with explanatory notes in *** ... 
***

If the AES key is 16 bytes long then define the _record-encryption
key_ as the encryption of the nonce using the AES key. *** so far, the 
case of 128-bit key***

If AES-256 is being used *** now the case of 256-bit key***
then this is insufficient as 256 bits of key material are needed *** 
because one invocation produces only 128 bits, and we want to derive a 
256-bit key ***
Therefore the record-encryption key in this case is the *** here is the 
explanation: ***
concatenation of the result of encrypting, using the AES key *** recall 
that it is the 256-bit case***, the nonce with the least-significant bit 
of the first byte set to zero and then to one.
*** that is AES  New key (256 bits) =  AES256 (NONCE[127:1] || 0) || 
AES256 (NONCE[127:1] || 1)  (256 bits altogether).

Thus, "This very much sounds to be like (a) a 256-bit key is derived 
from a 128-bit key and (b) the draft doesn't actually specify what the 
record" is not the case.
Shay

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

>>keys.
>>universal
>>key is

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 7 Apr 2016 21:11:28 -0700

On Thu, Apr 7, 2016 at 9:00 PM, Gueron, Shay <[email-masked]> wrote:
> Yes, of course. Here is the paragraph with explanatory notes in *** ... ***
>
> key_ as the encryption of the nonce using the AES key. *** so far, the case
> of 128-bit key***
>
> then this is insufficient as 256 bits of key material are needed *** because
> one invocation produces only 128 bits, and we want to derive a 256-bit key
> ***
> concatenation of the result of encrypting, using the AES key *** recall that
> it is the 256-bit case***, the nonce with the least-significant bit of the
> first byte set to zero and then to one.
> *** that is AES  New key (256 bits) =  AES256 (NONCE[127:1] || 0) || AES256
> (NONCE[127:1] || 1)  (256 bits altogether).
>
> Thus, "This very much sounds to be like (a) a 256-bit key is derived from a
> 128-bit key and (b) the draft doesn't actually specify what the record" is
> not the case.
> Shay
>

Hmm, I guess I didn't read it quite right.

What happens if AES-128 is used and the "AES key" is 32 bytes long?
Or is this not allowed?

It might help to clarify exactly what variants of this scheme exist in
terms of AES variant and key size.

--Andy

---

From: Shay Gueron <[email-masked]>
Date: Fri, 8 Apr 2016 11:25:52 +0300

OK, let me explain:

There are (only) two options for the key: 128 bit or 256 bits.

For the "128-bit" case, the document states
"If the AES key is 16 bytes long then define the _record-encryption-key_ as
the encryption of the nonce using the AES key".
That is AES128 (NONCE)  (using the 128-bit key). This is the
straightforward case.

The "256-bit" case, is covered in my previous explanation, basically:

AES256 (NONCE[127:1] || 0) || AES256 (NONCE[127:1] || 1)  (using the
256-bit key, and producing 256 bits altogether).

I hope this helps. We will definitely edit the text and post a version that
includes these explanations (soon).

Thank you, Shay

2016-04-08 7:11 GMT+03:00 Andy Lutomirski <[email-masked]>:

> case
> because
> that
> AES256
> from a

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 8 Apr 2016 13:49:22 +0000

> . . . . . . 
> AES256 (NONCE[127:1] || 0) || AES256 (NONCE[127:1] || 1)  (using the 256-bit
> key, and producing 256 bits altogether).

Another way to explain it – you run AES256 as a PRF to generate 256
pseudo-random bits with it, and take those 256 bits as a record key for
AES256.

(Sounds solid to me.)

---

From: "Gueron, Shay" <[email-masked]>
Date: Sun, 10 Apr 2016 13:45:47 +0000

Hi Uri,

You are definitely right.

I just tried to answer about the actual flow, rather than the intended 
cryptographic property (i.e., how the 256-bit case operates).

The details on how the nonce is used, show that AES256 is applied to 2 
different blocks. But again – your description grasps the intention.

A comment (that was asked / addressed in previous threads): AES256 used 
here is a permutation invoked over 2 different blocks. So, a key search 
can ignore 256-bit keys of the form “x || x” (i.e., there are only 
2^{256}-2^{128} options). This is negligible.

Thanks, Shay

---

From: Adam Langley <[email-masked]>
Date: Thu, 14 Apr 2016 14:12:36 -0700

> Will do as soon as I'm able (which should be next week).

-03 is hopefully clearer on this point:
https://tools.ietf.org/html/draft-gueron-gcmsiv-03#section-4

Cheers

AGL

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 15 Apr 2016 22:48:07 +0700

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: "Gueron, Shay" <[email-masked]>
Date: Fri, 15 Apr 2016 16:06:23 +0000

Hi Aaron,

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

AES-GCM-SIV (128/256 bit key) which is proposed for CFRG is a fully 
nonce misuse resistant authenticated encryption scheme. This means that 
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).

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 send many (e.g., 2^48) messages and always 
repeat the same nonce, then AES-GCM-SIV simply reduces to the GCM-SIV of 
the CCS2015 paper. Basically, it would behave similarly to AES-GCM with 
a random 96-bit nonce (this is also inevitable under such a "nonce 
abuse" scenario in a SIV construction).

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: Michael StJohns <[email-masked]>
Date: Fri, 15 Apr 2016 12:28:32 -0400

On 4/15/2016 12:06 PM, Gueron, Shay wrote:
> This means that 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). 

Is there any other scheme currently in use in our protocols (TLS, IPSEC, 
etc) that has the property that identical messages under the same 
key/nonce (or key IV) are encrypted identically?

I've been reading this thread only intermittently and perhaps I missed 
the discussion, but the above property seems to be a "bad thing"(tm) in 
the general scheme of things.  Perhaps it can be mitigated by specific 
protocols with specific techniques but that seems to be contrary to the 
idea that this is an idiot-proof (in terms of implementation) 
improvement over AES-GCM itself.

Mike

---

From: Adam Langley <[email-masked]>
Date: Fri, 15 Apr 2016 10:13:42 -0700

On Fri, Apr 15, 2016 at 9:28 AM, Michael StJohns <[email-masked]> wrote:
> etc) that has the property that identical messages under the same key/nonce
> (or key IV) are encrypted identically?

I think all encryption schemes have this property if I understand you.

Given a fixed (key, nonce, message), all AEADs should be
deterministic, i.e. will produce a fixed ciphertext. That includes
AES-GCM, ChaCha20-Poly1305, AES-CCM etc

For CBC modes, some people consider them to be functions of (key,
message)→ciphertext, in which case the random IV makes them
non-deterministic in that model. But if considered to be a function of
(key, message, IV)→ciphertext then they, too, are deterministic too.

Cheers

AGL

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 15 Apr 2016 13:46:19 -0700 (PDT)

> key/nonce (or key IV) are encrypted identically?

  Way back at IETF70 I proposed some ciphersuites for TLS using
AES-SIV (RFC 5297). AES-SIV has the same nonce-misuse properties
as AES-GCM-SIV but it's a 2-pass cipher mode. The general response
I received can be summarized as "we don't need nonce misuse because
the nonce is not part of the API that Joe User, who may be ignorant
of nonce usage issues, calls and everyone writing a TLS implementation
knows what he or she is doing so it's not a problem."

  Of course, times change and so do opinions.

  regards,

  Dan.

---

From: Michael StJohns <[email-masked]>
Date: Fri, 15 Apr 2016 21:00:39 -0400

> (key, message, IV)→ciphertext then they, too, are deterministic too.

Hi Adam - thanks for the question.

That's not exactly what I mean/meant.  In TLS, the same message (record, 
etc) sent under the same key and IV/NONCE (as produced by the TLS 
PRF/KDF functions or produced randomly) will provide different 
ciphertext based on the fact that the record counter changes with each 
message.  That counter doesn't necessarily have to be part of the 
authenticated data in an AEAD cipher as the nonce formation is somewhat 
external to processing (with the exception of the block counter).

To get the equivalent behavior for AES-GCM-SIV, you need to ensure there 
is some sort of per-message unique mixin (unique within the association 
duration at least) that causes the tag to be different which causes the 
nonce to be different.

*sigh* Let me try it another way.  Take generic AES-GCM, a key and a 
random association nonce.  We form the message nonce from the 
concatenation of the association nonce and a message id or counter. We 
form the block nonce from the concatenation of the message nonce and the 
block counter.  We encrypt the block nonce to provide the data to be 
XOR'd.  The message and AD that we encrypt and protect need not include 
the message id - as long as we can derive it or count it, we don't have 
to send it and it will not be included under the cryptographic 
calculations.  This mostly doesn't matter, because if either end gets 
the counter wrong, the message fails to authenticate at the receiver.

That's not the case for AES-GCM-SIV.  If the message ID is not part of 
the data provided (either payload to be encrypted or associated AD) to 
the POLYVAL function, you will have identical tags for identical 
messages leading to identical ciphertext for identical plain text.

It turns out that this mostly doesn't matter to TLS or IPSEC as they 
both MAC the message sequence number so that's going to be covered by 
any AEAD Associated Data integrity processing and result in a different 
cipher text for the same message even with AES-GCM-SIV. But I remember 
arguments about removing the sequence number in other protocols to save 
space (e.g. its running over TLS - what do we need a sequence number in 
the record for? ) and I worry that this nuance might be missed in future 
protocols that use this cipher mode.

Mike

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 16 Apr 2016 18:53:00 +0000

Date: Fri, 15 Apr 2016 13:46:19 -0700 (PDT)
   From: "Dan Harkins" <[email-masked]>

I drafted the following message in reply:

`For TLS, it is not a matter of ``all the implementors know what
 they're doing''.  Rather, if you reuse a nonce, your implementation
 is simply broken and will immediately, noisily fail to interoperate.

`For that case, AES-GCM-SIV is strictly less secure than AES-GCM
 because AES-GCM-SIV effectively uses randomly chosen 96-bit nonces
 and hence has a small birthday bound before an accidental internal
 nonce reuse (which is catastrophic).  AES-GCM nonces, in contrast,
 are guaranteed never to repeat in a TLS conversation.'

But then, on fact-checking myself, I discovered that the AES-GCM
cipher suites in TLS (RFC 5288) do not actually mandate the use of the
message sequence number as the nonce, which would have the fail-early
fail-closed effect I described -- instead the senders pick nonces on
their own arbitrarily and transmit them alongside the message, and the
receivers accept any nonces they receive.

---

From: Yoav Nir <[email-masked]>
Date: Sat, 16 Apr 2016 21:35:17 +0200

> On 16 Apr 2016, at 8:53 PM, Taylor R Campbell <[email-masked]> wrote:
> 

That is true. However, most implementers have used the record number as nonce, and TLS 1.3 makes this mandatory and implicit.

Yoav

---

From: Adam Langley <[email-masked]>
Date: Sun, 17 Apr 2016 10:25:32 -0700

On Fri, Apr 15, 2016 at 6:00 PM, Michael StJohns <[email-masked]> wrote:
> etc) sent under the same key and IV/NONCE (as produced by the TLS PRF/KDF
> functions or produced randomly) will provide different ciphertext based on
> the fact that the record counter changes with each message.  That counter
> doesn't necessarily have to be part of the authenticated data in an AEAD
> cipher as the nonce formation is somewhat external to processing (with the
> exception of the block counter).
>
> To get the equivalent behavior for AES-GCM-SIV, you need to ensure there is
> some sort of per-message unique mixin (unique within the association

That's correct and, in the case of TLS, I'd suggest that the sequence
number be used as the nonce in order to make sure that equal messages
don't produce equal ciphertexts. Although, to be clear, I'm not
suggesting that AES-GCM-SIV be used in TLS or in any situation where a
counter nonce is easy. Transport security is generally a situation
where a single sender can just use a counter and, in those cases,
AES-GCM is better.

But there are situations where nonce management is a problem (i.e.
where there are multiple machines encrypting with a single key) and,
for that, I think AES-GCM-SIV is pretty attractive because one can
reasonably use a random nonce.

Cheers

AGL

---

From: Fedor Brunner <[email-masked]>
Date: Mon, 18 Apr 2016 09:21:56 +0200

> reasonably use a random nonce.

https://cr.yp.to/papers.html#xsalsa

XSalsa20 is Salsa20 cipher with nonce extended to 192 bits. So there is
no need to manage nonces, they can be generated with RNG. Could you
please describe applications where you would prefer AES-GCM-SIV over
XSalsa20+Poly1305

> 
> 
> Cheers
> 
> AGL
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
> 
>

---

From: Paul Grubbs <[email-masked]>
Date: Mon, 18 Apr 2016 14:28:42 -0400

In some settings using AES for data encryption is required by law,
regulation, or best practices. I doubt the use of AES in Poly1305 would
pass muster, since it's only authenticating and not encrypting.

On Mon, Apr 18, 2016 at 3:21 AM, Fedor Brunner <[email-masked]>
wrote:

> PRF/KDF

---

From: Adam Langley <[email-masked]>
Date: Tue, 19 Apr 2016 07:41:53 -0700

> please describe applications where you would prefer AES-GCM-SIV over

Basically the increasing levels of hardware support for AES-GCM make
it compelling from a performance point of view.

(Storing the extra twelve bytes of nonce /might/ be a concern in some
cases but I'm not sure about that.)

Cheers

AGL

---

From: Paul Lambert <[email-masked]>
Date: Wed, 20 Apr 2016 00:40:54 +0000

>it compelling from a performance point of view.

Yes Š GCM is becoming the preferred hardware encryption algorithm for it¹s
performance. GCM is being designed into most layer 2 encryption protocols
and the associated hardware. Encryption hardware is a significant
investment in a chip and given the dominance of AES it is unlikely that an
additional cipher (like Salsa20) will be added broadly to hardware for a
very long time.  

>cases but I'm not sure about that.)

Yes - that will be an issue for many existing designs.  It¹s still a much
smaller change for a design that moving to Salsa or any other new cipher.

Nonce misuse-resistance is quite valuable in ad-hoc multicast
environments. It will be interesting to see how AES-GCM-SIV maps into the
formats of a multicast encryption protocols (like ad-hoc encrypted
multicast in 802.11). This nonce resistance is a mode I¹ve been hoping
would get support for many years for ad-hoc multicast environments. In
particular, it solves the n^2 key setup problems of 802.11 IBSS.

Paul

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 20 Apr 2016 02:13:36 +0000

Date: Mon, 18 Apr 2016 09:21:56 +0200
   From: Fedor Brunner <[email-masked]>

For NaCl crypto_secretbox_xsalsa20poly1305, nonce reuse -- e.g., due
to a buggy random number generator -- is catastrophic: an eavesdropper
learns the xor of two unknown-plaintext messages, or the content of
one unknown-plaintext message given one known-plaintext message, and
can forge arbitrarily many future messages.

For AES-GCM-SIV, nonce reuse enables the attacker to distinguish
duplicate messages from distinct messages, but is not otherwise
harmful.

Resistance to nonce reuse for AEAD is part of why there is an entire
AES-style crypto competition dedicated to AEAD schemes, CAESAR
<https://competitions.cr.yp.to/caesar.html>.  AES-GCM-SIV was not
submitted because it was put together too recently.

The creators of AES-GCM-SIV and chairs of the CFRG evidently decided
that it would be better to sidestep the competition and endorse crypto
that is, lacking hardware support, either unusably slow or vulnerable
to timing side channels, recommending it for general-purpose use on
the internet.

It's easy to say `all the hardware now supports it'.  It's much harder
to audit all the applications you're using to confirm that they
actually take advantage of the hardware support across umpteen layers
of software abstractions and do not render your keys vulnerable to
extraction by someone over the internet with a watch.

---

From: Fedor Brunner <[email-masked]>
Date: Wed, 20 Apr 2016 09:18:30 +0200

> can forge arbitrarily many future messages.
For most application you want to have forward secrecy. To have forward
secrecy you need to generate ephemeral keys using working random number
generator. So most applications already require correctly working RNG.
> to timing side channels, recommending it for general-purpose use on
I think a note about side channels should be added to Section 9 Security
Considerations.

---

From: Bryan Ford <[email-masked]>
Date: Wed, 20 Apr 2016 09:37:18 +0200

> to timing side channels, recommending it for general-purpose use on

I have to say I was also quite surprised by the declaration that there is “rough consensus” to adopt.  While I haven’t been following this thread extremely closely, what I remember seeing is:

- 2-3 messages (mostly early on in the thread) explicitly opposed to adoption due to this concern about sidestepping the CAESAR competition
- 2-3 messages expressing explicit support for adoption
- A whole bunch of E-mails discussing various technical issues, but neither explicitly supporting or opposing adoption as far as I could tell.

I admit I did not do any kind of precise tally on any basis, this is merely my impression, which is why the adoption declaration took me by surprise.

I personally also have deep concerns about CFRG hastily adopting an AEAD proposal that has not received the careful scrutiny that the CAESAR competitors are receiving, especially not primarily on the basis of performance claims.  I have not seen evidence of an urgent need for a misuse-resistant AEAD scheme to be standardized “right now” - and if there were an urgent need, the CFRG should at least choose among those CAESAR competitors still in the running (after the first round) that seem to have received the greatest analysis and community support so far.

Again just my $.02

B

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 20 Apr 2016 08:37:42 +0000

Hi

>to timing side channels, recommending it for general-purpose use on

As we said right back at the start, CFRG adopting AES-GCM-SIV does not
preclude us from also adopting other algorithms when they eventually
emerge from the CAESAR process. Indeed, we look forward to that happening.
There's certainly nothing definitive or final about AES-GCM-SIV as far as
we are concerned. 

Moreover, as chairs, we do not "endorse" anything, nor are we deliberately
side-stepping the CAESAR competition. Rather, we have the difficult task
of attempting to balance the interests and needs of some participants in
the group against those of others.

It's fine that you disagree on where we've struck the balance in this
case, but please do understand that these decisions are not black and
white.

Regards,

Kenny

---

From: Thomas Peyrin <[email-masked]>
Date: Wed, 20 Apr 2016 17:04:21 +0800

Hi,

Sorry to continue this discussion, but I'm still dubious on the
consideration of AES-GCM-SIV. I think there are two questions here:
- the first one is why do we need to push an AEAD now, while the CAESAR
competition will lead to a selected portfolio in a few years ?
- the second is if we really want to have an AEAD now, why looking at
AES-GCM-SIV only, while there are candidates from the CAESAR competitions
(that have probably been much more analysed than AES-GCM-SIV and thus
present a direct important advantage) ?

I understand the explanations for the first point (considering an AEAD now
doesn't preclude from having CAESAR candidates later as well), but I don't
understand for the second point. Why do we need to wait for the end of
CAESAR competition before considering CAESAR candidates instead of
AES-GCM-SIV ? I believe we should at least take a short look at the current
algorithms available now, and not only AES-GCM-SIV ?

Cheers,

Thomas.

---

From: Adam Langley <[email-masked]>
Date: Wed, 20 Apr 2016 08:59:17 -0700

> algorithms available now, and not only AES-GCM-SIV ?

Many CAESAR candidates may be "better designed" in the same way that
XSalsa20-Poly1305 is, in some sense, "better designed" than
AES-GCM-SIV: i.e. it uses operations that are independently useful on
CPUs and so more performant (with fewer tricks) than the binary fields
of AES and GHASH/POLYVAL.

But dedicated hardware for AES-GCM is now fairly common in many
environments and it's very hard for anything to beat the performance
and power efficiency of this dedicated hardware. (Which seems a little
like cheating, but that's where we are.)

Thus AES-GCM is the default for encrypting large amounts of data. But
in situations where a counter nonce isn't possible a significant
amount of worry has to go into convincing ourselves that a duplicate
nonce isn't possible. So what we want is AES-GCM—but with less worry.
Same underlying primitives, basically the same speed, same API, but no
detonation if nonce uniqueness slips for some crazy reason.

Since this is so so closely related to AES-GCM, I don't think that
volumes of analysis can be directly compared with CAESAR candidates:
AES is nearly axiomatic now and so doesn't need the sorts of analysis
that something like NORX warrants.

I know that some CAESAR candidates are based around AES for this
reason and in order to take advantage of hardware support. If you have
one in mind then it should be considered, but I believe that
AES-GCM-SIV is very useful as a tweak of AES-GCM and I'm not sure what
an alternative would usefully provide without venturing into being
"more exciting". I would like CAESAR to produce a primitive that
provides cool features like AEZ's (any maybe other's) arbitrary block
size. But, for now, I would welcome a slightly more robust AES-GCM.

Cheers

AGL

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 20 Apr 2016 16:25:59 +0000

> Sorry to continue this discussion, but I'm still dubious on the consideration
> of AES-GCM-SIV. I think there are two questions here:

Because we don’t want to wait for “a few years”.

> (that have probably been much more analysed than AES-GCM-SIV and thus present
> a direct important advantage) ?

I doubt the other candidates have been “much more analysed”.  Also, (a) I’m
happy with the analysis that accompanies AES-GCM-SIV, and (b) I’m well-aware
of the limitations of “security proofs” that more and more algorithms are
coming with nowadays.

But if you see a problem with GCM-SIV security proofs (or assumptions
they’re based on), by all means speak up.

> Why do we need to wait for the end of CAESAR competition before considering
> CAESAR candidates instead of AES-GCM-SIV ? I believe we should at least take a
> short look at the current algorithms available now, and not only AES-GCM-SIV ?

Fine with me. Take a short look and write a draft for another algorithm.
Explaining what properties you need that are missing  in GCM-SIV would be
nice too.

---

From: Thomas Peyrin <[email-masked]>
Date: Thu, 21 Apr 2016 00:35:28 +0800

Indeed, if the goal is to have an AES-based AEAD candidate that offers some
kind of misuse resistance, there are quite a few among the CAESAR designs
(AEZ being indeed on of them)

---

From: Thomas Peyrin <[email-masked]>
Date: Thu, 21 Apr 2016 00:48:25 +0800

2016-04-21 0:25 GMT+08:00 Blumenthal, Uri - 0553 - MITLL <[email-masked]>:

> I don't think I have ever said that ?

> Explaining what properties you need that are missing  in GCM-SIV would be

Perhaps before writing a draft for all CAESAR candidates (or even AES-based
CAESAR candidates), we could spend a little time discussing what would be
the advantages of the various options we have at hand ? I would say for 2nd
round AES-based CAESAR candidates that provide some kind of misuse
resistance, we should consider AES-COPA, AEZ, Deoxys, ElmD, POET and SHELL
(I hope I didn't forget any).

Thomas.

---

From: Andy Lutomirski <[email-masked]>
Date: Thu, 21 Apr 2016 12:45:40 -0700

> https://tools.ietf.org/html/draft-gueron-gcmsiv-03#section-4

This is much clearer to me.

However:

   This record-encryption
   key is defined as the concatenation of the result of encrypting,
   using the AES key, the nonce with the least-significant bit of the
   first byte set to zero and then to one.

Why is it designed this way?  This has the odd property that the
record encryption key is the same for two messages with nonces that
differ only in the LSB of the first byte.

Alternative designs include:

a) Concatenate the results of encrypting the nonce and the none with
the LSB of the first byte flipped.

b) Concatenate the results of encrypting the nonce and the nonce + 1.

Both of these will have related nonces generate related keys, but at
least they won't generate the *same* key.

It still seems to be that performance for short block sizes may be
rather poor given the key setup needed.

--Andy

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Apr 2016 20:00:23 +0000

>differ only in the LSB of the first byte.

You’re right!

>b) Concatenate the results of encrypting the nonce and the nonce + 1.

Have we all forgot the good ol’ OFB mode? This seems a perfect use case
for it. Take the 128-bit nonce as the seed and crank AES-256 engine twice
to get two 128-bit pseudorandom blocks. Concatenate them and use as the
record key. Same performance as what you’re getting, better security - and
the advantage of staying with standardized block cipher modes :).

>rather poor given the key setup needed.

Can’t comment, but frankly don’t care much.

---

From: Shay Gueron <[email-masked]>
Date: Thu, 21 Apr 2016 23:06:59 +0300

Andy,

Addressing your concern:
>>> This has the odd property that the
This is not the case. What the spec states means the following:
The record encryption key is derived by

AES256 (NONCE[127:1] || 0) || AES256 (NONCE[127:1] || 1)

I hope this helps clarifying.
Regards, Shay

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Apr 2016 20:11:33 +0000

I’m afraid Andy is correct. Say one record has its nonce xxxx…xxxx0 (127
bits plus 0), and another record has its nonce xxx…xxx1. The record key
produced for both records will be the same, because it clobbers/ignores the
LSB.

Again, why don’t you just use AES256-OFB to produce 256-bit record key?
-- 
Regards,
Uri Blumenthal

From:  Cfrg <[email-masked]> on behalf of Shay Gueron
<[email-masked]>
Date:  Thursday, April 21, 2016 at 16:06
To:  Andy Lutomirski <[email-masked]>
Cc:  Adam Langley <[email-masked]>, Yehuda Lindell
<[email-masked]>, CFRG <[email-masked]>, Adam Langley
<[email-masked]>
Subject:  Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant
Authenticated Encryption" as a CFRG document ---- Some clarifications

---

From: Adam Langley <[email-masked]>
Date: Thu, 21 Apr 2016 13:28:08 -0700

> produced for both records will be the same, because it clobbers/ignores the

That is what I understood when I wrote those words. I might have
misunderstood Shay however!

This is the reason that the Security Considerations section mentions
that it's only safe to repeat an nonce 2^31 (rather than 2^32) times
with the AES-256 version.

Cheers

AGL

---

From: "Gueron, Shay" <[email-masked]>
Date: Thu, 21 Apr 2016 20:38:33 +0000

OK, I did not understand what Andy meant...

Indeed, for deriving the encryption in the 256-bit key case, the nonce 
has effectively 127 bits.

Repeating this (127-bit) nonce degenerates the encryption to using the 
same 256-bit key.

Still, the CTR mode encryption that follows, is not going to leak 
information unless the same message (with the same 127-bit IV) is 
encrypted. In such, the equality of the message is revelaed. But this is 
the nature of the deterministic processing, and this is what the nonce 
misuse resistance provides.

Of course, there is another consideration: if on top of all this, there 
is a collision in the 96 bits of the CTR mode IV, which is derived from 
the POLYAVAL universal hash (and the nonce). This is addressed in the 
security considerations section.
(as promised, exact bounds will follow in a paper that we will soon 
release)

Regards, Shay

------ Original Message ------
From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
To: "Shay Gueron" <[email-masked]>; "Andy Lutomirski" 
<[email-masked]>
Cc: "Adam Langley" <[email-masked]>; "Yehuda Lindell" 
<[email-masked]>; "[email-masked]" <[email-masked]>; "Adam 
Langley" <[email-masked]>
Sent: 4/21/2016 11:11:33 PM
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant 
Authenticated Encryption" as a CFRG document ---- Some clarifications

>I’m afraid Andy is correct. Say one record has its nonce xxxx…xxxx0 
>(127 bits plus 0), and another record has its nonce xxx…xxx1. The 
>record key produced for both records will be the same, because it 
>clobbers/ignores the LSB.
>

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 26 Apr 2016 09:44:24 -0700

On Thu, Apr 21, 2016 at 1:38 PM, Gueron, Shay <[email-masked]> wrote:
> Indeed, for deriving the encryption in the 256-bit key case, the nonce has
> effectively 127 bits.
>
> Repeating this (127-bit) nonce degenerates the encryption to using the same
> 256-bit key.
>
> information unless the same message (with the same 127-bit IV) is encrypted.
> In such, the equality of the message is revelaed. But this is the nature of
> the deterministic processing, and this is what the nonce misuse resistance
> provides.

Then you're violating one of the basic properties that even
non-nonce-misuse-resistent schemes provide: when you encrypt two
messages using different nonces, you shouldn't reveal whether they're
the same message.  As proposed, this mode does *not* have that
property.

This isn't a probabilistic thing.  A program that uses a simple
counter as their nonce in the appropriate endianness will trigger this
for every single pair of consecutive messages.  That's a 100%
probability of information leak for a session that contains a mere 2^1
messages.

You can paper over it by saying that, in 256-bit AES mode, the nonce
is only 127 bits, but that's weird and someone's going to use it
wrong.  Given that fixing this is trivial, why not just fix it?  This
is, after all,
a mode designed to be misuse-resistant, and this design decision makes it very
easy to misuse.

--Andy

---

From: Adam Langley <[email-masked]>
Date: Tue, 26 Apr 2016 10:25:01 -0700

> the same message.  As proposed, this mode does *not* have that

Although the record encryption key may be the same for pairs of
messages in AES-256 mode, that doesn't lead to identical plaintexts
having identical ciphertexts because the nonce is xored into S_s,
which ends up controlling the tag and thus the initial counter.

Still, Shay and I chatted and the idea to XOR the nonce with 1 for the
second half seems like it might be cleaner. I believe that Shay and
Yehuda are working on updating the analysis and may incorporate this
change.

Cheers

AGL

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 26 Apr 2016 11:07:23 -0700

> On Apr 26, 2016, at 10:25 AM, Adam Langley <[email-masked]> wrote:
> 

While it probably wouldn’t lead to an attack, I have some hesitation about encrypting the first packet with (K0,K1) and the second packet with (K1,K0).

Too bad AES predates tweakable ciphers.  Then the solution would be easy.

— Mike

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 26 Apr 2016 18:22:16 +0000

>While it probably wouldn’t lead to an attack, I have some hesitation
>about encrypting the first packet with (K0,K1) and the second packet with
>(K1,K0).

AES seems to have resistance to related key attacks. I find this issue
(aka [K0, K1] vs [K1, K0]) a far lower risk that having the same key used
for both messages.

Of course I still think that OFB for record key generation is better than
either this or the original method. ;)

>Too bad AES predates tweakable ciphers.  Then the solution would be easy.

:-)

But it doesn’t, and it isn’t. ;)

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 26 Apr 2016 19:25:19 +0000

Date: Tue, 26 Apr 2016 18:22:16 +0000
   From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>

   On 4/26/16, 14:07 , "Cfrg on behalf of Mike Hamburg"
   <[email-masked] on behalf of [email-masked]> wrote:

   >While it probably wouldn't lead to an attack, I have some hesitation

Alex Biryukov and Dmitry Khovratovich, `Related-key Cryptanalysis of
the Full AES-192 and AES-256', <https://eprint.iacr.org/2009/317>.

Maybe the particular attacks discussed in that paper don't work
directly in this scenario (they almost certainly don't, since they
work with four keys), but `AES seems to have resistance to related key
attacks' is hardly the case.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 26 Apr 2016 19:47:21 +0000

>the Full AES-192 and AES-256', <https://eprint.iacr.org/2009/317>.

Sure, with 2^{99.5} time and data complexity (to be precise, $2^{77.5}$
time and $2^{99.5}$ data). Not my immediate threat risk, what about you?

At least, the authors seem to think so (section 7):

	However, both our attacks are still mainly of theoretical
	interest and do not present a threat to practical applications
	using AES.

 

Not to mention that the record keys are produced by a PRP (yes, I call AES
this in this context :), so any meaningful relation between the two
resulting 256-bit record keys is that $K_{1} = K_{2}^{‘}$ and vs. versa.

>attacks' is hardly the case.

“MAYBE . . . don’t work DIRECTLY”?

P.S. AES192 seems to fare much better, with the time complexity $2^{176}$
and the data complexity $2^{123}$. I might prefer better numbers, but both
count as “resistant” in my book. ;)