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 <sys/types.h>
  30
  31 #include <fcntl.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <unistd.h>
  35
  36 #ifndef HAVE_ARC4RANDOM
  37
  38 #ifdef WITH_OPENSSL
  39 #include <openssl/rand.h>
  40 #include <openssl/err.h>
  41 #endif
  42
  43 #include "log.h"
  44
  45 #define KEYSTREAM_ONLY
  46 #include "chacha_private.h"
  47
  48 #ifdef __GNUC__
  49 #define inline __inline
  50 #else                           /* !__GNUC__ */
  51 #define inline
  52 #endif                          /* !__GNUC__ */
  53
  54 /* OpenSSH isn't multithreaded */
  55 #define _ARC4_LOCK()
  56 #define _ARC4_UNLOCK()
  57
  58 #define KEYSZ   32
  59 #define IVSZ    8
  60 #define BLOCKSZ 64
  61 #define RSBUFSZ (16*BLOCKSZ)
  62 static int rs_initialized;
  63 static pid_t rs_stir_pid;
  64 static chacha_ctx rs;           /* chacha context for random keystream */
  65 static u_char rs_buf[RSBUFSZ];  /* keystream blocks */
  66 static size_t rs_have;          /* valid bytes at end of rs_buf */
  67 static size_t rs_count;         /* bytes till reseed */
  68
  69 static inline void _rs_rekey(u_char *dat, size_t datlen);
  70
  71 static inline void
  72 _rs_init(u_char *buf, size_t n)
  73 {
  74         if (n < KEYSZ + IVSZ)
  75                 return;
  76         chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
  77         chacha_ivsetup(&rs, buf + KEYSZ);
  78 }
  79
  80 #ifndef WITH_OPENSSL
  81 #define SSH_RANDOM_DEV "/dev/urandom"
  82 /* XXX use getrandom() if supported on Linux */
  83 static void
  84 getrnd(u_char *s, size_t len)
  85 {
  86         int fd;
  87         ssize_t r;
  88         size_t o = 0;
  89
  90         if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
  91                 fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
  92         while (o < len) {
  93                 r = read(fd, s + o, len - o);
  94                 if (r < 0) {
  95                         if (errno == EAGAIN || errno == EINTR ||
  96                             errno == EWOULDBLOCK)
  97                                 continue;
  98                         fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
  99                 }
 100                 o += r;
 101         }
 102         close(fd);
 103 }
 104 #endif
 105
 106 static void
 107 _rs_stir(void)
 108 {
 109         u_char rnd[KEYSZ + IVSZ];
 110
 111 #ifdef WITH_OPENSSL
 112         if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
 113                 fatal("Couldn't obtain random bytes (error 0x%lx)",
 114                     (unsigned long)ERR_get_error());
 115 #else
 116         getrnd(rnd, sizeof(rnd));
 117 #endif
 118
 119         if (!rs_initialized) {
 120                 rs_initialized = 1;
 121                 _rs_init(rnd, sizeof(rnd));
 122         } else
 123                 _rs_rekey(rnd, sizeof(rnd));
 124         explicit_bzero(rnd, sizeof(rnd));
 125
 126         /* invalidate rs_buf */
 127         rs_have = 0;
 128         memset(rs_buf, 0, RSBUFSZ);
 129
 130         rs_count = 1600000;
 131 }
 132
 133 static inline void
 134 _rs_stir_if_needed(size_t len)
 135 {
 136         pid_t pid = getpid();
 137
 138         if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
 139                 rs_stir_pid = pid;
 140                 _rs_stir();
 141         } else
 142                 rs_count -= len;
 143 }
 144
 145 static inline void
 146 _rs_rekey(u_char *dat, size_t datlen)
 147 {
 148 #ifndef KEYSTREAM_ONLY
 149         memset(rs_buf, 0,RSBUFSZ);
 150 #endif
 151         /* fill rs_buf with the keystream */
 152         chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
 153         /* mix in optional user provided data */
 154         if (dat) {
 155                 size_t i, m;
 156
 157                 m = MIN(datlen, KEYSZ + IVSZ);
 158                 for (i = 0; i < m; i++)
 159                         rs_buf[i] ^= dat[i];
 160         }
 161         /* immediately reinit for backtracking resistance */
 162         _rs_init(rs_buf, KEYSZ + IVSZ);
 163         memset(rs_buf, 0, KEYSZ + IVSZ);
 164         rs_have = RSBUFSZ - KEYSZ - IVSZ;
 165 }
 166
 167 static inline void
 168 _rs_random_buf(void *_buf, size_t n)
 169 {
 170         u_char *buf = (u_char *)_buf;
 171         size_t m;
 172
 173         _rs_stir_if_needed(n);
 174         while (n > 0) {
 175                 if (rs_have > 0) {
 176                         m = MIN(n, rs_have);
 177                         memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
 178                         memset(rs_buf + RSBUFSZ - rs_have, 0, m);
 179                         buf += m;
 180                         n -= m;
 181                         rs_have -= m;
 182                 }
 183                 if (rs_have == 0)
 184                         _rs_rekey(NULL, 0);
 185         }
 186 }
 187
 188 static inline void
 189 _rs_random_u32(u_int32_t *val)
 190 {
 191         _rs_stir_if_needed(sizeof(*val));
 192         if (rs_have < sizeof(*val))
 193                 _rs_rekey(NULL, 0);
 194         memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
 195         memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
 196         rs_have -= sizeof(*val);
 197         return;
 198 }
 199
 200 void
 201 arc4random_stir(void)
 202 {
 203         _ARC4_LOCK();
 204         _rs_stir();
 205         _ARC4_UNLOCK();
 206 }
 207
 208 void
 209 arc4random_addrandom(u_char *dat, int datlen)
 210 {
 211         int m;
 212
 213         _ARC4_LOCK();
 214         if (!rs_initialized)
 215                 _rs_stir();
 216         while (datlen > 0) {
 217                 m = MIN(datlen, KEYSZ + IVSZ);
 218                 _rs_rekey(dat, m);
 219                 dat += m;
 220                 datlen -= m;
 221         }
 222         _ARC4_UNLOCK();
 223 }
 224
 225 u_int32_t
 226 arc4random(void)
 227 {
 228         u_int32_t val;
 229
 230         _ARC4_LOCK();
 231         _rs_random_u32(&val);
 232         _ARC4_UNLOCK();
 233         return val;
 234 }
 235
 236 /*
 237  * If we are providing arc4random, then we can provide a more efficient
 238  * arc4random_buf().
 239  */
 240 # ifndef HAVE_ARC4RANDOM_BUF
 241 void
 242 arc4random_buf(void *buf, size_t n)
 243 {
 244         _ARC4_LOCK();
 245         _rs_random_buf(buf, n);
 246         _ARC4_UNLOCK();
 247 }
 248 # endif /* !HAVE_ARC4RANDOM_BUF */
 249 #endif /* !HAVE_ARC4RANDOM */
 250
 251 /* arc4random_buf() that uses platform arc4random() */
 252 #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
 253 void
 254 arc4random_buf(void *_buf, size_t n)
 255 {
 256         size_t i;
 257         u_int32_t r = 0;
 258         char *buf = (char *)_buf;
 259
 260         for (i = 0; i < n; i++) {
 261                 if (i % 4 == 0)
 262                         r = arc4random();
 263                 buf[i] = r & 0xff;
 264                 r >>= 8;
 265         }
 266         explicit_bzero(&r, sizeof(r));
 267 }
 268 #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
 269
 270 #ifndef HAVE_ARC4RANDOM_UNIFORM
 271 /*
 272  * Calculate a uniformly distributed random number less than upper_bound
 273  * avoiding "modulo bias".
 274  *
 275  * Uniformity is achieved by generating new random numbers until the one
 276  * returned is outside the range [0, 2**32 % upper_bound).  This
 277  * guarantees the selected random number will be inside
 278  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 279  * after reduction modulo upper_bound.
 280  */
 281 u_int32_t
 282 arc4random_uniform(u_int32_t upper_bound)
 283 {
 284         u_int32_t r, min;
 285
 286         if (upper_bound < 2)
 287                 return 0;
 288
 289         /* 2**32 % x == (2**32 - x) % x */
 290         min = -upper_bound % upper_bound;
 291
 292         /*
 293          * This could theoretically loop forever but each retry has
 294          * p > 0.5 (worst case, usually far better) of selecting a
 295          * number inside the range we need, so it should rarely need
 296          * to re-roll.
 297          */
 298         for (;;) {
 299                 r = arc4random();
 300                 if (r >= min)
 301                         break;
 302         }
 303
 304         return r % upper_bound;
 305 }
 306 #endif /* !HAVE_ARC4RANDOM_UNIFORM */
 307
 308 #if 0
 309 /*-------- Test code for i386 --------*/
 310 #include <stdio.h>
 311 #include <machine/pctr.h>
 312 int
 313 main(int argc, char **argv)
 314 {
 315         const int iter = 1000000;
 316         int     i;
 317         pctrval v;
 318
 319         v = rdtsc();
 320         for (i = 0; i < iter; i++)
 321                 arc4random();
 322         v = rdtsc() - v;
 323         v /= iter;
 324
 325         printf("%qd cycles\n", v);
 326         exit(0);
 327 }
 328 #endif