Make a unique filesystem path, without creating the file

[Chris Angelico]

On Tue, Feb 23, 2016 at 11:44 AM, Jon Ribbens
<jon+usenet at unequivocal.co.uk> wrote:
> On 2016-02-23, Chris Angelico <rosuav at gmail.com> wrote:
>> On Tue, Feb 23, 2016 at 11:26 AM, Jon Ribbens
>><jon+usenet at unequivocal.co.uk> wrote:
>>> On 2016-02-23, Chris Angelico <rosuav at gmail.com> wrote:
>>>> On Tue, Feb 23, 2016 at 11:08 AM, Jon Ribbens
>>>><jon+usenet at 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