10
$\begingroup$

I came across a question stating:

We have a message consisting of 10,000 characters. After computing its message digest using SHA-1, we decide to change the last 19 characters in the original message. How many bits in the digest will change if it is recomputed, and why?

Until and unless this is an explicit attack on the hashing scheme, the new hash would be different than the original one (sort of exhibiting an avalanche effect).

But I am unable to understand how does small changes in the input text affect their corresponding hashes. Like does there exist a relationship on how many bits of the hash will be affected, if a certain change is done to the input text?

P.S.: I am not a 100% sure, but I believe I have read it somewhere that a hashing algorithm should change the bits of hash by $X$% if a new character/bit is added/substituted to the previous input text.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ See also Hash functions and the Avalanche effect $\endgroup$
    – kelalaka
    Commented Jul 16, 2019 at 20:33
  • 2
    $\begingroup$ This sounds like a good job interview question. (Of the fizz buzz test kind, anyway.) It must either be a trick question or come from someone that doesn't understand hash functions. There isn't supposed to be any such relationship for a cryptographic hash. (Which isn't to say SHA-1 is safe...) $\endgroup$
    – Future Security
    Commented Jul 16, 2019 at 21:42
  • 5
    $\begingroup$ The statement "last 19 characters" is a red herring. Any change in the input on average changes half of all bits - anything else would be a serious issue for its properties. Considering the state of SHA-1, even if it is considered broken, this should still apply. $\endgroup$
    – tylo
    Commented Jul 17, 2019 at 1:52
  • 1
    $\begingroup$ Related is the idea of differential cryptanalysis, which tries to find sets of input pairs such that the corresponding output pairs' bits differ by something other than the usual 50% $\endgroup$
    – Joel
    Commented Jul 17, 2019 at 14:10
  • $\begingroup$ @Joel Thanks for referring to an application of this question! $\endgroup$
    – Vasu Deo.S
    Commented Jul 17, 2019 at 14:13

3 Answers 3

Reset to default
26
$\begingroup$

For any one of the SHA hashes, the hash should be indistinguishable from pseudo-random. That means each and every bit flips with a chance of 50%. So on average half of the amount of bits gets flipped, as long as the input message doesn't repeat (because that will match 100% with the hash of the identical message, of course). It doesn't matter how many input bits are removed, added or altered, this is always the case as long as the input message isn't identical to the previous one.

Hashes are likely well distributed, so the likely number of bits that get flipped is a bell curve like you would get by throwing dice. Same thing for the number of zero bits - or one bits of course. So you cannot give an absolute number as an answer to this question. The result is not a function on $x$ if $x$ is the number of bits flipped in the input - as long as $x$ is larger than zero.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ Yes, exactly. The chance of no change is the same as finding a specific collision of course. The chance of all bits changing is exactly as low (bell curve, right?). The chance that exactly half the bits changing is the highest, but the chance that half minus one bits are changing is pretty high as well (again bell curve). The only formula that describes this is, of course, the hash function itself. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 16, 2019 at 19:22
  • 2
    $\begingroup$ I did elaborate on it. Bell curve. The highest bar (we're working with discrete numbers here, so not a line but bars) is the most likely. Just like 7 is most likely if you throw two dice. But 6 and 8 are pretty likely as well. 5 and 9 a lot less so, 4 and 10 are pretty unlikely, 3 and 11 are rather unlikely, but only just not as unlikely as 2 and 12. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 16, 2019 at 21:25
  • 1
    $\begingroup$ @VasuDeo.S Given a hash of length N, in how many ways can you change 1 bit? N (you can change bit 0, or bit 1, or bit 2...., bit N-1). In how many ways can you change 2 bits? You can change bit 0, and then you can change 1 bit out of the remaining N-1, then change bit 1 and change one bit of the remaining N-2, ... in the end it's N*(N-1)/2. The number of ways becomes bigger the more "freedom" you have in choosing which bits to flip. Maximum freedom is when you can choose half of the bits (the thing is symmetric with choosing which bits remains the same). $\endgroup$
    – Giacomo Alzetta
    Commented Jul 17, 2019 at 7:32
  • 3
    $\begingroup$ Strictly speaking, it's not a bell curve, it's a binomial distribution with p = 0.5. But with large n, such as you'd get with a hash output, it's close enough to a normal distribution that you can treat it as one. $\endgroup$
    – Mark
    Commented Jul 17, 2019 at 21:51
  • 2
    $\begingroup$ @MaartenBodewes So, from what I understood is (Rectify me if I am wrong). The math is $160 bits$ with each bit having a $.5$(50% chance) probability of changing state => $160 * .5 = 80 bits$, in general will change their state. (this deduction is made keeping in mind, that the output of hash function is pseudo random) $\endgroup$
    – Vasu Deo.S
    Commented Jul 18, 2019 at 6:54
10
$\begingroup$

how many bits in the resultant hash will change, if the x bits are changed in its the original input

50% on average, regardless of how many bits are changed.

SHA-1, like all cryptographic hash functions, attempts to model a pseudorandom function according to the random oracle model.* This means that any change to the input will result in, on average, 50% of the output bits changing. Another way to put it is that each bit has exactly a 50% chance of toggling when the input changes. It doesn't matter what the input is and whether it differs by a single bit or nineteen bits.

In the random oracle model, every output bit is completely independent of every other bit. Because we don't have access to a "real" random oracle, we can only approximate it using mathematical functions. While this does mean that the output bits are not independent, they appear to be, and any distinguisher would constitute a cryptanalytic attack against the core hash function, which would be pretty big news.

* It doesn't model it perfectly, as evidenced by both the length extension attack and extant collision attacks, but that doesn't matter for the sake of your question. Despite its weaknesses, it still exhibits the avalanche effect extremely well.

Improve this answer
$\endgroup$
6
$\begingroup$

Actually, the number of changed bits is approximated by using a formula. It's about 80 with a 6% probability. As you've guessed, the hash exhibits an avalanche effect. On average each output bit will flip with a probability $P =0.5$ if an input bit flips. And the output bits are independent of each other (as far as we can tell). Thus one input flip or multiple input flips has the same effect. That generates a classic Binomial distribution defined as $Bin(160, 0.5)$, resulting in $\mu = \frac{160}{2}, \sigma = \frac{\sqrt{160}}{2}$.

And it will look like this:-

dist

Improve this answer
$\endgroup$
1
  • $\begingroup$ The output bits are independent of each other? Huh? It's a hash function. $\endgroup$
    – forest
    Commented Jul 23, 2019 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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