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

[Laurent Fousse]

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.

> Right now, it is safe to assume that randomly generated
> message IDs are unique: until the server is holding 2**80 messages,
> the chance of collision is negligible.  But even if every single
> person on earth sent you one message per second for the next hundred
> years, and you kept them all in your account at once, you'd only have
> 2**58 messages.  Even if the messages were all empty, the server would
> need 20 yottabytes (!!!!!) of storage just to hold the message IDs.

Yes, I knew the combinatorial argument works both ways when I posted
:-)

If we drop the "randomness" requirement however, we have a
straightforward way to generate message IDs without the need to store
them all in the server.

If all the message IDs randomness is supposed to bring us is a good
probability of no message IDs reuse, then drop it and clearly ask for
this uniqueness. 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 -- and the client would have to be able to deal with
such server which follow the specs and have a higher probability of
message IDs collision.

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

> Therefore, it's safe to assume that randomly generated message IDs are
> unique.

Sure. In our current client implementation, we're being cautious
against server using a flawed definition of "random", like calling
rand() without any kind of seeding. If the specs would clarify the
meaning of "random" to disallow such broken server implementation we
could get rid of some ugliness in the data structures (just to let you
know I'm not just pushing my proposal for its sheer beauty).

Hum. If I have a secret permutation (call if Phi) of the mid space,
would the generated sequence Phi(1), Phi(2), etc... still be
considered "random" ?
-------------- 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/0864839b/attachment.pgp