Improve random number generation
authorEric Biggers <ebiggers3@gmail.com>
Tue, 27 Dec 2016 02:27:29 +0000 (20:27 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Tue, 27 Dec 2016 03:11:05 +0000 (21:11 -0600)
wimlib used rand() to generate random numbers, e.g. for GUIDs.  This was
neither cryptographically secure nor thread-safe.  Use getrandom(),
/dev/urandom, or RtlGenRandom() instead.

configure.ac
include/wimlib/guid.h
include/wimlib/util.h
src/mount_image.c
src/util.c
src/win32_apply.c
src/win32_replacements.c
src/write.c

index 46dd6f0..d7de0b0 100644 (file)
@@ -75,6 +75,7 @@ AC_CHECK_HEADERS([alloca.h            \
                  sys/byteorder.h       \
                  sys/endian.h          \
                  sys/file.h            \
+                 sys/syscall.h         \
                  sys/sysctl.h          \
                  sys/times.h           \
                  sys/xattr.h           \
@@ -90,6 +91,13 @@ AC_CHECK_MEMBER([struct stat.st_mtim],
                [],
                [#include <sys/stat.h>])
 
+# Check for possible support for the Linux getrandom() system call
+AC_CHECK_DECL([__NR_getrandom],
+             [AC_DEFINE([HAVE_NR_GETRANDOM], [1], [Define to 1 if the system
+              headers define a system call number for getrandom()])],
+             [],
+             [#include <sys/syscall.h>])
+
 ###############################################################################
 #                           Required libraries                               #
 ###############################################################################
index be9a10f..8c5e306 100644 (file)
@@ -34,7 +34,7 @@ guids_equal(const u8 guid1[GUID_SIZE], const u8 guid2[GUID_SIZE])
 static inline void
 generate_guid(u8 guid[GUID_SIZE])
 {
-       return randomize_byte_array(guid, GUID_SIZE);
+       return get_random_bytes(guid, GUID_SIZE);
 }
 
 #endif /* _WIMLIB_GUID_H */
index 82fc5fb..3dc59f4 100644 (file)
@@ -88,11 +88,15 @@ extern void *
 mempcpy(void *dst, const void *src, size_t n);
 #endif
 
+/**************************
+ * Random number generation
+ **************************/
+
 extern void
-randomize_byte_array(u8 *p, size_t n);
+get_random_bytes(void *p, size_t n);
 
 extern void
-randomize_char_array_with_alnum(tchar *p, size_t n);
+get_random_alnum_chars(tchar *p, size_t n);
 
 /************************
  * Hashing and comparison
index ed9001c..8ad4fdc 100644 (file)
@@ -669,7 +669,7 @@ create_staging_file(const struct wimfs_context *ctx, char **name_ret)
        name[STAGING_FILE_NAME_LEN] = '\0';
 
 retry:
-       randomize_char_array_with_alnum(name, STAGING_FILE_NAME_LEN);
+       get_random_alnum_chars(name, STAGING_FILE_NAME_LEN);
        fd = openat(ctx->staging_dir_fd, name,
                    O_WRONLY | O_CREAT | O_EXCL | O_NOFOLLOW, 0600);
        if (unlikely(fd < 0)) {
@@ -853,7 +853,7 @@ make_staging_dir_at(int parent_dir_fd, const char *wim_basename,
        p = staging_dir_name;
        p = mempcpy(p, wim_basename, wim_basename_len);
        p = mempcpy(p, common_suffix, sizeof(common_suffix));
-       randomize_char_array_with_alnum(p, random_suffix_len);
+       get_random_alnum_chars(p, random_suffix_len);
        p += random_suffix_len;
        *p = '\0';
 
@@ -2305,7 +2305,7 @@ generate_message_queue_name(char name[WIMFS_MQUEUE_NAME_LEN + 1])
 {
        name[0] = '/';
        memcpy(name + 1, "wimfs-", 6);
-       randomize_char_array_with_alnum(name + 7, WIMFS_MQUEUE_NAME_LEN - 7);
+       get_random_alnum_chars(name + 7, WIMFS_MQUEUE_NAME_LEN - 7);
        name[WIMFS_MQUEUE_NAME_LEN] = '\0';
 }
 
index 47aedd4..0fe3d4e 100644 (file)
@@ -24,6 +24,7 @@
 #endif
 
 #include <errno.h>
+#include <fcntl.h>
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -32,6 +33,9 @@
 #  include <sys/types.h>
 #  include <sys/sysctl.h>
 #endif
+#ifdef HAVE_SYS_SYSCALL_H
+#  include <sys/syscall.h>
+#endif
 #include <unistd.h>
 
 #include "wimlib.h"
@@ -166,41 +170,110 @@ void *mempcpy(void *dst, const void *src, size_t n)
 }
 #endif
 
-static bool seeded = false;
+/**************************
+ * Random number generation
+ **************************/
 
-static void
-seed_random(void)
+#ifndef __WIN32__
+/*
+ * Generate @n cryptographically secure random bytes (thread-safe)
+ *
+ * This is the UNIX version.  It uses the Linux getrandom() system call if
+ * available; otherwise, it falls back to reading from /dev/urandom.
+ */
+void
+get_random_bytes(void *p, size_t n)
 {
-       srand(now_as_wim_timestamp());
-       seeded = true;
+       if (n == 0)
+               return;
+#ifdef HAVE_NR_GETRANDOM
+       static bool getrandom_unavailable;
+
+       if (getrandom_unavailable)
+               goto try_dev_urandom;
+       do {
+               int res = syscall(__NR_getrandom, p, n, 0);
+               if (unlikely(res < 0)) {
+                       if (errno == ENOSYS) {
+                               getrandom_unavailable = true;
+                               goto try_dev_urandom;
+                       }
+                       if (errno == EINTR)
+                               continue;
+                       ERROR_WITH_ERRNO("getrandom() failed");
+                       wimlib_assert(0);
+                       res = 0;
+               }
+               p += res;
+               n -= res;
+       } while (n != 0);
+       return;
+
+try_dev_urandom:
+       ;
+#endif /* HAVE_NR_GETRANDOM */
+       int fd = open("/dev/urandom", O_RDONLY);
+       if (fd < 0) {
+               ERROR_WITH_ERRNO("Unable to open /dev/urandom");
+               wimlib_assert(0);
+       }
+       do {
+               int res = read(fd, p, min(n, INT_MAX));
+               if (unlikely(res < 0)) {
+                       if (errno == EINTR)
+                               continue;
+                       ERROR_WITH_ERRNO("Error reading from /dev/urandom");
+                       wimlib_assert(0);
+                       res = 0;
+               }
+               p += res;
+               n -= res;
+       } while (n != 0);
+       close(fd);
 }
+#endif /* !__WIN32__ */
 
-/* Fills @n characters pointed to by @p with random alphanumeric characters. */
+/*
+ * Generate @n cryptographically secure random alphanumeric characters
+ * (thread-safe)
+ *
+ * This is implemented on top of get_random_bytes().  For efficiency the calls
+ * to get_random_bytes() are batched.
+ */
 void
-randomize_char_array_with_alnum(tchar *p, size_t n)
+get_random_alnum_chars(tchar *p, size_t n)
 {
-       if (!seeded)
-               seed_random();
-       while (n--) {
-               int r = rand() % 62;
-               if (r < 26)
-                       *p++ = r + 'a';
-               else if (r < 52)
-                       *p++ = r - 26 + 'A';
+       u32 r[64];
+       int r_idx = 0;
+       int r_end = 0;
+
+       for (; n != 0; p++, n--) {
+               tchar x;
+
+               if (r_idx >= r_end) {
+                       r_idx = 0;
+                       r_end = min(n, ARRAY_LEN(r));
+                       get_random_bytes(r, r_end * sizeof(r[0]));
+               }
+
+               STATIC_ASSERT(sizeof(r[0]) == sizeof(u32));
+               while (unlikely(r[r_idx] >= UINT32_MAX - (UINT32_MAX % 62)))
+                       get_random_bytes(&r[r_idx], sizeof(r[0]));
+
+               x = r[r_idx++] % 62;
+
+               if (x < 26)
+                       *p = 'a' + x;
+               else if (x < 52)
+                       *p = 'A' + x - 26;
                else
-                       *p++ = r - 52 + '0';
+                       *p = '0' + x - 52;
        }
 }
 
-/* Fills @n bytes pointer to by @p with random numbers. */
-void
-randomize_byte_array(u8 *p, size_t n)
-{
-       if (!seeded)
-               seed_random();
-       while (n--)
-               *p++ = rand();
-}
+/************************
+ * System information
+ ************************/
 
 #ifndef __WIN32__
 unsigned
index f971ca6..96d9df6 100644 (file)
@@ -807,7 +807,7 @@ end_wimboot_extraction(struct win32_apply_ctx *ctx)
 
        build_win32_extraction_path(dentry, ctx);
 
-       randomize_char_array_with_alnum(subkeyname, 20);
+       get_random_alnum_chars(subkeyname, 20);
        subkeyname[20] = L'\0';
 
        res = RegLoadKey(HKEY_LOCAL_MACHINE, subkeyname, ctx->pathbuf.Buffer);
@@ -1268,18 +1268,11 @@ retry:
                                      FileShortNameInformation);
 
        if (status == STATUS_INVALID_PARAMETER && !retried) {
-
                /* Microsoft forgot to make it possible to remove short names
                 * until Windows 7.  Oops.  Use a random short name instead.  */
-
+               get_random_alnum_chars(info->FileName, 8);
+               wcscpy(&info->FileName[8], L".WLB");
                info->FileNameLength = 12 * sizeof(wchar_t);
-               for (int i = 0; i < 8; i++)
-                       info->FileName[i] = 'A' + (rand() % 26);
-               info->FileName[8] = L'.';
-               info->FileName[9] = L'W';
-               info->FileName[10] = L'L';
-               info->FileName[11] = L'B';
-               info->FileName[12] = L'\0';
                retried = true;
                goto retry;
        }
index 26f4b4b..2a16500 100644 (file)
@@ -439,7 +439,7 @@ win32_rename_replacement(const wchar_t *srcpath, const wchar_t *dstpath)
                p = tmpname;
                p = wmempcpy(p, dstpath, dstlen);
                p = wmempcpy(p, orig_suffix, ARRAY_LEN(orig_suffix));
-               randomize_char_array_with_alnum(p, num_rand_chars);
+               get_random_alnum_chars(p, num_rand_chars);
                p += num_rand_chars;
                *p = L'\0';
        }
@@ -748,4 +748,30 @@ win32_open_logfile(const wchar_t *path)
        return fp;
 }
 
+#define RtlGenRandom SystemFunction036
+BOOLEAN WINAPI RtlGenRandom(PVOID RandomBuffer, ULONG RandomBufferLength);
+
+/*
+ * Generate @n cryptographically secure random bytes (thread-safe)
+ *
+ * This is the Windows version.  It uses RtlGenRandom() (actually called
+ * SystemFunction036) from advapi32.dll.
+ */
+void
+get_random_bytes(void *p, size_t n)
+{
+       while (n != 0) {
+               u32 count = min(n, UINT32_MAX);
+
+               if (!RtlGenRandom(p, count)) {
+                       win32_error(GetLastError(),
+                                   L"RtlGenRandom() failed (count=%u)", count);
+                       wimlib_assert(0);
+                       count = 0;
+               }
+               p += count;
+               n -= count;
+       }
+}
+
 #endif /* __WIN32__ */
index 7eaa0df..4edf64e 100644 (file)
@@ -3245,7 +3245,7 @@ overwrite_wim_via_tmpfile(WIMStruct *wim, int write_flags, unsigned num_threads)
        wim_name_len = tstrlen(wim->filename);
        tchar tmpfile[wim_name_len + 10];
        tmemcpy(tmpfile, wim->filename, wim_name_len);
-       randomize_char_array_with_alnum(tmpfile + wim_name_len, 9);
+       get_random_alnum_chars(tmpfile + wim_name_len, 9);
        tmpfile[wim_name_len + 9] = T('\0');
 
        ret = wimlib_write(wim, tmpfile, WIMLIB_ALL_IMAGES,