[Cfrg] KDF: Randomness extraction vs. key expansion

[canetti <canetti at watson.ibm.com>]

I have a high level remark on the KDF I-D and much of the following
discussion. (Some of these issues appear in Hugo's recent notes to cfrg,
but way too implicitly in my eyes...)

The proposed KDF function takes as input a "secret value" SV and stretches
it to a longer "pseudorandom" output. The value SV is not assumed to be
pseudorandom; rather, it can only have "high entropy". In fact, in
typical applications (such as the result of a DH exchange)  the
entropy of SV given the public values is zero; so SV only
has "high computational entropy".

This definition of KDF in the I-D lumps together two very
different cryptographic tasks:

* Randomness extraction: taking an input with "high computational entropy"
and generating from it a pseudorandom value.

* Key expansion: taking a short pseudorandom value and extending it to a
longer pseudorandom value, here the output length is variable anddepends
on the application.

The second task is rather simple, and can be carried out by straightforward
application of a PRF (eg, HMAC or any block cipher) in either counter
or feedback mode or a combination of the two. The first task is more
intricate, and has different solutions in different settings
(see more details below).

Furthermore, in typical modeling and security analysis of key exchange
protocols the two tasks live on different layers: randomness extraction is
part of the key exchange protocol itself, in an effort to output a
pseudorandom key to the application that uses the key exchange protocol.
in particular, in order to do randomness extraction you dont need to know
the specific length of keyng material needed for the application.
In contrast, key expansion is done in the layer that uses the "raw
key" in order to key the actual transforms in use (encryption mac, etc.).

So, it seems to me that lumping randomness extraction and key expansion into
a single function is a "cryptographic layer violation". We would be better
off having two different functions, one for each task. Some advantages:

* We can analyze each function separately, based on different assumptions on
cryptographic algorithms in use. This way, we can get better, tighter, and
more meaningful analysis rather than just "assuming that this all works".

* We can have key expansion functions for different settings, and - more
importantly - different randomness expansion functions for different
settings. This would bring us closer to the notion of a "toolbox", as
proposed earlier on saag.

* We dont break the standard layering of cryptographic protocols, thus
making cryptographic protocol analysis somewhat easier.

One potential disadvantage of two separate functions is efficiency.
But I dont think that the price here is significant. The functions we're
talking about here are typically very efficeint, much more so than the
public key operations that are bound to be part of almost any key
exchange.

A remark on randomness extraction: Randomness extraction becomes
significantly easier if the extracting function has some public random input
that is independent from the secret value. In many situations such public
randomness is readily available (eg, take the nonces used in the exchange).
So it makes much sense to design a randomness extraction function that
makes use of such public random values when they are available.
(In contrast, there are situations where no such public randomness is
avilable, eg, the MQV or HMQV protocols. For such cases, a different
design is needed.)

Finally, a general remark on modeling and abstractions: I can imagine people
read this note and think to themselves: "why is he bothing us with these
abstract notions. In the end of the day all that is going to be done is a
bunch of hashes and/or block cipher operations, so why not do it explicitly
and be done with it." My answer is that these abstractions are our
only hope to make sense of this spaghetti of hashes, shifts,
concatenations, exponentiations etc. If we want to build systems that will
have some pretence of security we have no choice but use the abstractions
and abide by them, even is there is some price in complexity.


Ran



_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg