5 ms·

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

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

Dylan16807 14y 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 14y 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 14y 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.
  - Dylan16807 14y ago
    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.
- cmurphycode 14y 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.
- JadeNB 14y ago
  > Pleasant tickle? Isn't it just 1/max(SHA-1)? Only if there is a unique fixed point ….
  - Dylan16807 14y ago
    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.
JadeNB 14y 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.
- ColinWright 14y 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.
- cmurphycode 14y 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 14y 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 14y ago
  ROT13ed and fixed the link: one minus derangements over permutations see https://en.wikipedia.org/wiki/Derangement#Limit_of_ratio_of_derangement_to_permutation_as_n_approaches_.E2.88.9E https://en.wikipedia.org/wiki/Derangement#Limit_of_ratio_of_...

Dylan16807 14y 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 14y 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 14y 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.
- Dylan16807 14y ago
  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.
cmurphycode 14y 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.
JadeNB 14y ago
> Pleasant tickle? Isn't it just 1/max(SHA-1)? Only if there is a unique fixed point ….
- Dylan16807 14y ago
  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.

JadeNB 14y 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.

ColinWright 14y 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.
cmurphycode 14y 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 14y 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 14y ago
ROT13ed and fixed the link: one minus derangements over permutations see https://en.wikipedia.org/wiki/Derangement#Limit_of_ratio_of_derangement_to_permutation_as_n_approaches_.E2.88.9E https://en.wikipedia.org/wiki/Derangement#Limit_of_ratio_of_...