/* * random.c -- A (strong?) random number generator for SunSolaris * * Version 0.2, last modified 11-May-2000 * * Copyright (c) Andreas Maier, 2000. All rights reserved. * Andreas Maier * * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, and the entire permission notice in its entirety, * including the disclaimer of warranties. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. The name of the author may not be used to endorse or promote * products derived from this software without specific prior * written permission. * * ALTERNATIVELY, this product may be distributed under the terms of * the GNU Public License, in which case the provisions of the GPL are * required INSTEAD OF the above restrictions. (This clause is * necessary due to a potential bad interaction between the GPL and * the restrictions contained in a BSD-style copyright.) * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. */ /* * These routines provide /dev/random and /dev/urandom, similar to the * devices found in Linux, and used by cryptographic software (e.g. open-ssl). */ /* * Acknowledgements: * ================= * * This software is a poor mans adaptation of 'random.c', which is part * of the Linux kernel source, and written by Theodore Ts'o. * For a 'theory of operation' look at Theodore Ts'o code. You can * find a very good and extensive description there. * * Details on Sun Solaris device drivers can be found in * 'Writing Device Drivers', Sun Microsystems, PartNo: 805-3024-10. * This document is available online at the Sun Developer Connection. * * Any flaws in the design are solely my responsibility, and should * not be attributed to Theodore Ts'o or Sun Microsystems. */ /* * Cryptographic software needs good random numbers. On way to provide * such numbers is by gathering various unpredictable events in the * kernel. This collected information can than be read on a character * interface. Unfortunatly Sun Solaris (as of version 7) does not have * such an interface. This is a try to fix the problem by means of a * loadable kernel module. * * * NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE * * -) The sources for randomness are poor. * -) There is no such thing as a randomness estimate. * -) This software is only tested on my SunSparc20 / Solaris7. * -) /dev/random and /dev/urandom are the same (no blocking). * -) No ioctls * * NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE NOTE */ /* * Installation: * ============= * * Create a file '/usr/kernel/drv/random.conf' with contents similar to: * name="random" parent="pseudo" instance=0; * * Append the following lines to '/etc/devlink.tab': * type=ddi_pseudo;name=random;addr=0;minor=random \M0 * type=ddi_pseudo;name=random;addr=0;minor=urandom \M0 * type=ddi_pseudo;name=random \M0\N0 * * (note that a TAB _must_ separate the second argument) * * Compile this file (gcc 2.8.1 works for me): * % (g)cc -D_KERNEL -O2 -c random.c * % ld -r -o random random.o * * Install the driver: * # cp random /usr/kernel/drv * # add_drv -m '* 0644 root sys' random * * Preload random data at startup: * The random pool can be initialized at system startup by * a script containing a line simmilar to: * dd if=$random_seed_file of=/dev/urandom */ /* * History: * ======== * * v0.2: * rand_chpoll (for poll/select system call) added * v0.1: * Initial Release. */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define RAND_DEV "random" /* more or less standard device names */ #define URAND_DEV "urandom" #define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */ struct rand_state { dev_info_t * dip; /* device (kernel needs this) */ struct pollhead pollhead; /* for chpoll */ kmutex_t guard; /* data update mutex */ unsigned int add_ptr; unsigned int entropy_count; uint32_t pool[POOLWORDS]; /* pool of random numbers */ }; static int rand_getinfo (dev_info_t * dip, ddi_info_cmd_t infocmd, void * arg, void ** result); static int rand_attach (dev_info_t * dip, ddi_attach_cmd_t cmd); static int rand_detach (dev_info_t * dip, ddi_attach_cmd_t cmd); static int rand_open (dev_t * devp, int flag, int otyp, cred_t * credp); static int rand_close (dev_t devp, int flag, int otyp, cred_t * credp); /* static int rand_ioctl (dev_t dev, int cmd, int arg, int mode, cred_t * credp, int * rvalp); */ static int rand_read (dev_t dev, uio_t * uiop, cred_t * credp); static int rand_write (dev_t dev, uio_t * uiop, cred_t * credp); static int rand_chpoll (dev_t dev, short int events, int anyyet, short int * reventsp, struct pollhead ** phpp); static void add_entropy_words (struct rand_state * r, uint32_t x, uint32_t y); static int extract_entropy (struct rand_state * r, uio_t * uiop); static void add_timer_rand (struct rand_state * r); static void add_pid_rand (struct rand_state * r); /* device access routines */ static struct cb_ops cb_ops = { rand_open, /* open */ rand_close, /* close */ nodev, /* strategy (blockdev) */ nodev, /* print (blockdev) */ nodev, /* dump (blockdev) */ rand_read, /* read */ rand_write, /* write */ nodev, /* ioctl */ nodev, /* devmap */ nodev, /* mmap */ nodev, /* segmap */ rand_chpoll, /* chpoll */ ddi_prop_op, /* prop_op */ NULL, /* STREAMS ops */ (D_NEW | D_MP), /* flags */ CB_REV, /* revision */ nodev, /* aread */ nodev /* awrite */ }; /* device setup */ static struct dev_ops dev_ops = { DEVO_REV, /* revision */ 0, /* refcnt */ rand_getinfo, /* getinfo */ nulldev, /* identify (obsolete) */ nulldev, /* probe */ rand_attach, /* attach */ rand_detach, /* detach */ nodev, /* reset (not impl) */ &cb_ops, /* cb_ops */ NULL, /* bus_ops */ NULL /* power */ }; /* loadable module support */ static struct modldrv modldrv = { &mod_driverops, "[u]random devices v0.2", &dev_ops }; static struct modlinkage modlinkage = { MODREV_1, { &modldrv, NULL } }; /* head of per instance data struct */ static void * rs; /* load the module, alloc mem, and install the module */ int _init (void) { int err; err = ddi_soft_state_init (&rs, sizeof (struct rand_state), 1); if (err == 0) { err = mod_install (&modlinkage); if (err != 0) { ddi_soft_state_fini (&rs); } } return (err); } /* remove the module, and free mem */ int _fini (void) { int err; err = mod_remove (&modlinkage); if (err == 0) { ddi_soft_state_fini (&rs); } return (err); } /* supply info needed by the module loader */ int _info (struct modinfo * modinfop) { return (mod_info (&modlinkage, modinfop)); } /* create one driver instance */ static int rand_attach (dev_info_t * dip, ddi_attach_cmd_t cmd) { minor_t instance; struct rand_state * rsp; switch (cmd) { case DDI_ATTACH: instance = ddi_get_instance (dip); if (ddi_soft_state_zalloc (rs, instance) != DDI_SUCCESS) { cmn_err(CE_CONT, "%s%d: can't allocate state\n", ddi_get_name(dip), instance); return (DDI_FAILURE); } else { rsp = ddi_get_soft_state (rs, instance); } if (ddi_create_minor_node (dip, RAND_DEV, S_IFCHR, (instance * 2), DDI_PSEUDO, 0) != DDI_SUCCESS) { ddi_soft_state_free (rs, instance); return (DDI_FAILURE); } else if (ddi_create_minor_node (dip, URAND_DEV, S_IFCHR, ((instance * 2) + 1), DDI_PSEUDO, 0) != DDI_SUCCESS) { ddi_remove_minor_node (dip, NULL); ddi_soft_state_free (rs, instance); return (DDI_FAILURE); } rsp->dip = dip; mutex_init (&(rsp->guard), NULL, MUTEX_DRIVER, NULL); /* report our presence */ ddi_report_dev (dip); add_timer_rand (rsp); return (DDI_SUCCESS); break; default: return (DDI_FAILURE); break; } return (DDI_FAILURE); } /* destroy one driver instance */ static int rand_detach (dev_info_t * dip, ddi_attach_cmd_t cmd) { minor_t instance; struct rand_state * rsp; switch (cmd) { case DDI_DETACH: ddi_prop_remove_all (dip); instance = ddi_get_instance (dip); rsp = ddi_get_soft_state (rs, instance); if (rsp != NULL) { mutex_destroy (&(rsp->guard)); } ddi_remove_minor_node (dip, NULL); ddi_soft_state_free (rs, instance); return (DDI_SUCCESS); break; default: return (DDI_FAILURE); break; } return (DDI_FAILURE); } /* supply instance specific information */ static int rand_getinfo (dev_info_t * dip, ddi_info_cmd_t infocmd, void * arg, void ** result) { struct rand_state * rsp; int instance; instance = getminor ((dev_t) arg) / 2; switch (infocmd) { case DDI_INFO_DEVT2INSTANCE: * result = (void *) instance; return (DDI_SUCCESS); break; case DDI_INFO_DEVT2DEVINFO: rsp = ddi_get_soft_state (rs, instance); if (rsp != NULL) { * result = rsp->dip; add_timer_rand (rsp); return (DDI_SUCCESS); } else { return (DDI_FAILURE); } break; default: return (DDI_FAILURE); break; } return (DDI_FAILURE); } static int rand_open (dev_t * devp, int flag, int otyp, cred_t * credp) { minor_t instance; struct rand_state * rsp; instance = getminor (* devp) / 2; /* a character device? */ if (otyp != OTYP_CHR) { return (EINVAL); } /* valid minor number? */ rsp = ddi_get_soft_state (rs, instance); if (rsp == NULL) { return (ENXIO); } add_pid_rand (rsp); return (0); } static int rand_close (dev_t devp, int flag, int otyp, cred_t * credp) { minor_t instance; struct rand_state * rsp; instance = getminor (devp) / 2; /* valid minor number? */ rsp = ddi_get_soft_state (rs, instance); if (rsp == NULL) { return (ENXIO); } add_pid_rand (rsp); return (0); } static int rand_read (dev_t dev, uio_t * uiop, cred_t * credp) { struct rand_state * rsp; int instance; instance = getminor (dev) / 2; /* valid minor number? */ rsp = ddi_get_soft_state (rs, instance); if (rsp == NULL) { return (ENXIO); } add_pid_rand (rsp); return (extract_entropy (rsp, uiop)); } static int rand_write (dev_t dev, struct uio * uiop, cred_t * credp) { struct rand_state * rsp; int instance; uint32_t buf[16]; int i; int err; instance = getminor (dev) / 2; rsp = ddi_get_soft_state (rs, instance); if (rsp == NULL) { cmn_err (CE_CONT, "=== write(): invalied minor\n"); return (ENXIO); } while (uiop->uio_resid > 0) { err = uiomove ((caddr_t) buf, sizeof (buf), UIO_WRITE, uiop); if (err != 0) { return (err); } i = sizeof (buf) / (2 * sizeof (buf[0])); while (i > 0) { i --; add_entropy_words (rsp, buf[2 * i], buf[2 * i + 1]); } } add_pid_rand (rsp); return (0); } static int rand_chpoll (dev_t dev, short int events, int anyyet, short int * reventsp, struct pollhead ** phpp) { struct rand_state * rsp; int instance; instance = getminor (dev) / 2; /* valid minor number? */ rsp = ddi_get_soft_state (rs, instance); if (rsp == NULL) { return (ENXIO); } if ((events & (POLLIN | POLLOUT | POLLNORM)) != 0) { * reventsp = events & (POLLIN | POLLOUT | POLLNORM); } else { * reventsp = 0; if (anyyet == 0) { * phpp = & (rsp->pollhead); } } add_pid_rand (rsp); return (0); } /* add entropy be means of high resolution timer and kernel timer ticks */ static void add_timer_rand (struct rand_state * r) { int ticks; if (drv_getparm (TIME, &ticks) == 0) { add_entropy_words (r, (uint32_t) gethrtime(), (uint32_t) ticks); } } /* add entropy be means of high resolution timer and caller PID */ static void add_pid_rand (struct rand_state * r) { int pid; if (drv_getparm (PPID, &pid) == 0) { add_entropy_words (r, (uint32_t) gethrtime (), (uint32_t) pid); } } /* * This function adds a byte into the entropy "pool". It does not * update the entropy estimate. The caller must do this if appropriate. * * This function is tuned for speed above most other considerations. * * The pool is stirred with a primitive polynomial of the appropriate degree, * and then twisted. We twist by three bits at a time because it's * cheap to do so and helps slightly in the expected case where the * entropy is concentrated in the low-order bits. */ #define MASK(x) ((x) & (POOLWORDS - 1)) /* Convenient abreviation */ #define TAP1 103 #define TAP2 76 #define TAP3 51 #define TAP4 25 #define TAP5 1 static void add_entropy_words (struct rand_state * r, uint32_t x, uint32_t y) { static uint32_t const twist_table[8] = { 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; unsigned int i; mutex_enter (&(r->guard)); i = MASK (r->add_ptr - 2); /* i is always even */ r->add_ptr = i; /* * XOR in the various taps. Even though logically, we compute * x and then compute y, we read in y then x order because most * caches work slightly better with increasing read addresses. */ y ^= r->pool[MASK(i+TAP1)]; x ^= r->pool[MASK(i+TAP1+1)]; y ^= r->pool[MASK(i+TAP2)]; x ^= r->pool[MASK(i+TAP2+1)]; y ^= r->pool[MASK(i+TAP3)]; x ^= r->pool[MASK(i+TAP3+1)]; y ^= r->pool[MASK(i+TAP4)]; x ^= r->pool[MASK(i+TAP4+1)]; y ^= r->pool[MASK(i+TAP5)]; x ^= r->pool[MASK(i+TAP5+1)]; y ^= r->pool[i]; x ^= r->pool[i+1]; r->pool[i] = (y >> 3) ^ twist_table[y & 7]; r->pool[i+1] = (x >> 3) ^ twist_table[x & 7]; mutex_exit (&(r->guard)); } /* * This chunk of code defines a function * void SHATransform(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE], * __u32 const data[16]) * * The function hashes the input data to produce a digest in the first * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE * more words for internal purposes. (This buffer is exported so the * caller can wipe it once rather than this code doing it each call, * and tacking it onto the end of the digest[] array is the quick and * dirty way of doing it.) * * It so happens that MD5 and SHA share most of the initial vector * used to initialize the digest[] array before the first call: * 1) 0x67452301 * 2) 0xefcdab89 * 3) 0x98badcfe * 4) 0x10325476 * 5) 0xc3d2e1f0 (SHA only) * * For /dev/random purposes, the length of the data being hashed is * fixed in length (at POOLWORDS words), so appending a bit count in * the usual way is not cryptographically necessary. */ /* * SHA transform algorithm, taken from code written by Peter Gutmann, * and placed in the public domain. */ /* The SHA f()-functions. */ #define f1(x,y,z) (z ^ (x & (y ^ z))) /* Rounds 0-19: x ? y : z */ #define f2(x,y,z) (x ^ y ^ z) /* Rounds 20-39: XOR */ #define f3(x,y,z) ((x & y) + (z & (x ^ y))) /* Rounds 40-59: majority */ #define f4(x,y,z) (x ^ y ^ z) /* Rounds 60-79: XOR */ /* The SHA Mysterious Constants */ #define K1 0x5A827999L /* Rounds 0-19: sqrt(2) * 2^30 */ #define K2 0x6ED9EBA1L /* Rounds 20-39: sqrt(3) * 2^30 */ #define K3 0x8F1BBCDCL /* Rounds 40-59: sqrt(5) * 2^30 */ #define K4 0xCA62C1D6L /* Rounds 60-79: sqrt(10) * 2^30 */ #define ROTL(n,X) (((X) << n) | ((X) >> (32 - n))) #define HASH_BUFFER_SIZE 5 #define HASH_EXTRA_SIZE 80 static void SHATransform (uint32_t digest[85], uint32_t const data[16]) { uint32_t A, B, C, D, E; /* Local vars */ uint32_t TEMP; uint32_t * W; int i; /* * Do the preliminary expansion of 16 to 80 words. Doing it * out-of-line line this is faster than doing it in-line on * register-starved machines like the x86, and not really any * slower on real processors. */ W = digest + HASH_BUFFER_SIZE; bcopy (data, W, sizeof (data)); for (i = 0; i < 64; i++) { TEMP = W[i] ^ W[i + 2] ^ W[i + 8] ^ W[i + 13]; W[i + 16] = ROTL (1, TEMP); } /* Set up first buffer and local data buffer */ A = digest[0]; B = digest[1]; C = digest[2]; D = digest[3]; E = digest[4]; /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */ for (i = 0; i < 80; i++) { if (i < 40) { if (i < 20) TEMP = f1 (B, C, D) + K1; else TEMP = f2 (B, C, D) + K2; } else { if (i < 60) TEMP = f3 (B, C, D) + K3; else TEMP = f4 (B, C, D) + K4; } TEMP += ROTL (5, A) + E + W[i]; E = D; D = C; C = ROTL (30, B); B = A; A = TEMP; } /* Build message digest */ digest[0] += A; digest[1] += B; digest[2] += C; digest[3] += D; digest[4] += E; } #undef f1 #undef f2 #undef f3 #undef f4 #undef K1 #undef K2 #undef K3 #undef K4 #undef ROTL /* * This function extracts randomness from the "entropy pool", and * returns it in a buffer. This function computes how many remaining * bits of entropy are left in the pool, but it does not restrict the * number of bytes that are actually obtained. */ #if POOLWORDS % 16 != 0 #error extract_entropy() assumes that POOLWORDS is a multiple of 16 words. #endif static int extract_entropy (struct rand_state * r, uio_t * uiop) { uint32_t tmp[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; int i; int err; while (uiop->uio_resid > 0) { /* Hash the pool to get the output */ tmp[0] = 0x67452301; tmp[1] = 0xefcdab89; tmp[2] = 0x98badcfe; tmp[3] = 0x10325476; tmp[4] = 0xc3d2e1f0; for (i = 0; i < POOLWORDS; i += 16) { SHATransform (tmp, r->pool + i); } /* * The following code does two separate things that happen * to both work two words at a time, so are convenient * to do together. * * First, this feeds the output back into the pool so * that the next call will return different results. * Any perturbation of the pool's state would do, even * changing one bit, but this mixes the pool nicely. * * Second, this folds the output in half to hide the data * fed back into the pool from the user and further mask * any patterns in the hash output. (The exact folding * pattern is not important; the one used here is quick.) * * Fold the middle word by half. */ add_entropy_words (r, tmp[0], tmp[3]); tmp[0] ^= tmp[3]; add_entropy_words (r, tmp[1], tmp[4]); tmp[1] ^= tmp[4]; tmp[2] = ((tmp[2] ^ (tmp[2] >> 16)) & 0x0000ffff) | (tmp[2] & 0xffff0000L); /* Copy data to destination */ err = uiomove ((caddr_t) tmp, HASH_BUFFER_SIZE * (sizeof (uint32_t) / 2), UIO_READ, uiop); if (err != 0) { return (err); } } /* Wipe data just returned from memory */ bzero (tmp, sizeof(tmp)); return (0); }