Subject: Re: rpc xid randomness
To: Jun-ichiro itojun Hagino <>
From: David Laight <>
List: tech-security
Date: 09/08/2003 22:03:30
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!

It ought to be possible to find a 16bit block cipher with a long enough
key that a significant part of the domain can be encripted without the
key being determinable in a reasonable time.


David Laight: