From: Richard Kettlewell Date: Mon, 19 May 2008 19:51:40 +0000 (+0100) Subject: disorder-choose now uses an arcfour keystream as its RNG instead of X-Git-Tag: 4.0~73 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/disorder/commitdiff_plain/fcdff1398b72c97915b11975046865fbdf2f8713 disorder-choose now uses an arcfour keystream as its RNG instead of hitting up /dev/urandom for every single byte. It is still seeded from the kernel's RNG. arcfour.[ch] come from gnulib. --- diff --git a/.bzrignore b/.bzrignore index b3032ad..1f06458 100644 --- a/.bzrignore +++ b/.bzrignore @@ -187,3 +187,4 @@ doc/disorder_options.5 doc/disorder_options.5.html doc/disorder_actions.5.in doc/disorder_templates.5.in +lib/t-arcfour diff --git a/README b/README index 774d95d..5f09fc2 100644 --- a/README +++ b/README @@ -273,6 +273,8 @@ Portions copyright (C) 2007 Mark Wooding Portions extracted from MPG321, http://mpg321.sourceforge.net/ Copyright (C) 2001 Joe Drew Copyright (C) 2000-2001 Robert Leslie +Portions Copyright (C) 2000, 2001, 2002, 2003, 2005, 2006 Free Software +Foundation, Inc. Binaries may derive extra copyright owners through linkage (binary distributors are expected to do their own legwork) diff --git a/lib/Makefile.am b/lib/Makefile.am index 9c9826f..70cf8dd 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -18,7 +18,7 @@ # USA # -TESTS=t-addr t-basen t-bits t-cache t-casefold t-cookies \ +TESTS=t-addr t-arcfour t-basen t-bits t-cache t-casefold t-cookies \ t-filepart t-hash t-heap t-hex t-kvp t-mime t-printf \ t-regsub t-selection t-signame t-sink t-split t-syscalls \ t-trackname t-unicode t-url t-utf8 t-vector t-words t-wstat \ @@ -37,6 +37,7 @@ endif libdisorder_a_SOURCES=charset.c charset.h \ addr.c addr.h \ alsabg.c alsabg.h \ + arcfour.c arcfour.h \ authhash.c authhash.h \ basen.c basen.h \ base64.c base64.h \ @@ -69,6 +70,7 @@ libdisorder_a_SOURCES=charset.c charset.h \ printf.c printf.h \ asprintf.c fprintf.c snprintf.c \ queue.c queue.h \ + random.c random.h \ regsub.c regsub.h \ rights.c queue-rights.c rights.h \ rtp.h \ @@ -127,6 +129,10 @@ t_addr_SOURCES=t-addr.c test.c test.h t_addr_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) t_addr_DEPENDENCIES=libdisorder.a +t_arcfour_SOURCES=t-arcfour.c test.c test.h +t_arcfour_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) +t_arcfour_DEPENDENCIES=libdisorder.a + t_basen_SOURCES=t-basen.c test.c test.h t_basen_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) t_basen_DEPENDENCIES=libdisorder.a diff --git a/lib/arcfour.c b/lib/arcfour.c new file mode 100644 index 0000000..42aaf2b --- /dev/null +++ b/lib/arcfour.c @@ -0,0 +1,76 @@ +/* arcfour.c --- The arcfour stream cipher + * Copyright (C) 2000, 2001, 2002, 2003, 2005, 2006 Free Software + * Foundation, Inc. + * + * This file is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * This file is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this file; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + * + */ + +/* Code from Libgcrypt adapted for gnulib by Simon Josefsson. */ + +/* + * For a description of the algorithm, see: + * Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996. + * ISBN 0-471-11709-9. Pages 397 ff. + */ + +#include "arcfour.h" + +void +arcfour_stream (arcfour_context * context, const char *inbuf, char *outbuf, + size_t length) +{ + uint8_t i = context->idx_i; + uint8_t j = context->idx_j; + char *sbox = context->sbox; + + for (; length > 0; length--) + { + char t; + + i++; + j += sbox[i]; + t = sbox[i]; + sbox[i] = sbox[j]; + sbox[j] = t; + *outbuf++ = (*inbuf++ + ^ sbox[(0U + sbox[i] + sbox[j]) % ARCFOUR_SBOX_SIZE]); + } + + context->idx_i = i; + context->idx_j = j; +} + +void +arcfour_setkey (arcfour_context * context, const char *key, size_t keylen) +{ + size_t i, j, k; + char *sbox = context->sbox; + + context->idx_i = context->idx_j = 0; + for (i = 0; i < ARCFOUR_SBOX_SIZE; i++) + sbox[i] = i; + for (i = j = k = 0; i < ARCFOUR_SBOX_SIZE; i++) + { + char t; + j = (j + sbox[i] + key[k]) % ARCFOUR_SBOX_SIZE; + t = sbox[i]; + sbox[i] = sbox[j]; + sbox[j] = t; + if (++k == keylen) + k = 0; + } +} diff --git a/lib/arcfour.h b/lib/arcfour.h new file mode 100644 index 0000000..0a9d75c --- /dev/null +++ b/lib/arcfour.h @@ -0,0 +1,51 @@ +/* arcfour.h --- The arcfour stream cipher + * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 + * Free Software Foundation, Inc. + * + * This file is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * This file is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this file; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + * + */ + +/* Code from Libgcrypt adapted for gnulib by Simon Josefsson. */ + +#ifndef ARCFOUR_H +# define ARCFOUR_H + +# include +# include + +#define ARCFOUR_SBOX_SIZE 256 + +typedef struct +{ + char sbox[ARCFOUR_SBOX_SIZE]; + uint8_t idx_i, idx_j; +} arcfour_context; + +/* Apply ARCFOUR stream to INBUF placing the result in OUTBUF, both of + LENGTH size. CONTEXT must be initialized with arcfour_setkey + before this function is called. */ +extern void +arcfour_stream (arcfour_context * context, + const char *inbuf, char *outbuf, size_t length); + +/* Initialize CONTEXT using encryption KEY of KEYLEN bytes. KEY + should be 40 bits (5 bytes) or longer. The KEY cannot be zero + length. */ +extern void +arcfour_setkey (arcfour_context * context, const char *key, size_t keylen); + +#endif /* ARCFOUR_H */ diff --git a/lib/random.c b/lib/random.c new file mode 100644 index 0000000..70e19f8 --- /dev/null +++ b/lib/random.c @@ -0,0 +1,85 @@ +/* + * This file is part of DisOrder + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ + +/** @file lib/random.c + * @brief Random number generator + * + */ + +#include +#include "types.h" + +#include +#include +#include +#include + +#include "random.h" +#include "log.h" +#include "arcfour.h" + +static int random_count; +static int random_fd = -1; +static arcfour_context random_ctx[1]; + +/** @brief Rekey the RNG + * + * Resets the RNG's key to a random one read from /dev/urandom + */ +static void random__rekey(void) { + char key[128]; + int n; + + if(random_fd < 0) { + if((random_fd = open("/dev/urandom", O_RDONLY)) < 0) + fatal(errno, "opening /dev/urandom"); + } + if((n = read(random_fd, key, sizeof key)) < 0) + fatal(errno, "reading from /dev/urandom"); + if((size_t)n < sizeof key) + fatal(0, "reading from /dev/urandom: short read"); + arcfour_setkey(random_ctx, key, sizeof key); + random_count = 8 * 1024 * 1024; +} + +/** @brief Get random bytes + * @param ptr Where to put random bytes + * @param bytes How many random bytes to generate + */ +void random_get(uint8_t *ptr, size_t bytes) { + if(random_count == 0) + random__rekey(); + /* Encrypting 0s == just returning the keystream */ + memset(ptr, 0, bytes); + arcfour_stream(random_ctx, (char *)ptr, (char *)ptr, bytes); + if(bytes > (size_t)random_count) + random_count = 0; + else + random_count -= bytes; +} + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/random.h b/lib/random.h new file mode 100644 index 0000000..f125e3c --- /dev/null +++ b/lib/random.h @@ -0,0 +1,39 @@ +/* + * This file is part of DisOrder + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ + +/** @file lib/random.h + * @brief Random number generator + * + */ +#ifndef RANDOM_H +#define RANDOM_H + +void random_get(uint8_t *ptr, size_t bytes); + +#endif /* RANDOM_H */ + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/t-arcfour.c b/lib/t-arcfour.c new file mode 100644 index 0000000..c0dce36 --- /dev/null +++ b/lib/t-arcfour.c @@ -0,0 +1,51 @@ +/* + * This file is part of DisOrder. + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ +#include "test.h" +#include "arcfour.h" + +#define TEST_ARCFOUR(K, P, C) do { \ + arcfour_setkey(ac, K, strlen(K)); \ + arcfour_stream(ac, P, (char *)output, strlen(P)); \ + output_hex = hex(output, strlen(P)); \ + check_string(output_hex, C); \ +} while(0) + +static void test_arcfour(void) { + arcfour_context ac[1]; + uint8_t output[64]; + char *output_hex; + + /* from wikipedia */ + TEST_ARCFOUR("Key", "Plaintext", "bbf316e8d940af0ad3"); + TEST_ARCFOUR("Wiki", "pedia", "1021bf0420"); + TEST_ARCFOUR("Secret", "Attack at dawn", "45a01f645fc35b383552544b9bf5"); + +} + +TEST(arcfour); + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/server/choose.c b/server/choose.c index dbb962c..927d613 100644 --- a/server/choose.c +++ b/server/choose.c @@ -56,6 +56,7 @@ #include "trackname.h" #include "queue.h" #include "server-queue.h" +#include "random.h" #define BASE_WEIGHT 90000 @@ -189,35 +190,6 @@ static unsigned long compute_weight(const char *track, return BASE_WEIGHT; } -static unsigned char random_buffer[4096]; -static size_t random_left; - -/** @brief Fill [buf, buf+n) with random bytes */ -static void random_bytes(unsigned char *buf, size_t n) { - while(n > 0) { - if(random_left > 0) { - const size_t this_time = n > random_left ? random_left : n; - - memcpy(buf, random_buffer + random_left - this_time, this_time); - n -= this_time; - random_left -= this_time; - } else { - static int fd = -1; - int r; - - if(fd < 0) { - if((fd = open("/dev/urandom", O_RDONLY)) < 0) - fatal(errno, "opening /dev/urandom"); - } - if((r = read(fd, random_buffer, sizeof random_buffer)) < 0) - fatal(errno, "reading /dev/urandom"); - if((size_t)r < sizeof random_buffer) - fatal(0, "short read from /dev/urandom"); - random_left = sizeof random_buffer; - } - } -} - /** @brief Pick a random integer uniformly from [0, limit) */ static unsigned long long pick_weight(unsigned long long limit) { unsigned char buf[(sizeof(unsigned long long) * CHAR_BIT + 7)/8], m; @@ -262,7 +234,7 @@ static unsigned long long pick_weight(unsigned long long limit) { do { /* Actually get some random data. */ - random_bytes(buf, nby); + random_get(buf, nby); /* Clobber the top byte. */ buf[0] &= m;