src/lj_prng.c

   1 /*
   2 ** Pseudo-random number generation.
   3 ** Copyright (C) 2005-2023 Mike Pall. See Copyright Notice in luajit.h
   4 */
   5
   6 #define lj_prng_c
   7 #define LUA_CORE
   8
   9 /* To get the syscall prototype. */
  10 #if defined(__linux__) && !defined(_GNU_SOURCE)
  11 #define _GNU_SOURCE
  12 #endif
  13
  14 #include "lj_def.h"
  15 #include "lj_arch.h"
  16 #include "lj_prng.h"
  17
  18 /* -- PRNG step function -------------------------------------------------- */
  19
  20 /* This implements a Tausworthe PRNG with period 2^223. Based on:
  21 **   Tables of maximally-equidistributed combined LFSR generators,
  22 **   Pierre L'Ecuyer, 1991, table 3, 1st entry.
  23 ** Full-period ME-CF generator with L=64, J=4, k=223, N1=49.
  24 **
  25 ** Important note: This PRNG is NOT suitable for cryptographic use!
  26 **
  27 ** But it works fine for math.random(), which has an API that's not
  28 ** suitable for cryptography, anyway.
  29 **
  30 ** When used as a securely seeded global PRNG, it substantially raises
  31 ** the difficulty for various attacks on the VM.
  32 */
  33
  34 /* Update generator i and compute a running xor of all states. */
  35 #define TW223_GEN(rs, z, r, i, k, q, s) \
  36   z = rs->u[i]; \
  37   z = (((z<<q)^z) >> (k-s)) ^ ((z&((uint64_t)(int64_t)-1 << (64-k)))<<s); \
  38   r ^= z; rs->u[i] = z;
  39
  40 #define TW223_STEP(rs, z, r) \
  41   TW223_GEN(rs, z, r, 0, 63, 31, 18) \
  42   TW223_GEN(rs, z, r, 1, 58, 19, 28) \
  43   TW223_GEN(rs, z, r, 2, 55, 24,  7) \
  44   TW223_GEN(rs, z, r, 3, 47, 21,  8)
  45
  46 /* PRNG step function with uint64_t result. */
  47 LJ_NOINLINE uint64_t LJ_FASTCALL lj_prng_u64(PRNGState *rs)
  48 {
  49   uint64_t z, r = 0;
  50   TW223_STEP(rs, z, r)
  51   return r;
  52 }
  53
  54 /* PRNG step function with double in uint64_t result. */
  55 LJ_NOINLINE uint64_t LJ_FASTCALL lj_prng_u64d(PRNGState *rs)
  56 {
  57   uint64_t z, r = 0;
  58   TW223_STEP(rs, z, r)
  59   /* Returns a double bit pattern in the range 1.0 <= d < 2.0. */
  60   return (r & U64x(000fffff,ffffffff)) | U64x(3ff00000,00000000);
  61 }
  62
  63 /* Condition seed: ensure k[i] MSB of u[i] are non-zero. */
  64 static LJ_AINLINE void lj_prng_condition(PRNGState *rs)
  65 {
  66   if (rs->u[0] < (1u << 1)) rs->u[0] += (1u << 1);
  67   if (rs->u[1] < (1u << 6)) rs->u[1] += (1u << 6);
  68   if (rs->u[2] < (1u << 9)) rs->u[2] += (1u << 9);
  69   if (rs->u[3] < (1u << 17)) rs->u[3] += (1u << 17);
  70 }
  71
  72 /* -- PRNG seeding from OS ------------------------------------------------ */
  73
  74 #if LUAJIT_SECURITY_PRNG == 0
  75
  76 /* Nothing to define. */
  77
  78 #elif LJ_TARGET_XBOX360
  79
  80 extern int XNetRandom(void *buf, unsigned int len);
  81
  82 #elif LJ_TARGET_PS3
  83
  84 extern int sys_get_random_number(void *buf, uint64_t len);
  85
  86 #elif LJ_TARGET_PS4 || LJ_TARGET_PS5 || LJ_TARGET_PSVITA
  87
  88 extern int sceRandomGetRandomNumber(void *buf, size_t len);
  89
  90 #elif LJ_TARGET_NX
  91
  92 #include <unistd.h>
  93
  94 #elif LJ_TARGET_WINDOWS || LJ_TARGET_XBOXONE
  95
  96 #define WIN32_LEAN_AND_MEAN
  97 #include <windows.h>
  98
  99 #if LJ_TARGET_UWP || LJ_TARGET_XBOXONE
 100 /* Must use BCryptGenRandom. */
 101 #include <bcrypt.h>
 102 #pragma comment(lib, "bcrypt.lib")
 103 #else
 104 /* If you wonder about this mess, then search online for RtlGenRandom. */
 105 typedef BOOLEAN (WINAPI *PRGR)(void *buf, ULONG len);
 106 static PRGR libfunc_rgr;
 107 #endif
 108
 109 #elif LJ_TARGET_POSIX
 110
 111 #if LJ_TARGET_LINUX
 112 /* Avoid a dependency on glibc 2.25+ and use the getrandom syscall instead. */
 113 #include <sys/syscall.h>
 114 #else
 115
 116 #if LJ_TARGET_OSX && !LJ_TARGET_IOS
 117 /*
 118 ** In their infinite wisdom Apple decided to disallow getentropy() in the
 119 ** iOS App Store. Even though the call is common to all BSD-ish OS, it's
 120 ** recommended by Apple in their own security-related docs, and, to top
 121 ** off the foolery, /dev/urandom is handled by the same kernel code,
 122 ** yet accessing it is actually permitted (but less efficient).
 123 */
 124 #include <Availability.h>
 125 #if __MAC_OS_X_VERSION_MIN_REQUIRED >= 101200
 126 #define LJ_TARGET_HAS_GETENTROPY        1
 127 #endif
 128 #elif (LJ_TARGET_BSD && !defined(__NetBSD__)) || LJ_TARGET_SOLARIS || LJ_TARGET_CYGWIN || LJ_TARGET_QNX
 129 #define LJ_TARGET_HAS_GETENTROPY        1
 130 #endif
 131
 132 #if LJ_TARGET_HAS_GETENTROPY
 133 extern int getentropy(void *buf, size_t len)
 134 #ifdef __ELF__
 135   __attribute__((weak))
 136 #endif
 137 ;
 138 #endif
 139
 140 #endif
 141
 142 /* For the /dev/urandom fallback. */
 143 #include <fcntl.h>
 144 #include <unistd.h>
 145
 146 #endif
 147
 148 #if LUAJIT_SECURITY_PRNG == 0
 149
 150 /* If you really don't care about security, then define
 151 ** LUAJIT_SECURITY_PRNG=0. This yields a predictable seed
 152 ** and provides NO SECURITY against various attacks on the VM.
 153 **
 154 ** BTW: This is NOT the way to get predictable table iteration,
 155 ** predictable trace generation, predictable bytecode generation, etc.
 156 */
 157 int LJ_FASTCALL lj_prng_seed_secure(PRNGState *rs)
 158 {
 159   lj_prng_seed_fixed(rs);  /* The fixed seed is already conditioned. */
 160   return 1;
 161 }
 162
 163 #else
 164
 165 /* Securely seed PRNG from system entropy. Returns 0 on failure. */
 166 int LJ_FASTCALL lj_prng_seed_secure(PRNGState *rs)
 167 {
 168 #if LJ_TARGET_XBOX360
 169
 170   if (XNetRandom(rs->u, (unsigned int)sizeof(rs->u)) == 0)
 171     goto ok;
 172
 173 #elif LJ_TARGET_PS3
 174
 175   if (sys_get_random_number(rs->u, sizeof(rs->u)) == 0)
 176     goto ok;
 177
 178 #elif LJ_TARGET_PS4 || LJ_TARGET_PS5 || LJ_TARGET_PSVITA
 179
 180   if (sceRandomGetRandomNumber(rs->u, sizeof(rs->u)) == 0)
 181     goto ok;
 182
 183 #elif LJ_TARGET_NX
 184
 185   if (getentropy(rs->u, sizeof(rs->u)) == 0)
 186     goto ok;
 187
 188 #elif LJ_TARGET_UWP || LJ_TARGET_XBOXONE
 189
 190   if (BCryptGenRandom(NULL, (PUCHAR)(rs->u), (ULONG)sizeof(rs->u),
 191                       BCRYPT_USE_SYSTEM_PREFERRED_RNG) >= 0)
 192     goto ok;
 193
 194 #elif LJ_TARGET_WINDOWS
 195
 196   /* Keep the library loaded in case multiple VMs are started. */
 197   if (!libfunc_rgr) {
 198     HMODULE lib = LJ_WIN_LOADLIBA("advapi32.dll");
 199     if (!lib) return 0;
 200     libfunc_rgr = (PRGR)GetProcAddress(lib, "SystemFunction036");
 201     if (!libfunc_rgr) return 0;
 202   }
 203   if (libfunc_rgr(rs->u, (ULONG)sizeof(rs->u)))
 204     goto ok;
 205
 206 #elif LJ_TARGET_POSIX
 207
 208 #if LJ_TARGET_LINUX && defined(SYS_getrandom)
 209
 210   if (syscall(SYS_getrandom, rs->u, sizeof(rs->u), 0) == (long)sizeof(rs->u))
 211     goto ok;
 212
 213 #elif LJ_TARGET_HAS_GETENTROPY
 214
 215 #ifdef __ELF__
 216   if (&getentropy && getentropy(rs->u, sizeof(rs->u)) == 0)
 217     goto ok;
 218 #else
 219   if (getentropy(rs->u, sizeof(rs->u)) == 0)
 220     goto ok;
 221 #endif
 222
 223 #endif
 224
 225   /* Fallback to /dev/urandom. This may fail if the device is not
 226   ** existent or accessible in a chroot or container, or if the process
 227   ** or the OS ran out of file descriptors.
 228   */
 229   {
 230     int fd = open("/dev/urandom", O_RDONLY|O_CLOEXEC);
 231     if (fd != -1) {
 232       ssize_t n = read(fd, rs->u, sizeof(rs->u));
 233       (void)close(fd);
 234       if (n == (ssize_t)sizeof(rs->u))
 235         goto ok;
 236     }
 237   }
 238
 239 #else
 240
 241   /* Add an elif above for your OS with a secure PRNG seed.
 242   ** Note that fiddling around with rand(), getpid(), time() or coercing
 243   ** ASLR to yield a few bits of randomness is not helpful.
 244   ** If you don't want any security, then don't pretend you have any
 245   ** and simply define LUAJIT_SECURITY_PRNG=0 for the build.
 246   */
 247 #error "Missing secure PRNG seed for this OS"
 248
 249 #endif
 250   return 0;  /* Fail. */
 251
 252 ok:
 253   lj_prng_condition(rs);
 254   (void)lj_prng_u64(rs);
 255   return 1;  /* Success. */
 256 }
 257
 258 #endif
 259