[messaging] Deterministic nonce generation for AES-CTR

[Taylor R Campbell]

   Date: Thu, 12 Nov 2015 11:05:59 -0800
   From: Nick Badger <nbadger1 at gmail.com>

   But three relevant details are that 1.) key/access control is separate from
   content containers, 2.) all resources are content-addressed by their hash
   digests, and 3.) the protocol is transport agnostic, so traffic analysis,
   etc are deliberately out-of-scope.

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, and of
course it tends to be hard to ensure the AES code that your
application will use is not vulnerable to timing attacks[*].

If you used, e.g., XSalsa20 or XChaCha instead, which have 192-bit
nonces in addition to a counter, random nonces would be OK -- a
birthday bound of 2^96 is reasonably high and you can theoretically
have up to 2^64-block messages.

All that said, depending on the rest of your protocol, you may be
better off with an independent key per message, as, e.g., Tahoe-LAFS
and Tarsnap do.  Then you don't need to worry about nonces at all.
(If you're not familiar with Tahoe-LAFS, you should read up on it!)


[*] Yes, there's AES-NI -- and usually a byzantine maze of
impenetrable OpenSSL abstractions between your application and AES-NI,
making it hard to confirm that it's being used.