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 #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b)))) 31 #define QR(a, b, c, d) ( \ 32 a += b, d ^= a, d = ROTL(d,16), \ 33 c += d, b ^= c, b = ROTL(b,12), \ 34 a += b, d ^= a, d = ROTL(d, 8), \ 35 c += d, b ^= c, b = ROTL(b, 7)) 36 static void chacha_block(u32 *out, const u32 *in){ 37 int i; 38 u32 x[16]; 39 memcpy(x, in, 64); 40 for(i=0; i<10; i++){ 41 QR(x[0], x[4], x[ 8], x[12]); 42 QR(x[1], x[5], x[ 9], x[13]); 43 QR(x[2], x[6], x[10], x[14]); 44 QR(x[3], x[7], x[11], x[15]); 45 QR(x[0], x[5], x[10], x[15]); 46 QR(x[1], x[6], x[11], x[12]); 47 QR(x[2], x[7], x[ 8], x[13]); 48 QR(x[3], x[4], x[ 9], x[14]); 49 } 50 for(i=0; i<16; i++) out[i] = x[i]+in[i]; 51 } 52 53 /* 54 ** Return N random bytes. 55 */ 56 void sqlite3_randomness(int N, void *pBuf){ 57 unsigned char *zBuf = pBuf; 58 59 /* The "wsdPrng" macro will resolve to the pseudo-random number generator 60 ** state vector. If writable static data is unsupported on the target, 61 ** we have to locate the state vector at run-time. In the more common 62 ** case where writable static data is supported, wsdPrng can refer directly 63 ** to the "sqlite3Prng" state vector declared above. 64 */ 65 #ifdef SQLITE_OMIT_WSD 66 struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng); 67 # define wsdPrng p[0] 68 #else 69 # define wsdPrng sqlite3Prng 70 #endif 71 72 #if SQLITE_THREADSAFE 73 sqlite3_mutex *mutex; 74 #endif 75 76 #ifndef SQLITE_OMIT_AUTOINIT 77 if( sqlite3_initialize() ) return; 78 #endif 79 80 #if SQLITE_THREADSAFE 81 mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG); 82 #endif 83 84 sqlite3_mutex_enter(mutex); 85 if( N<=0 || pBuf==0 ){ 86 wsdPrng.s[0] = 0; 87 sqlite3_mutex_leave(mutex); 88 return; 89 } 90 91 /* Initialize the state of the random number generator once, 92 ** the first time this routine is called. The seed value does 93 ** not need to contain a lot of randomness since we are not 94 ** trying to do secure encryption or anything like that... 95 ** 96 ** Nothing in this file or anywhere else in SQLite does any kind of 97 ** encryption. The RC4 algorithm is being used as a PRNG (pseudo-random 98 ** number generator) not as an encryption device. 99 */ 100 if( wsdPrng.s[0]==0 ){ 101 sqlite3_vfs *pVfs = sqlite3_vfs_find(0); 102 static const u32 chacha20_init[] = { 103 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574 104 }; 105 memcpy(&wsdPrng.s[0], chacha20_init, 16); 106 if( NEVER(pVfs==0) ){ 107 memset(&wsdPrng.s[4], 0, 44); 108 }else{ 109 sqlite3OsRandomness(pVfs, 44, (char*)&wsdPrng.s[4]); 110 } 111 wsdPrng.s[15] = wsdPrng.s[12]; 112 wsdPrng.s[12] = 0; 113 wsdPrng.n = 0; 114 } 115 116 assert( N>0 ); 117 while( 1 /* exit by break */ ){ 118 if( N<=wsdPrng.n ){ 119 memcpy(zBuf, &wsdPrng.out[wsdPrng.n-N], N); 120 wsdPrng.n -= N; 121 break; 122 } 123 if( wsdPrng.n>0 ){ 124 memcpy(zBuf, wsdPrng.out, wsdPrng.n); 125 N -= wsdPrng.n; 126 zBuf += wsdPrng.n; 127 } 128 wsdPrng.s[12]++; 129 chacha_block((u32*)wsdPrng.out, wsdPrng.s); 130 wsdPrng.n = 64; 131 } 132 sqlite3_mutex_leave(mutex); 133 } 134 135 #ifndef SQLITE_UNTESTABLE 136 /* 137 ** For testing purposes, we sometimes want to preserve the state of 138 ** PRNG and restore the PRNG to its saved state at a later time, or 139 ** to reset the PRNG to its initial state. These routines accomplish 140 ** those tasks. 141 ** 142 ** The sqlite3_test_control() interface calls these routines to 143 ** control the PRNG. 144 */ 145 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng; 146 void sqlite3PrngSaveState(void){ 147 memcpy( 148 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 149 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 150 sizeof(sqlite3Prng) 151 ); 152 } 153 void sqlite3PrngRestoreState(void){ 154 memcpy( 155 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 156 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 157 sizeof(sqlite3Prng) 158 ); 159 } 160 #endif /* SQLITE_UNTESTABLE */ 161