Subject: Re: [Cfrg] AES-based PRF - comment please

From: Ran Canetti <[email-masked]>
Date: Thu, 10 Apr 2003 00:49:35 -0400

- A few belated remarks on this thread. (Sorry for not being able to respond 
in a more on-line fashion.)

Let me first recap the discussion as I understand it. The overall question
is how to construct a good key-derivation function for key-exchange
protocols, and for Diffie-Hellman based protocols in particular.
There were three main topics:
1. How to deal with the case where the "rough keying material" we start with
   is not guaranteed to be "pseudorandom" - ie, not completely secret or 
   not uniformly distributed. 
2. How to deal with the case where the "rough keying material" we start with
   is of variable length.
3. How to obtain a variable-length output.

I believe topic 3 is pretty well understood, once we have a pseudorandom key; 
there are several ways to do it, with known tradeoffs, and with good analysis 
that provides concrete and quantitative security bounds. (Some of these ways 
were suggested in this thread.)

Topic 2 is also well understood - at least for the case where 
the keying material we start with is pseudorandom and is of
sufficient length. In this case, we simply use as many bits of the key
as are necessary to key the cyptographic function we're working with. 
Unused key bits can be prepended to the "non-secret" input of the 
underlying cryptographic function - this may help reduce the assumptions on
that function. If the keying material is too short then we're back to topic 1.

Topic 1 is much more of an unstable ground - and the focus of the rest of
this note. First, at the risk of being redundant, let me recap what is 
usually meant by a "pseudorandom keying material": Roughly speaking, 
the keying material to the key derivation function is said to be 
"pseudorandom" if no adversary that (uses a given amount of
computational resources and) is given all the publicly available
information can win in the following game with probability that 
is non-negligibly more than one half. In the game, the adversary is given 
either the real keying material (with probability one half) or an
independently and uniformly chosen string of the same length. It wins if it
guesses correctly which is  the case. 
(Ofcourse, this qualitative definition can be made quantitative, relating 
the actual success probability to the resources used by the adversary.)

For sake of presentation let me concentrate on DH-based key exchange.
Here the keying material is g^xy and the adversary knows g^x,g^y.
So, if the DDH assumption holds (ie, if g^xy is pseudorandom given g^x,g^y)
then we're golden. But what if not? (This is the "belt and suspenders"
question. Great term.)

Ofcourse, if DH is completely broken and g^xy is completely computable from 
g^x,g^y then nothing can be done. But what if we're in an "in-between"
situation, where g^xy canot be completely computed, but it is possible to 
distinguish it from random, either by predicting some of the bits based on 
the public info, or in other ways? How can we "extract" a pseudorandom 
key from g^xy?

As a side remark, let me first say that, at least in principle,
the problem is solved: The theory of cryptography offers a number of generic
ways to extract pseudorandom bits from g^xy, based only on the minimal 
assumption that g^xy cannot be completely computed given g^x,g^y.
But these methods are highly inefficient. In particular, we'd be able to
extract only very few bits from each DH exchange - or in other words we'd
need several DH exchanges to get a sizable key. (I'm referring here to the
standard constructions of pseudorandom generators based on any
one-way function.)

So the question is how to do it in a more reasonable way from an efficiency
point of view. In other words we're looking for a way to use some readily
avaliable cryptographic function (say SHA, AES etc) in order to extract a
significant number of bits from g^xy, so that these bits will be
pseudorandom based on minimal assumptions on the DH problem and on the
underlying cryptographic function. I dont have a good, well analyzed
proposal here. I think this is a good research topic.

Ran

A couple more remarks:

1. A cryptographic primitive that is closely related to what we need is
"exposure resilient function (ERF)". These are functions whose output is
pseudorandom even if part of the input is known. Some initial and theoretical
study of such functionas was done in [1]. Unfortunately, I didnt see 
an immediate way to use the techniques from there in our case.

[1] R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, A. Sahai,
``Exposure-Resilient Functions and All-or-Nothing Transforms,''
Eurocrypt, 2000.

2. Regarding random oracles. It was suggested to model the underlying
cryptographic function (SHA, AES, etc.) as a random oracle and analyze the
security of the construction using the random oracle methodology 
(David gave a great description of this methodology - it ought to be quoted
in some textbook). But I dont think that such a modeling will be
helpful in our context. One issue is ofourse the inherent unsoundness of 
this methodology, as was already discussed on this thread. But there is 
a much more immediate issue. Recall that we're trying to find a construction
that would make only minimal assumption on the underlying functions.
But if we model these functions as random oracles then almost any
construction would be labeled "secure" - good ones as well as 
less good ones. In other words, this modeling is so "coarse grained"
that it doesnt allow investigating what we are interested
in (minimizing assumptions). It is a bit like using a 10 pounds axe 
to trim fingernails...

[Something somewhat similar happens in the case of hash-based MACs. If we
model the hash function as a random oracle then many different ways of 
keying the underlying hash function result in equally secure MACs.
But constructions do differ a lot in the assumption they make on the
underlying hash function. In particular, HMAC tries to minimize those
assumptions, and I believe that this is at least partly why it was chosen 
over other constructions.]

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

---

From: John Viega <[email-masked]>
Date: Thu, 10 Apr 2003 01:10:19 -0400

On Thursday, April 10, 2003, at 12:49  AM, Ran Canetti wrote:

> [...]
> Topic 1 is much more of an unstable ground [...]

I disagree.  We know how to do 1 quite well.  David McGrew and I were 
recently talking about this thread.  A simple PRF that takes a variable 
length input and produces a variable length output is to hash the input 
(if necessary), then produce as much output as necessary by using a 
keyed counter mode operation.

When using SHA1 as a primitive, you could simply use the keying 
material as-is, and HMAC-SHA1 a counter for however much output you 
need.  Or, if the keying material is large, you can hash it down and 
use the result to key HMAC-SHA1 in counter mode.

If using AES as a primitive, one can first hash the input down to the 
size of an AES key by using one of the many constructions that turn a 
block cipher into a hash function.  Then, one simply uses the result to 
key counter mode.

The real issue we couldn't get past is how to create a PRF based from a 
single primitive that is easy to pipeline in hardware.  The AES-based 
solution looks particularly unappealing from that point of view.

Nonetheless, either of those PRFs should be fine for fairly 
general-purpose use, unless you care about protecting against password 
computation attacks, in which case there's no reason not to use 
PKCS#5's PBKDF2.

John

---

From: "David A. Mcgrew" <[email-masked]>
Date: Thu, 10 Apr 2003 09:09:08 -0700

Ran,

an excellent writeup, more inline:

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of Ran
> Canetti
> Sent: Wednesday, April 09, 2003 9:50 PM
> To: [email-masked]
> Subject: Re: [Cfrg] AES-based PRF - comment please
>
>
>

Agreed.

> proposal here. I think this is a good research topic.

Agreed.  FWIW, I would expect that any AES-based solution to this problem would
involve an AES-based unkeyed collision-resistant hash function.  Such a
construct, if efficient and proven secure under reasonable assumptions, would be
of general utility.

From an engineering standpoint, it seems to me that the responsibility for
producing uniformly random output bits should be put onto the DH component.
I'm thinking of the following structure:

 - a DH component, which takes public keys as input and outputs a (uniformly
unpredictable) secret, and

 - a key derivation component, which takes a (uniformly unpredictable) secret
and some set of public data (e.g. nonces, labels, and so forth) and produces a
set of unpredictable keys.

Using this structure, we get the benefits that we've isolated the well-solved
problem, and that the DH component can be swapped out for other components (e.g.
symmetric or asymmetric key transport, elliptic curve variants, out-of-band
keys, or whatever).  Also, this separation can help the key derivation component
meet other secondary design goals, such as providing forward security (in the
sense of the 'serial' method in "Increasing the lifetime of a key", by Abdalla
and Bellare, - Asiacrypt 2000, online at
http://www.cs.ucsd.edu/users/mihir/papers/rekey.html).

> in (minimizing assumptions). It is a bit like using a 10 pounds axe

ugh! :-)

David

---

From: Uri Blumenthal <[email-masked]>
Date: Thu, 10 Apr 2003 13:44:53 -0400

Ran Canetti wrote:
> 2........
 > 3........
> I believe topic 3 is pretty well understood, once we have a
 > pseudorandom key..........Topic 2 is also well understood -
 > at least for the case where the keying material we start
 > with is pseudorandom and is of sufficient length........

Yes.

> Topic 1 is much more of an unstable ground.............

Yes. And we'll deal with two cases: (a) the input is
"hopefully" random "enough" - e.g. g^xy, and (b) we
know nothing of the input quality but assume that
it can have fewer bits of randomness thn the
required key size.

> then we're golden. But what if not? (This is the "belt and suspenders"

Yes, the term is great.  The problem is: if DDH doesn't hold - then
you have to resort to unproved properties of SHA, actually modeling
it as a random oracle - which you don't seem to like.

> ...[assume].... we're in an "in-between"
> key from g^xy?...how to do it in a more reasonable way from an efficiency
> underlying cryptographic function.

A nicer way IMHO would be to "post-process" g^xy and extract
some "random" bits with quantitative guarantees... Though it
may be that the most reasonable way of doing it is running,
say AES-hash over it...

 > I dont have a good, well analyzed

:-)

> pseudorandom even if part of the input is known....

Would love to look at this paper.

> helpful in our context.

You already use such a modeling of the currently defined PRF.
Recall David's description: two assumptions "balancing" each
other - either DDH holds, or SHA behaves like a random oracle.
If you assume that SHA does NOT behave like a random oracle,
then your security proofs are dependent on DDH.

Now since you can't just go from "it's collision-resistant"
to "it behaves like a random oracle" - it has to be a leap
of faith, supported by the fact that the opposite hasn't
been proven/demonstrated.