Subject: [Cfrg] one question about hash

From: "Wang, Steve" <[email-masked]>
Date: Wed, 9 Jul 2003 12:14:42 -0400

Hi,
 
I have one question about secure hash functions. Assume that H is a
secure hash function and k is a 128-bit symmetric key. One can compute
k1 = H (k || 1) and k2 = H(k || 2) {|| denotes string concatenation}. If
H is an ideal function, then it is hard to compute k1 from k2 and vice
versa. What will happen if we replace H with SHA-1?
 
Thanks,
 
Steve

---

From: canetti <[email-masked]>
Date: Wed, 9 Jul 2003 15:15:24 -0400 (EDT)

Well, that's the million-dollar question... :)

We have no definite guarantees that "SHA1 behaves like an ideal  function".
In fact, your example demonstrates that it does not really: 
With your construction the answer may depend on how "1" and "2" are
encoded. For instance, if |k| is exactly a block-size, and you encode "1"
as a block of 1's, and encode "2" as two blocks of 1's, then k2 is easily
computable from k1 if SHA1 is used.
 
The trick is to be able to show how to derive keys using SHA1, while
making the weakest assumptions on SHA1. If you define k1=HMAC_k(1) and
k2=HMAC_k(2) then k1 and k2 will be "computationally independent" under
relatively weak assumptions on SHA1, regardless of how "1" and "2" are
encoded. (In particular, you would not need to assume that "SHA1 behaves
like an ideal function".)

Ran

> versa. What will happen if we replace H with SHA-1?

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

---

From: David Hopwood <[email-masked]>
Date: Thu, 10 Jul 2003 16:09:14 +0000

-----BEGIN PGP SIGNED MESSAGE-----

> computable from k1 if SHA1 is used.

I think you mean that "1" and "2" would have be encoded in such a way that
the result of padding k || "1", taking into account the length field, is a
prefix of k || "2"; in that case k2 is easily computed from k1.

I agree that it is better to use HMAC for key separation than a plain hash
function.

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip