[messaging] Deterministic nonce generation for AES-CTR

[Nick Badger]

Hello,

I'm working on a cryptographically enforced asynchronous social protocol (
https://github.com/Muterra/doc-muse, but we don't have a formal security
analysis yet and the spec and whitepaper are very long. None of it has been
put into code yet; we'd like to have third-party protocol reviewers first).
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.

Because everything is hash addressed, and content is retained
asynchronously (potentially indefinitely; note that key persistence is
handled separately), we're very concerned about data deduplication.
"Ideally" (ie, ignoring security, which we're obviously not doing), to
minimize network clutter, every (plaintext + key) combination would result
in identical ciphertext. Of course, in practice, we need to be extremely
concerned about reusing a (key + nonce) combination, but for reasons I
won't go into here, replay attacks are meaningless to the protocol -- so
the thought is, we can generate the nonce from a manipulation of the hash
of the plaintext. The nonce will still need to be prepended to the
ciphertext in the clear for decryption, but this way an identical (key +
nonce) combination will by definition have an identical resulting file.

First question: is this a reasonable approach? I'm honestly having a
difficult time deciding if this increases or decreases our attack surface
area, given the way the rest of the protocol is set up.

Second question: assuming it is reasonable, what's the best way to do this?
We do have to be concerned about leaking information from the inner
container, so our current process is NONCE = AES-ECB( message_key, HASH(
plaintext ) ) with the hash truncated to match the symmetric block size.
Frankly though, that seems off to me, at the very least because we're
reusing the message key. We should probably transition the message key to a
master key, and use a KDF to generate both the nonce key and the message
key. To that end, would NONCE = AES-ECB( KDF( master_key, HASH(plaintext)
), HASH(plaintext) ) make more sense? The "extra" AES here is to protect
from dictionary attacks and against potential hash compromise.

Thanks much.

Nick Badger
https://www.ethyr.net
https://www.muterra.io
http://www.nickbadger.com
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/f36843f5/attachment.html>