In case you missed it, a question I asked on this blog way back in lecture 4 has generated a bit of discussion (which I am glad to see!). I’ll try to come up with similar questions on other lectures…

University of Maryland, College Park

In case you missed it, a question I asked on this blog way back in lecture 4 has generated a bit of discussion (which I am glad to see!). I’ll try to come up with similar questions on other lectures…

%d bloggers like this:

September 29, 2009 at 7:03 pm |

I am looking forward to them impatiently.

In my opinion that kind of questions would be very helpful for learning. As you try to answer a question, your facing with new questions in your minds. Once you are believing that you solved them, if you think a little more, you are facing with new problems and questions. The only question is where is the end of this pleasant journey š

November 16, 2009 at 4:20 pm |

I think a have found a problem which is quite challenging and similarly important the one in Lecture 4. I think, understanding it helps to really understand hash functions. It may even be an example of a crypto pitfall if the evaluation below is correct.

In this post (http://www.mail-archive.com/cryptography@metzdowd.com/msg11041.html), a hash construction is proposed as follows.

C(x) = H1(H1(x) || H2(x))

The hope is that this construction is is stronger than either of its two underlying hash functions H1 and H2.

I am not sure, but I would intuitively say that the construction C is just as secure as H1.

Here is a try for proofing this intuition in which I am not sure:

let

y = C(X) = H1(H1(X) || H2(X)) = H1(X’) with X’ = (X’1 || X’2)

Consider the H1(X’) part of the construction. (|H1|+|H2|)-bit inputs are

mapped to (|H1|)-bit outputs. This means for every output “y” that are 2^(|

H2|) possible inputs.

Now, consider the probability of the following event:

y = C(K) = H1(H1(K) || H2(K)) = H1(X”).

This means find a X” hashing to y. There are 2^(|

H2|) such inputs as shown above.

Therefore we need to compute the probability

= Pr[H1(K) = X”1 and H2(K) = X”2]

= Pr[H1(K) = X”1] * Pr[ H2(K) = X”2]* 2^(|

H2|)

= 1/2^(|H1|)

Obviously, this is equal to the security level of H1.

Do you have any comments if I am thinking wrong or right?