Subject: [Cfrg] On using ROs for analyzing randomness extraction functions

From: David Wagner <[email-masked]>
Date: Fri, 28 Oct 2005 14:14:36 -0700 (PDT)

Ran Canetti writes:
>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.

I guess I have a different take on this.  I wouldn't say that the RO
model proves security for some task is impossible in practice.  Rather,
I would say that the RO model idealization implicitly assumes that the
source does not depend on H in any way.  Consequently, in any real world
protocol, we have an obligation to convince ourselves that the source
does not depend on ("is independent of" / "does not interact badly with")
the hash function if we want the RO security proofs to mean anything.
The RO model cannot help us with the latter obligation; that's something
we have to assess heuristically via some other kind of reasoning.  But in
many cases the "no bad interactions" hypothesis looks very plausible
(even if we cannot prove it), and in such cases one would expect the RO
model to form good evidence for security in real life.

Let me try an analogy.  When we analyze "hash-then-sign" (FDH signatures)
in the RO model, our RO idealization implicitly assumes that the
trapdoor permutation is independent of the choice of H.  That's an
assumption that is never proved; and one has to look at the real world
scheme and guess whether the assumption is met.  But if we take, say,
a FDH signature where we hash with SHA256 and then sign with raw RSA, it
boggles the imagination that there could be any bad interaction between
SHA256 and RSA.  Consequently, the "no bad interactions" looks like a
fairly plausible assumption, even though it is not something we know how
to prove.  We wouldn't say that the "hash-then-sign" task is impossible in
reality, even though it is true that there do exist (contrived-looking)
trapdoor permutations that interact with SHA256 badly enough to make
"hash-then-sign" insecure with those trapdoor permutations.

So the random oracle model, and the assumptions needed to make it
meaningful, doesn't seem so bad to me in this setting.

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

---

From: Jack Lloyd <[email-masked]>
Date: Fri, 28 Oct 2005 17:25:39 -0400

On Fri, Oct 28, 2005 at 02:14:36PM -0700, David Wagner wrote:

[...]

> "hash-then-sign" insecure with those trapdoor permutations.

Could you provide a reference to or sketch of what such a function might look
like? I gave it a bit of thought and couldn't see any way of creating a
trapdoor such as you describe, so now I'm curious.

-Jack

---

From: canetti <[email-masked]>
Date: Sat, 29 Oct 2005 01:16:48 -0400 (EDT)

David,

I think our takes on this are not as different as it might seem.
We agree that randomness extraction when the input distribution depends on
the definition of the extraction function H is impossible in general.
we also agree that we should not stop here, but rather try to get around
this by somehow finding a meaningful way to assume that the input
distribution does not depend on the definition of H. we differ in how to
make this assumption: You seem satisfied with using the RO abstraction.
To me, this abstraction seems unsatisfactory, since it does not allow me
to *precisely state what it is that I'm assuming*. I'm not talking here
about proving anything, just on precise statement of the "non
dependence" assumption. (It sounds great in English, but does it really
mean?)

This is why I'd rather make an explicit, well-defined assumption within
the standard model. Note: I'm not claiming that I have such an assumption
formulated. I also agree that this would probably end up being much more
messy than the RO stuff. But I think it's worth it here to not take the
"easy way out" and try to formulate those things precisely. In some cases,
such as FDH,  the RO seems indispensable (as pointed out by Ilya). I have
a strong feeling that in our case it is dispensable.)

Ran

PS - forgot to agree before - this discussion is indeed very insteresting
and illuminating.

---

From: John Wilkinson <[email-masked]>
Date: Sun, 30 Oct 2005 08:27:34 -0500

Perhaps this is the discussion topic I should have replied to with my  
questions about Bernstein and Wagner's non-NIST KDF discussion. I  
apologize for any confusion I may have caused on the other topic.

Perhaps some will think it is only of academic interest, but I, for  
one, would be very interested in continuing the discussion on KDFs  
that can minimize, or avoid entirely, our reliance on the RO  
assumption for hash functions. So, in the interest of having a  
suitable target to throw darts at, what, if anything, is wrong with  
the following proposal, and does anything like it already exist as a  
standard or write-up?

1. Assume that there has already been an authenticated DH key  
exchange (details and caveats to be fleshed out later), resulting in  
the sharing of the secret g^xy between Alice and Bob.

2. To extract "computational entropy" (or whatever term is most  
correct) from g^xy, Alice and Bob each use, as specified by their  
protocol, the fixed universal hash function H(g^xy), where H(m) is  
defined as:

H(m) := m*x^256 mod x^256 + x^10 + x^5 + x^2 + 1

Where m is interpreted as a polynomial in x, with coefficients modulo 2.

3. H(g^xy) can then be used directly for further communications, if  
only 256-bits of key material are required, or H(g^xy) can be used as  
the key to a PRF (say, HMAC-SHA256 or CMAC-AES256) to derive more key  
material.

Such a construction would seem to be efficient and practical, and  
avoids any reliance on random oracles, so, something must be wrong  
with it. :)

-John

---

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

> H(m) := m*x^256 mod x^256 + x^10 + x^5 + x^2 + 1

Compressibility alert! I'm willing to bet quite a lot of money that you
didn't produce this polynomial by flipping 256 coins and then testing
irreducibility. Here's a replacement for 10,5,2,1: the nonzero bits of
80732611323681528892253724266645620659672229865344711926625102802953711697391.

> avoids any reliance on random oracles, so, something must be wrong  

It's certainly much better than nothing. But it doesn't guarantee
security: among other problems, it could allow related-key attacks.
That's why we use things like SHA-256.

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

---

From: John Wilkinson <[email-masked]>
Date: Mon, 31 Oct 2005 12:01:24 -0500

On Oct 31, 2005, at 12:41 AM, D. J. Bernstein wrote:
> irreducibility.

You're right, I didn't. I chose the first irreducible polynomial of  
degree 256, on the mistaken assumption that one member of the  
universal hash family was as good as any other. I see now that some  
members may be "weak", and that I should have chosen a member at  
random. I'd be happy to use your choice of hash function, or one  
based on digits of pi, or whatever . . .

I also see your point about related key attacks, so it seems we need  
some sort of "public randomness", as suggested by Canetti.

I really wasn't trying to design anything new myself, I was just  
trying to focus the discussion, to hash out some of the ideas that  
had been suggested during discussion of the NIST HKDF.

It seems to me that during this discussion, two categories of KDFs  
have been suggested: 1) NIST's "all-in-one" HKDF, and 2) a two-layer  
"randomness extraction"/"key expansion" scheme. Adherents to the two- 
layer philosophy seem to agree that a PRF should be used for key  
expansion, but several suggestions for randomness extraction have  
been made: 2.1) a cryptographic hash function, 2.2) a PRF keyed with  
a public random nonce, and 2.3) a universal hash function selected  
from a universal hash family using a public random nonce. If I  
understand the suggestions correctly, they are, in compact notation:

1) K_i = H( i || SV || context )

2.1) K_i = PRF( H(SV), i || context )

2.2) K_i = PRF( PRF( R, SV ), i || context )

2.3) K_i = PRF( UH( R, SV ), i || context )

Where the first input to the PRF is always the key, and the second  
input is the message; UH is a universal hash function family, where  
the input R selects a specific hash function from the family, and the  
second input is the message to be hashed; and R is a public random  
nonce.

1 makes strong assumptions on the hash function H, but it is noted  
that these assumptions have never been violated in practice. The  
implementation is straightforward, and requires only a single  
cryptographic primitive, with the ability to reuse H if it is already  
present in the system.

2.1 makes weaker assumptions on H, it requires only one primitive if  
the PRF is taken to be HMAC-H, and it can reuse H if present  
elsewhere in the system.

2.2 makes a non-standard assumption about the PRF, namely, that it  
has properties similar to universal hash families and that it retains  
some security after the key is made public. It has the advantage of  
requiring only a single cryptographic primitive, and can reuse either  
a hash function or a block cipher, if either is already present in  
the system. Additionally, it does not *require* public randomness R,  
as this could be taken to be 0 if no R is available, reducing the  
security guarantee, but probably retaining as much security as 2.1.

2.3 seems to be the only one that offers security in the standard  
model, but it may be practically unacceptable in many applications,  
since it requires two cryptographic primitives, a PRF and a universal  
hash function family. A "lighter-weight" KDF is clearly needed for  
some applications, even if some others might be better using 2.3.

-John

---

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

John Wilkinson writes:
> 2.3 seems to be the only one that offers security in the standard model,

You've been misled. That construction does _not_ guarantee secure key
derivation under standard assumptions.

---

From: John Wilkinson <[email-masked]>
Date: Mon, 31 Oct 2005 13:22:38 -0500

On Oct 31, 2005, at 1:10 PM, D. J. Bernstein wrote:

>> model,

OK, clearly I'm in way over my head, but isn't that what the  
discussion about the Leftover Hash Lemma was about? Doesn't that  
lemma guarantee that UH(R,SV) is delta-uniform when R is chosen  
independently of SV? And if the output of UH is delta-uniform, then  
isn't the PRF secure under standard assumptions? I know this falls  
far short of a real proof, but, as I said, I'm in over my head here.

-John

---

From: "D. J. Bernstein" <[email-masked]>
Date: 31 Oct 2005 23:34:43 -0000

There are both quantitative problems and qualitative problems with this
type of universal hashing. The most obvious quantitative problem is that
if you start with (e.g.) a 256-bit elliptic-curve g^xy, and hash it to a
(e.g.) a 256-bit key, then the leftover-hash lemma says _nothing_ about
the resulting distribution. The most obvious qualitative problem is that
real-world protocols reuse Diffie-Hellman keys with multiple parties,
forcing the key-derivation function to eliminate related keys, which
universal hashing fails to do.

---

From: canetti <[email-masked]>
Date: Mon, 31 Oct 2005 23:18:53 -0500 (EST)

John,

Again, if I may intervene...

my take here is that, yes, in principle the method you suggest works for
the reasons you stated.

But Dan is right that care should be taken: First, the leftover hash lemma
guarantees almost-randomness of the output only if the output size is much
shorter than the input (and is roughly the size of the underlying
entropy).

Also, there is dependence of the specific key exchange method in use, and
in some cased UH is not enough. an example is the case mentioned by Dan,
where parties use related exponents for different exchanges. other examples
includes, say, exchanges where the peer identities must be incorporated
into the derivation procedure to prevent "identity misbinding attacks".
so, in all, it is probably hard to come up with a generic method that will
provide a good extraction/derivation function for all KE methods,
even if an independent R is given.

however, for "standard" ke methods such as the ISO-9798-3 or IKE, without
reuse of the ephemeral exponents,  universal hashing with sufficiently
short output should work.

Ran