From 9a356934a3a8aebc5822ec33f95340401a618b02 Mon Sep 17 00:00:00 2001 From: markus <> Date: Tue, 1 Oct 2013 18:34:57 +0000 Subject: replace rc4 with ChaCha20; inspired by Nick Mathewson's work on libottery; feedback and ok djm@ --- src/lib/libc/crypt/arc4random.c | 204 +++++++++++++++++++++------------------- 1 file changed, 106 insertions(+), 98 deletions(-) (limited to 'src/lib/libc/crypt/arc4random.c') diff --git a/src/lib/libc/crypt/arc4random.c b/src/lib/libc/crypt/arc4random.c index f00f5ee9f1..356e231815 100644 --- a/src/lib/libc/crypt/arc4random.c +++ b/src/lib/libc/crypt/arc4random.c @@ -1,8 +1,9 @@ -/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */ +/* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */ /* * Copyright (c) 1996, David Mazieres * Copyright (c) 2008, Damien Miller + * Copyright (c) 2013, Markus Friedl * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above @@ -18,20 +19,13 @@ */ /* - * Arc4 random number generator for OpenBSD. - * - * This code is derived from section 17.1 of Applied Cryptography, - * second edition, which describes a stream cipher allegedly - * compatible with RSA Labs "RC4" cipher (the actual description of - * which is a trade secret). The same algorithm is used as a stream - * cipher called "arcfour" in Tatu Ylonen's ssh package. - * - * RC4 is a registered trademark of RSA Laboratories. + * ChaCha based random number generator for OpenBSD. */ #include #include #include +#include #include #include #include @@ -39,64 +33,43 @@ #include #include "thread_private.h" +#define KEYSTREAM_ONLY +#include "chacha_private.h" + #ifdef __GNUC__ #define inline __inline #else /* !__GNUC__ */ #define inline #endif /* !__GNUC__ */ -struct arc4_stream { - u_int8_t i; - u_int8_t j; - u_int8_t s[256]; -}; - +#define KEYSZ 32 +#define IVSZ 8 +#define BLOCKSZ 64 +#define RSBUFSZ (16*BLOCKSZ) static int rs_initialized; -static struct arc4_stream rs; -static pid_t arc4_stir_pid; -static int arc4_count; - -static inline u_int8_t arc4_getbyte(void); +static pid_t rs_stir_pid; +static chacha_ctx rs; /* chacha context for random keystream */ +static u_char rs_buf[RSBUFSZ]; /* keystream blocks */ +static size_t rs_have; /* valid bytes at end of rs_buf */ +static size_t rs_count; /* bytes till reseed */ -static inline void -arc4_init(void) -{ - int n; - - for (n = 0; n < 256; n++) - rs.s[n] = n; - rs.i = 0; - rs.j = 0; -} +static inline void _rs_rekey(u_char *dat, size_t datlen); static inline void -arc4_addrandom(u_char *dat, int datlen) +_rs_init(u_char *buf, size_t n) { - int n; - u_int8_t si; - - rs.i--; - for (n = 0; n < 256; n++) { - rs.i = (rs.i + 1); - si = rs.s[rs.i]; - rs.j = (rs.j + si + dat[n % datlen]); - rs.s[rs.i] = rs.s[rs.j]; - rs.s[rs.j] = si; - } - rs.j = rs.i; + if (n < KEYSZ + IVSZ) + return; + chacha_keysetup(&rs, buf, KEYSZ * 8, 0); + chacha_ivsetup(&rs, buf + KEYSZ); } static void -arc4_stir(void) +_rs_stir(void) { - int i, mib[2]; + int mib[2]; size_t len; - u_char rnd[128]; - - if (!rs_initialized) { - arc4_init(); - rs_initialized = 1; - } + u_char rnd[KEYSZ + IVSZ]; mib[0] = CTL_KERN; mib[1] = KERN_ARND; @@ -104,68 +77,109 @@ arc4_stir(void) len = sizeof(rnd); sysctl(mib, 2, rnd, &len, NULL, 0); - arc4_addrandom(rnd, sizeof(rnd)); + if (!rs_initialized) { + rs_initialized = 1; + _rs_init(rnd, sizeof(rnd)); + } else + _rs_rekey(rnd, sizeof(rnd)); + memset(rnd, 0, sizeof(rnd)); - /* - * Discard early keystream, as per recommendations in: - * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps - */ - for (i = 0; i < 256; i++) - (void)arc4_getbyte(); - arc4_count = 1600000; + /* invalidate rs_buf */ + rs_have = 0; + memset(rs_buf, 0, RSBUFSZ); + + rs_count = 1600000; } -static void -arc4_stir_if_needed(void) +static inline void +_rs_stir_if_needed(size_t len) { pid_t pid = getpid(); - if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) { - arc4_stir_pid = pid; - arc4_stir(); + if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) { + rs_stir_pid = pid; + _rs_stir(); + } else + rs_count -= len; +} + +static inline void +_rs_rekey(u_char *dat, size_t datlen) +{ +#ifndef KEYSTREAM_ONLY + memset(rs_buf, 0,RSBUFSZ); +#endif + /* fill rs_buf with the keystream */ + chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); + /* mix in optional user provided data */ + if (dat) { + size_t i, m; + + m = MIN(datlen, KEYSZ + IVSZ); + for (i = 0; i < m; i++) + rs_buf[i] ^= dat[i]; } + /* immediately reinit for backtracking resistance */ + _rs_init(rs_buf, KEYSZ + IVSZ); + memset(rs_buf, 0, KEYSZ + IVSZ); + rs_have = RSBUFSZ - KEYSZ - IVSZ; } -static inline u_int8_t -arc4_getbyte(void) +static inline void +_rs_random_buf(void *_buf, size_t n) { - u_int8_t si, sj; - - rs.i = (rs.i + 1); - si = rs.s[rs.i]; - rs.j = (rs.j + si); - sj = rs.s[rs.j]; - rs.s[rs.i] = sj; - rs.s[rs.j] = si; - return (rs.s[(si + sj) & 0xff]); + u_char *buf = (u_char *)_buf; + size_t m; + + _rs_stir_if_needed(n); + while (n > 0) { + if (rs_have > 0) { + m = MIN(n, rs_have); + memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); + memset(rs_buf + RSBUFSZ - rs_have, 0, m); + buf += m; + n -= m; + rs_have -= m; + } + if (rs_have == 0) + _rs_rekey(NULL, 0); + } } -static inline u_int32_t -arc4_getword(void) +static inline void +_rs_random_u32(u_int32_t *val) { - u_int32_t val; - val = arc4_getbyte() << 24; - val |= arc4_getbyte() << 16; - val |= arc4_getbyte() << 8; - val |= arc4_getbyte(); - return val; + _rs_stir_if_needed(sizeof(*val)); + if (rs_have < sizeof(*val)) + _rs_rekey(NULL, 0); + memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); + memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); + rs_have -= sizeof(*val); + return; } void arc4random_stir(void) { _ARC4_LOCK(); - arc4_stir(); + _rs_stir(); _ARC4_UNLOCK(); } void arc4random_addrandom(u_char *dat, int datlen) { + int m; + _ARC4_LOCK(); if (!rs_initialized) - arc4_stir(); - arc4_addrandom(dat, datlen); + _rs_stir(); + while (datlen > 0) { + m = MIN(datlen, KEYSZ + IVSZ); + _rs_rekey(dat, m); + dat += m; + datlen -= m; + } _ARC4_UNLOCK(); } @@ -173,25 +187,18 @@ u_int32_t arc4random(void) { u_int32_t val; + _ARC4_LOCK(); - arc4_count -= 4; - arc4_stir_if_needed(); - val = arc4_getword(); + _rs_random_u32(&val); _ARC4_UNLOCK(); return val; } void -arc4random_buf(void *_buf, size_t n) +arc4random_buf(void *buf, size_t n) { - u_char *buf = (u_char *)_buf; _ARC4_LOCK(); - arc4_stir_if_needed(); - while (n--) { - if (--arc4_count <= 0) - arc4_stir(); - buf[n] = arc4_getbyte(); - } + _rs_random_buf(buf, n); _ARC4_UNLOCK(); } @@ -249,5 +256,6 @@ main(int argc, char **argv) v /= iter; printf("%qd cycles\n", v); + exit(0); } #endif -- cgit v1.2.3-55-g6feb