Annotation of src/usr.bin/ssh/randoms.c, Revision 1.1
1.1 ! deraadt 1: /*
! 2:
! 3: random.c
! 4:
! 5: Author: Tatu Ylonen <ylo@cs.hut.fi>
! 6:
! 7: Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
! 8: All rights reserved
! 9:
! 10: Created: Sat Mar 4 14:55:57 1995 ylo
! 11:
! 12: Cryptographically strong random number generation.
! 13:
! 14: */
! 15:
! 16: #include "includes.h"
! 17: RCSID("$Id: randoms.c,v 1.3 1999/05/04 11:58:58 bg Exp $");
! 18:
! 19: #include "randoms.h"
! 20: #include "getput.h"
! 21: #include "ssh_md5.h"
! 22:
! 23: #ifdef HAVE_GETRUSAGE
! 24: #include <sys/resource.h>
! 25: #ifdef HAVE_RUSAGE_H
! 26: #include <sys/rusage.h>
! 27: #endif /* HAVE_RUSAGE_H */
! 28: #endif /* HAVE_GETRUSAGE */
! 29:
! 30: #ifdef HAVE_TIMES
! 31: #include <sys/times.h>
! 32: #endif /* HAVE_TIMES */
! 33:
! 34: /* Initializes the random number generator, loads any random information
! 35: from the given file, and acquires as much environmental noise as it
! 36: can to initialize the random number generator. More noise can be
! 37: acquired later by calling random_add_noise + random_stir, or by
! 38: calling random_get_environmental_noise again later when the environmental
! 39: situation has changed. */
! 40:
! 41: void random_initialize(RandomState *state, const char *filename)
! 42: {
! 43: char buf[8192];
! 44: int f, bytes;
! 45:
! 46: state->add_position = 0;
! 47: state->next_available_byte = sizeof(state->stir_key);
! 48:
! 49: /* This isn't strictly necessary, but will keep programs like 3rd degree or
! 50: purify silent. */
! 51: memset(state, 0, sizeof(state));
! 52:
! 53: /* Get noise from the file. */
! 54: random_add_noise(state, filename, strlen(filename)); /* Use the path. */
! 55: f = open(filename, O_RDONLY);
! 56: if (f >= 0)
! 57: {
! 58: state->state[0] += f;
! 59: bytes = read(f, buf, sizeof(buf));
! 60: close(f);
! 61: if (bytes > 0)
! 62: random_add_noise(state, buf, bytes);
! 63: memset(buf, 0, sizeof(buf));
! 64: }
! 65: else
! 66: {
! 67: /* Get all possible noise since we have no seed. */
! 68: random_acquire_environmental_noise(state);
! 69: random_save(state, filename);
! 70: }
! 71:
! 72: /* Get easily available noise from the environment. */
! 73: random_acquire_light_environmental_noise(state);
! 74: }
! 75:
! 76: void random_xor_noise(RandomState *state, unsigned int i, word32 value)
! 77: {
! 78: value ^= GET_32BIT(state->state + 4 * i);
! 79: PUT_32BIT(state->state + 4 * i, value);
! 80: }
! 81:
! 82: /* Acquires as much environmental noise as it can. This is probably quite
! 83: sufficient on a unix machine, but might be grossly inadequate on a
! 84: single-user PC or a Macintosh.
! 85:
! 86: We test the elapsed real time after each command, and abort if we have
! 87: consumed over 30 seconds. */
! 88:
! 89: void random_acquire_environmental_noise(RandomState *state)
! 90: {
! 91: time_t start_time;
! 92:
! 93: /* Record the start time. */
! 94: start_time = time(NULL);
! 95:
! 96: /* Run these first so that other statistics accumulate from these. We stop
! 97: collecting more noise when we have spent 30 seconds real time; on a large
! 98: system a single executed command is probably enough, whereas on small
! 99: systems we must use all possible noise sources. */
! 100: random_get_noise_from_command(state, "ps laxww 2>/dev/null");
! 101: if (time(NULL) - start_time < 30)
! 102: random_get_noise_from_command(state, "ps -al 2>/dev/null");
! 103: if (time(NULL) - start_time < 30)
! 104: random_get_noise_from_command(state, "ls -alni /tmp/. 2>/dev/null");
! 105: if (time(NULL) - start_time < 30)
! 106: random_get_noise_from_command(state, "w 2>/dev/null");
! 107: if (time(NULL) - start_time < 30)
! 108: random_get_noise_from_command(state, "netstat -s 2>/dev/null");
! 109: if (time(NULL) - start_time < 30)
! 110: random_get_noise_from_command(state, "netstat -an 2>/dev/null");
! 111: if (time(NULL) - start_time < 30)
! 112: random_get_noise_from_command(state, "netstat -in 2>/dev/null");
! 113:
! 114: /* Get other easily available noise. */
! 115: random_acquire_light_environmental_noise(state);
! 116: }
! 117:
! 118: /* Acquires easily available environmental noise. */
! 119:
! 120: void random_acquire_light_environmental_noise(RandomState *state)
! 121: {
! 122: int f;
! 123: char buf[32];
! 124: int len;
! 125:
! 126: /* If /dev/random is available, read some data from there in non-blocking
! 127: mode and mix it into the pool. */
! 128: f = open("/dev/random", O_RDONLY);
! 129: if (f >= 0)
! 130: {
! 131: /* Set the descriptor into non-blocking mode. */
! 132: #if defined(O_NONBLOCK) && !defined(O_NONBLOCK_BROKEN)
! 133: fcntl(f, F_SETFL, O_NONBLOCK);
! 134: #else /* O_NONBLOCK && !O_NONBLOCK_BROKEN */
! 135: fcntl(f, F_SETFL, O_NDELAY);
! 136: #endif /* O_NONBLOCK && !O_NONBLOCK_BROKEN */
! 137: len = read(f, buf, sizeof(buf));
! 138: close(f);
! 139: if (len > 0)
! 140: random_add_noise(state, buf, len);
! 141: }
! 142:
! 143: /* Get miscellaneous noise from various system parameters and statistics. */
! 144: random_xor_noise(state,
! 145: (unsigned int)(state->state[0] + 256*state->state[1]) %
! 146: (RANDOM_STATE_BYTES / 4),
! 147: (word32)time(NULL));
! 148:
! 149: #ifdef HAVE_GETTIMEOFDAY
! 150: {
! 151: struct timeval tv;
! 152: gettimeofday(&tv, NULL);
! 153: random_xor_noise(state, 0, (word32)tv.tv_usec);
! 154: random_xor_noise(state, 1, (word32)tv.tv_sec);
! 155: #ifdef HAVE_CLOCK
! 156: random_xor_noise(state, 3, (word32)clock());
! 157: #endif /* HAVE_CLOCK */
! 158: }
! 159: #endif /* HAVE_GETTIMEOFDAY */
! 160: #ifdef HAVE_TIMES
! 161: {
! 162: struct tms tm;
! 163: random_xor_noise(state, 2, (word32)times(&tm));
! 164: random_xor_noise(state, 4, (word32)(tm.tms_utime ^ (tm.tms_stime << 8) ^
! 165: (tm.tms_cutime << 16) ^
! 166: (tm.tms_cstime << 24)));
! 167: }
! 168: #endif /* HAVE_TIMES */
! 169: #ifdef HAVE_GETRUSAGE
! 170: {
! 171: struct rusage ru, cru;
! 172: getrusage(RUSAGE_SELF, &ru);
! 173: getrusage(RUSAGE_CHILDREN, &cru);
! 174: random_xor_noise(state, 0, (word32)(ru.ru_utime.tv_usec +
! 175: cru.ru_utime.tv_usec));
! 176: random_xor_noise(state, 2, (word32)(ru.ru_stime.tv_usec +
! 177: cru.ru_stime.tv_usec));
! 178: random_xor_noise(state, 5, (word32)(ru.ru_maxrss + cru.ru_maxrss));
! 179: random_xor_noise(state, 6, (word32)(ru.ru_ixrss + cru.ru_ixrss));
! 180: random_xor_noise(state, 7, (word32)(ru.ru_idrss + cru.ru_idrss));
! 181: random_xor_noise(state, 8, (word32)(ru.ru_minflt + cru.ru_minflt));
! 182: random_xor_noise(state, 9, (word32)(ru.ru_majflt + cru.ru_majflt));
! 183: random_xor_noise(state, 10, (word32)(ru.ru_nswap + cru.ru_nswap));
! 184: random_xor_noise(state, 11, (word32)(ru.ru_inblock + cru.ru_inblock));
! 185: random_xor_noise(state, 12, (word32)(ru.ru_oublock + cru.ru_oublock));
! 186: random_xor_noise(state, 13, (word32)((ru.ru_msgsnd ^ ru.ru_msgrcv ^
! 187: ru.ru_nsignals) +
! 188: (cru.ru_msgsnd ^ cru.ru_msgrcv ^
! 189: cru.ru_nsignals)));
! 190: random_xor_noise(state, 14, (word32)(ru.ru_nvcsw + cru.ru_nvcsw));
! 191: random_xor_noise(state, 15, (word32)(ru.ru_nivcsw + cru.ru_nivcsw));
! 192: }
! 193: #endif /* HAVE_GETRUSAGE */
! 194: random_xor_noise(state, 11, (word32)getpid());
! 195: random_xor_noise(state, 12, (word32)getppid());
! 196: random_xor_noise(state, 10, (word32)getuid());
! 197: random_xor_noise(state, 10, (word32)(getgid() << 16));
! 198: #ifdef _POSIX_CHILD_MAX
! 199: random_xor_noise(state, 13, (word32)(_POSIX_CHILD_MAX << 16));
! 200: #endif /* _POSIX_CHILD_MAX */
! 201: #ifdef CLK_TCK
! 202: random_xor_noise(state, 14, (word32)(CLK_TCK << 16));
! 203: #endif /* CLK_TCK */
! 204:
! 205: random_stir(state);
! 206: }
! 207:
! 208: /* Executes the given command, and processes its output as noise. */
! 209:
! 210: void random_get_noise_from_command(RandomState *state, const char *cmd)
! 211: {
! 212: #ifdef HAVE_POPEN
! 213: char line[1000];
! 214: FILE *f;
! 215:
! 216: f = popen(cmd, "r");
! 217: if (!f)
! 218: return;
! 219: while (fgets(line, sizeof(line), f))
! 220: random_add_noise(state, line, strlen(line));
! 221: pclose(f);
! 222: memset(line, 0, sizeof(line));
! 223: #endif /* HAVE_POPEN */
! 224: }
! 225:
! 226: /* Adds the contents of the buffer as noise. */
! 227:
! 228: void random_add_noise(RandomState *state, const void *buf, unsigned int bytes)
! 229: {
! 230: unsigned int pos = state->add_position;
! 231: const char *input = buf;
! 232: while (bytes > 0)
! 233: {
! 234: if (pos >= RANDOM_STATE_BYTES)
! 235: {
! 236: pos = 0;
! 237: random_stir(state);
! 238: }
! 239: state->state[pos] ^= *input;
! 240: input++;
! 241: bytes--;
! 242: pos++;
! 243: }
! 244: state->add_position = pos;
! 245: }
! 246:
! 247: /* Stirs the random pool to consume any newly acquired noise or to get more
! 248: random numbers.
! 249:
! 250: This works by encrypting the data in the buffer in CFB mode with MD5 as
! 251: the cipher. */
! 252:
! 253: void random_stir(RandomState *state)
! 254: {
! 255: uint32 iv[4];
! 256: unsigned int i;
! 257:
! 258: /* Start IV from last block of random pool. */
! 259: iv[0] = GET_32BIT(state->state);
! 260: iv[1] = GET_32BIT(state->state + 4);
! 261: iv[2] = GET_32BIT(state->state + 8);
! 262: iv[3] = GET_32BIT(state->state + 12);
! 263:
! 264: /* First CFB pass. */
! 265: for (i = 0; i < RANDOM_STATE_BYTES; i += 16)
! 266: {
! 267: MD5Transform(iv, state->stir_key);
! 268: iv[0] ^= GET_32BIT(state->state + i);
! 269: PUT_32BIT(state->state + i, iv[0]);
! 270: iv[1] ^= GET_32BIT(state->state + i + 4);
! 271: PUT_32BIT(state->state + i + 4, iv[1]);
! 272: iv[2] ^= GET_32BIT(state->state + i + 8);
! 273: PUT_32BIT(state->state + i + 8, iv[2]);
! 274: iv[3] ^= GET_32BIT(state->state + i + 12);
! 275: PUT_32BIT(state->state + i + 12, iv[3]);
! 276: }
! 277:
! 278: /* Get new key. */
! 279: memcpy(state->stir_key, state->state, sizeof(state->stir_key));
! 280:
! 281: /* Second CFB pass. */
! 282: for (i = 0; i < RANDOM_STATE_BYTES; i += 16)
! 283: {
! 284: MD5Transform(iv, state->stir_key);
! 285: iv[0] ^= GET_32BIT(state->state + i);
! 286: PUT_32BIT(state->state + i, iv[0]);
! 287: iv[1] ^= GET_32BIT(state->state + i + 4);
! 288: PUT_32BIT(state->state + i + 4, iv[1]);
! 289: iv[2] ^= GET_32BIT(state->state + i + 8);
! 290: PUT_32BIT(state->state + i + 8, iv[2]);
! 291: iv[3] ^= GET_32BIT(state->state + i + 12);
! 292: PUT_32BIT(state->state + i + 12, iv[3]);
! 293: }
! 294:
! 295: memset(iv, 0, sizeof(iv));
! 296:
! 297: state->add_position = 0;
! 298:
! 299: /* Some data in the beginning is not returned to aboid giving an observer
! 300: complete knowledge of the contents of our random pool. */
! 301: state->next_available_byte = sizeof(state->stir_key);
! 302: }
! 303:
! 304: /* Returns a random byte. Stirs the random pool if necessary. Acquires
! 305: new environmental noise approximately every five minutes. */
! 306:
! 307: unsigned int random_get_byte(RandomState *state)
! 308: {
! 309: if (state->next_available_byte >= RANDOM_STATE_BYTES)
! 310: {
! 311: /* Get some easily available noise. More importantly, this stirs
! 312: the pool. */
! 313: random_acquire_light_environmental_noise(state);
! 314: }
! 315: assert(state->next_available_byte < RANDOM_STATE_BYTES);
! 316: return state->state[state->next_available_byte++];
! 317: }
! 318:
! 319: /* Saves random data in a disk file. This is used to create a file that
! 320: can be used as a random seed on future runs. Only half of the random
! 321: data in our pool is written to the file to avoid an observer being
! 322: able to deduce the contents of our random pool from the file. */
! 323:
! 324: void random_save(RandomState *state, const char *filename)
! 325: {
! 326: char buf[RANDOM_STATE_BYTES / 2]; /* Save only half of its bits. */
! 327: int i, f;
! 328:
! 329: /* Get some environmental noise to make it harder to predict previous
! 330: values from saved bits (besides, we have now probably consumed some
! 331: resources so the noise may be really useful). This also stirs
! 332: the pool. */
! 333: random_acquire_light_environmental_noise(state);
! 334:
! 335: /* Get as many bytes as is half the size of the pool. I am assuming
! 336: this will get enough randomness for it to be very useful, but will
! 337: not reveal enough to make it possible to determine previous or future
! 338: returns by the generator. */
! 339: for (i = 0; i < sizeof(buf); i++)
! 340: buf[i] = random_get_byte(state);
! 341:
! 342: /* Again get a little noise and stir it to mix the unrevealed half with
! 343: those bits that have been saved to a file. There should be enough
! 344: unrevealed bits (plus the new noise) to make it infeasible to try to
! 345: guess future values from the saved bits. */
! 346: random_acquire_light_environmental_noise(state);
! 347:
! 348: /* Create and write the file. Failure to create the file is silently
! 349: ignored. */
! 350: f = open(filename, O_WRONLY|O_CREAT|O_TRUNC, 0600);
! 351: if (f >= 0)
! 352: {
! 353: /* Creation successful. Write data to the file. */
! 354: write(f, buf, sizeof(buf));
! 355: close(f);
! 356: }
! 357: memset(buf, 0, sizeof(buf));
! 358: }
! 359:
! 360: /* Clears the random number generator data structures. */
! 361:
! 362: void random_clear(RandomState *state)
! 363: {
! 364: memset(state, 0, sizeof(*state));
! 365: }