crypto/openssh/openbsd-compat/arc4random.c

   1 /* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */
   2
   3 /*      $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $  */
   4
   5 /*
   6  * Copyright (c) 1996, David Mazieres <dm@uun.org>
   7  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
   8  * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
   9  *
  10  * Permission to use, copy, modify, and distribute this software for any
  11  * purpose with or without fee is hereby granted, provided that the above
  12  * copyright notice and this permission notice appear in all copies.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  15  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  16  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  17  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  18  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  19  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  20  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  21  */
  22
  23 /*
  24  * ChaCha based random number generator for OpenBSD.
  25  */
  26
  27 #include "includes.h"
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <unistd.h>
  32 #include <sys/types.h>
  33
  34 #ifndef HAVE_ARC4RANDOM
  35
  36 #include <openssl/rand.h>
  37 #include <openssl/err.h>
  38
  39 #include "log.h"
  40
  41 #define KEYSTREAM_ONLY
  42 #include "chacha_private.h"
  43
  44 #ifdef __GNUC__
  45 #define inline __inline
  46 #else                           /* !__GNUC__ */
  47 #define inline
  48 #endif                          /* !__GNUC__ */
  49
  50 /* OpenSSH isn't multithreaded */
  51 #define _ARC4_LOCK()
  52 #define _ARC4_UNLOCK()
  53
  54 #define KEYSZ   32
  55 #define IVSZ    8
  56 #define BLOCKSZ 64
  57 #define RSBUFSZ (16*BLOCKSZ)
  58 static int rs_initialized;
  59 static pid_t rs_stir_pid;
  60 static chacha_ctx rs;           /* chacha context for random keystream */
  61 static u_char rs_buf[RSBUFSZ];  /* keystream blocks */
  62 static size_t rs_have;          /* valid bytes at end of rs_buf */
  63 static size_t rs_count;         /* bytes till reseed */
  64
  65 static inline void _rs_rekey(u_char *dat, size_t datlen);
  66
  67 static inline void
  68 _rs_init(u_char *buf, size_t n)
  69 {
  70         if (n < KEYSZ + IVSZ)
  71                 return;
  72         chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
  73         chacha_ivsetup(&rs, buf + KEYSZ);
  74 }
  75
  76 static void
  77 _rs_stir(void)
  78 {
  79         u_char rnd[KEYSZ + IVSZ];
  80
  81         if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
  82                 fatal("Couldn't obtain random bytes (error %ld)",
  83                     ERR_get_error());
  84
  85         if (!rs_initialized) {
  86                 rs_initialized = 1;
  87                 _rs_init(rnd, sizeof(rnd));
  88         } else
  89                 _rs_rekey(rnd, sizeof(rnd));
  90         explicit_bzero(rnd, sizeof(rnd));
  91
  92         /* invalidate rs_buf */
  93         rs_have = 0;
  94         memset(rs_buf, 0, RSBUFSZ);
  95
  96         rs_count = 1600000;
  97 }
  98
  99 static inline void
 100 _rs_stir_if_needed(size_t len)
 101 {
 102         pid_t pid = getpid();
 103
 104         if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
 105                 rs_stir_pid = pid;
 106                 _rs_stir();
 107         } else
 108                 rs_count -= len;
 109 }
 110
 111 static inline void
 112 _rs_rekey(u_char *dat, size_t datlen)
 113 {
 114 #ifndef KEYSTREAM_ONLY
 115         memset(rs_buf, 0,RSBUFSZ);
 116 #endif
 117         /* fill rs_buf with the keystream */
 118         chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
 119         /* mix in optional user provided data */
 120         if (dat) {
 121                 size_t i, m;
 122
 123                 m = MIN(datlen, KEYSZ + IVSZ);
 124                 for (i = 0; i < m; i++)
 125                         rs_buf[i] ^= dat[i];
 126         }
 127         /* immediately reinit for backtracking resistance */
 128         _rs_init(rs_buf, KEYSZ + IVSZ);
 129         memset(rs_buf, 0, KEYSZ + IVSZ);
 130         rs_have = RSBUFSZ - KEYSZ - IVSZ;
 131 }
 132
 133 static inline void
 134 _rs_random_buf(void *_buf, size_t n)
 135 {
 136         u_char *buf = (u_char *)_buf;
 137         size_t m;
 138
 139         _rs_stir_if_needed(n);
 140         while (n > 0) {
 141                 if (rs_have > 0) {
 142                         m = MIN(n, rs_have);
 143                         memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
 144                         memset(rs_buf + RSBUFSZ - rs_have, 0, m);
 145                         buf += m;
 146                         n -= m;
 147                         rs_have -= m;
 148                 }
 149                 if (rs_have == 0)
 150                         _rs_rekey(NULL, 0);
 151         }
 152 }
 153
 154 static inline void
 155 _rs_random_u32(u_int32_t *val)
 156 {
 157         _rs_stir_if_needed(sizeof(*val));
 158         if (rs_have < sizeof(*val))
 159                 _rs_rekey(NULL, 0);
 160         memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
 161         memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
 162         rs_have -= sizeof(*val);
 163         return;
 164 }
 165
 166 void
 167 arc4random_stir(void)
 168 {
 169         _ARC4_LOCK();
 170         _rs_stir();
 171         _ARC4_UNLOCK();
 172 }
 173
 174 void
 175 arc4random_addrandom(u_char *dat, int datlen)
 176 {
 177         int m;
 178
 179         _ARC4_LOCK();
 180         if (!rs_initialized)
 181                 _rs_stir();
 182         while (datlen > 0) {
 183                 m = MIN(datlen, KEYSZ + IVSZ);
 184                 _rs_rekey(dat, m);
 185                 dat += m;
 186                 datlen -= m;
 187         }
 188         _ARC4_UNLOCK();
 189 }
 190
 191 u_int32_t
 192 arc4random(void)
 193 {
 194         u_int32_t val;
 195
 196         _ARC4_LOCK();
 197         _rs_random_u32(&val);
 198         _ARC4_UNLOCK();
 199         return val;
 200 }
 201
 202 /*
 203  * If we are providing arc4random, then we can provide a more efficient
 204  * arc4random_buf().
 205  */
 206 # ifndef HAVE_ARC4RANDOM_BUF
 207 void
 208 arc4random_buf(void *buf, size_t n)
 209 {
 210         _ARC4_LOCK();
 211         _rs_random_buf(buf, n);
 212         _ARC4_UNLOCK();
 213 }
 214 # endif /* !HAVE_ARC4RANDOM_BUF */
 215 #endif /* !HAVE_ARC4RANDOM */
 216
 217 /* arc4random_buf() that uses platform arc4random() */
 218 #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
 219 void
 220 arc4random_buf(void *_buf, size_t n)
 221 {
 222         size_t i;
 223         u_int32_t r = 0;
 224         char *buf = (char *)_buf;
 225
 226         for (i = 0; i < n; i++) {
 227                 if (i % 4 == 0)
 228                         r = arc4random();
 229                 buf[i] = r & 0xff;
 230                 r >>= 8;
 231         }
 232         explicit_bzero(&r, sizeof(r));
 233 }
 234 #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
 235
 236 #ifndef HAVE_ARC4RANDOM_UNIFORM
 237 /*
 238  * Calculate a uniformly distributed random number less than upper_bound
 239  * avoiding "modulo bias".
 240  *
 241  * Uniformity is achieved by generating new random numbers until the one
 242  * returned is outside the range [0, 2**32 % upper_bound).  This
 243  * guarantees the selected random number will be inside
 244  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 245  * after reduction modulo upper_bound.
 246  */
 247 u_int32_t
 248 arc4random_uniform(u_int32_t upper_bound)
 249 {
 250         u_int32_t r, min;
 251
 252         if (upper_bound < 2)
 253                 return 0;
 254
 255         /* 2**32 % x == (2**32 - x) % x */
 256         min = -upper_bound % upper_bound;
 257
 258         /*
 259          * This could theoretically loop forever but each retry has
 260          * p > 0.5 (worst case, usually far better) of selecting a
 261          * number inside the range we need, so it should rarely need
 262          * to re-roll.
 263          */
 264         for (;;) {
 265                 r = arc4random();
 266                 if (r >= min)
 267                         break;
 268         }
 269
 270         return r % upper_bound;
 271 }
 272 #endif /* !HAVE_ARC4RANDOM_UNIFORM */
 273
 274 #if 0
 275 /*-------- Test code for i386 --------*/
 276 #include <stdio.h>
 277 #include <machine/pctr.h>
 278 int
 279 main(int argc, char **argv)
 280 {
 281         const int iter = 1000000;
 282         int     i;
 283         pctrval v;
 284
 285         v = rdtsc();
 286         for (i = 0; i < iter; i++)
 287                 arc4random();
 288         v = rdtsc() - v;
 289         v /= iter;
 290
 291         printf("%qd cycles\n", v);
 292         exit(0);
 293 }
 294 #endif