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 (file)
--- 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
 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 (file)
--- 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 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)
 
 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 (file)
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -18,7 +18,7 @@
 # USA
 #
 
 # 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 \
                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                               \
 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                               \
        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                                 \
        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                                           \
        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_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
 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 (file)
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 (file)
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 <stddef.h>
+# include <stdint.h>
+
+#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 (file)
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 <config.h>
+#include "types.h"
+
+#include <fcntl.h>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+
+#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 (file)
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 (file)
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 (file)
--- a/server/choose.c
+++ b/server/choose.c
@@ -56,6 +56,7 @@
 #include "trackname.h"
 #include "queue.h"
 #include "server-queue.h"
 #include "trackname.h"
 #include "queue.h"
 #include "server-queue.h"

+#include "random.h"

 
 #define BASE_WEIGHT 90000
 
 
 #define BASE_WEIGHT 90000
 


@@ -189,35 +190,6 @@ static unsigned long compute_weight(const char *track,
   return BASE_WEIGHT;
 }
 
   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;
 /** @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. */
 
   do {
     /* Actually get some random data. */

-    random_bytes(buf, nby);
+    random_get(buf, nby);

 
     /* Clobber the top byte.  */
     buf[0] &= m;
 
     /* Clobber the top byte.  */
     buf[0] &= m;