lib/libc/gen/randomid.c

   1 /*      $NetBSD: randomid.c,v 1.13 2009/01/11 02:46:27 christos Exp $   */
   2 /*      $KAME: ip6_id.c,v 1.8 2003/09/06 13:41:06 itojun Exp $  */
   3 /*      $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $       */
   4
   5 /*
   6  * Copyright (C) 2003 WIDE Project.
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. Neither the name of the project nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * Copyright 1998 Niels Provos <provos@citi.umich.edu>
  36  * All rights reserved.
  37  *
  38  * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
  39  * such a mathematical system to generate more random (yet non-repeating)
  40  * ids to solve the resolver/named problem.  But Niels designed the
  41  * actual system based on the constraints.
  42  *
  43  * Redistribution and use in source and binary forms, with or without
  44  * modification, are permitted provided that the following conditions
  45  * are met:
  46  * 1. Redistributions of source code must retain the above copyright
  47  *    notice, this list of conditions and the following disclaimer.
  48  * 2. Redistributions in binary form must reproduce the above copyright
  49  *    notice, this list of conditions and the following disclaimer in the
  50  *    documentation and/or other materials provided with the distribution.
  51  *
  52  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  53  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  54  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  55  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  56  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  57  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  58  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  59  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  60  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  61  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  62  */
  63
  64 /*
  65  * seed = random (bits - 1) bit
  66  * n = prime, g0 = generator to n,
  67  * j = random so that gcd(j,n-1) == 1
  68  * g = g0^j mod n will be a generator again.
  69  *
  70  * X[0] = random seed.
  71  * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
  72  * with a = 7^(even random) mod m,
  73  *      b = random with gcd(b,m) == 1
  74  *      m = constant and a maximal period of m-1.
  75  *
  76  * The transaction id is determined by:
  77  * id[n] = seed xor (g^X[n] mod n)
  78  *
  79  * Effectivly the id is restricted to the lower (bits - 1) bits, thus
  80  * yielding two different cycles by toggling the msb on and off.
  81  * This avoids reuse issues caused by reseeding.
  82  */
  83
  84 #include <sys/cdefs.h>
  85 #if defined(LIBC_SCCS) && !defined(lint)
  86 __RCSID("$NetBSD: randomid.c,v 1.13 2009/01/11 02:46:27 christos Exp $");
  87 #endif
  88
  89 #include "namespace.h"
  90
  91 #include <sys/types.h>
  92 #include <sys/time.h>
  93 #include <stdlib.h>
  94 #include <string.h>
  95 #include <errno.h>
  96 #include <randomid.h>
  97
  98 #ifdef __weak_alias
  99 __weak_alias(randomid,_randomid)
 100 __weak_alias(randomid_new,_randomid_new)
 101 __weak_alias(randomid_delete,_randomid_delete)
 102 #endif
 103
 104 struct randomconf {
 105         const int       rc_bits; /* resulting bits */
 106         const u_int32_t rc_max; /* Uniq cycle, avoid blackjack prediction */
 107         const u_int32_t rc_gen; /* Starting generator */
 108         const u_int32_t rc_n;   /* ru_n: prime, ru_n - 1: product of pfacts[] */
 109         const u_int32_t rc_agen; /* determine ru_a as ru_agen^(2*rand) */
 110         const u_int32_t rc_m;   /* ru_m = 2^x*3^y */
 111         const u_int32_t rc_pfacts[4];   /* factors of ru_n */
 112         const int       rc_skip;        /* skip values */
 113 };
 114
 115 struct randomid_ctx {
 116         struct randomconf *ru_conf;
 117 #define ru_bits         ru_conf->rc_bits
 118 #define ru_max          ru_conf->rc_max
 119 #define ru_gen          ru_conf->rc_gen
 120 #define ru_n            ru_conf->rc_n
 121 #define ru_agen         ru_conf->rc_agen
 122 #define ru_m            ru_conf->rc_m
 123 #define ru_pfacts       ru_conf->rc_pfacts
 124 #define ru_skip         ru_conf->rc_skip
 125         long ru_out;            /* Time after wich will be reseeded */
 126         u_int32_t ru_counter;
 127         u_int32_t ru_msb;
 128
 129         u_int32_t ru_x;
 130         u_int32_t ru_seed, ru_seed2;
 131         u_int32_t ru_a, ru_b;
 132         u_int32_t ru_g;
 133         time_t ru_reseed;
 134 };
 135
 136 static struct randomconf randomconf[] = {
 137   {
 138         32,                     /* resulting bits */
 139         1000000000,             /* Uniq cycle, avoid blackjack prediction */
 140         2,                      /* Starting generator */
 141         2147483629,             /* RU_N-1 = 2^2*3^2*59652323 */
 142         7,                      /* determine ru_a as RU_AGEN^(2*rand) */
 143         1836660096,             /* RU_M = 2^7*3^15 - don't change */
 144         { 2, 3, 59652323, 0 },  /* factors of ru_n */
 145         3,                      /* skip values */
 146   },
 147   {
 148         20,                     /* resulting bits */
 149         200000,                 /* Uniq cycle, avoid blackjack prediction */
 150         2,                      /* Starting generator */
 151         524269,                 /* RU_N-1 = 2^2*3^2*14563 */
 152         7,                      /* determine ru_a as RU_AGEN^(2*rand) */
 153         279936,                 /* RU_M = 2^7*3^7 - don't change */
 154         { 2, 3, 14563, 0 },     /* factors of ru_n */
 155         3,                      /* skip values */
 156   },
 157   {
 158         16,                     /* resulting bits */
 159         30000,                  /* Uniq cycle, avoid blackjack prediction */
 160         2,                      /* Starting generator */
 161         32749,                  /* RU_N-1 = 2^2*3*2729 */
 162         7,                      /* determine ru_a as RU_AGEN^(2*rand) */
 163         31104,                  /* RU_M = 2^7*3^5 - don't change */
 164         { 2, 3, 2729, 0 },      /* factors of ru_n */
 165         0,                      /* skip values */
 166   },
 167   {
 168         .rc_bits = -1,          /* termination */
 169   },
 170 };
 171
 172 static u_int32_t pmod(u_int32_t, u_int32_t, u_int32_t);
 173 static void initid(struct randomid_ctx *);
 174
 175 struct randomid_ctx *randomid_new(int, long);
 176 void randomid_delete(struct randomid_ctx *);
 177 u_int32_t randomid(struct randomid_ctx *);
 178
 179 /*
 180  * Do a fast modular exponation, returned value will be in the range
 181  * of 0 - (mod-1)
 182  */
 183
 184 static u_int32_t
 185 pmod(u_int32_t gen, u_int32_t expo, u_int32_t mod)
 186 {
 187         u_int64_t s, t, u;
 188
 189         s = 1;
 190         t = gen;
 191         u = expo;
 192
 193         while (u) {
 194                 if (u & 1)
 195                         s = (s * t) % mod;
 196                 u >>= 1;
 197                 t = (t * t) % mod;
 198         }
 199         return ((u_int32_t)s & UINT32_MAX);
 200 }
 201
 202 /*
 203  * Initalizes the seed and chooses a suitable generator. Also toggles
 204  * the msb flag. The msb flag is used to generate two distinct
 205  * cycles of random numbers and thus avoiding reuse of ids.
 206  *
 207  * This function is called from id_randomid() when needed, an
 208  * application does not have to worry about it.
 209  */
 210 static void
 211 initid(struct randomid_ctx *p)
 212 {
 213         u_int32_t j, i;
 214         int noprime = 1;
 215         struct timeval tv;
 216
 217         p->ru_x = arc4random() % p->ru_m;
 218
 219         /* (bits - 1) bits of random seed */
 220         p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));
 221         p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
 222
 223         /* Determine the LCG we use */
 224         p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;
 225         p->ru_a = pmod(p->ru_agen,
 226             (arc4random() & (~0U >> (32 - p->ru_bits))) & (~1U), p->ru_m);
 227         while (p->ru_b % 3 == 0)
 228                 p->ru_b += 2;
 229
 230         j = arc4random() % p->ru_n;
 231
 232         /*
 233          * Do a fast gcd(j, RU_N - 1), so we can find a j with
 234          * gcd(j, RU_N - 1) == 1, giving a new generator for
 235          * RU_GEN^j mod RU_N
 236          */
 237         while (noprime) {
 238                 for (i = 0; p->ru_pfacts[i] > 0; i++)
 239                         if (j % p->ru_pfacts[i] == 0)
 240                                 break;
 241
 242                 if (p->ru_pfacts[i] == 0)
 243                         noprime = 0;
 244                 else
 245                         j = (j + 1) % p->ru_n;
 246         }
 247
 248         p->ru_g = pmod(p->ru_gen, j, p->ru_n);
 249         p->ru_counter = 0;
 250
 251         gettimeofday(&tv, NULL);
 252         p->ru_reseed = tv.tv_sec + p->ru_out;
 253         p->ru_msb = p->ru_msb ? 0 : (1U << (p->ru_bits - 1));
 254 }
 255
 256 struct randomid_ctx *
 257 randomid_new(int bits, long timeo)
 258 {
 259         struct randomconf *conf;
 260         struct randomid_ctx *ctx;
 261
 262         if (timeo < RANDOMID_TIMEO_MIN) {
 263                 errno = EINVAL;
 264                 return (NULL);
 265         }
 266
 267         for (conf = randomconf; conf->rc_bits > 0; conf++) {
 268                 if (bits == conf->rc_bits)
 269                         break;
 270         }
 271
 272         /* unsupported bits */
 273         if (bits != conf->rc_bits) {
 274                 errno = ENOTSUP;
 275                 return (NULL);
 276         }
 277
 278         ctx = malloc(sizeof(*ctx));
 279         if (!ctx)
 280                 return (NULL);
 281
 282         memset(ctx, 0, sizeof(*ctx));
 283         ctx->ru_conf = conf;
 284         ctx->ru_out = timeo;
 285
 286         return (ctx);
 287 }
 288
 289 void
 290 randomid_delete(struct randomid_ctx *ctx)
 291 {
 292
 293         memset(ctx, 0, sizeof(*ctx));
 294         free(ctx);
 295 }
 296
 297 u_int32_t
 298 randomid(struct randomid_ctx *p)
 299 {
 300         int i, n;
 301         struct timeval tv;
 302
 303         gettimeofday(&tv, NULL);
 304         if (p->ru_counter >= p->ru_max || tv.tv_sec > p->ru_reseed)
 305                 initid(p);
 306
 307         /* Skip a random number of ids */
 308         if (p->ru_skip) {
 309                 n = arc4random() & p->ru_skip;
 310                 if (p->ru_counter + n >= p->ru_max)
 311                         initid(p);
 312         } else
 313                 n = 0;
 314
 315         for (i = 0; i <= n; i++) {
 316                 /* Linear Congruential Generator */
 317                 p->ru_x = (u_int32_t)(((u_int64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m);
 318         }
 319
 320         p->ru_counter += i;
 321
 322         return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 + p->ru_x, p->ru_n)) |
 323             p->ru_msb;
 324 }