Question

Q2 1. If Alice and Bob decide to use a hash function where the hash output is a 512-bits-long binary string, given a message m and its corresponding hash output h(m), what is the average probability that an attacker Eve can send another message m' ‡ m that has the same hash output? In your computations, assume that Eve make 261 attempts. 2. If Alice and Bob decide to use a hash function where the hash output is again a 512-bits-long binary string, how many attempts, on average, would Eve have to make to find two messages m and m' that are not the same, but have the same hash output.

Answer 1

The probability that Eve can find another message with the same 512-bit hash output as the original message after 2^61 attempts is 1/2^451. To find any two messages with the same hash, Eve would need to make approximately 2^256 attempts on average.

Step-by-step explanation:

Probability of a Collision in Hash Functions

1. For a hash function with a 512-bit output, assuming a perfectly random hash function, the probability of a hash collision (different messages yielding the same hash) is 1/(2^512).

Given that Eve makes 2^61 attempts, the chance of her finding a collision is approximately 2^61/2^512, which simplifies to 1/2^451.

This is still an extremely small probability, demonstrating the security of a 512-bit hash function against collision attempts.

This calculation assumes that the hash function behaves like a random function (the ideal situation).

2. According to the birthday paradox, to find two messages that produce the same hash, it's not necessary to try all 2^512 possibilities.

Instead, the number of required attempts is the square root of the number of possible hash outputs, hence 2^(512/2) or 2^256 attempts on average are needed to find a collision.