Re: [Cfrg] KDF: Randomness extraction vs. key expansion

["D. J. Bernstein" <[e-mail]>]

How do we encrypt a series of messages using a Diffie-Hellman shared
secret g^xy? There are many solutions that are conjectured to be secure.
The most efficient solutions all have two common levels of structure:

   * They convert g^xy into a long string and then xor pieces of the
     string with the messages.

   * They compute the long string as a series of short blocks, where the
     nth block is obtained by feeding (g^xy,n) to a primitive circuit.

One conjectures that the attacker, given g^x and g^y, can't distinguish
the circuit outputs from independent uniform random strings. This
implies that a passive attacker can't break the encryption. (A more
complicated conjecture handles active attackers.) Essentially identical
comments apply to authentication, thanks to Wegman-Carter.

It also turns out that the most efficient solutions use elliptic-curve
groups. This may change---perhaps someone will find a better attack;
even if not, genus 2 has evolved into a serious competitor---but it's
shared structure for the moment.

Are there other common structures? In particular, is there a common
structure to the fastest primitive circuits used to mangle (g^xy,n)?

The answer is no. There are many competing structures for the primitive
circuit. One can easily take any of these structures and use it to build
an apparently unbreakable circuit that, on today's CPUs, uses fewer than
20 cycles per output byte. No single structure is a clear speed leader.

There are, however, some structures that clearly are _not_ speed leaders
for their conjectured security level. In particular, a structure that
combines SHA-256 with AES ends up consuming considerably more hardware
resources, L1 I-cache, etc. than a structure that iterates a unified
round function for a similar number of rounds.

I've noticed some people becoming overly excited about particular
structures. Often these people get so caught up in the buzzwords used to
describe their structures, such as ``randomness extraction,'' that they
lose sight of what users actually want, namely security and speed of the
encryption (and authentication) system as a whole. These people start
demanding that other people follow the same structures---even when the
structures are neither necessary nor sufficient for security!

Ran Canetti says, for example, that one is obliged to use the following
structure, because anything else is a ``cryptographic layer violation'':

   * apply a ``randomness extractor'' R to g^xy;
   * use R(g^xy) as a key for a ``conjectured PRG'' G; and
   * use G(R(g^xy)) as a key for a ``conjectured PRF'' F producing the
     desired output blocks.

If R and G are both serious cryptographic functions then this structure
is overkill. The generator G is pointless complication, making the
cryptosystem unnecessarily difficult to implement, especially in FPGAs.

If, on the other hand, R and G are not serious cryptographic functions,
then this structure can easily lose all security. An active attacker can
feed related inputs to R (such as g^(xy+x), g^(xy+2x), g^(xy+3x), etc.),
unless higher-level protocol layers take tons of time to check proof of
secret-key possession. Typical randomness extractors R, even perfectly
secure ones, will turn those related inputs into related outputs. If the
key for F isn't longer than the output of R then G can be the identity
function, a provable PRG. The keys for F are then related---exposing F
to a related-key attack, which PRFs are not required to resist.

The whole point of key derivation is to eliminate related-key attacks,
known-DH-bit attacks, etc. We all know how to do this properly: feed the
shared secret through a cryptographic hash function---even a fairly
wimpy one, such as g^xy |-> MD5(g^xy,0),MD5(g^xy,1). I don't object to
using larger hash functions, preferably sharing code with functions that
need to be implemented anyway; this computation is amortized over many
blocks. I do, however, object to having the hash function constrained to
follow someone's naive notion of proper ``cryptographic layers.''

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg