[or-cvs] Remove minor biasing problem from crypto_pseudo_rand_int

[nickm@seul.org (Nick Mathewson)]

Update of /home/or/cvsroot/src/common
In directory moria.mit.edu:/tmp/cvs-serv22861/common

Modified Files:
	crypto.c crypto.h 
Log Message:
Remove minor biasing problem from crypto_pseudo_rand_int

Index: crypto.c
===================================================================
RCS file: /home/or/cvsroot/src/common/crypto.c,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- crypto.c	12 Nov 2003 04:12:35 -0000	1.42
+++ crypto.c	12 Nov 2003 04:28:30 -0000	1.43
@@ -16,6 +16,7 @@
 #include <stdlib.h>
 #include <assert.h>
 #include <stdio.h>
+#include <limits.h>
 
 #include "crypto.h"
 #include "../or/or.h"
@@ -1008,14 +1009,21 @@
   }
 }
 
-int crypto_pseudo_rand_int(int max) {
+int crypto_pseudo_rand_int(unsigned int max) {
   unsigned int val;
-  crypto_pseudo_rand(sizeof(val), (unsigned char*) &val);
-  /* Bug: Low values are _slightly_ favored over high values because
-   * ((unsigned)-1)%max != max-1 .  This shouldn't matter if max is
-   * significantly smaller than ((unsigned)-1).
-   **/
-  return val % max;
+  unsigned int cutoff;
+  assert(max < UINT_MAX);
+
+  /* We ignore any values that are >= 'cutoff,' to avoid biasing the
+   * distribution with clipping at the upper end of unsigned int's
+   * range.
+   */
+  cutoff = UINT_MAX - (UINT_MAX%max);
+  while(1) {
+    crypto_pseudo_rand(sizeof(val), (unsigned char*) &val);
+    if (val < cutoff)
+      return val % max;
+  }
 }
 
 /* errors */

Index: crypto.h
===================================================================
RCS file: /home/or/cvsroot/src/common/crypto.h,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- crypto.h	12 Nov 2003 04:12:35 -0000	1.21
+++ crypto.h	12 Nov 2003 04:28:30 -0000	1.22
@@ -101,7 +101,7 @@
 int crypto_seed_rng();
 int crypto_rand(unsigned int n, unsigned char *to);
 void crypto_pseudo_rand(unsigned int n, unsigned char *to);
-int crypto_pseudo_rand_int(int max);
+int crypto_pseudo_rand_int(unsigned int max);
 
 /* errors */
 char *crypto_perror();