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…
- Comment
- Reblog
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
CMSC414: Computer/Network Security 
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?