[noise] Thoughts on semi-deterministic encryption

[Brian Warner]

I think your approach is sound, although maybe it's a tad pessimistic:
trying hard to survive a situation which is going to cause other
problems anyways. But it's always nice know where you stand when things
start to break down :).

To get semantic security, you either need entropy (for the RNG) or
storage (for a counter). Clocks are a special form of storage, and have
other handy properties when they work, but I don't like to depend upon
them because they'll lead you into temptation. One temptation is to
compare clocks, which is almost always wrong (even if you're only
comparing a server's clock against itself, somebody might have changed
it significantly in the meantime). Another is the danger of subtle
consequences: the admin who sets the clock back a few minutes to make it
accurate is probably not considering the perils of nonce reuse that it
might cause.

So step one is to get non-semantic security: someone who knows a
plaintext can tell if you've just encrypted the same thing, or are
accessing its ciphertext. Even if the attacker doesn't strictly know the
plaintext, they might be able to guess, and then the question is how
much effort it takes to test each guess. We called this the
"partial-information-guessing attack".

Step two is to remove this attack, which we do in Tahoe-LAFS by adding a
"convergence secret" that's randomly generated when your client first
starts up. It's mixed into the key=H(plaintext) function, and lets you
control who can make this guessing attack (and also who you get to
converge storage with) by sharing/not-sharing the secret.

Then step three, if you don't care about convergence, is to get proper
semantic security by using a different convergence secret for each file,
either by using a random nonce (entropy), or a counter (storage), or
time.

But yeah, I think mixing in the entropy with the deterministically
generated (H(plaintext)) key is fine. I'd use HKDF for the mixing, but
it's basically the same as your HMAC scheme. The HKDF paper has some
descriptions of how it's designed to tolerate an attacker controlling
certain inputs (the salt, I think): so maybe you could treat the RNG as
untrusted by passing it as the salt. I think the goal would be for a
computationally-bounded attacker who gets to see everything else to
remain unable to force the encryption key into a particular value.

cheers,
 -Brian