Question

A cryptographic hash takes a message as input and produces a fixed-length string as output, called the digital fingerprint. A brute force attack involves computing the hash for a large number of messages until a pair of distinct messages with the same hash is found. Find the number of attempts required so that the probability of obtaining a match is How many attempts are required to find a matching pair if the digital fingerprint is 64 bits long? 128 bits long?

Answer 1

`1.85x10^(19)` attempts are required to find a matching pair if the digital fingerprint is 64 bits long.

`3.40*10^(38)` attempts are required to find a matching pair if the digital fingerprint is 128 bits long.

Explanation:

Each bit has two options. So

How many attempts are required to find a matching pair if the digital fingerprint is 64 bits long?

So for each of the 64 bits, we have the following number of options.

2 - 2 - 2 - 2 -... - 2

So, in all, there are

`T = 2^(64) = 1.85x10^(19)`

options.

So,
`1.85x10^(19)` attempts are required to find a matching pair if the digital fingerprint is 64 bits long.

128 bits long?

Using the same logic as the first question.

`T = 2^(128) = 3.40*10^(38)`

So,
`3.40*10^(38)` attempts are required to find a matching pair if the digital fingerprint is 128 bits long.