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

[Nick Mathewson]

On Wed, May 04, 2005 at 10:33:05AM +0200, Laurent Fousse wrote:
> Hi Nick,
> 
> * Nick Mathewson [Tue, May 03, 2005 at 09:58:24PM -0400]:
> > On Tue, May 03, 2005 at 06:03:46PM +0200, Laurent Fousse wrote:
> > > Hi Nick,
> > > 
> > > I suggest the following patch to nym-spec.txt. Rationale:
> > > 
> > >     - although the probability of message-id collision through mid
> > >       reuse in the server is low if the mid are truly randomly
> > >       generated, it would be preferable to request no mid collision in
> > >       the specs, as it greatly eases client operations.
> > 
> > I worry that this proposal would place more implementation burden on
> > the client.
> 
> From your following explanation I assume you meant "server" here,
> because the whole point of my proposal is to make it easier for the
> client : no mid reuse means it is safe to assume a MSG reply from the
> server does not have the same mid of a message we already fetched,
> asked for deletion, kept in the client, and the server later
> mistakenly reused.

I agree what I want to make it safe for the client to assume that
message IDs will not be reused: the point of the combinatorial
argument was to show that if the IDs are chosen randomly, the
clients can assume that they are unique.

 [...]
>                   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.)

 [...]
> 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.

>                                                         In my
> 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.)

-- 
Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
Url : http://lists.noreply.org/pipermail/nym3-devel/attachments/20050504/ca0bd0cf/attachment.pgp