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

[canetti <[e-mail]>]

Dan,

If one prefers to treat the entire cryptographic processing in, say,
a VPN application as a single unit with no punctuations then indeed my
proposal is of no value. But then, as you point out, we're left with one
main analytical tool: the vague notion of a "serious cryptographic function".

Note: No specific abstraction (or, layering) is ever mandatory, and they
are all naive to some extent, by the essence of being abstractions. But
we can't do without abstractions, and the one I'm advocating is
standard (and quite effective as well).

Ran


On Sat, 29 Oct 2005, D. J. Bernstein wrote:

> 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
> _______________________________________________
> saag mailing list
> [e-mail]
> https://jis.mit.edu/mailman/listinfo/saag
>

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