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

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 28 Mar 2016 14:34:53 +0000

Dear CFRG,

Shay, Adam and Yehuda have asked the CFRG chairs whether their draft for
AES-GCM-SIV can be adopted as a CFRG document. We are minded to do so, but
first wanted to canvass members of the group for their opinions on taking
this step.

We are aware of the on-going CAESAR competition for AEAD schemes.
AES-GCM-SIV is not a CAESAR candidate. CFRG adopting this document should
not be interpreted as competing with or pre-empting the results of that
very valuable activity. Indeed, once CAESAR is complete, we hope that some
or all of the competition winners will end up being turned into RFCs under
the auspices of CFRG.

Regards,

Kenny (for the chairs)

On 06/03/2016 03:50, "Cfrg on behalf of Shay Gueron"
<[email-masked] on behalf of [email-masked]> wrote:

>Hello CFRG,
>
> 
>We would like to draw your attention to our new submission draft entitled
>“AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption”. Posted on
>https://www.ietf.org/internet-drafts/draft-gueron-gcmsiv-00.txt
> 
>The submission specifies two authenticated encryption algorithms that are
>nonce misuse-resistant. Their performance is expected to be roughly on
>par with AES-GCM,
> when run on modern processors that have AES instructions.
> 
>Security and performance analysis can be found in S. Gueron and Y.
>Lindell. GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at
>Under One Cycle
> per Byte. In 22nd ACM CCS, pages 109-119, 2015.
> 
>We hope that the CFRG will take this up as a working-group item.
> 
>Thank you,
>
> 
>Shay Gueron, Adam Langley, Yehuda Lindell
> 
>
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 28 Mar 2016 18:22:50 +0300

> On 28 Mar 2016, at 5:34 PM, Paterson, Kenny <[email-masked]> wrote:
> 
> Dear CFRG,
> 

+1: definitely take this step.

That said, I think the current document is missing a convincing motivation. The security considerations section talks about randomly choosing nonces and limits the number of such nonces that can safely be randomly generated to 2^32. This makes sense, but for most uses (TLS, IPsec, SSH) we can use a non-random nonces (a counter; an LFSR if you want to get fancy; DES-encrypting a counter if you want to get really fancy). I’d be happier if there was an example where a counter is not practical. 

Yoav

---

From: Shay Gueron <[email-masked]>
Date: Mon, 28 Mar 2016 18:41:43 +0300

Hi Yoav,

The number of nonces is not limited by 2^32.

What is limited by this number is the maximum number of blocks per nonce in
a single message. Exactly as CTR (and AES-GCM), and for the same reason:
there are only 32 bits in a 128-bit block, that are left to increment  a
counter.

On the other hand, since a new key is derived each time from the IV (and
the encryption key), GCM-SIV can be used, with a given key, practically an
"unlimited" number of times.

This details is different from the CCS paper and the (later) proposed spec.

Thanks, Shay

2016-03-28 18:22 GMT+03:00 Yoav Nir <[email-masked]>:

> That said, I think the current document is missing a convincing
> motivation. The security considerations section talks about randomly
> choosing nonces and limits the number of such nonces that can safely be
> randomly generated to 2^32. This makes sense, but for most uses (TLS,
> IPsec, SSH) we can use a non-random nonces (a counter; an LFSR if you want
> to get fancy; DES-encrypting a counter if you want to get really fancy).
> I’d be happier if there was an example where a counter is not practical.
>
> Yoav
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Greg Hudson <[email-masked]>
Date: Mon, 28 Mar 2016 11:48:09 -0400

> That said, I think the current document is missing a convincing motivation. The security considerations section talks about randomly choosing nonces and limits the number of such nonces that can sa…

Kerberos might work as an example.  RFC 3961 encryption types must
address long-lived keys used by multiple processes without
coordination--for instance, multiple KDCs in the same realm will encrypt
tickets using the same server keys.

---

From: David McGrew <[email-masked]>
Date: Mon, 28 Mar 2016 11:50:53 -0400

Hi Kenny,

> On Mar 28, 2016, at 10:34 AM, Paterson, Kenny <[email-masked]> wrote:
> 
> Dear CFRG,
> 

I support taking on this draft as an RG item, and I offer to review it and offer some detailed comments.  

best

David

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 28 Mar 2016 09:37:52 -0700 (PDT)

> first wanted to canvass members of the group for their opinions on taking

  I am in favor of adoption of this draft as a CFRG document.

  regards,

  Dan.

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 28 Mar 2016 10:41:41 -0700

Introducing a new AEAD scheme outside of the CAESAR process devalues CAESAR, ultimately reducing CAESAR's importance. It would have been much better for AES-GCM-SIV to be introduced as part of the CAESAR process and have it win mindshare based on its merits rather than its "first mover" status. By advancing this RFC, we likely entrench AES-GCM-SIV to every other CAESAR candidate's detriment.

Might it be better to integrate this new proposal with CAESAR somehow? Perhaps the CAESAR committee could invite AES-GCM-SIV to become an official candidate, and then all the CAESAR candidates could be considered by CAESAR and CFRG on level terms? Or barring CAESAR allowing AES-GCM-SIV into the competition late, CFRG could delay consideration of the AES-GCM-SIV RFC until CAESAR recommends its portfolio. We don't want to bless too many AEAD schemes. If AES-GCM-SIV is not best-in-class, we don't want to recommend it at all, but we won't know that until CAESAR has finished its work.

The end result of delaying the AES-GCM-SIV RFC would likely be a smaller number of better AEAD schemes being recommended: either an improved AES-GCM-SIV RFC evolves because it goes through a more rigorous vetting process and gets improved along the way, or it doesn't get recommended and something better does.

Ted Krovetz
(author of HS1-SIV CAESAR submission)

> On Mar 28, 2016, at 7:34 AM, Paterson, Kenny <[email-masked]> wrote:
> 
> Dear CFRG,
>

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 28 Mar 2016 17:46:09 +0000

I'd like to understand why this didn't end up in CAESAR?  If it's just schedule (we thought of it too late), okay.  If it's more along the lines of a frank and open discussion that doesn't go well on public archives mailing lists, oh well, but I still want to know.

---

From: "Grigory Marshalko" <[email-masked]>
Date: Mon, 28 Mar 2016 17:59:04 +0000

Having in mind discussions on [saag] possible BCP on public review being needed for standards-track crypto
should we need an independent cryptoanalysis for this submission? This, of cause, is not a standards-track, but still.

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru
28 марта 2016 г., 20:46, "Salz, Rich" <[email-masked]> написал:
> I'd like to understand why this didn't end up in CAESAR? If it's just schedule (we thought of it
> too late), okay. If it's more along the lines of a frank and open discussion that doesn't go well
> on public archives mailing lists, oh well, but I still want to know.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 28 Mar 2016 18:11:13 +0000

Some good points, some not so good - like "the first mover status”. In any
case, I’d much prefer to have something useful (that can benefit from
AESNI) *now*, rather than waiting for CAESAR to complete.

CAESAR has been going on forever, and will go on for uncertain (two?)
number of years yet. I’d much rather explore AES-GCM-SIV in the meanwhile.

If you know of better alternatives, by all means feel free to (a) submit
an RFC defining them, and (b) explain where they are better (and worse)
than other modes.
-- 
Regards,
Uri Blumenthal

On 3/28/16, 13:41 , "Cfrg on behalf of Ted Krovetz" <[email-masked]
on behalf of [email-masked]> wrote:

>Introducing a new AEAD scheme outside of the CAESAR process devalues
>CAESAR, ultimately reducing CAESAR's importance. It would have been much
>better for AES-GCM-SIV to be introduced as part of the CAESAR process and
>have it win mindshare based on its merits rather than its "first mover"
>status. By advancing this RFC, we likely entrench AES-GCM-SIV to every
>other CAESAR candidate's detriment.
>
>Might it be better to integrate this new proposal with CAESAR somehow?
>Perhaps the CAESAR committee could invite AES-GCM-SIV to become an
>official candidate, and then all the CAESAR candidates could be
>considered by CAESAR and CFRG on level terms? Or barring CAESAR allowing
>AES-GCM-SIV into the competition late, CFRG could delay consideration of
>the AES-GCM-SIV RFC until CAESAR recommends its portfolio. We don't want
>to bless too many AEAD schemes. If AES-GCM-SIV is not best-in-class, we
>don't want to recommend it at all, but we won't know that until CAESAR
>has finished its work.
>
>The end result of delaying the AES-GCM-SIV RFC would likely be a smaller
>number of better AEAD schemes being recommended: either an improved
>AES-GCM-SIV RFC evolves because it goes through a more rigorous vetting
>process and gets improved along the way, or it doesn't get recommended
>and something better does.
>
>Ted Krovetz

---

From: Yoav Nir <[email-masked]>
Date: Mon, 28 Mar 2016 22:45:14 +0300

Hi.

> On 28 Mar 2016, at 6:41 PM, Shay Gueron <[email-masked]> wrote:
> 
> Hi Yoav, 
> 

No. It’s limited by 2^96

> What is limited by this number is the maximum number of blocks per nonce in a single message.

We’re talking about a different part of the Security Considerations section:
                                                      Since the nonce
   size for GCM is only 12 bytes, NIST set a limit [GCM] of 2^32
   encryptions before the probability of duplicate nonces becomes too
   high.
And this limitation makes sense only if the nonces are chosen randomly. Otherwise we can generate 2^96 unique nonces with no problem. It does make sense if there are multiple senders and no sane way to partition the nonce space.

Yoav

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 28 Mar 2016 20:59:40 +0000

Hi Rich,

We asked the proposers this. They said it was not ready in time for the
CAESAR competition (so, yes, it's a schedule issue).

Cheers

Kenny 

On 28/03/2016 18:46, "Cfrg on behalf of Salz, Rich" <[email-masked]
on behalf of [email-masked]> wrote:

>I'd like to understand why this didn't end up in CAESAR?  If it's just
>schedule (we thought of it too late), okay.  If it's more along the lines
>of a frank and open discussion that doesn't go well on public archives
>mailing lists, oh well, but I still want to know.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 28 Mar 2016 21:00:42 +0000

Dear Grigory,

The proposal comes with an associated research paper that contains a
formal security analysis of the scheme. I assume this is the kind of
analysis you'd like to see?

It would be great if people were to check the proofs' details, if we adopt
it as a CFRG document.

Regards,

Kenny 

On 28/03/2016 18:59, "Cfrg on behalf of Grigory Marshalko"
<[email-masked] on behalf of [email-masked]> wrote:

>should we need an independent cryptoanalysis for this submission? This,
>of cause, is not a standards-track, but still.
>
>
>Regards,
>Grigory Marshalko,
>expert,
>>schedule (we thought of it

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 28 Mar 2016 21:34:47 +0000

Hi Ted,

Thanks for sharing your thoughts on these delicate issues.

I can't speak for what those running the CASEAR competition might or might
not want to do regarding inclusion of AES-GCM-SIV in the competition, nor
what the proposers of AES-GCM-SIV might think of that option. The relevant
people are generally paying attention to this list; we'll just have to let
them put their heads together if they choose to do so.

I can, however, report that the research paper that accompanies the
proposal (see https://eprint.iacr.org/2015/102 for the free version) does
contain an analysis comparing AES-GCM-SIV to the relevant group of CAESAR
candidates - see pages 4 and 5. This might help to start answer your
question of whether AES-GCM-SIV is best-in-class, as you put it, where the
class is that of nonce-misuse-resistant AEADs.

I don't want to pre-judge that issue, but it looks to me like it offers
better performance than the comparable CAESAR candidates, at least on
hardware with support for AES-NI and PCLMULQDQ instructions. What's your
thinking on that?

If that's correct, then I think it would be unfortunate for us (CFRG) to
wait another two years to turn this scheme into an RFC if it's already
better than all the other schemes in the same class in the competition for
a particularly relevant hardware profile.

That need not rule out CFRG adoption of other competition winners in the
same class but targeting, for example, constrained environments, after the
competition has completed.

Regards,

Kenny

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 28 Mar 2016 15:46:24 -0700

> hardware with support for AES-NI and PCLMULQDQ instructions. What's your

We've seen AEZ achieve peak performance of 0.63 cpu cycles per byte on Intel Skylake and 1.3 cpu cycles per byte on Apple's A9. And because it doesn't use GF(2^128) operations, AEZ is likely much faster than AES-GCM-SIV on other architectures.

I don't want to make any claims of superiority, I just don't understand what the rush is. Once AES-GCM-SIV is an RFC and starts appearing in protocols, it will be very hard to displace, even if it's not the best choice.

Uri suggested that other proposed AEAD schemes interested in short-circuiting the CAESAR process could submit proposed RFCs to CFRG. Is that what you'd like?

-Ted

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 28 Mar 2016 23:03:35 +0000

I want a good fast nonce misuse-resistant scheme, and not in two years (with no guarantees of delivery, BTW) but now.

Yes if other competitors want to submit their proposals as RFCS, IMHO it would be fine.

Sent from my BlackBerry 10 smartphone on the Verizon Wireless 4G LTE network.
  Original Message
From: Ted Krovetz
Sent: Monday, March 28, 2016 18:46
To: [email-masked]
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document

-Ted

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 28 Mar 2016 17:03:56 -0700

> number of years yet. I’d much rather explore AES-GCM-SIV in the meanwhile.

+1. CAESAR has been dragging on for quite some time, and AES-GCM-SIV is
"good enough"

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Tue, 29 Mar 2016 08:54:21 +0300

On 29 Mar 2016, at 8:06 AM, Adam Langley <[email-masked]> wrote:

> On Mon, Mar 28, 2016 at 8:45 PM, Yoav Nir <[email-masked] <mailto:[email-masked]>> wrote:
> You're correct that the limit of 2^32 only applies when the nonces are chosen at random—the text could be clearer there.
> 
> For situations were a counter can be maintained (i.e. transport security) then I don't believe that SIV modes are called for. AES-GCM works fine.
> 
> However, a consider a situation where a number of machines are encrypting and decrypting blobs of data because the data is stored on an untrusted storage system. A scheme for distributing fractions of the nonce space to the servers is possible, but complex and fragile. Generating the nonces at random is desirable, but 2^32 encryptions just isn't very many. In this case I think AES-GCM-SIV is quite attractive.
> 
> (There are schemes like XChaCha20-Poly1305, which has a 192-bit nonce but, while fast, many CPUs have dedicated hardware for AES-GCM and that's a hard advantage for alternatives to overcome.)
> 

Ah, that’s what I figured. So it’s useful for cases where you have multiple encryptors, or even a single encryptor over a long time and multiple overwrites. So yeah, disk encryption makes sense as do some multicast VPN scenarios.

Thanks

Yoav

---

From: "Paterson, Kenny" <[email-masked]>
Date: Tue, 29 Mar 2016 10:05:30 +0000

Dear Ted,

On 28/03/2016 23:46, "Cfrg on behalf of Ted Krovetz"
<[email-masked] on behalf of [email-masked]> wrote:

>Uri suggested that other proposed AEAD schemes interested in
>short-circuiting the CAESAR process could submit proposed RFCs to CFRG.
>Is that what you'd like?

It's not really a question of what I'd like, or what the chairs would
like. It's a question of what CFRG, based on consensus if possible and
rough consensus if not, decides collectively to do.

My personal view, for what it's worth, is that it would be better to wait
until CAESAR is complete and then look in the round at the portfolio that
it has produced before adopting any of the CAESAR candidates.

Cheers,

Kenny

---

From: Thomas Peyrin <[email-masked]>
Date: Tue, 29 Mar 2016 20:45:11 +0800

I also think it is wiser to wait for the CAESAR outcome. Probably most of
the cryptanalysis time in the last two years was spent on analysing CAESAR
candidates, and not AES-GCM-SIV. If really a misuse-resistant candidate is
absolutely required now, I would say one better go for any of the
misuse-resistant schemes from the 2nd round.

Cheers,

Thomas (full disclosure: I am co-designer of some CAESAR candidates)

---

From: "Paterson, Kenny" <[email-masked]>
Date: Tue, 29 Mar 2016 12:49:46 +0000

Thomas,

Just to avoid any confusion: my personal preference as expressed below
pertained only to what to do concerning CAESAR candidates, not
AES-GCM-SIV. (I was answering Ted's specific question about whether I
would like CAESAR candidates to be submitted to CFRG now.)

Regards

Kenny

On 29/03/2016 13:45, "Thomas Peyrin" <[email-masked]> wrote:

>the cryptanalysis time in the last two years was spent on analysing
>CAESAR candidates, and not AES-GCM-SIV. If really a misuse-resistant
>candidate is absolutely required
> now, I would say one better go for any of the misuse-resistant schemes
>from the 2nd round.
>
>
>Cheers,
>
>

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 30 Mar 2016 12:22:14 -0700 (PDT)

Hi Shay,

  Would you agree that AEAD_AES_256_GCM_SIV provides no more
security than AEAD_AES_128_GCM_SIV? I say this because the
authentication key is 128-bits regardless (and authentication
is arguably more important than encryption) and when using a
256-bit encryption key the "record encryption key" can only
take on 2^128 values.

  If there a benefit to the 256-bit variant over the 128-bit
one? I may be misunderstanding something.

  regards,

  Dan.

On Mon, March 28, 2016 8:41 am, Shay Gueron wrote:
>> > On 28 Mar 2016, at 5:34 PM, Paterson, Kenny
>> <[email-masked]>
>> wrote:
>> >
>> > Dear CFRG,
>> >

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 30 Mar 2016 18:11:00 -0700

On Wed, Mar 30, 2016 at 12:22 PM, Dan Harkins <[email-masked]> wrote:

> authentication key is 128-bits regardless

I disagree with this. 128-bits of symmetric security is fine today. The
threats where you might want 256-bit encryption are things like
hypothetical future quantum computers which are able to use Grover's
algorithm.

Encryption needs to stand the test of time. Authentication has less
burdensome demands. If it's possible to pull off an online chosen
ciphertext attack after the advent of quantum computers which can use
Grover's algorithm to break 128-bit crypto (10+ years in the future
maybe?), the story might be different, but for long-term confidentiality of
ciphertexts I think a larger key size for a symmetric cipher is more
important.

The same argument can be applied to digital signatures and quantum
cryptography: they matter less than encryption, because we can resign data
if a quantum attack seems imminent, but if a quantum attacker already has
access to ciphertexts there's nothing we can do.

-- 
Tony Arcieri