1 /* 2 ** 2001 September 15 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** This file contains code to implement a pseudo-random number 13 ** generator (PRNG) for SQLite. 14 ** 15 ** Random numbers are used by some of the database backends in order 16 ** to generate random integer keys for tables or random filenames. 17 */ 18 #include "sqliteInt.h" 19 20 21 /* All threads share a single random number generator. 22 ** This structure is the current state of the generator. 23 */ 24 static SQLITE_WSD struct sqlite3PrngType { 25 u32 s[16]; /* 64 bytes of chacha20 state */ 26 u8 out[64]; /* Output bytes */ 27 u8 n; /* Output bytes remaining */ 28 } sqlite3Prng; 29 30 31 /* The RFC-7539 ChaCha20 block function 32 */ 33 #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b)))) 34 #define QR(a, b, c, d) ( \ 35 a += b, d ^= a, d = ROTL(d,16), \ 36 c += d, b ^= c, b = ROTL(b,12), \ 37 a += b, d ^= a, d = ROTL(d, 8), \ 38 c += d, b ^= c, b = ROTL(b, 7)) 39 static void chacha_block(u32 *out, const u32 *in){ 40 int i; 41 u32 x[16]; 42 memcpy(x, in, 64); 43 for(i=0; i<10; i++){ 44 QR(x[0], x[4], x[ 8], x[12]); 45 QR(x[1], x[5], x[ 9], x[13]); 46 QR(x[2], x[6], x[10], x[14]); 47 QR(x[3], x[7], x[11], x[15]); 48 QR(x[0], x[5], x[10], x[15]); 49 QR(x[1], x[6], x[11], x[12]); 50 QR(x[2], x[7], x[ 8], x[13]); 51 QR(x[3], x[4], x[ 9], x[14]); 52 } 53 for(i=0; i<16; i++) out[i] = x[i]+in[i]; 54 } 55 56 /* 57 ** Return N random bytes. 58 */ 59 void sqlite3_randomness(int N, void *pBuf){ 60 unsigned char *zBuf = pBuf; 61 62 /* The "wsdPrng" macro will resolve to the pseudo-random number generator 63 ** state vector. If writable static data is unsupported on the target, 64 ** we have to locate the state vector at run-time. In the more common 65 ** case where writable static data is supported, wsdPrng can refer directly 66 ** to the "sqlite3Prng" state vector declared above. 67 */ 68 #ifdef SQLITE_OMIT_WSD 69 struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng); 70 # define wsdPrng p[0] 71 #else 72 # define wsdPrng sqlite3Prng 73 #endif 74 75 #if SQLITE_THREADSAFE 76 sqlite3_mutex *mutex; 77 #endif 78 79 #ifndef SQLITE_OMIT_AUTOINIT 80 if( sqlite3_initialize() ) return; 81 #endif 82 83 #if SQLITE_THREADSAFE 84 mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG); 85 #endif 86 87 sqlite3_mutex_enter(mutex); 88 if( N<=0 || pBuf==0 ){ 89 wsdPrng.s[0] = 0; 90 sqlite3_mutex_leave(mutex); 91 return; 92 } 93 94 /* Initialize the state of the random number generator once, 95 ** the first time this routine is called. 96 */ 97 if( wsdPrng.s[0]==0 ){ 98 sqlite3_vfs *pVfs = sqlite3_vfs_find(0); 99 static const u32 chacha20_init[] = { 100 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574 101 }; 102 memcpy(&wsdPrng.s[0], chacha20_init, 16); 103 if( NEVER(pVfs==0) ){ 104 memset(&wsdPrng.s[4], 0, 44); 105 }else{ 106 sqlite3OsRandomness(pVfs, 44, (char*)&wsdPrng.s[4]); 107 } 108 wsdPrng.s[15] = wsdPrng.s[12]; 109 wsdPrng.s[12] = 0; 110 wsdPrng.n = 0; 111 } 112 113 assert( N>0 ); 114 while( 1 /* exit by break */ ){ 115 if( N<=wsdPrng.n ){ 116 memcpy(zBuf, &wsdPrng.out[wsdPrng.n-N], N); 117 wsdPrng.n -= N; 118 break; 119 } 120 if( wsdPrng.n>0 ){ 121 memcpy(zBuf, wsdPrng.out, wsdPrng.n); 122 N -= wsdPrng.n; 123 zBuf += wsdPrng.n; 124 } 125 wsdPrng.s[12]++; 126 chacha_block((u32*)wsdPrng.out, wsdPrng.s); 127 wsdPrng.n = 64; 128 } 129 sqlite3_mutex_leave(mutex); 130 } 131 132 #ifndef SQLITE_UNTESTABLE 133 /* 134 ** For testing purposes, we sometimes want to preserve the state of 135 ** PRNG and restore the PRNG to its saved state at a later time, or 136 ** to reset the PRNG to its initial state. These routines accomplish 137 ** those tasks. 138 ** 139 ** The sqlite3_test_control() interface calls these routines to 140 ** control the PRNG. 141 */ 142 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng; 143 void sqlite3PrngSaveState(void){ 144 memcpy( 145 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 146 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 147 sizeof(sqlite3Prng) 148 ); 149 } 150 void sqlite3PrngRestoreState(void){ 151 memcpy( 152 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 153 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 154 sizeof(sqlite3Prng) 155 ); 156 } 157 #endif /* SQLITE_UNTESTABLE */ 158