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

[John Wilkinson <wilkjohn at gmail.com>]

On Oct 31, 2005, at 12:41 AM, D. J. Bernstein wrote:
> 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.

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


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