Subject: [Cfrg] Nonce Misuse Resistant AEAD

From: Paul Lambert <[email-masked]>
Date: Thu, 9 Apr 2015 03:54:40 -0700

In an ad hoc communication topology, the use of stream ciphers for
encryption is problematic.  Nonce/key uniqueness must be maintained for
each pair-wise session.  The maintenance of the nonces and keys becomes a
scaling issue when the networks are large.  In emerging peer-to-peer
wireless protocols there is a potential to have hundreds to thousands of
possible peers in a crowed environment.  The currently prescribed
encryption algorithms (AES-CCM and AES-GCM) are not well suited for these
new environments.  Nonce uniqueness requires maintaining state and this
may not be possible for limited devices in dense environments.  Nonce
state of a device may also be lost (reset, restart of application, etc.)

Are there any recommendations for a 'nonce misuse resistant AEAD¹
algorithm from this group?

AES-SIV is one possibility.  Are there others?

Paul

---

From: Philipp Jovanovic <[email-masked]>
Date: Thu, 9 Apr 2015 14:58:03 +0200

> AES-SIV is one possibility.  Are there others?

Nonce misuse resistant AEAD is a very active research field currently. Beyond AES-SIV, there are quite a few CAESAR candidates which provide this property, such as AEZ, HS1-SIV, or Minalpher. For an overview on the nonce misuse resistant CAESAR designs you can check out for example https://eprint.iacr.org/2014/792.pdf <https://eprint.iacr.org/2014/792.pdf> (chapter 5) or https://aezoo.compute.dtu.dk/doku.php <https://aezoo.compute.dtu.dk/doku.php>. Note that the CAESAR-ciphers are still rather new and it will take some more time to gather further analysis on those algorithms.

There is also an active discussion on robust online AE on the crypto-competitions mailing list that might be interesting for you: https://groups.google.com/forum/#!topic/crypto-competitions/g4HapF-hskc <https://groups.google.com/forum/#!topic/crypto-competitions/g4HapF-hskc>

All the best,
Philipp

---

From: Russ Housley <[email-masked]>
Date: Thu, 9 Apr 2015 09:58:21 -0400

Paul:

Is the concern the space needed to keep the state with the key?

You seem to have storage for hundreds or thousands of keys, but you cannot keep 64 bits of state with each of them?

Russ

---

From: Adam Langley <[email-masked]>
Date: Thu, 9 Apr 2015 07:30:11 -0700

> algorithm from this group?

In addition to nonce-misuse resistant algorithms, it's also possible
to have a large enough nonce such that it can be chosen randomly with
acceptable security properties. (Assuming that your devices have
access to an RNG, which can be problem in small devices, although some
small ARM chips come with a hardware RNG these days.)

For example, crypto_secretbox_xsalsa20poly1305[1] from NaCl has a
192-bit nonce, although you don't have to use all of it if you don't
need to.

[1] http://nacl.cr.yp.to/secretbox.html

Cheers

AGL

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 10 Apr 2015 01:15:11 -0700 (PDT)

On Thu, April 9, 2015 7:30 am, Adam Langley wrote:
>> Are there any recommendations for a 'nonce misuse resistant AEADÂ¹

  Well strictly speaking GCM can use a larger nonce too. In fact, [2] talks
about using 160 bit nonces with GCM in it's "RBG" nonce construction and
it says 1 <= len(IV) <= 2^64 -1, which can be considerably larger than
192 (yes it gets reduced with GHASH but that's an internal operation). But
using a larger nonce doesn't really address the problem, it just kind of
dilutes it, while also increasing the amount of state that has to be
managed. AES is not as trendy as salsa and poly1305 but [3] is really
misuse-resistant, not just "less fragile".

> [1] http://nacl.cr.yp.to/secretbox.html

  [2] http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
  [3] https://tools.ietf.org/html/rfc5297

  regards,

  Dan.

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

---

From: Paul Lambert <[email-masked]>
Date: Fri, 10 Apr 2015 08:47:49 -0700

Nonce misuse resistant AEAD is a very active research field currently. Beyond AES-SIV, there are quite a few CAESAR candidates which provide this property, such as AEZ, HS1-SIV, or Minalpher. For an overview on the nonce misuse resistant CAESAR designs you can check out for example https://eprint.iacr.org/2014/792.pdf (chapter 5)
Thank you, very nice summary.   It’s to see that the summary has quite a few candidates with 'Nonce-MR’.

or https://aezoo.compute.dtu.dk/doku.php. Note that the CAESAR-ciphers are still rather new and it will take some more time to gather further analysis on those algorithms.
Yes … there a long baking time required for the selection process (2017 for CEASER) – hence my posting.  My application in another forum needs a solution in the next 6 months.

There is also an active discussion on robust online AE on the crypto-competitions mailing list that might be interesting for you: https://groups.google.com/forum/#!topic/crypto-competitions/g4HapF-hskc
Thank you …. I’ll start to lurk …

Regards,

Paul

All the best,
Philipp

---

From: Paul Lambert <[email-masked]>
Date: Fri, 10 Apr 2015 08:59:27 -0700

Hi Russ,

>Is the concern the space needed to keep the state with the key?
Concerns are:
 - key and nonce space. Some concern, over a long key period in crowds
   this could be 100s to 1000s and not viable for constrained devices
 - Rest issues.  Big concern, If a device loses power and forgets it’s
state
   then sequential nonces (e.g. AES-CCMP in 802.11) break if there’s no
   new pairwise key negotiated.
 - Multicast nonce coordination.  Big problem. N^2 scaling per some
   Current solutions (each transmitter must exchange it’s own group key
   With all others).  On loss of state it must contact all N again.
   Implicit per device keys have been used, but state loss can still be
   a problem and also require per device state storage.
   
>
>You seem to have storage for hundreds or thousands of keys, but
>you cannot keep 64 bits of state with each of them?
Per above … no, I’m looking for methods that do not require O(N)
state storage or O(N^2) protocol and are resistant to state loss.

Paul

---

From: Paul Lambert <[email-masked]>
Date: Fri, 10 Apr 2015 09:10:11 -0700

>small ARM chips come with a hardware RNG these days.)
Nice, many thanks for the idea.

>[1] http://nacl.cr.yp.to/secretbox.html
A good technique to reuse existing nonce sensitive algorithms.

So … pre-2017 viable constructs might include:
 - AES-SIV
 - AES-CCM-RN (128 bit random nonce)
 - Salsa or ChaCha20Poly1305-RN

Is there value in or any current definition of a ChaCha20Poly1305-SIV?

Regards,

Paul

---

From: Philipp Jovanovic <[email-masked]>
Date: Fri, 10 Apr 2015 18:24:26 +0200

> Is there value in or any current definition of a ChaCha20Poly1305-SIV?

I am not aware of a specification of ChaCha20-Poly1305-SIV. The closest you might find out there is HS1-SIV [1] from CAESAR which uses ChaCha20 internally but HS1-Hash instead of Poly1305.

All the best,
Philipp

[1] http://competitions.cr.yp.to/round1/hs1sivv1.pdf <http://competitions.cr.yp.to/round1/hs1sivv1.pdf>

---

From: Adam Langley <[email-masked]>
Date: Fri, 10 Apr 2015 09:43:14 -0700

On Fri, Apr 10, 2015 at 1:15 AM, Dan Harkins <[email-masked]> wrote:
> 192 (yes it gets reduced with GHASH but that's an internal operation).

I don't think that the fact that the larger nonce gets hashed down to
96-bits can be abstracted away and considered an internal operation.
The hashing down means that larger nonces are effectively random,
96-bit nonces.

For example, in SP-800-38D that you referenced, section 8.3 requires a
limit of 2^32 invocations whenever the IV is not 96-bits (i.e.
whenever the hashing applies), even if it's a counter, because of
this.

In contrast, the larger nonce in crypto_secretbox_xsalsa20poly1305 is
used to diversify both the key and the nonce[1], leading to a larger
"effective" nonce space. The same cascade could also be applied to
AES-GCM to create an AES mode with a large "effective" nonce space. I
would welcome a specification of such a construction because AES-GCM
enjoys good hardware support and the 96-bit IV is a problem that has
arisen in projects that I'm aware of.

[1] http://cr.yp.to/snuffle/xsalsa-20081128.pdf

> But

I think that "diluting" the problem is acceptable so long as the
dilution is sufficient. We deal with security levels all the time in
cryptography and, if the probability of a collision can be reduced to
an acceptable degree then I don't think it's qualitatively different
than, say, the probability of an attacker brute-forcing a symmetric
key.

But certainly sending the large nonces around and generating them is
overhead and it's not a misuse-resistant mode. An RNG failure is much
worse for a large-nonce scheme than SIV.

Cheers

AGL

---

From: Paul Lambert <[email-masked]>
Date: Fri, 10 Apr 2015 10:00:40 -0700

For better context on the problem space,
here’s one set of possible use cases (you tube video):
http://www.wi-fi.org/discover-wi-fi/wi-fi-aware

> - Reset issues.  Big concern, If a device loses power and
>  forgets it’s state then sequential nonces
>  (e.g. AES-CCMP in 802.11) break if there’s no new pairwise
>  key negotiated.
   - Lightweight setup is very important.
     Some existing protocols require 4 messages to be exchanged
     (e.g. IEEE 802.11 4-way handshake) before sending encrypted
     data to establish key/nonce uniqueness.
     IEEE 802.11 IBSS requires N*(N-1)*8 messages for NxN
     Connectivity with multicast

Paul

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 10 Apr 2015 16:58:52 +0000

>The hashing down means that larger nonces are effectively random,

True. But what are the cryptographic implications of that fact?

>worse for a large-nonce scheme than SIV.

Hardware RNG failure is not as common, AFAIK.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 10 Apr 2015 10:45:02 -0700

> True. But what are the cryptographic implications of that fact?

That a system using a counter to generate long nonces for GCM is going to
collide much sooner then you think.

> Hardware RNG failure is not as common, AFAIK.

Tell that to the Taiwanese goverment. They had to spend millions fixing a
flawed deployment of smart cards because of RNG failures.

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 10 Apr 2015 11:42:12 -0700 (PDT)

> whenever the hashing applies), even if it's a counter, because of

  For the record, it's hashed down to 128 bits (GHASH does a reduction
modulo a polynomial of degree 128) and is used as the initial counter
block for AES-CTR, but your point is correct and well taken.

  thanks,

  Dan.

---

From: Russ Housley <[email-masked]>
Date: Fri, 10 Apr 2015 15:01:16 -0400

> state storage or O(N^2) protocol and are resistant to state loss.

Thanks for the additional details.

Russ

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 10 Apr 2015 19:12:52 +0000

> collide much sooner then you think.

Yes, but again, what is the cryptographic implication of this in our
context? Birthday paradox space of 2^48?

> flawed deployment of smart cards because of RNG failures.

I’ll make sure of that, the next time I’m invited to dine with them. :-)
Still, how many HSM devices were pulled because of RNG failures?
I do take your point, though.

---

From: Jonathan Trostle <[email-masked]>
Date: Sun, 12 Apr 2015 19:32:03 -0700

Also CMCC which is another nonce-MR Caesar candidate. CMCC allows less length expansion than SIV.

Jonathan

--------------------------------------------
On Thu, 4/9/15, Philipp Jovanovic <[email-masked]> wrote:

 Subject: Re: [Cfrg] Nonce Misuse Resistant AEAD
 To: "Paul Lambert" <[email-masked]>
 Cc: "[email-masked]" <[email-masked]>
 Date: Thursday, April 9, 2015, 5:58 AM

 Are there any recommendations
 for a 'nonce misuse resistant AEAD¹
 algorithm from this group?
 
 AES-SIV is one possibility.  Are
 there others?
 
 Nonce misuse
 resistant AEAD is a very active research field currently.
 Beyond AES-SIV, there are quite a few CAESAR candidates
 which provide this property, such as AEZ, HS1-SIV, or
 Minalpher. For an overview on the nonce misuse resistant
 CAESAR designs you can check out for example https://eprint.iacr.org/2014/792.pdf (chapter
 5) or https://aezoo.compute.dtu.dk/doku.php.
 Note that the CAESAR-ciphers are still rather new and it
 will take some more time to gather further analysis on those
 algorithms.
 There is also an active
 discussion on robust online AE on the crypto-competitions
 mailing list that might be interesting for you: https://groups.google.com/forum/#!topic/crypto-competitions/g4HapF-hskc
 All the
 best,Philipp

---

From: Alex Elsayed <[email-masked]>
Date: Sun, 12 Apr 2015 23:24:20 -0700

One thing to keep in mind: There are multiple competing definitions of 
"misuse-resistant AEAD".

The strongest of these is put forward by Rogaway et. al. (present in the 
introduction of [2], and elsewhere) and states that authenticity is 
preserved even in the case of nonce reuse, no information is leaked to an 
attacker unless the tuple (nonce, AD, message) repeats, and the leakage is 
limited to the fact that the tuple repeated.

With such a construction, arbitrary-length "nonces" can be achieved simply 
by including them in the AD.

AEZ [1] implements MRAE under that definition, and in another paper Rogaway 
et. al. described [2] a further construction based on strong MRAE, called 
CHAIN, that provides much the same (security) behavior and guarantees as the 
record layer on the whole seems to intend, up to and including termination 
on a broken record - backed by crypto, not just implementation.

[1] http://eprint.iacr.org/2014/793
[2] http://eprint.iacr.org/2015/189

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Apr 2015 11:34:38 -0500

> Is the concern the space needed to keep the state with the key?

Consider Kerberos...

Kerberos has long-term symmetric keys, but Kerberos is stateless.

For confounded CTS cipher modes this works fine.  For AEAD/stream cipher
modes... it doesn't.  (The now-obsolete RC4 enctype gets around this by
deriving a sub-key for every encryption operation.)

AES-SIV[0] looks quite appealing, actually.  It'd be nicer to have such a
mode that is widely popular (like GCM and OCB).  What's the status of
SIV cryptanalysis?  Can we use it?

Other constructions using more traditional AEAD modes but wasting an
extra block on the wire (not unlike the confounder in the CTS enctypes)
and extra cipher operations (also not unlike the confounder in the CTS
enctypes) should be possible.  For example, do an ECB encryption of a
timestamp and a nonce to derive a sub-key, then use that key and a nonce
as the inputs to AES in CCM/GCM/OCB mode, prefixing the timestamp and
nonce bitstrings to the ciphertext.

> You seem to have storage for hundreds or thousands of keys, but you
> cannot keep 64 bits of state with each of them?

Exactly.  That's exactly what Kerberos does.

Even with PKINIT, and if we ever build PKCROSS, and even if we add PFS
to AP exchanges, and even if we use ECDH for keying service principals,
we'll still want the KDC and the service principals to share long-term
symmetric keys as an optimization (basically that's caching an ECDH
shared secret).

There are potentially many KDCs in a Kerberos realm, they are stateless
because the protocol is stateless (on the client and server sides of
it).  The KDCs simply can't replicate state.

Even if we partitioned a counter space across a realm's KDCs, we'd still
need enough local counter bits, and to keep state, and since that's
quite difficult we'd need quite a few bits of local counter space to
make keeping state easier (state then being a monotonic clock and a
single counter used for all operations).  All such bits would have to
end up on the wire (since services can't have this state replicated to
them from the KDC), which complicates the protocol or the enctype
specification.

We really need cipher modes that are make IV/counter/nonce reuse safe,
as they make all this complexity go away.

AES-SIV does that.  Can we use it?

[0] RFC5297.

    SIV cleverly MACs the plaintext and additional data to produce the
    integrity tag *and* the counter for encryption.  This means that
    (key, counter) reuse ~= (key, plaintex and AD) reuse, which is
    harmless.

    The downside of this is that it slows everything down, since the
    integrity protection step (S2V) has to be done first, and then the
    encryption; the plaintext and AD must be consumed twice.
    For small messages (like Kerberos Tickets) this is not that big a
    deal (especially since decryption is not serialized the way
    encryption is).

    For bulk, SIV is out (but then, for bulk data one really does want,
    and often have, session state, or sub-keys derived from larger
    nonces and timestamps).

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Apr 2015 11:55:16 -0500

> by including them in the AD.

Yes, that's one way to do it.  Then one can just have a decent local
clock, a single decent, a single persistent local counter, and a
non-persistent local counter per-CPU hardware thread.  That's still a
fair bit of state.  SIV doesn't require any state: because the (key,
plaintext and AD) is the state.  I'd prefer a cipher mode that requires
no state.

> [2] http://eprint.iacr.org/2015/189

Thanks for the links!

Nico
--

---

From: Alex Elsayed <[email-masked]>
Date: Fri, 17 Apr 2015 10:23:36 -0700

[Accidentally sent directly; reposting to list]

Nico Williams wrote:

>> With such a construction, arbitrary-length "nonces" can be achieved
>> simply by including them in the AD.
> 

Um, I think you misunderstand. AEZ was created by Rogaway (who also created 
SIV) to be _better_.

SIV's state is (key, AD, plaintext). If any part of that state changes, then 
it preserves confidentiality completely. I don't know if integrity is 
preserved unconditionally; I also don't know what confidentiality fails if 
the full tuple repeats.

AEZ's state is (key, nonce, AD, plaintext). If any part of that state 
changes, then it preserves confidentiality completely. It preserves 
intergity unconditionally. If the full tuple repeats, the *only* failure of 
confidentiality is the fact that *some unknown tuple* repeated.

In terms of what you prefer, AEZ is strictly better than SIV.

>> AEZ [1] implements MRAE under that definition, and in another paper
>> Rogaway et. al. described [2] a further construction based on strong
>> MRAE, called CHAIN, that provides much the same (security) behavior and
>> guarantees as the record layer on the whole seems to intend, up to and
>> including termination on a broken record - backed by crypto, not just
>> implementation.
>>

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Apr 2015 18:32:56 -0500

> > [2] http://eprint.iacr.org/2015/189

The second link says that we can't have the cake (online authenticated
encryption) and eat it (statelessness).  That's very good to know.

SIV is stateless, but not online.  GCM and OCB are online, but require
state (non-repeating IV).  Constructions that minimize the amount of
state to keep are possible, but obnoxious.

For protocols like TLS the statefulness requirement of GCM and OCB are
not a problem.  Ditto GSS-API.  Both keep state in a session structure.
Protocols like Kerberos, on the other hand, cannot keep state[*], so SIV
is more appropriate to them.  The obvious thing to do is to use MRAE
cipher modes where statelessness is required, and nOAE modes where
session state can be kept.

Thanks again for the links.

[*] Kerberos KRB-PRIV/SAFE/CRED PDUs are session-oriented; all othe
    Kerberos PDUs are not, and require statelessness.

---

From: Nico Williams <[email-masked]>
Date: Sun, 19 Apr 2015 14:22:49 -0500

> preserved unconditionally; I also don't know what confidentiality fails if 

Clearly if you send the same ciphertext, then that leaks some
information (namely: that you sent it more than once).  It can't leak
the key, but the context in which the retransmission happens could lead
to leaking more than just that retransmission happened.

> confidentiality is the fact that *some unknown tuple* repeated.

The latter is true of any deterministic AE.  If the AE keeps state
between encryptions, then repetitions of (key, [IV,] plaintext, AD) will
yield different ciphertexts because of the hidden state (e.g., IV
chaining), but repetitions of (key, state, [IV,] plaintext, AD)
necessarily produce the same output.

> In terms of what you prefer, AEZ is strictly better than SIV.

The second paper you linked shows that we can't have both features at
once: online _and_ stateless MRAE.

The trade-off is clear.  There are middle grounds, like confounded CBC
(or CTS) with a MAC, trading off one thing for another (in the case of
confounding: there's one more block operation and one more block of
ciphertext to pay for, and no parallelization of encryption).

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Sun, 19 Apr 2015 16:34:59 -0700

> to leaking more than just that retransmission happened.

*No* encryption scheme can ever avoid this leak. It's up to the
protocol designer to ensure that this doesn't completely break
confidentiality.

> once: online _and_ stateless MRAE.

Huh? AEZ is "stateless": it's a deterministic function of a key,
associated data, a nonce, and plaintext. This is clearly explained in
the AEZ paper http://web.cs.ucdavis.edu/~rogaway/aez/rae.pdf. Of
course, AEZ does have the problem that it's security is not reducible
directly to that of AES, but rather employs a novel cipher, so much
more cryptanalysis is required before it can be recommended.

SIV is massively complex. There are much simpler wide-block cipher
constructions, which are considerably cheaper in runtime on most
processors.
> ciphertext to pay for, and no parallelization of encryption).

Kerberos in your application  requires certain things to be true of
the cipher it uses. If those aren't true, the whole thing breaks down.
So the tradeoff doesn't actually exist, unless you are willing to
change the guaranties Kerberos makes.

Sincerely,
Watson Ladd

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Alex Elsayed <[email-masked]>
Date: Sun, 19 Apr 2015 19:52:04 -0700

Nico Williams wrote:

>> Um, I think you misunderstand. AEZ was created by Rogaway (who also
>> created SIV) to be _better_.
>> 
>> SIV's state is (key, AD, plaintext). If any part of that state changes,
>> then it preserves confidentiality completely. I don't know if integrity
>> is preserved unconditionally; I also don't know what confidentiality
>> fails if the full tuple repeats.
> 
>> intergity unconditionally. If the full tuple repeats, the *only* failure
>> of confidentiality is the fact that *some unknown tuple* repeated.
> 

It's true that that leakage is unavoidable for deterministic AE.

What is important - and why I emphasized that it is the *only* leak with AEZ 
- is that there exist (multiple) nonce-based AEAD schemes which leak _more_ 
than that or have reduced integrity guarantees in the event of nonce 
repetition.

---

From: Paul Lambert <[email-masked]>
Date: Sun, 19 Apr 2015 23:51:53 -0700

>constructions, which are considerably cheaper in runtime on most

Do you have a specific recommendation other than AES-SIV that has
sufficient published analysis for use in a standards activity
this year?

Paul

---

From: Watson Ladd <[email-masked]>
Date: Mon, 20 Apr 2015 07:28:21 -0700

> sufficient published analysis for use in a standards activity

Combine https://www.iacr.org/archive/crypto2007/46220405/46220405.pdf
with what is presented in the AEZ paper, and I think the proofs line
up. But yes, there is an absence of such things, hence CAESER.