Subject: [Cfrg] Eliminate the State! Re: Nonce Misuse Resistant AEAD

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Fri, 10 Apr 2015 16:20:38 +0000

Folks:

I'd like to emphasize that stateful nonces turn state-management
failures into security failures, and *state-management failures are
ubiquitous*.

Nobody has yet figured out how to get deployed, Internet-connected
computers to count from one to a billion without forgetting where they
were and double-counting. This is demonstrated by frequent observed
failures in the wild *even in the absence of malicious intervention*.

I'd like to put forward several separable arguments so that even if
you disagree with me about whether state-management is a hard problem,
you'll still agree with me on the other points:

1. State-management is a hard problem. Nobody has demonstrated secure
state-management at scale in the wild, to my knowledge.

2. There are two basically ways to manage your need for non-repeating
values in a crypto protocol: stateful or random.

3. Given a sufficiently large nonce, random works great (see AGL's
comment on this thread).

4. If your crypto protocol has too small of a nonce for the random
approach, you're requiring implementors to use the stateful approach,
making the practical security of your crypto protocol dependent on
secure state-management.

My recommendations:

1. Make every nonce big enough to allow the random-nonce approach.

2. Teach implementors to use the random approach to generating nonces.

By the way, this same argument is why I think stateful hash-based
signature schemes
(https://tools.ietf.org/html/draft-mcgrew-hash-sigs-02) are a bad idea
that should not be recommended and stateless hash-based signature
schemes (http://sphincs.cr.yp.to/) are a good idea.

Regards,

Zooko

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 10 Apr 2015 11:48:07 -0700

> 2. Teach implementors to use the random approach to generating nonces.

I would argue that this should be weakened a little bit.  For things
like the TLS record layer, there's a good sequence number to use as a
nonce, so I think that the stateful approach is better.

Otherwise I tend to agree with you.

--Andy

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

-- 
Andy Lutomirski
AMA Capital Management, LLC

---

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

Zooko:

I understand your point.  This is a problem that we should solve, but it does not mean that every algorithm implementation that requires state is insecure.

IEEE 802.11i does not have this problem when using AES-CCM because a new connection with a new key is established whenever the connection is lost.

Russ