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

From: canetti <[email-masked]>
Date: Fri, 28 Oct 2005 15:48:59 -0400 (EDT)

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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: canetti <[email-masked]>
Date: Fri, 28 Oct 2005 16:49:12 -0400 (EDT)

I'd like to share some thoughts regarding the use of the RO modeling in
the randomness extraction problem.

Beyond the known formal problems with the
applicability of analysis in the RO model, such analysis usually leaves me
with an uneasy feeling of being "cheated out" of a real proof. One main
reason is that the RO, being so powerful, blends within it many different
idealizations. And I never know for sure what idealizations were actually
used in the proof at hand, and what are unnecessary.  (For instance, was the
"programmability" used? was the fact that the output is always uniform for
any two different inputs used? was the "perfect one wayness" used? was the
"hardness to find inputs such that the output has a given property" used?)
I would much rather have analysis in the standard model that makes explicit
assumptions on the hash functions and the adversary. This way, we'll at
least know for sure what I'm assuming away.

More concretely, regarding the problem of "deterministic computational
randomness extraction" - namely, coming up with a public function H that
turns inputs with high computational entropy into pseudorandom values. We
know that if the distribution of inputs to H can depend on the definition
of H then this task is impossible.

One way to get around this impossibility is to model H as a RO. Then
ofcourse this problem becomes not only doable but also trivial: almost any
way of feeding the input to the RO will be equally as secure as any other
way. But, alas, this doesnt change the fact that the task is impossible
in reality... in particular, we have learned nothing regarding which
constructions are better than others.

An alternative way to get around this impossiblity would be to remain in
our real world (without ROs) and instead make assumptions on the input
distribution of H. (For instance,  we can assume that the description of H
contains some public and random key k, and that the input distribution is
indistinguishable from a distribution that does not depend on k.)
This would indeed be a weaker result than what we'd like, but at least it
we will have some concrete result in our hands.

Ran

PS. One more, loosely relate point: As was already pointed out in this
thread, randomness extraction is actually possible when the extracting
function has some public random input that is independent from the secret
input. Many key exchange protocols give such public randomness "for free",
eg via the nonces etc., while others dont. This should be a good
motivation to (1) prefer the key exchange protocols that give out this
"public randomness", and (2) design randomness extraction functions that
make used of this public randomness.

---

From: Bill Sommerfeld <[email-masked]>
Date: Fri, 28 Oct 2005 16:58:39 -0400

> longer pseudorandom value, here the output length is variable anddepends

Some plumbing-level questions:

you suggested that random nonces should go into the first stage.  would
non-random context/identity inputs go there, too?

and: would it ever be appropriate to use multiple stages of key
expansion?

for instance:

[diffie-hellman] -> [randomness extraction] -> [key expansion] -> (A, B,
C)

A -> [key expansion] -> (A1, A2, A3)
B -> [key expansion] -> (B1, B2, B3)
C -> [key expansion] -> (C1, C2, C3)

					- Bill

---

From: canetti <[email-masked]>
Date: Sat, 29 Oct 2005 00:45:50 -0400 (EDT)

Bill,

Thanks for the good questions. See inline:

> non-random context/identity inputs go there, too?

Yes. But indeed not for the purpose of randomness extraction.
eg, the identities are useful for binding the generated key to the
identitied of the peers. In general, the first stage should do whatever
is necessary to get an initial seed of fixed length (say, 128 or 160 bits)
that is pseudorandom for anyone except the two peers, and is bound to
the correct peer identity within each one of the peers.

> and: would it ever be appropriate to use multiple stages of key

Yes, that could ofcourse happen. But the requirements from all levels of
key expansion are the same: take a fixed-length pseudorandom key and expand
it to a long-enough pseudorandom value.
This is in fact another motivation for separating randomness extraction
from key expansion. All these levels of key expansion already get a
pseudorandom key, so they dont need the full power of the KDF proposed
in the I-D.

Ran

---

From: Nicolas Williams <[email-masked]>
Date: Sat, 29 Oct 2005 03:08:31 -0500

> and abide by them, even is there is some price in complexity.

I'm with you on the same layering abstraction matter; even we agreed on
the identity function for randomness extraction there would still be a
layering abstraction.

This KDF has a lot of inputs, and in some ways arguably not enough
(e.g., IDs but, surprisingly, no ID types), but a PRF has a much
simpler function signature.  So it seems simpler to define a PRF
and then a KDF in terms of said PRF than to inextricably mix the two.

And why shouldn't there be a standard PRF if there is to be a standard
KDF?  And if there's to be a standard PRF then that'd be all the more
reason to base a standard KDF on a standard PRF.

Nico
--

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Oct 2005 10:15:12 -0000

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

---

From: canetti <[email-masked]>
Date: Sun, 30 Oct 2005 10:33:43 -0500 (EST)

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:

> saag mailing list
> [email-masked]
> https://jis.mit.edu/mailman/listinfo/saag
>

---

From: "D. J. Bernstein" <[email-masked]>
Date: 31 Oct 2005 05:26:10 -0000

canetti writes:
> But then, as you point out, we're left with one main analytical tool:
> the vague notion of a "serious cryptographic function".

The security of a key-derivation function is _always_ a vague notion.
You _must_ combine key derivation with a Diffie-Hellman group to produce
a clear security notion, namely HDH. _Every_ key-derivation function can
have its security destroyed by a poor choice of Diffie-Hellman function.
In fact, _every_ key-derivation function, no matter how many buzzwords
were used in its construction, can potentially have security destroyed
by a choice of Diffie-Hellman function that would have been secure with
most key-derivation functions. Even worse, if you make a sufficiently
poor choice of key-derivation function, then your security _will_ be
destroyed by _standard_ choices of Diffie-Hellman functions.

You've made a contrary claim, namely that you can build a conjecturally
secure key-derivation function by combining any randomness extractor and
any conjectured PRG. That claim is _false_. Your construction can lose
all the security that would have been produced by the NIST KDF. Your
construction fails to prevent related-key attacks. The last two
paragraphs of my previous message explain this in detail.

You could try to fix your security mistake by replacing ``randomness
extractor'' with a stronger notion---but if you continue trying to avoid
vague notions then you'll inevitably end up with something that's either
too weak or too strong. You do _not_ have, and you will never have, a
key-derivation function that's provably secure assuming AES security.

---

From: canetti <[email-masked]>
Date: Mon, 31 Oct 2005 10:04:47 -0500 (EST)

Dan, we seem to be in violent agreement, at least on the main point of this

> key-derivation function that's provably secure assuming AES security.

Exactly. Being a block cipher is not a strong enough property for randomness
extraction (or, key derivation if you prefer this name). In contrast, being
a block cipher is a perfect fit for key expansion. So let's separate the
two tasks!

BTW. In spite of the date, I dont share your pessimistic view that key
derivation/randomness extraction is doomed to be a vague notion where
sorcery rules forever. I think we do have tools to make mathematical
sense of it and to make concrete security claims. But I certainly agree
that it's a very different (and harder) task than key expansion.

Ran