[Nym3-devel] Re: [specs] Message ID and collision prevention.

[Laurent Fousse]

Hi Nick,

* Nick Mathewson [Wed, May 04, 2005 at 05:13:34AM -0400]:
> >                   If I write a C implementation of a server and I use
> > rand() for message ID generation it would seem my implementation
> > follows the specs but message IDs collision would now have a greater
> > chance to happen
> 
> Ah, I see.  There is ambiguity in the word "random."  The spec should
> say "cryptographically random" instead.  This way, using rand()
> wouldn't follow the spec, and the combinatoric argument would apply.
> 
> (Do I need to define what 'cryptographically random' means?
> Informally: every possible message ID should get chosen with equal
> probability; message IDs should get chosen independently of one
> another; and an attacker should not be able to predict, guess, or
> influence message IDs.)

Cryptographically random would indeed address my concern: it would
mean we don't have to worry about a now utterly negligible probability
of message IDs collisions. That's really good enough for me :-)

About the inclusion of the definition in the specs: I think just
changing to "cryptographically random" would make the intent clear
enough, and it is a notion that is already shared among the people
interested in a nymserver anyway, so I would not add it.

> > I can understand how requiring message ID randomness seems a good
> > idea, and I would like to understand why truly random (in some sense)
> > message IDs would be beneficial from the anonymity POV.
> 
> It depends on what alternate way the message IDs would be generated
> instead.  There are other (non-random) ways to generate message IDs
> that have very bad anonymity properties; the nice thing about random
> IDs is that it leaks absolutely nothing.

Yes.

> > understanding it does not bring anything, because in a situation where
> > an attacker would be able to read the message ID it would have already
> > gained a lot more knowledge about the account than mere message IDs.
> 
> Consider forward secrecy: *if* information is leaked by the IDs, but
> that information has already been deleted, but the IDs haven't, then
> learning the IDs exposes that information.  (This wouldn't apply in
> all cases, naturally.)

I agree. Let's just keep a clarified meaning of "random" that makes
everybody happier :-)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.noreply.org/pipermail/nym3-devel/attachments/20050504/714d9c6c/attachment.pgp