Hacker News Reader

Comment by Dylan16807 | Hacker News Reader

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

View on HN

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.

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.

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

Reply on news.ycombinator.com