Fix numerous problems with Tor's weak RNG.

We need a weak RNG in a couple of places where the strong RNG is
both needless and too slow.  We had been using the weak RNG from our
platform's libc implementation, but that was problematic (because
many platforms have exceptionally horrible weak RNGs -- like, ones
that only return values between 0 and SHORT_MAX) and because we were
using it in a way that was wrong for LCG-based weak RNGs.  (We were
counting on the low bits of the LCG output to be as random as the
high ones, which isn't true.)

This patch adds a separate type for a weak RNG, adds an LCG
implementation for it, and uses that exclusively where we had been
using the platform weak RNG.

1 files changed, 40 insertions, 0 deletions

diff --git a/src/common/util.c b/src/common/util.c
index 93e2ba8e14..03840402b7 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -4996,3 +4996,43 @@ tor_check_port_forwarding(const char *filename,
   }
 }
 
+/** Initialize the insecure RNG <b>rng</b> from a seed value <b>seed</b>. */
+void
+tor_init_weak_random(tor_weak_rng_t *rng, unsigned seed)
+{
+  rng->state = (uint32_t)(seed & 0x7fffffff);
+}
+
+/** Return a randomly chosen value in the range 0..TOR_WEAK_RANDOM_MAX based
+ * on the RNG state of <b>rng</b>.  This entropy will not be cryptographically
+ * strong; do not rely on it for anything an adversary should not be able to
+ * predict. */
+int32_t
+tor_weak_random(tor_weak_rng_t *rng)
+{
+  /* Here's a linear congruential generator. OpenBSD and glibc use it. We
+   * don't want to use windows's rand(), because that returns values in the
+   * range 0..INT16_MAX, which just isn't enough. */
+  rng->state = (rng->state * 1103515245 + 12345) & 0x7fffffff;
+  return (int32_t) rng->state;
+}
+
+/** Return a random number in the range [0 , <b>top</b>). {That is, the range
+ * of integers i such that 0 <= i < top.}  Chooses uniformly.  Requires that
+ * top is greater than 0. This randomness is not cryptographically strong; do
+ * not rely on it for anything an adversary should not be able to predict. */
+int32_t
+tor_weak_random_range(tor_weak_rng_t *rng, int32_t top)
+{
+  /* We don't want to just do tor_weak_random() % top, since random() is often
+   * implemented with an LCG whose modulus is a power of 2, and those are
+   * cyclic in their low-order bits. */
+  int divisor, result;
+  tor_assert(top > 0);
+  divisor = TOR_WEAK_RANDOM_MAX / top;
+  do {
+    result = (int32_t)(tor_weak_random(rng) / divisor);
+  } while (result >= top);
+  return result;
+}
+