On Tue, Feb 23, 2016 at 11:44 AM, Jon Ribbens <jon+use...@unequivocal.co.uk> wrote: > On 2016-02-23, Chris Angelico <ros...@gmail.com> wrote: >> On Tue, Feb 23, 2016 at 11:26 AM, Jon Ribbens >><jon+use...@unequivocal.co.uk> wrote: >>> On 2016-02-23, Chris Angelico <ros...@gmail.com> wrote: >>>> On Tue, Feb 23, 2016 at 11:08 AM, Jon Ribbens >>>><jon+use...@unequivocal.co.uk> wrote: >>>>>> If you generate 2**128 + 1 such numbers, you are *guaranteed* to >>>>> >>>>> ... have expired due to the heat death of the universe. >>>> >>>> Maybe... but by the time you get to 2**64 of them, you have a 50% >>>> chance of a collision. (That's either utterly intuitive or completely >>>> counter-intuitive, depending on who you are.) >>> >>> Um, did you mean to say 2**127? Are you thinking of the >>> birthday paradox or something, which doesn't apply here? >> >> By the time you generate 2**64 of them, you have a 50% chance that >> some pair of them collides. Yes, the birthday paradox does apply here. > > Oh, I see, you're thinking of it differently. I was thinking of it as > Alice is choosing a filename and Mallet is trying to guess it, in which > case the birthday paradox doesn't apply. You're thinking of it as Alice > is generating many random filenames and, even though she could avoid > collisions with 100% certainty by remembering what she's already had, > isn't doing so, and must avoid colliding with herself. I don't think > your version makes has much relevance as an attack model.
Ah. Steven was talking about collisions; once you have 2**128+1 of them, you're guaranteed a collision (pigeonhole principle). What you're talking about gives certainty slightly sooner - specifically, once you've tried 2**128 of them, you're guaranteed to have hit it :) ChrisA -- https://mail.python.org/mailman/listinfo/python-list
