[messaging] Deterministic nonce generation for AES-CTR

Nick Badger nbadger1 at gmail.com
Thu Nov 12 13:15:16 PST 2015

I'm merging message trees here to avoid multiple replies.

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.
> The simplest thing is to just have two keys, one for the MAC computation
> and one for the encryption.

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).

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.

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.

I'd definitely like to look into Salsa/ChaCha in the future, but right now
we don't really have the resources to make that switch.

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.

I probably should have clarified that as well. Generally speaking,
independent messages should have different keys. However -- and this
decision may come back to bite us -- key choice is deliberately left out of
the protocol spec. So it's possible, given that we do have a concept of a
dynamic message (that discussion gets complicated quickly[1]), that clients
may choose to reuse keys for dynamic messages. In the future we'd like to
add an (optional) overlay standard that mandates some kind of ratcheting,
probably axolotl. For scope limitation reasons that would still be outside
of the "spec proper", but at least it'd be heavily recommended.

I've seen Tahoe-LAFS before, but am probably not as familiar with it as I
should be. Thanks for the suggestion, I'll take a second look.

[1] Relevant whitepaper section:


Nick Badger
PGP fingerprint 37B9 22FC 2E47 50AA E06B 9CEC FB65 8930 46F0 333A, listed
at MIT <https://pgp.mit.edu/> and PGP <http://keyserver.pgp.com/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151112/561e7d4d/attachment.html>

More information about the Messaging mailing list