[messaging] Deterministic nonce generation for AES-CTR

[Taylor R Campbell]

   Date: Thu, 12 Nov 2015 13:15:16 -0800
   From: Nick Badger <nbadger1 at gmail.com>

   Re: Taylor --

   > What you describe is roughly the SIV construction of RFC 5297. The
   > 128-bit block size of AES makes me nervous for random nonces, no
   > matter how you carve it up or mix it up for nonce and counter

   SIV is an awesome thing that I didn't know about, thanks. Wouldn't the
   128-bit block size then be an argument *for* deterministic nonce
   generation? It's a bit tough for me to tell from your message. For our
   application, deterministic nonce generation is highly desirable, but we
   don't want that to compromise security. Point is, we're already on the side
   of non-random.

The critical distinction I meant to make was not between
nondeterministic versus deterministic nonces, but rather between
(pseudo)random versus sequential nonces.

If you first use 0, then 1, then 2, &c., you are guaranteed never to
repeat in a (say) 96-bit string.

If you first use AES-CMAC_k(p0), then AES-CMAC_k(p1), &c., or use
successive outputs of a PRNG, or use fresh observations from an
avalanche transistor, then after 2^64 nonces the chance of a collision
is about 1/2.  (Here p0, p1, ..., are the plaintext messages.)

You could stop after fewer nonces, but if you stop after, say, 2^32
messages, the chance of collision is about 2^-65 -- small, but not
unimaginably so.  (The Bitcoin network computes about 2^65 hashes
every minute.)

You could use a PRP: AES_k(0), AES_k(1), AES_k(2), ... -- but then you
might as well just use 0, 1, 2, ..., since you can obviously maintain
state between messages.

   Re: Joe --

   > Your proposed scheme might be secure there, but the straightforward way to
   > do what you're trying to do is compute a MAC of the plaintext and use that
   > as your IV. Key-reuse is a problem for provable security, as you point out.

   MACs are definitely simpler and feel more elegant, but if possible, I'd
   prefer to stick with an encrypt-then-MAC/sign approach all around (the
   containers themselves are signed, not MAC'd).

Note that the word you want here is `PRF', not `MAC', for deriving an
unpredictable string from a key and a plaintext.  A good PRF makes a
good MAC (e.g., keyed blake2s), but the converse is not necessarily
true (e.g., poly1305).