Subject: [Cfrg] Re: one question about hash

From: "John R. Black" <[email-masked]>
Date: Thu, 10 Jul 2003 11:20:29 -0600

> Date: Wed, 9 Jul 2003 15:15:24 -0400 (EDT)
> From: canetti <[email-masked]>
> 
> 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.
>  

Ran,

You're assuming that you can extend SHA1(k || 1^n) to SHA1(k || 1^{2n})
without knowing k?

Remember that SHA1 (and SHA-{256,384,512}) all use MD-strengthening so
the bit-length of the hashed msg is encoded in the final bits of the
input before it is hashed.  This means it is non-trivial to extend a
SHA1 output.

john//

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

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 11 Jul 2003 00:03:43 +0300 (IDT)

Don't take Ran's example too literally.
What he was pointing out to (even if he did not say this explicitly) is
that even if the compression function of SHA-1 is a totally random
function then the iterated SHA-1 is not. In particular, this brings up the
issue that using plain SHA-1 your security may depend on the way you
encode the input to the function. 

To make Ran's example really work you have to encode 1 as a string of 448
(=512-64) 1's, and encode 2 as the concatenation of 448 1's followed by a
64-bit representation of the number 2^63+448, followed by another 448 1's.
Surely enough, no one is going to use such an encoding but, again, the
point is in showing that the iterated SHA-1 is not random (or unpredictable 
for this matter) even if the compression function is.

These considerations however do not really answer the original question
that arises in natural settings, namely, are SHA1(k,1) and SHA(k,2)
"computationally independent", if we fix the encoding to be 160 bits for
the key followed by a single octet representing 1 or 2 (or 0 and 1)? Here
the answer is: we do not realy know. Or, with a more optimistic twist: as
far as we know today, this is ok.

Yet it is always good to use standard constructions with security proven
independently of the application and other specifics such as the semantics
of the data or its encoding. In that sense HMAC is a good solution.
Especially that it enjoys a proof of security based on much less that
"ideal" assumptions on the compression function.  
In addition, I personally do not like "counter mode" constructions where
the only difference between two inputs to the function (as is the case
with SHA1(k,1) and SHA(k,2)) is by one or two bits at most. In my opinion,
robustness to cryptanalytical advances calls for more prudent designs.  
In this sense, HMAC has a significant contribution via its "double hashing". 
Moreover, as in the case of TLS and IKE, also here I'd recommend
"feedback mode" for key derivation; in the above example we would have
K1=HMAC-SHA1(k,1) and K2=HMAC-SHA1(k,K1)).

Finally, there is also a drawback to using HMAC. While SHA-1(k,i) takes
only one application of the compression function, HMAC would take two (or
even three, if you do not cache the initial value produced by the first
iteration of HMAC). This may be totally negligible (especially in the case
of key derivation) but may be significant in other situations (e.g. when
implementing defenses against DoS attacks). In these cases the engineering
trade-offs (and possibly the less stringent security requirements) may
justify going to the less robust solutions

Sorry for the long response, I just wanted to write the first paragraph
but found myself in a too talkative mode...

Hugo

---

From: "Anton Stiglic" <[email-masked]>
Date: Fri, 11 Jul 2003 11:43:28 -0400

> the answer is: we do not really know. Or, with a more optimistic twist: as

If you consider SHA1(k, .) as a PRF, and the input is prefix-free (that is
the
case say if the representation of 1, 2,... is made in say n octets for some
fixed
n), then results of the paper "The Cascade Construction and its Concrete
Security"
(by Hugo, Ran, and Mihir) apply.  By that I mean (informally) that if you
assume
that the compression function of SHA1 makes for a good Finite-length Input
PRF, and assume some other pseudoranmness properties about the compression
function (which are also assumed in the proof of HMAC), then SHA1(k,.) makes
for a good PRF (assuming k is chosen randomly of course...).

These are about the same assumption needed to prove that HMAC based on SHA1
makes for a good PRF (note that I'm not talking about the proof that HMAC is
a good
MAC, which assumes that the compression function acts like a good MAC, which
is
possibly a weaker assumption).

So I don't understand why you state that we don't really know about the
security
of such a scheme.  I say we know as much about the security of SHA1(k,.) as
a PRF, with prefix-free inputs, that we know about HMAC-SHA1 on variable
inputs.

But Hugo you are one of the authors of the paper I referred to, so you
surely have
more insight than I do, can you elaborate? Is it really just an educated
feeling you have
that makes you say that HMAC-SHA1 would be better because the inner hash
randomizes in some sense the inputs to the PRF?

--Anton

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 11 Jul 2003 21:06:37 +0300 (IDT)

In order to apply the results from the paper you mention to SHA1(k,...)
you have to assume that k occupies a full block (i.e. the input is aligned
to start in the second block) and that (as you say) the inputs are ensured
to be prefix-free (i.e. the atacker will never see the output of the
function on two different inputs x and x for which x is a prefix of x'). 
This strong requirement for prefix-freeness is avoided at all by hmac and
in that sense hmac is a (significantly) better prf construction than 
SHA1(k,...) for general use.

For the specific case of key derivation the prefix-freeness may be less of
a problem if you are careful enough to design the input to the function in
the key-derivation process to be prefix-free. But the original question
talked about SHA1(k,i) which I guess (that is the usual and natural case)
was intended to mean k concatenated with the index i all filling in one
block. In this case the analysis of the mentioned paper does not apply
(or at least requires a re-modelling of the prf family).

Besides, as you hint to I also like the "double hashing" of HMAC as a
"robustness measure" (or second line defense).

Hugo