Subject: Re: random ip_id must be configurable
To: None <tech-net@netbsd.org>
From: Simon Burge <simonb@wasabisystems.com>
List: tech-net
Date: 09/13/2003 17:04:01
--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
On Fri, Sep 12, 2003 at 06:24:21AM +0900, Jun-ichiro itojun Hagino wrote:
> > * There are environments where the downside of reducing the (already small)
> > ip_id space overwhelms the alleged security gains.
>
> reducing? with ip_randomid(), the *guaranteed minimum* interval between
> the generation of the same output value is 36000 calls.
> even after 36000 calls, it is highly unlikely that we see the same
> number generated from ip_randomid(). if you have concrete number
> please show me.
The following program (which originally used the kernel version of
ip_randomid() but has been modified to use randomid(3)) shows that often
enough, _consecutive_calls_ to randomid(3) return the _same_number_.
This is using the 16-bit version of randomid(3) that (looks to) have the
same configuration parameters as ip_randomid(). Very similar results
were observed with ip_randomid() too.
Here is some sample output showing that after 12339 calls we produced
the same id as 55 calls prior to that, and at 465456 calls we produced
the same id as the previous call.
In the first 18000ish calls (half of the quoted "36000" number above)
we produced the same id that was produced within the previous 56 calls
at least 50 times (and possibly more since the program just reports
differences less than or equal to the previous lowest difference).
Another run with a slight modification showed 1911 repeats less than 50
calls apart in 36000 calls.
id 30728 last call for id at 12284, current call 12339 (diff 55)
id 29866 last call for id at 12285, current call 12340 (diff 55)
id 17761 last call for id at 12290, current call 12345 (diff 55)
id 2184 last call for id at 12291, current call 12346 (diff 55)
id 32716 last call for id at 12292, current call 12347 (diff 55)
id 24515 last call for id at 12298, current call 12353 (diff 55)
id 27895 last call for id at 12302, current call 12357 (diff 55)
id 9070 last call for id at 12303, current call 12358 (diff 55)
id 31697 last call for id at 12307, current call 12360 (diff 53)
id 7615 last call for id at 12308, current call 12361 (diff 53)
id 12750 last call for id at 12310, current call 12363 (diff 53)
id 2184 last call for id at 12346, current call 12399 (diff 53)
id 32716 last call for id at 12347, current call 12400 (diff 53)
id 6666 last call for id at 12349, current call 12402 (diff 53)
id 7382 last call for id at 12374, current call 12427 (diff 53)
id 20159 last call for id at 12375, current call 12428 (diff 53)
id 20269 last call for id at 12377, current call 12430 (diff 53)
id 6670 last call for id at 12380, current call 12431 (diff 51)
id 20805 last call for id at 12381, current call 12432 (diff 51)
id 25981 last call for id at 12382, current call 12433 (diff 51)
id 31937 last call for id at 12387, current call 12437 (diff 50)
id 4749 last call for id at 12390, current call 12440 (diff 50)
id 21579 last call for id at 12403, current call 12453 (diff 50)
id 19600 last call for id at 12405, current call 12454 (diff 49)
id 27053 last call for id at 12409, current call 12458 (diff 49)
id 19999 last call for id at 12410, current call 12459 (diff 49)
id 7180 last call for id at 12411, current call 12460 (diff 49)
id 7615 last call for id at 12416, current call 12464 (diff 48)
id 12750 last call for id at 12418, current call 12466 (diff 48)
id 16465 last call for id at 12487, current call 12535 (diff 48)
id 7684 last call for id at 12493, current call 12541 (diff 48)
id 27464 last call for id at 12515, current call 12563 (diff 48)
id 22654 last call for id at 12516, current call 12564 (diff 48)
id 12280 last call for id at 12526, current call 12574 (diff 48)
id 9259 last call for id at 12530, current call 12576 (diff 46)
id 6193 last call for id at 12736, current call 12782 (diff 46)
id 25664 last call for id at 13114, current call 13160 (diff 46)
id 12750 last call for id at 13124, current call 13170 (diff 46)
id 12962 last call for id at 13146, current call 13192 (diff 46)
id 19913 last call for id at 13148, current call 13194 (diff 46)
id 5590 last call for id at 13149, current call 13195 (diff 46)
id 12849 last call for id at 13401, current call 13447 (diff 46)
id 10317 last call for id at 13890, current call 13936 (diff 46)
id 20269 last call for id at 13897, current call 13943 (diff 46)
id 6670 last call for id at 13898, current call 13944 (diff 46)
id 30136 last call for id at 13900, current call 13945 (diff 45)
id 16465 last call for id at 13902, current call 13946 (diff 44)
id 6193 last call for id at 13907, current call 13949 (diff 42)
id 918 last call for id at 17825, current call 17867 (diff 42)
id 3148 last call for id at 17827, current call 17868 (diff 41)
id 52018 last call for id at 465455, current call 465456 (diff 1)
id 61704 last call for id at 3483418, current call 3483419 (diff 1)
id 33945 last call for id at 5935819, current call 5935820 (diff 1)
id 30918 last call for id at 16623469, current call 16623470 (diff 1)
id 36190 last call for id at 34320998, current call 34320999 (diff 1)
id 14198 last call for id at 49763584, current call 49763585 (diff 1)
id 15403 last call for id at 70091776, current call 70091777 (diff 1)
id 2475 last call for id at 72643812, current call 72643813 (diff 1)
id 29307 last call for id at 85673723, current call 85673724 (diff 1)
id 51025 last call for id at 106130766, current call 106130767 (diff 1)
id 24311 last call for id at 111150745, current call 111150746 (diff 1)
id 7675 last call for id at 116503727, current call 116503728 (diff 1)
id 64231 last call for id at 260645710, current call 260645711 (diff 1)
id 59199 last call for id at 269157012, current call 269157013 (diff 1)
id 49981 last call for id at 278571728, current call 278571729 (diff 1)
id 5897 last call for id at 287959135, current call 287959136 (diff 1)
id 44515 last call for id at 288429490, current call 288429491 (diff 1)
id 11901 last call for id at 296754447, current call 296754448 (diff 1)
id 38648 last call for id at 300431773, current call 300431774 (diff 1)
Simon.
--
Simon Burge <simonb@wasabisystems.com>
NetBSD Development, Support and Service: http://www.wasabisystems.com/
--lrZ03NoBR/3+SXJZ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="harness.c"
#include <sys/types.h>
#include <string.h>
#include <limits.h>
#include <randomid.h>
uint64_t last[65536];
uint64_t n = 0;
main()
{
static randomid_t ctx = NULL;
uint64_t lowest;
uint16_t id;
int i;
memset(last, 0, sizeof(last));
ctx = randomid_new(16, (long)3600);
lowest = ULLONG_MAX;
while (n < ULLONG_MAX) {
id = randomid(ctx);
if (last[id] > 0) {
if (n - last[id] <= lowest) {
if (lowest != ULLONG_MAX)
printf("id %5d "
"last call for id at %9lld, "
"current call %9lld (diff %5lld)\n",
id, last[id], n, n - last[id]);
lowest = n - last[id];
}
}
last[id] = n;
n++;
}
exit(0);
}
--lrZ03NoBR/3+SXJZ--