Subject: [Cfrg] Fwd: Hash-Based Key Derivation

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 15:20:32 -0700 (PDT)

Daniel Brown writes:
>David Wagner wrote on 10/25/2005 02:51:58 PM:
>> >>       http://www.ietf.org/internet-drafts/draft-dang-nistkdf-00.txt
>> 
>> General: The document doesn't specify how integers are to be encoded.
>> Little-endian?  Big-endian?  It seems to me that protocols that reference
>> this spec should be required to specify the encoding of integers into
>> bit-strings.
>
>The counter in Step 3, Section 2.2 is said to be big-endian.

Right.  It is the only quantity whose endianness is specified.
Everything else has its encoding left unspecified.

>I presume that endian-ness of the various length indicators (for
>algorithmID, contextID, SharedInfo) are intended to specified by the
>application protocol, as this spec only says that they are fixed-length
>bit strings without specifying the length.

I too assume that this is the intent, but having good intentions is
not enough.  The nistkdf document should explicitly state the requirement
that protocols must specify this.  If you read my comment above, that is
exactly what I suggested.

>> 2.1.2: algorithmOID is variable-length, but there is no length field
>> prepended to it.  It seems like this omission should be remedied.
>
>Doesn't algorithmLen do this?

Yes.  You're absolutely right, I read too quickly and I misunderstood.
I withdraw my comment.  Thanks for the correction.

>My concern is with the ASCII string 
>encoding of algorithmOID: why not use the usual DER encoding?  What ASCII 
>string should be encoded?   The sequence of numbers, separated as spaces, 
>embedding as ASCII?

Interesting question.  I don't have any suggestions.

>> 2.1.4: The size of keydatalen is not specified.  It should be.
>
>But keydatalen is an input, how can it be specified?  Do you mean that 
>there should be a minimum size for keydatalen?

Sorry, you're absolutely right.  I read too quickly again.

Let me try again.  Should the value of keydatalen be included in the
input to the hash function?  It could be relevant if one ever calls the
KDF with the same secret value and the same other parameters but with
different values of keydatalen.  Probably implementors are unlikely to
make that mistake, but if the value of keydatalen is included in the
input to the hash function, then the size (in bits) of the encoding of
keydatalen should be specified by the protocol.

>Presumably this is based on two results: (1) HMAC makes a good PRF and (2) 
>PRF makes a good KDF.  Are there convenient references for such results? 

For (1), I believe the HMAC paper mentions this.  It is straightforward
to adapt the standard proof that HMAC is a good MAC into a proof that HMAC
is a good PRF, modifying the assumptions slightly (instead of assuming
that the compression function is a good MAC on single-block inputs, we
assume it is a good PRF on single-block inputs, which is just as
reasonable an assumption).  I'm pretty sure that Hugo K has discussed
this on some IETF mailing list or other, though I can't remember where
(IPSEC? TLS? CFRG?).

For (2), I don't understand the question.  Isn't a PRF exactly the
obvious and right way of making precise what we expect from a KDF?
I have a suspicion that this may be a question of semantics (i.e.,
of what definitions we attach to KDF).  So probably before I can answer
whether a PRF makes for something that *you* would call a good PRF, I
should ask you whether you can make precise what you mean by a KDF.
For me, when I say KDF, what I mean is almost exactly that it should
act as a PRF when given secret inputs from some specified distribution(s).

>Moreover, this comments implies some doubt about the security of the more 
>direct construction in HKDF, i.e. that without going through a HMAC may 
>not only be formally unjustified but perhaps insecure.

Let me try putting it another way.  Going through a plain hash places
more stress on the hash function, possibly in ways that the hash function
wasn't designed for.  In contrast, a PRF like HMAC was designed precisely
for this purpose of handling many chosen-input queries under related
inputs.  A PRF is the right tool for this job; a hash isn't.  A hash might
happen to work, or might not, but a PRF like HMAC should give more
confidence in the security of the result than a plain hash.  Given the
recent attacks on hash functions, it's probably a good idea to reduce
our dependence on the hashes to the minimal assumptions we can get away
with.

>Wouldn't pre-hashing create a bottleneck for entropy, albeit one large 
>enough for adequate security?

Yes.  I think you've got it exactly right.

I don't see an entropy bottleneck as a problem.  The obvious instantiation
of this scheme will be with SHA256.  I can't see any reason to care
about a 256-bit bottleneck on entropy.  If anyone is worried about
attacks with a 2^256 workfactor, they are worrying about the wrong things.

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

---

From: Daniel Brown <[email-masked]>
Date: Wed, 26 Oct 2005 11:22:13 -0400

> act as a PRF when given secret inputs from some specified 
distribution(s).

A KDF should be "one-way", at least for some protocols.  (For example, see 
http://eprint.iacr.org/2004/306 or the recent papers on HMQV.)

I'm not well-versed in the formal definitions for PRF (not to mention a 
KDF), but as I see it, certain PRFs can fail to be 1-way.  If the PRF is 
the identity and the secret input is uniform and unpredictable, then the 
output is indistinguishable (from random), so it seems to be a PRF.

I realize that length-expanding PRFs must be 1-way, because otherwise one 
can recover the input and re-run the PRF to distinguish its output from 
random.  However KDFs may not necessarily be length-expanding, and in fact 
they are often length-decreasing.

This is not at all to say that any of the existing PRF designs are 
inadequate as a KDFs, (usually the designs have length-expanding options 
and thus must be one-way).  All I'm saying is that there's something's 
more to the KDF security than pseudorandom output.

On the other hand, if the output of KDF is meant to be used as a key in a 
secure algorithm, how crucial is pseudorandomness, or even 1-wayness, in 
practical terms?  (For protocols that use the KDF output directly, e.g. as 
a stream cipher, then full pseudorandomness is essential.)  If the KDF 
output goes directly into a AES key or HMAC key, then having a small 
amount of bias seems relatively harmless.  I appreciate the theoretical 
value: AES is secure with a random key, then AES is secure with a 
pseudorandom key.   I also recall the attacks on ARC4 with the keys have 
extensive structure (highly non pseudorandom), but am not aware if such 
attacks are expected for AES, HMAC, etc.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg