On Mon, Feb 24, 2003 at 10:31:58AM -0500, Steven M. Bellovin wrote:
> As I recall, the OpenBSD system rekeys its generator periodically.  
> That's a good idea -- it's not hard to build a table of 2^16 entries -- 
> but it makes it harder to avoid reuse.  Here's a scheme that handles 
> that problem, too (I hope -- this is off the top of my head).  Use a 
> PRNG with a cycle of 2^15.  When it wraps, rekey, but invert the 
> high-order bit of the 16-bit space.  That bit gets flipped back when 
> this key wraps.  In other words, we partition the IPid space, but since 
> we're using a 15-bit generator, the high-order bit is acting as the 
> IPid space selector in some sense.  We therefore can't have collisions 
> any more frequently than 2^15 packets -- not as good as 2^16, but I 
> suspect as good as you can do if you want the ability to rekey.
That is how I implemented it for OpenBSD a few years ago.  FreeBSD
adapated the same code awhile back.  However, I would be more happy if
the ID generation was destination address based.

Nowadays, I would probably reimplement it using a fast 15-bit block
cipher.  And then hash the destination address to a table that
contains different key and counter state for each bucket.

For Scanssh, I changed TEA to be a variable block sized cipher.  This
allows me to pick unique random sequences out of 2**n with 1 <= n <=
32 without keeping any state but the key and the counter value.

Niels.