[cryptography] "folded" SHA1 vs HMAC for entropy extraction

Marsh Ray marsh at extendedsubset.com
Thu Jan 5 19:42:32 EST 2012


On 01/05/2012 05:59 PM, Thor Lancelot Simon wrote:
>
> FWIW, using HMAC like this is the "extract" step of the two-step
> extract-expand HMAC based construction that is HKDF


 From http://tools.ietf.org/html/draft-krawczyk-hkdf-01
> 2.2.  Step 1: Extract
>
>    PRK = HKDF-Extract(salt, IKM)
>
>    Options:
>       Hash     a hash function; HashLen denotes the length of the
>                hash function output in octets
>    Inputs:
>       salt     optional salt value (a non-secret random value);
>                if not provided, it is set to a string of HashLen zeros.
                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
So this is your fixed-value 'tweak'.

>       IKM      input keying material
>    Output:
>       PRK      a pseudo-random key (of HashLen octets)
>
>    The output PRK is calculated as follows:
>
>    PRK = HMAC-Hash(salt, IKM)

Now the definition of HMAC from http://tools.ietf.org/html/rfc2104
where 'K' is the key/tweak input:

>                  ipad = the byte 0x36 repeated B times
>                  opad = the byte 0x5C repeated B times.
>
>                     H(K XOR opad, H(K XOR ipad, text))

So HMAC with a fixed key input is exactly equivalent to evaluating the 
underlying hash function twice with two different fixed prefixes.

> HMAC does have some other desirable properties that the raw
> hash functions do not, no?

I'm not seeing any for the simple extraction scenario, other than the 
doubling-up of the hash function.

> I thought HMAC met the strict avalanche
> criterion, while SHA1 does not,

Well perhaps, but what I'm saying is that if you believe that that has 
implications for your RNG extractor, then you also believe that SHA-1 is 
not an ideal hash function, i.e., it is "broken" (and I think most folks 
would agree with you on that).

But the hash function
     SHA-1(fixed_prefix_b || SHA-1(fixed_prefix_a || text))
AKA
     HMAC_SHA-1(fixed_key, text)

MAY be usefully less broken. However, the result will have slightly less 
than the theoretical 160 bits of entropy (maybe 159.2) due to the way 
SHA-1 is iterated.

> and that this was one of the reasons
> why truncation of HMAC results was considered safer than truncation
> of raw hash results.

I think that that has more to do with the presumption that the key is 
secret. If the attacker doesn't know the key, he can't compute the 
function so he can't conduct offline attacks against the truncated result.

>  In this application, the result will often be
> truncated when it is used, which is another reason why I -- naive
> crypto-plumber though I am -- thought HMAC might be a better choice.

IMHO the bigger danger in RNGs is complexity and overengineering.

But others have well-reasoned opinions that differ from mine. :-)

- Marsh



More information about the cryptography mailing list