News for hackers. Stuff that matters.
Re:The birthday paradox in action: calculating the probabili... by cmurphycode on Wednesday November 07, 2012 @11:28AM (#4753921)
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")

Re:The birthday paradox in action: calculating the probabili... by JadeNB on Wednesday November 07, 2012 @02:27PM (#4754759)
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.
Re:The birthday paradox in action: calculating the probabili... by ColinWright on Wednesday November 07, 2012 @02:31PM (#4754782)
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.

Re:The birthday paradox in action: calculating the probabili... by cmurphycode on Wednesday November 07, 2012 @03:40PM (#4755088)
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.
Re:The birthday paradox in action: calculating the probabili... by Dylan16807 on Wednesday November 07, 2012 @12:42PM (#4754299)
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".

Re:The birthday paradox in action: calculating the probabili... by cmurphycode on Wednesday November 07, 2012 @01:20PM (#4754482)
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.
Re:The birthday paradox in action: calculating the probabili... by Someone on Wednesday November 07, 2012 @01:03PM (#4754407)
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).

Re:The birthday paradox in action: calculating the probabili... by jlgreco on Wednesday November 07, 2012 @01:05PM (#4754413)
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.

Re:The birthday paradox in action: calculating the probabili... by Dylan16807 on Wednesday November 07, 2012 @01:26PM (#4754504)
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.
Re:The birthday paradox in action: calculating the probabili... by JadeNB on Wednesday November 07, 2012 @02:27PM (#4754764)
> Pleasant tickle? Isn't it just 1/max(SHA-1)?

Only if there is a unique fixed point ….

Re:The birthday paradox in action: calculating the probabili... by Dylan16807 on Wednesday November 07, 2012 @10:56PM (#4756446)
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.
Re:The birthday paradox in action: calculating the probabili... by im3w1l on Wednesday November 07, 2012 @03:56PM (#4755151)
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

Re:The birthday paradox in action: calculating the probabili... by wlesieutre on Wednesday November 07, 2012 @04:55PM (#4755381)
ROT13ed and fixed the link:

one minus derangements over permutations

see

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