make things more complicated.

1 files changed, 46 insertions, 13 deletions

diff --git a/lib/libc/net/res_random.c b/lib/libc/net/res_random.c
index d6d3a9269c8..f6956bdd36d 100644
--- a/lib/libc/net/res_random.c
+++ b/lib/libc/net/res_random.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: res_random.c,v 1.1 1997/04/13 21:30:47 provos Exp $ */
+/* $OpenBSD: res_random.c,v 1.2 1997/04/19 09:53:25 provos Exp $ */
 
 /*
  * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de>
@@ -43,7 +43,9 @@
  *
  * X[0] = random seed.
  * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
- * with a = 625, b = 6571, m = 31104 and a maximal period of m-1.
+ * with a = 7^(even random) mod m, 
+ *      b = random with gcd(b,m) == 1
+ *      m = 31104 and a maximal period of m-1.
  *
  * The transaction id is determined by:
  * id[n] = seed xor (g^X[n] mod n)
@@ -51,6 +53,10 @@
  * Effectivly the id is restricted to the lower 15 bits, thus
  * yielding two different cycles by toggling the msb on and off.
  * This avoids reuse issues caused by reseeding.
+ *
+ * The 16 bit space is very small and brute force attempts are
+ * entirly feasible, we skip a random number of transaction ids
+ * so that an attacker will not get sequential ids.
  */
 
 #include <sys/types.h>
@@ -61,13 +67,14 @@
 #include <unistd.h>
 #include <stdlib.h>
 #include <string.h>
+#include <time.h>
 
-#define RU_MAX	20000		/* Uniq cycle, avoid blackjack prediction */
+#define RU_OUT  180             /* Time after wich will be reseeded */
+#define RU_MAX	30000		/* Uniq cycle, avoid blackjack prediction */
 #define RU_GEN	2		/* Starting generator */
 #define RU_N	32749		/* RU_N-1 = 2*2*3*2729 */
-#define RU_A	625
-#define RU_B	6571
-#define RU_M	31104
+#define RU_AGEN	7               /* determine ru_a as RU_AGEN^(2*rand) */
+#define RU_M	31104           /* RU_M = 2^7*3^5 - don't change */
 
 #define PFAC_N 3
 const static u_int16_t pfacts[PFAC_N] = {
@@ -78,9 +85,12 @@ const static u_int16_t pfacts[PFAC_N] = {
 
 static u_int16_t ru_x;
 static u_int16_t ru_seed;
+static u_int16_t ru_a, ru_b;
 static u_int16_t ru_g;
 static u_int16_t ru_counter = 0;
 static u_int16_t ru_msb = 0;
+static time_t ru_reseed;
+static u_int32_t tmp;                /* Storage for unused random */
 
 static u_int32_t pmod __P((u_int32_t, u_int32_t, u_int32_t));
 static void res_initid __P((void));
@@ -110,7 +120,7 @@ pmod(gen, exp, mod)
 }
 
 /* 
- * Initalizes the seed and choosed a suitable generator. Also toggles 
+ * Initalizes the seed and chooses a suitable generator. Also toggles 
  * the msb flag. The msb flag is used to generate two distinct
  * cycles of random numbers and thus avoiding reuse of ids.
  *
@@ -121,7 +131,6 @@ static void
 res_initid()
 {
 	u_int16_t j, i;
-	u_int32_t tmp;
 	int noprime = 1;
 
 	tmp = arc4random();
@@ -130,7 +139,17 @@ res_initid()
 	/* 15 bits of random seed */
 	ru_seed = (tmp >> 16) & 0x7FFF;
 
-	j = arc4random() % RU_N;
+	tmp = arc4random();
+
+	/* Determine the LCG we use */
+	ru_b = (tmp & 0xfffe) | 1;
+	ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
+	while (ru_b % 3 == 0)
+	  ru_b += 2;
+	
+	tmp = arc4random();
+	j = tmp % RU_N;
+	tmp = tmp >> 16;
 
 	/* 
 	 * Do a fast gcd(j,RU_N-1), so we can find a j with
@@ -152,19 +171,31 @@ res_initid()
 	ru_g = pmod(RU_GEN,j,RU_N);
 	ru_counter = 0;
 
+	ru_reseed = time(NULL) + RU_OUT;
 	ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; 
 }
 
 u_int
 res_randomid()
 {
-	if (ru_counter % RU_MAX == 0)
+        int i, n;
+
+	if (ru_counter >= RU_MAX || time(NULL) > ru_reseed)
 		res_initid();
 
-	ru_counter++;
+	if (!tmp)
+	        tmp = arc4random();
+
+	/* Skip a random number of ids */
+	n = tmp & 0x2f; tmp = tmp >> 6;
+	if (ru_counter + n >= RU_MAX)
+                res_initid();
+
+	for (i=0; i<=n; i++)
+	        /* Linear Congruential Generator */
+	        ru_x = (ru_a*ru_x + ru_b) % RU_M;
 
-	/* Linear Congruential Generator */
-	ru_x = (RU_A*ru_x + RU_B) % RU_M;
+	ru_counter += i;
 
 	return (ru_seed ^ pmod(ru_g,ru_x,RU_N)) | ru_msb;
 }
@@ -181,6 +212,8 @@ main(int argc, char **argv)
 	printf("Generator: %d\n", ru_g);
 	printf("Seed: %d\n", ru_seed);
 	printf("Ru_X: %d\n", ru_x);
+	printf("Ru_A: %d\n", ru_a);
+	printf("Ru_B: %d\n", ru_b);
 
 	n = atoi(argv[1]);
 	for (i=0;i<n;i++) {