chiark / gitweb /
disorder-choose now uses an arcfour keystream as its RNG instead of
authorRichard Kettlewell <rjk@greenend.org.uk>
Mon, 19 May 2008 19:51:40 +0000 (20:51 +0100)
committerRichard Kettlewell <rjk@greenend.org.uk>
Mon, 19 May 2008 19:51:40 +0000 (20:51 +0100)
hitting up /dev/urandom for every single byte.  It is still seeded
from the kernel's RNG.

arcfour.[ch] come from gnulib.

.bzrignore
README
lib/Makefile.am
lib/arcfour.c [new file with mode: 0644]
lib/arcfour.h [new file with mode: 0644]
lib/random.c [new file with mode: 0644]
lib/random.h [new file with mode: 0644]
lib/t-arcfour.c [new file with mode: 0644]
server/choose.c

index b3032ad..1f06458 100644 (file)
@@ -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 (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 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)
 
index 9c9826f..70cf8dd 100644 (file)
@@ -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 (file)
index 0000000..42aaf2b
--- /dev/null
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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:
+*/
index dbb962c..927d613 100644 (file)
@@ -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;