Subject: [Acme] On the entropy of the nonce

From: [email-masked] (Michele Orrù)
Date: Wed, 11 May 2016 20:48:08 +0200

Dear brothers and sisters,

I would like to start a small discussion around section 5.4,
replay attack prevention and the introduction of a nonce.

I was not able to find any thread around the "nonce" header in this
working group before - hence this post.  
In the latest version[0] of the RFC I read:

«The precise method used to generate and track nonces is up to the
server. For example, the server could generate a random 128-bit value
for each response, keep a list of issued nonces, and strike nonces from
this list as they are used.»

This paragraph has been introduced in the second version of the draft,
and it seems to be the only place describing a bit more in depth how the
nonce should look like.

It is not yet completely clear to me what the adversarial model should
be here (can somebody elaborate?), but is «the precise method used to
generate and track nonces» really up to the server, without any boundary
on the entropy of the nonce?

More specifically, is a 1-bit nonce going to provide an acceptable level
of security for this protocol? If not, is there a reason why there's not
a "MUST" (or at least a "SHOULD") directive for the minimum bits of
entropy required to prevent replay attacks?

I tried to find some relevant information on the JWS RFC[1], but none
found. I also gave a look at letsencrypt/boulder[2], and as far as I've
been able to understand there is a in64 counter, and 7 bytes of
randomness that determine the nonce. Am I wrong to say that there
are less than 128 bits of entropy here then? 

Ciao ciao,
[0]
<https://github.com/ietf-wg-acme/acme/blob/master/draft-ietf-acme-acme.md>
[1]
<https://tools.ietf.org/html/rfc7515>
[2]
<https://github.com/letsencrypt/boulder>
-- 
µ.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 12 May 2016 12:22:58 +1000

On 12 May 2016 at 04:48, Michele Orrù <[email-masked]> wrote:
> I also gave a look at letsencrypt/boulder[2], and as far as I've

Yes, that is less than 128 bits, and maybe lower still if you were
talking about predictability, but it's still probably plenty
(depending on how that counter is set and reset).  I believe that the
important point here is not predictability in the crypto sense, but
uniqueness.  The nonce needs to be generated such that an attacker has
very low odds of being able to find and use a collision.

Of course, having very low odds of collision is a good way of managing
that (128 bits of randomness gives pretty low odds).

I'll bet that boulder is doing that so that they good space efficiency
when the nonce is encoded in base64.  The last octet in a 128 bit
value takes a whole extra byte to encode.  A 32 bit counter and 11
bytes of randomness would better meet the above goals, or just 15
octets of randomness.