| 1 | /*␊ |
| 2 | * Copyright (c) 1996, David Mazieres <dm@uun.org>␊ |
| 3 | * Copyright (c) 2008, Damien Miller <djm@openbsd.org>␊ |
| 4 | *␊ |
| 5 | * Permission to use, copy, modify, and distribute this software for any␊ |
| 6 | * purpose with or without fee is hereby granted, provided that the above␊ |
| 7 | * copyright notice and this permission notice appear in all copies.␊ |
| 8 | *␊ |
| 9 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES␊ |
| 10 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF␊ |
| 11 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR␊ |
| 12 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES␊ |
| 13 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN␊ |
| 14 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF␊ |
| 15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.␊ |
| 16 | */␊ |
| 17 | ␊ |
| 18 | /*␊ |
| 19 | * Arc4 random number generator for OpenBSD.␊ |
| 20 | *␊ |
| 21 | * This code is derived from section 17.1 of Applied Cryptography,␊ |
| 22 | * second edition, which describes a stream cipher allegedly␊ |
| 23 | * compatible with RSA Labs "RC4" cipher (the actual description of␊ |
| 24 | * which is a trade secret). The same algorithm is used as a stream␊ |
| 25 | * cipher called "arcfour" in Tatu Ylonen's ssh package.␊ |
| 26 | *␊ |
| 27 | * Here the stream cipher has been modified always to include the time␊ |
| 28 | * when initializing the state. That makes it impossible to␊ |
| 29 | * regenerate the same random sequence twice, so this can't be used␊ |
| 30 | * for encryption, but will generate good random numbers.␊ |
| 31 | *␊ |
| 32 | * RC4 is a registered trademark of RSA Laboratories.␊ |
| 33 | */␊ |
| 34 | ␊ |
| 35 | ␊ |
| 36 | #include "libsaio.h"␊ |
| 37 | ␊ |
| 38 | ␊ |
| 39 | struct arc4_stream {␊ |
| 40 | ␉u_int8_t i;␊ |
| 41 | ␉u_int8_t j;␊ |
| 42 | ␉u_int8_t s[256];␊ |
| 43 | };␊ |
| 44 | ␊ |
| 45 | ␊ |
| 46 | #define KEYSIZE␉␉128␊ |
| 47 | ␊ |
| 48 | static struct arc4_stream rs = {␊ |
| 49 | ␉.i = 0,␊ |
| 50 | ␉.j = 0,␊ |
| 51 | ␉.s = {␊ |
| 52 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,␊ |
| 53 | 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,␊ |
| 54 | 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,␊ |
| 55 | 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,␊ |
| 56 | 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,␊ |
| 57 | 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,␊ |
| 58 | 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,␊ |
| 59 | ␉␉112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,␊ |
| 60 | ␉␉128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,␊ |
| 61 | ␉␉144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,␊ |
| 62 | ␉␉160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,␊ |
| 63 | ␉␉176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,␊ |
| 64 | ␉␉192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,␊ |
| 65 | ␉␉208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,␊ |
| 66 | ␉␉224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,␊ |
| 67 | ␉␉240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255␊ |
| 68 | ␉}␊ |
| 69 | };␊ |
| 70 | //static int rs_initialized;␊ |
| 71 | static int rs_stired;␊ |
| 72 | static int arc4_count;␊ |
| 73 | ␊ |
| 74 | static inline u_int8_t arc4_getbyte(void);␊ |
| 75 | static void arc4_stir(void);␊ |
| 76 | __private_extern__ void _arc4_fork_child(void);␊ |
| 77 | ␊ |
| 78 | static struct {␊ |
| 79 | ␉struct timeval␉tv;␊ |
| 80 | ␉u_int8_t␉rnd[KEYSIZE];␊ |
| 81 | } rdat;␊ |
| 82 | static volatile int rs_data_available = 0;␊ |
| 83 | ␊ |
| 84 | static inline void␊ |
| 85 | arc4_addrandom(u_char *dat, int datlen)␊ |
| 86 | {␊ |
| 87 | ␉int n;␊ |
| 88 | ␉u_int8_t si;␊ |
| 89 | ␊ |
| 90 | ␉rs.i--;␊ |
| 91 | ␉for (n = 0; n < 256; n++) {␊ |
| 92 | ␉␉rs.i = (rs.i + 1);␊ |
| 93 | ␉␉si = rs.s[rs.i];␊ |
| 94 | ␉␉rs.j = (rs.j + si + dat[n % datlen]);␊ |
| 95 | ␉␉rs.s[rs.i] = rs.s[rs.j];␊ |
| 96 | ␉␉rs.s[rs.j] = si;␊ |
| 97 | ␉}␊ |
| 98 | ␉rs.j = rs.i;␊ |
| 99 | }␊ |
| 100 | ␊ |
| 101 | static void␊ |
| 102 | arc4_fetch(void)␊ |
| 103 | {␊ |
| 104 | ␉␊ |
| 105 | ␉(void)gettimeofday(&rdat.tv, NULL);␊ |
| 106 | ␉␊ |
| 107 | }␊ |
| 108 | ␊ |
| 109 | static void␊ |
| 110 | arc4_stir(void)␊ |
| 111 | {␊ |
| 112 | ␉int n;␊ |
| 113 | ␉/*␊ |
| 114 | ␉ * If we don't have data, we need some now before we can integrate␊ |
| 115 | ␉ * it into the static buffers␊ |
| 116 | ␉ */␊ |
| 117 | ␉if (!rs_data_available)␊ |
| 118 | ␉{␊ |
| 119 | ␉␉arc4_fetch();␊ |
| 120 | ␉}␊ |
| 121 | ␉rs_data_available = 0;␊ |
| 122 | ␉__sync_synchronize();␊ |
| 123 | ␊ |
| 124 | ␉arc4_addrandom((u_char *)&rdat, KEYSIZE);␊ |
| 125 | ␊ |
| 126 | ␉/*␊ |
| 127 | ␉ * Throw away the first N bytes of output, as suggested in the␊ |
| 128 | ␉ * paper "Weaknesses in the Key Scheduling Algorithm of RC4"␊ |
| 129 | ␉ * by Fluher, Mantin, and Shamir. N=1024 is based on␊ |
| 130 | ␉ * suggestions in the paper "(Not So) Random Shuffles of RC4"␊ |
| 131 | ␉ * by Ilya Mironov.␊ |
| 132 | ␉ */␊ |
| 133 | ␉for (n = 0; n < 1024; n++)␊ |
| 134 | ␉␉(void) arc4_getbyte();␊ |
| 135 | ␉arc4_count = 1600000;␊ |
| 136 | ␉rs_stired = 1;␊ |
| 137 | }␊ |
| 138 | ␊ |
| 139 | static inline u_int8_t␊ |
| 140 | arc4_getbyte(void)␊ |
| 141 | {␊ |
| 142 | ␉u_int8_t si, sj;␊ |
| 143 | ␊ |
| 144 | ␉rs.i = (rs.i + 1);␊ |
| 145 | ␉si = rs.s[rs.i];␊ |
| 146 | ␉rs.j = (rs.j + si);␊ |
| 147 | ␉sj = rs.s[rs.j];␊ |
| 148 | ␉rs.s[rs.i] = sj;␊ |
| 149 | ␉rs.s[rs.j] = si;␊ |
| 150 | ␊ |
| 151 | ␉return (rs.s[(si + sj) & 0xff]);␊ |
| 152 | }␊ |
| 153 | ␊ |
| 154 | static inline u_int32_t␊ |
| 155 | arc4_getword(void)␊ |
| 156 | {␊ |
| 157 | ␉u_int32_t val;␊ |
| 158 | ␊ |
| 159 | ␉val = arc4_getbyte() << 24;␊ |
| 160 | ␉val |= arc4_getbyte() << 16;␊ |
| 161 | ␉val |= arc4_getbyte() << 8;␊ |
| 162 | ␉val |= arc4_getbyte();␊ |
| 163 | ␊ |
| 164 | ␉return (val);␊ |
| 165 | }␊ |
| 166 | ␊ |
| 167 | /* 7944700: force restir in child */␊ |
| 168 | __private_extern__ void␊ |
| 169 | _arc4_fork_child(void)␊ |
| 170 | {␊ |
| 171 | ␉rs_stired = 0;␊ |
| 172 | ␉rs_data_available = 0;␊ |
| 173 | }␊ |
| 174 | ␊ |
| 175 | static inline int␊ |
| 176 | arc4_check_stir(void)␊ |
| 177 | {␊ |
| 178 | ␉if (!rs_stired || arc4_count <= 0) {␊ |
| 179 | ␉␉arc4_stir();␊ |
| 180 | ␉␉return 1;␊ |
| 181 | ␉}␊ |
| 182 | ␉return 0;␊ |
| 183 | }␊ |
| 184 | ␊ |
| 185 | void␊ |
| 186 | arc4random_stir(void)␊ |
| 187 | {␊ |
| 188 | ␉arc4_stir();␊ |
| 189 | }␊ |
| 190 | ␊ |
| 191 | void␊ |
| 192 | arc4random_addrandom(u_char *dat, int datlen)␊ |
| 193 | {␊ |
| 194 | ␉arc4_check_stir();␊ |
| 195 | ␉arc4_addrandom(dat, datlen);␊ |
| 196 | }␊ |
| 197 | ␊ |
| 198 | u_int32_t␊ |
| 199 | arc4random(void)␊ |
| 200 | {␊ |
| 201 | ␉u_int32_t rnd;␊ |
| 202 | ␊ |
| 203 | ␉int did_stir = arc4_check_stir();␊ |
| 204 | ␉rnd = arc4_getword();␊ |
| 205 | ␉arc4_count -= 4;␊ |
| 206 | ␊ |
| 207 | ␉if (did_stir)␊ |
| 208 | ␉{␊ |
| 209 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
| 210 | ␉␉arc4_fetch();␊ |
| 211 | ␉␉rs_data_available = 1;␊ |
| 212 | ␉␉__sync_synchronize();␊ |
| 213 | ␉}␊ |
| 214 | ␊ |
| 215 | ␉return (rnd);␊ |
| 216 | }␊ |
| 217 | ␊ |
| 218 | void␊ |
| 219 | arc4random_buf(void *_buf, size_t n)␊ |
| 220 | {␊ |
| 221 | ␉u_char *buf = (u_char *)_buf;␊ |
| 222 | ␉int did_stir = 0;␊ |
| 223 | ␊ |
| 224 | ␉while (n--) {␊ |
| 225 | ␉␉if (arc4_check_stir())␊ |
| 226 | ␉␉{␊ |
| 227 | ␉␉␉did_stir = 1;␊ |
| 228 | ␉␉}␊ |
| 229 | ␉␉buf[n] = arc4_getbyte();␊ |
| 230 | ␉␉arc4_count--;␊ |
| 231 | ␉}␊ |
| 232 | ␉␊ |
| 233 | ␉if (did_stir)␊ |
| 234 | ␉{␊ |
| 235 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
| 236 | ␉␉arc4_fetch();␊ |
| 237 | ␉␉rs_data_available = 1;␊ |
| 238 | ␉␉__sync_synchronize();␊ |
| 239 | ␉}␊ |
| 240 | }␊ |
| 241 | ␊ |
| 242 | /*␊ |
| 243 | * Calculate a uniformly distributed random number less than upper_bound␊ |
| 244 | * avoiding "modulo bias".␊ |
| 245 | *␊ |
| 246 | * Uniformity is achieved by generating new random numbers until the one␊ |
| 247 | * returned is outside the range [0, 2**32 % upper_bound). This␊ |
| 248 | * guarantees the selected random number will be inside␊ |
| 249 | * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)␊ |
| 250 | * after reduction modulo upper_bound.␊ |
| 251 | */␊ |
| 252 | u_int32_t␊ |
| 253 | arc4random_uniform(u_int32_t upper_bound)␊ |
| 254 | {␊ |
| 255 | ␉u_int32_t r, min;␊ |
| 256 | ␊ |
| 257 | ␉if (upper_bound < 2)␊ |
| 258 | ␉␉return (0);␊ |
| 259 | ␊ |
| 260 | #if (ULONG_MAX > 0xffffffffUL)␊ |
| 261 | ␉min = 0x100000000UL % upper_bound;␊ |
| 262 | #else␊ |
| 263 | ␉/* Calculate (2**32 % upper_bound) avoiding 64-bit math */␊ |
| 264 | ␉if (upper_bound > 0x80000000)␊ |
| 265 | ␉␉min = 1 + ~upper_bound;␉␉/* 2**32 - upper_bound */␊ |
| 266 | ␉else {␊ |
| 267 | ␉␉/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */␊ |
| 268 | ␉␉min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;␊ |
| 269 | ␉}␊ |
| 270 | #endif␊ |
| 271 | ␊ |
| 272 | ␉/*␊ |
| 273 | ␉ * This could theoretically loop forever but each retry has␊ |
| 274 | ␉ * p > 0.5 (worst case, usually far better) of selecting a␊ |
| 275 | ␉ * number inside the range we need, so it should rarely need␊ |
| 276 | ␉ * to re-roll.␊ |
| 277 | ␉ */␊ |
| 278 | ␉for (;;) {␊ |
| 279 | ␉␉r = arc4random();␊ |
| 280 | ␉␉if (r >= min)␊ |
| 281 | ␉␉␉break;␊ |
| 282 | ␉}␊ |
| 283 | ␊ |
| 284 | ␉return (r % upper_bound);␊ |
| 285 | }␊ |
| 286 | ␊ |
| 287 | #if 0␊ |
| 288 | void␊ |
| 289 | arc4_init(void)␊ |
| 290 | {␉␊ |
| 291 | }␊ |
| 292 | ␊ |
| 293 | /*-------- Test code for i386 --------*/␊ |
| 294 | #include <stdio.h>␊ |
| 295 | #include <machine/pctr.h>␊ |
| 296 | int␊ |
| 297 | main(int argc, char **argv)␊ |
| 298 | {␊ |
| 299 | ␉const int iter = 1000000;␊ |
| 300 | ␉int i;␊ |
| 301 | ␉pctrval v;␊ |
| 302 | ␊ |
| 303 | ␉v = rdtsc();␊ |
| 304 | ␉for (i = 0; i < iter; i++)␊ |
| 305 | ␉␉arc4random();␊ |
| 306 | ␉v = rdtsc() - v;␊ |
| 307 | ␉v /= iter;␊ |
| 308 | ␊ |
| 309 | ␉printf("%qd cycles\n", v);␊ |
| 310 | }␊ |
| 311 | #endif␊ |
| 312 | |
