Hacker News Reader

Comment by cmurphycode | Hacker News Reader

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")

View on HN

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.

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.

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.

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".

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).

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.

You would expect about 1 per unflawed hash function tested. But the law of averages is less powerful when you focus on a specific hash. The chance of having no fixed points in a particular unflawed hash is 1/e, so there is probably a fixed point, and possibly more than one.

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.

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

Only if there is a unique fixed point ….

Not really. If we're talking about abstract probability over hash functions it's the same no matter how many fixed points SHA1 happens to have. If we talk about concrete numbers then it's actually 1 or 0 for each hash.

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

ROT13ed and fixed the link:

one minus derangements over permutations

see

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

Reply on news.ycombinator.com