The birthday paradox in action: calculating the probability of a hash collision

http://www.solipsys.co.uk/new/TheBirthdayParadox.html?HN2

by ColinWright • 14 years ago

100 43 14 years ago

solipsys.co.uk

Xylakant2• 14 years ago

It is very important to note that this is the probability that any two hashes collide in a set of hashes. It is not the probability to find a second plaintext that hashes to the same hash as a given one. It's far harder to find a colliding value to a given one than to just grab a group of values and have two of them hash to the same hash.

ColinWright6• 14 years ago

Indeed, pretty much exactly that point is made in the third box on the right:

    In case you are one of the many, many people who get this wrong
    and are astonished, you may be thinking of a different question.
    My birthday is a specific date. If we assume birthdays are
    uniformly distributed, how many people must you ask before you
    find someone who has the same birthday as me?

    On average, about 182.

    If you ask some 150 to 200 people, the odds are about 50% that
    you'll find someone who shares my specific birthday.

    But that's not the question I asked. They don't just need to share
    my birthday, it can be that any birthday is shared among them, and
    that changes the odds dramatically.

dsego2• 14 years ago

I don't see how that point relates to Xylakant's comment. The text you quoted basically points to the difference between these two cases:

1) that if you have a specific hash, how many more hashes would have to be generated to get the same hash.

2) how many hashes would you have to generate before a collision occurs between any of them.

So in the two cases above we're dealing with sets of hashes, and we don't care how they are generated.

Xylakant's comment was about a different type of collision. This collision happens because you are mapping an arbitrary large text into a fixed size hash, which means that different texts can map to the same hash, hence creating a collision.

davidjohnstone• 14 years ago

I once made a little web page that calculates the probability of a hash collision: http://davidjohnstone.net/pages/hash-collision-probability

maebert• 14 years ago

In Python: https://gist.github.com/4031135

Peaker• 14 years ago

In Haskell: http://hpaste.org/77404

bigiain2• 14 years ago

So has anyone yet done the calculation to work out how many files github will need to store to have a non-negligeable chance of hash collisions in the git file names? Or perhaps the linux kernel?

dbaupp3• 14 years ago

The formula given at the end of the article implies that to have a 5% chance of a collision you would need 3.87e23 objects. (SHA-1 is 160 bits.) Even storing 1 trillion objects gives a collision probability of 3e-19.

So this is unlikely to be a concern, ever.

bigiain2• 14 years ago

Hmmm, I wonder how many objects are currently stored in S3? And what rate that's rowing at? Or how many documents Google has stored in bigtable?

But yeah, 160 bits is probably "enough" :-)

rmc• 14 years ago

Doesn't even need to be in filenames, but the content of files aswell.

dbaupp3• 14 years ago

I believe bigiain is referring to the fact that git objects are stored by their SHA-1 digest (so a hash-collision will cause a collision in these filenames) not the filenames of the contents. (The objects are stored under the .git/objects directory, in the format xx/y...y, where the directory xx is the first two digits of the digest, and the 38 y's are the rest of the digest.)

VMG• 14 years ago

Hidden gem on the right side:

[...] People often ask why they need to memorise formulas, or why they need to practice solving equations, when they can simply look stuff up whenever they need it, and on-line computer algebra systems can solve equations faster than they can, and more reliably.

But this is an example of why the ability simply to look stuff up is near useless on its own. Searches are deep and wide, and you need intuition to guide you. You need to recognise what might work, things you've seen before, directions to take that are more likely to be fruitful. [...]

loonoddoo• 14 years ago

In what sense is the birthday paradox a paradox?

DanBC• 14 years ago

It's sometimes called the Birthday Problem to avoid the paradox label. (See, for example, the wikipedia article.)

The paradoxy bits of the problem are the things that people find confusing. "Only 23?!" or "So if there are 23 people in a room there's a 50% chance that one of them will share a birthday with me?"

pendext2• 14 years ago

Is "So if there are 23 people in a room there's a 50% chance that one of them will share a birthday with me?" correct? If you pick a fixed person (you) that would break the pigeonhole principle, I think.

I would think that saying "So if there are 23 people in the room there is a 50% chance any 2 of those people share the same birthday" is better.

Edit: I misunderstood, you're saying that other people are misunderstanding. My mistake!

utopkara• 14 years ago

It is not a logical paradox, it is very counterintuitive. With just about 23 samples, you'll have a birthday collision with 50% chance. Many people would think to get 50%, you'd need 183 samples.

It is also counterintuitive, because it is unavoidable. Even with a very large hash range, one can force a collision with a relatively small number of samples.

dbaupp3• 14 years ago

The same sense that the Banach-Tarksi paradox[1] is: it's a counter-intuitive mathematical truth.

[1] https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

mikeash• 14 years ago

"a seemingly absurd or self-contradictory statement or proposition that when investigated or explained may prove to be well founded or true: in a paradox, he has discovered that stepping back from his job has increased the rewards he gleans from it."

pedrocr• 14 years ago

That's a neat formula, and directly applicable to having a bunch of objects in a git repository.

Applying the formula for 160bit SHA-1 you need 1.7e23 objects to get a 1% chance of collision. The current Linus kernel repository has 2.7 million objects. So to get a collision you'd need a repository that's 6e16 times larger. That should be plenty.

For some wacky perspective that's 10 million kernel sized contributions for every man woman and child on earth together in a single repository. It would seem git will reach plenty of other bottlenecks before SHA-1 becomes a problem...

viraptor• 14 years ago

It is a huge number. Of course the fun part is that after precisely calculating that probability and proving that we don't have anything to worry about, the next commit we make could collide... and it will be the only git collision within the history of human race.

Probabilities are fun, because anything non-zero is non-zero ;) (I don't expect to ever witness a git hash collision of course)

ericcholis• 14 years ago

My favorite header ever "Mathematicians aren't normal people". The numbers, they're everywhere!!!

cmurphycode3• 14 years ago

At my day job, SHA-1 is the basis for our deduplication. As such, we love talking about frames of reference for the probability of a SHA-1 collision. One of our presentations includes such facts as "the probability of dying in a vending machine accident", etc.

If you enjoy this stuff, you'll get a pleasant tickle out of this one:

What is the probability that there exists a SHA-1 hash which hashes to itself? In other words, are there any fixed points?

(This post was edited to fix the phrasing mistake nicely pointed out by a commenter. Originally, I asked "probability that a SHA-1" when I meant "probability that any SHA-1")

Dylan168073• 14 years ago

Pleasant tickle? Isn't it just 1/max(SHA-1)?

I do get a pleasant tickle from expanding that to the question of if there is any fixed point in SHA-1, but the chance for a particular value is the answer you always get for "what is the chance of a specific hash".

Someone• 14 years ago

Nitpick: proofing that (as opposed to showing it to be likely by hashing a few zillion candidate keys and computing stats on their hashes) may be a bit of a challenge.

I am making this remark because the question reminded me of the question "If it is the 13th of the month, what is the probability that it is Friday?" (no tricks with weird calendars; you should just use the Gregorian one).

jlgreco• 14 years ago

If there are max(SHA-1) hashes, and a 1/max(SHA-1) chance any particular one will hash to itself, does that mean we would expect only a single instance of a hash hashing to itself?

I have no idea how you might go about finding that one expected instance.

cmurphycode3• 14 years ago

Yeah, that was a phrasing mistake in my original post. I meant if there are ANY hashes that hash to itself (any fixed point). Thanks for noticing.

JadeNB2• 14 years ago

> Pleasant tickle? Isn't it just 1/max(SHA-1)?

Only if there is a unique fixed point ….

JadeNB2• 14 years ago

This sounds snarky, but I mean it as a genuine question about your revised post: what do you mean by asking about the probability of something that either definitely happens or definitely doesn't? That is to say, either there is a fixed point or there isn't; in either case, I can't see even an informal way to assign any probability other than 0 or 1 to the question.

ColinWright6• 14 years ago

We can say:

    Without using any knowledge about how they are
    computed, & only using the fact that a hash is,
    in effect, a result chosen uniformly at random
    from a set of results, what is the probability
    that ...

So in particular, consider a collection of numbers, and for each one, choose a target uniformly at random from the same collection. So for the set X you have a function f:X->X. What is the probability that there is a fixed point x such that f(x)=x?

This, by the way, is a very well known calculation/result in my area of math.

cmurphycode3• 14 years ago

Colin explained it, but I wanted to apologize for the dissonance. Essentially, I'm phrasing the abstract "pick an element, then pick again" problem in terms of SHA collisions. Just for fun.

im3w1l• 14 years ago

bar zvahf qrenatrzragf bire crezhgngvbaf

frr uggcf//ra.jvxvcrqvn.bet/jvxv/Qrenatrzrag#Yvzvg_bs_engvb_bs_qrenatrzrag_gb_crezhgngvba_nf_a_nccebnpurf_.R2.88.9R

wlesieutre• 14 years ago

ROT13ed and fixed the link:

one minus derangements over permutations

see

https://en.wikipedia.org/wiki/Derangement#Limit_of_ratio_of_...

alexcsm• 14 years ago

Interesting analysis on the collision angle.

For those interested in another look (basic) at the Birthday Paradox, check out http://alexanderle.com/blog/2011/birthday-paradox.html !

mauerbac• 14 years ago

I just took an exam on this....

The birthday paradox in action: calculating the probability of a hash collision

Related Stories