4
$\begingroup$

Question

When determining the security of a hash system, the cryptanalyst tries the following attacks.

(a) If the attacker is NOT allowed to modify the original message, determine the number of hash calculations that would be required to have a 50% chance of generating a new message with the same hash as the original message. In your calculations, assume the hash length is 8 bits.

(b) Derive the expression of number of hash calculations, $n$, required to have a 30% chance of generating two different messages with the same hash. Determine the approximate value of $n$.

My Answer

These are what I think is correct, please let me know if I am wrong, Thank you!

a)

$\text{Hashed} = \big(\frac{2^8}{2}\big)$ = $\big(2\big)^7$

$p = 1 - \big(\frac{(2^7-1)}{2^7}\big)^n$

$n = 88.38 \rightarrow n = 89$.

b)

$\text{Hashed} = \big(2^\frac{8}{2}\big)$ = $\big(2\big)^4$ = $16$

$p(n) = 1 - (\frac{\text{Hashed}!}{\text{hashed}^n(\text{hashed}-n)!})$ = $1 - (\frac{16!}{16^n(16-n)!})$

$p(n) = 1 - e^{(-n^2+n/2 \times 16)}$

$n = 4.57 \rightarrow n = 5$

Birthday Attack

$q(n) = 1 - \big(\frac{365-1}{365}\big)^n$

$\endgroup$
  • 10
    $\begingroup$ Just a note: "Hash" (short for "hash function") is not an acronym, so it doesn't need to be written in all-capitals. $\endgroup$ – Paŭlo Ebermann Jun 14 at 21:06
  • $\begingroup$ @PaŭloEbermann I just joined this community, thanks to HNQ, to note that you can edit the question. We get this a lot with "visa" over on Travel. $\endgroup$ – phoog Jun 15 at 16:29
  • $\begingroup$ And Java at Stack Overflow $\endgroup$ – OrangeDog Jun 15 at 16:33
  • $\begingroup$ @phoog thank you, I'm aware of this (I've got the copy editor badge both here and at Stack Overflow). I guess I should have been less lazy in this occasion too. $\endgroup$ – Paŭlo Ebermann Jun 15 at 20:45
7
$\begingroup$

What needs to be memorized in applied science (physics, crypto) is not a set of formulas. It's, for a few of the simplest formulas studied: what the formula yields, for what inputs, the units for inputs and output, and how to derive the formula when it does not boil down to multiplying or dividing the inputs in a way that can be found from the units. When one can't derive a formula or don't know its units, it's risky to apply it in real life¹.

We have an illustration: the question originally came with all the right formulas, but what the inputs should be was lost, or in the wrong unit (number of hashes versus hash length in bits), as quickly hinted by the terser answer. And for the now added formula-as-a-picture $q(n)=1-\left(\frac{365-1}{365}\right)^n$ it is lost what the formula yields, which has next to no relation with a birthday attack, contrary to the formula's heading.

That formula gives the probability that among $n$ persons, at least one was born on the 4th of July² of some unspecified year, assuming even repartition of birth days of humans on each of 365 days in a year³, and random selection of the $n$ humans⁴.

How do we derive a formula for that probability $q(n)$ ? Picture a room. Let $n$ be the number of persons in the room, $k=365$ the number of days in a year. If the room is empty, no one in the room was born on the 4th of July. Thus $q(0)=0$. Now, picture persons entering the room one by one (nobody leaves) until there are $n>0$. Someone in the room was born on the 4th of July if and only if at least one of two events hold:

  1. Before the last person who entered the room did so, there was already one person born on the 4th of July. The probability of that event is $q(n-1)$, by the definition we give to $q$.
  2. The last person who entered the room was born on the 4th of July. The probability of that event is $1/k$ and independent of $n$ and of the previous event (under hypothesis above following "assuming").

There's a formula for the probability that one of multiple independent events hold. Do yourself a favor and forget about it. Instead: if the probability of an event does not come evident, try the complementary event. Here that complementary event is: nobody in the room was born on the 4th of July. It should be clear that in our (non-empty) room there's nobody born on the 4th of July if and only if that held before the last person entered the room, and that person was not born on the 4th of July, which is the complementary event of (2.) above.

Now it's time to apply three indispensable rules in probability:

  • The probability that independent events all hold is the product of their probabilities.
  • The probability of the complementary event is 1 minus the probability of the event.
  • Independence of events is maintained when going to the complementary event.

And we get: $\forall n>0$, it holds $1-q(n)=(1-q(n-1))\times(1-1/k)$.

By induction, or directly by applying the first rule to all persons in the room, it comes $1-q(n)=(1-1/k)^n$, which we can rewrite as $$q(n)=1-\left(\frac{k-1}k\right)^n$$ and obtain the question's formula for $k=365$.


How does that apply to the question then? Well, in (a) we want the probability that $n$ hashes of $b=8$ bit length have the same value as a the hash of a particular message. Picture a hash as an 8-bit value like $\tt 01100101$. Under the standard assumption that the hash function (the thing producing hashes from messages) behaves as a random function, the hashes behave as random values among $2^b=2^8=256$. That parallels the birth days of people in the room, which behaves as random values among $k=365$. We can thus adapt our existing formula, replacing $k$ with $2^b=2^8=256$, and get $q(n)=1-\left(\frac{2^b-1}{2^b}\right)^n$ or the equivalent $q(n)=1-\left(1-2^{-b}\right)^n$.

Here, we can directly apply that formula since $b=8$ is small. But take note that in cryptography, our hashes often use much larger values of $b$, e.g. $b=224$ would be considered a bare minimum nowadays in some applications. That formula still holds, but we can get into issues with its numerical stability. Using an ounce of math around that is not hard.

I really suggest that a student derives the formula for question (b), and only uses the ones in my Birthday problem for cryptographic hashing, 101 to verify the outcome, or after trying hard.


¹ Wrongly applying formulas can kill or cause huge losses, in engineering, chemistry, medicine, and business. In higher ed, well-thought notation at such exams should IMHO penalize incorrect answers, much more than no answer vs correct answer.

² That also works for my birthday, or any particular day in the year except February 29th.

³ An approximate model, mostly because reproductive activity is seasonal in most species, including humans to some degree.

⁴ That hypothesis could be seriously wrong at an exam for the driver's license.

| improve this answer | |
$\endgroup$
4
$\begingroup$

You're wrong. Hint: a value of 8 bits has 256 possible values, not 8.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I have changed my answer, please let me know if i did it correctly. $\endgroup$ – John Jun 14 at 13:06
  • 1
    $\begingroup$ @Johon: closer, but still far from OK. Poncho's hint remains. You are trying to apply $p(n)=1-\left(\frac{k-1}k\right)^n$ for (a) and $p(n)=1-\frac{k!}{(k-n)!\;k^n}$ for (b). There are the right formulas, but you miss what $k$ is. Rather than guessing that, what about deriving these formulas from simple principles, so that what $k$ is becomes clear from the onset? That's simple for the formula for (a). It's a little more involved for (b), and I have tried my best at an explanation with Birthday problem for cryptographic hashing, 101. $\endgroup$ – fgrieu Jun 14 at 13:58
  • $\begingroup$ @fgrieu Ok so is k = 2^8 = 256 bits then? I'm just confused cause in my notes it says for a naive approach: Birthday paradox where someone tries to find another person with same birthday = (2^hashsize)/2 = (2^8)/2 = 2^7. And then it says less naive approach: Birthday paradox where someone tries to find any two people in a room with the same birthday = 2^(hashsize/2) = 2^(8/2) = 2^4 $\endgroup$ – John Jun 14 at 14:38
  • $\begingroup$ @John: the statement says "assume the HASH length is 8 bits". Picture yourself what that means: a hash values is on the tune of $\tt 01100101$. How many distinct possible hashes are there? That's similar to: how many distinct birthdays (discounting year) are there. This is $k$. This is NOT "256 bits", much like the numbers of distinct birthdays (discounting year) is not "365 digits". Again, it's best to derive the formulas, not apply them. And forget about the part of the notes ending with $2^8/2$, it is only meant to show what a (broken) intuition could tell. $\endgroup$ – fgrieu Jun 14 at 15:03
  • $\begingroup$ @fgrieu I have attached an extract from my notes that shows for an actual birthday example, 365 digits was chosen for k. $\endgroup$ – John Jun 14 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.