freeswan/lib/prng.c

   1 /*
   2  * crypto-class pseudorandom number generator
   3  * currently uses same algorithm as RC4(TM), from Schneier 2nd ed p397
   4  * Copyright (C) 2002  Henry Spencer.
   5  *
   6  * This library is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU Library General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or (at your
   9  * option) any later version.  See <http://www.fsf.org/copyleft/lgpl.txt>.
  10  *
  11  * This library is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  14  * License for more details.
  15  *
  16  * RCSID $Id: prng.c,v 1.3 2002/03/26 00:50:04 henry Exp $
  17  */
  18 #include "internal.h"
  19 #include "freeswan.h"
  20
  21 /*
  22  - prng_init - initialize PRNG from a key
  23  */
  24 void
  25 prng_init(prng, key, keylen)
  26 struct prng *prng;
  27 const unsigned char *key;
  28 size_t keylen;
  29 {
  30         unsigned char k[256];
  31         int i, j;
  32         unsigned const char *p;
  33         unsigned const char *keyend = key + keylen;
  34         unsigned char t;
  35
  36         for (i = 0; i <= 255; i++)
  37                 prng->sbox[i] = i;
  38         p = key;
  39         for (i = 0; i <= 255; i++) {
  40                 k[i] = *p++;
  41                 if (p >= keyend)
  42                         p = key;
  43         }
  44         j = 0;
  45         for (i = 0; i <= 255; i++) {
  46                 j = (j + prng->sbox[i] + k[i]) & 0xff;
  47                 t = prng->sbox[i];
  48                 prng->sbox[i] = prng->sbox[j];
  49                 prng->sbox[j] = t;
  50                 k[i] = 0;       /* clear out key memory */
  51         }
  52         prng->i = 0;
  53         prng->j = 0;
  54         prng->count = 0;
  55 }
  56
  57 /*
  58  - prng_bytes - get some pseudorandom bytes from PRNG
  59  */
  60 void
  61 prng_bytes(prng, dst, dstlen)
  62 struct prng *prng;
  63 unsigned char *dst;
  64 size_t dstlen;
  65 {
  66         int i, j, t;
  67         unsigned char *p = dst;
  68         size_t remain = dstlen;
  69 #       define  MAX     4000000000ul
  70
  71         while (remain > 0) {
  72                 i = (prng->i + 1) & 0xff;
  73                 prng->i = i;
  74                 j = (prng->j + prng->sbox[i]) & 0xff;
  75                 prng->j = j;
  76                 t = prng->sbox[i];
  77                 prng->sbox[i] = prng->sbox[j];
  78                 prng->sbox[j] = t;
  79                 t = (t + prng->sbox[i]) & 0xff;
  80                 *p++ = prng->sbox[t];
  81                 remain--;
  82         }
  83         if (prng->count < MAX - dstlen)
  84                 prng->count += dstlen;
  85         else
  86                 prng->count = MAX;
  87 }
  88
  89 /*
  90  - prnt_count - how many bytes have been extracted from PRNG so far?
  91  */
  92 unsigned long
  93 prng_count(prng)
  94 struct prng *prng;
  95 {
  96         return prng->count;
  97 }
  98
  99 /*
 100  - prng_final - clear out PRNG to ensure nothing left in memory
 101  */
 102 void
 103 prng_final(prng)
 104 struct prng *prng;
 105 {
 106         int i;
 107
 108         for (i = 0; i <= 255; i++)
 109                 prng->sbox[i] = 0;
 110         prng->i = 0;
 111         prng->j = 0;
 112         prng->count = 0;        /* just for good measure */
 113 }
 114
 115
 116
 117 #ifdef PRNG_MAIN
 118
 119 #include <stdio.h>
 120
 121 void regress();
 122
 123 int
 124 main(argc, argv)
 125 int argc;
 126 char *argv[];
 127 {
 128         struct prng pr;
 129         unsigned char buf[100];
 130         unsigned char *p;
 131         size_t n;
 132
 133         if (argc < 2) {
 134                 fprintf(stderr, "Usage: %s {key|-r}\n", argv[0]);
 135                 exit(2);
 136         }
 137
 138         if (strcmp(argv[1], "-r") == 0) {
 139                 regress();
 140                 fprintf(stderr, "regress() returned?!?\n");
 141                 exit(1);
 142         }
 143
 144         prng_init(&pr, argv[1], strlen(argv[1]));
 145         prng_bytes(&pr, buf, 32);
 146         printf("0x");
 147         for (p = buf, n = 32; n > 0; p++, n--)
 148                 printf("%02x", *p);
 149         printf("\n%lu bytes\n", prng_count(&pr));
 150         prng_final(&pr);
 151         exit(0);
 152 }
 153
 154 void
 155 regress()
 156 {
 157         struct prng pr;
 158         unsigned char buf[100];
 159         unsigned char *p;
 160         size_t n;
 161         /* somewhat non-random sample key */
 162         unsigned char key[] = "here we go gathering nuts in May";
 163         /* first thirty bytes of output from that key */
 164         unsigned char good[] = "\x3f\x02\x8e\x4a\x2a\xea\x23\x18\x92\x7c"
 165                                 "\x09\x52\x83\x61\xaa\x26\xce\xbb\x9d\x71"
 166                                 "\x71\xe5\x10\x22\xaf\x60\x54\x8d\x5b\x28";
 167         int nzero, none;
 168         int show = 0;
 169
 170         prng_init(&pr, key, strlen(key));
 171         prng_bytes(&pr, buf, sizeof(buf));
 172         for (p = buf, n = sizeof(buf); n > 0; p++, n--) {
 173                 if (*p == 0)
 174                         nzero++;
 175                 if (*p == 255)
 176                         none++;
 177         }
 178         if (nzero > 3 || none > 3) {
 179                 fprintf(stderr, "suspiciously non-random output!\n");
 180                 show = 1;
 181         }
 182         if (memcmp(buf, good, strlen(good)) != 0) {
 183                 fprintf(stderr, "incorrect output!\n");
 184                 show = 1;
 185         }
 186         if (show) {
 187                 fprintf(stderr, "0x");
 188                 for (p = buf, n = sizeof(buf); n > 0; p++, n--)
 189                         fprintf(stderr, "%02x", *p);
 190                 fprintf(stderr, "\n");
 191                 exit(1);
 192         }
 193         if (prng_count(&pr) != sizeof(buf)) {
 194                 fprintf(stderr, "got %u bytes, but count is %lu\n",
 195                                         sizeof(buf), prng_count(&pr));
 196                 exit(1);
 197         }
 198         prng_final(&pr);
 199         exit(0);
 200 }
 201
 202 #endif /* PRNG_MAIN */