randomint() bias and patch
Nathan Kennedy <[email protected]>
| Newsgroups | gmane.comp.security.invisiblenet.iip.devel |
|---|---|
| Message-ID | <[email protected]> |
As implemented, IIP's randomint(unsigned int i) function is biased when i doesn't divide UINT_MAX+1--in this case, all integers less than (UINT_MAX+1)%i will occur with probability 1/i + ((UINT_MAX+1)%i)/(UINT_MAX+1). The second term creates a bias--which is quite small when i is small with respect to UINT_MAX, but can be significantly larger with larger i--for instance, on 32-bit machines, randint(2863311530) will return integers in the range [0,1431655766] twice as often as it will return integers in the range [1431655767,2863311529]--a terrible bias. I have attached a cvs patch. -Nathan
randint_patch.diff
(text/x-patch, 449 B)
Index: src/crypt/random.c =================================================================== RCS file: /cvsroot/invisibleip/iip/src/crypt/random.c,v retrieving revision 1.6 diff -r1.6 random.c 12a13 > #include <limits.h> 203c204,206 < randomkeyGetBuffer(randomkey, tempbuffer, sizeof(unsigned int)); --- > do > randomkeyGetBuffer(randomkey, tempbuffer, sizeof(unsigned int)); > while (*((unsigned int *)tempbuffer) < (UINT_MAX - i + 1U) % i);
signature.asc
(application/pgp-signature, 189 B)
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iD8DBQA9sLT9+OvPO9l/6iERAuvDAKCs7RG+GFXW/+QDnvg/nNRjlbprpgCeI3nQ zWNSBIfx2lL7hNWpI4H0Q2c= =AwTx -----END PGP SIGNATURE-----