Encryption and authentication protocols

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…

2 Responses to “Encryption and authentication protocols”

  1. Anonymous Says:

    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 šŸ™‚

  2. osmugus Says:

    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:

    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^(|
    = 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: