Subject: Re: synchronous ip_id
To: Steven M. Bellovin <email@example.com>
From: Niels Provos <firstname.lastname@example.org>
Date: 02/24/2003 11:07:36
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.