Subject: Re: rpc xid randomness
To: None <david@l8s.co.uk>
From: Jun-ichiro itojun Hagino <itojun@itojun.org>
List: tech-userlevel
Date: 09/09/2003 07:00:55
> On Mon, Sep 08, 2003 at 07:50:58PM +0900, Jun-ichiro itojun Hagino wrote:
> > to summarize,
> > - the currently-committed code is not good. it is not resistant to
> > number reuse/duplication.
> > - sequential number with time.tv_sec initialization is resistant to
> > number reuse/duplication, if we don't set date(1).
> > - niels' generator is resistant to number reuse/duplcation, and probably
> > there's no chance for duplication on reboot (due to the use of random
> > number as initialization)
> >
> > now, may i commit?
>
> IMHO this generator is too expensive for RPC xids, and I'm not sure
> that it is good enough for anything that needs randomness.
>
> It looks as though the value is calculated from:
> a ** b mod c
> where 'a' changes for each block of numbers, 'b' sequences through
> terms of a LCG whenever a value is wanted (missing 0 to 7 each time)
> and 'c' is constant.
>
> Some notes I have on the security of RSA (where 'a' would be the message
> and 'b' and 'c' the key) say that you should not use different values of
> 'b' with the same 'c' - otherwise recovering the key is trivial if the
> same message (ie 'a') is encypted with both.
> This use of the equation seems to be going out of its way to make it easy
> to break!
take a look at the comment on sys/netinet/ip_id.c more carefully.
X[n] sequence is generated by a ** b mod m, but the actual id
is seed xor (g^X[n] mod n). and seed is random. i don't think
it emit predictable sequence of number. it just avoids number
collision in the sequence.
itojun