ares_rand.c (10927B)
1 /* MIT License 2 * 3 * Copyright (c) 2023 Brad House 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a copy 6 * of this software and associated documentation files (the "Software"), to deal 7 * in the Software without restriction, including without limitation the rights 8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 * copies of the Software, and to permit persons to whom the Software is 10 * furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 * 24 * SPDX-License-Identifier: MIT 25 */ 26 27 #include "ares_private.h" 28 #include <stdlib.h> 29 30 /* Older MacOS versions require including AvailabilityMacros.h before 31 * sys/random.h */ 32 #ifdef HAVE_AVAILABILITYMACROS_H 33 # include <AvailabilityMacros.h> 34 #endif 35 36 #ifdef HAVE_SYS_RANDOM_H 37 # include <sys/random.h> 38 #endif 39 40 41 typedef enum { 42 ARES_RAND_OS = 1 << 0, /* OS-provided such as RtlGenRandom or arc4random */ 43 ARES_RAND_FILE = 1 << 1, /* OS file-backed random number generator */ 44 ARES_RAND_RC4 = 1 << 2 /* Internal RC4 based PRNG */ 45 } ares_rand_backend; 46 47 #define ARES_RC4_KEY_LEN 32 /* 256 bits */ 48 49 typedef struct ares_rand_rc4 { 50 unsigned char S[256]; 51 size_t i; 52 size_t j; 53 } ares_rand_rc4; 54 55 static unsigned int ares_u32_from_ptr(void *addr) 56 { 57 /* LCOV_EXCL_START: FallbackCode */ 58 if (ares_is_64bit()) { 59 return (unsigned int)((((ares_uint64_t)addr >> 32) & 0xFFFFFFFF) | 60 ((ares_uint64_t)addr & 0xFFFFFFFF)); 61 } 62 return (unsigned int)((size_t)addr & 0xFFFFFFFF); 63 /* LCOV_EXCL_STOP */ 64 } 65 66 /* initialize an rc4 key as the last possible fallback. */ 67 static void ares_rc4_generate_key(ares_rand_rc4 *rc4_state, unsigned char *key, 68 size_t key_len) 69 { 70 /* LCOV_EXCL_START: FallbackCode */ 71 size_t i; 72 size_t len = 0; 73 unsigned int data; 74 ares_timeval_t tv; 75 76 if (key_len != ARES_RC4_KEY_LEN) { 77 return; 78 } 79 80 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 81 /* For fuzzing, random should be deterministic */ 82 srand(0); 83 #else 84 /* Randomness is hard to come by. Maybe the system randomizes heap and stack 85 * addresses. Maybe the current timestamp give us some randomness. Use 86 * rc4_state (heap), &i (stack), and ares_tvnow() 87 */ 88 data = ares_u32_from_ptr(rc4_state); 89 memcpy(key + len, &data, sizeof(data)); 90 len += sizeof(data); 91 92 data = ares_u32_from_ptr(&i); 93 memcpy(key + len, &data, sizeof(data)); 94 len += sizeof(data); 95 96 ares_tvnow(&tv); 97 data = (unsigned int)((tv.sec | tv.usec) & 0xFFFFFFFF); 98 memcpy(key + len, &data, sizeof(data)); 99 len += sizeof(data); 100 101 srand(ares_u32_from_ptr(rc4_state) | ares_u32_from_ptr(&i) | 102 (unsigned int)((tv.sec | tv.usec) & 0xFFFFFFFF)); 103 #endif 104 105 for (i = len; i < key_len; i++) { 106 key[i] = (unsigned char)(rand() % 256); /* LCOV_EXCL_LINE */ 107 } 108 /* LCOV_EXCL_STOP */ 109 } 110 111 #define ARES_SWAP_BYTE(a, b) \ 112 do { \ 113 unsigned char swapByte = *(a); \ 114 *(a) = *(b); \ 115 *(b) = swapByte; \ 116 } while (0) 117 118 static void ares_rc4_init(ares_rand_rc4 *rc4_state) 119 { 120 /* LCOV_EXCL_START: FallbackCode */ 121 unsigned char key[ARES_RC4_KEY_LEN]; 122 size_t i; 123 size_t j; 124 125 ares_rc4_generate_key(rc4_state, key, sizeof(key)); 126 127 for (i = 0; i < sizeof(rc4_state->S); i++) { 128 rc4_state->S[i] = i & 0xFF; 129 } 130 131 for (i = 0, j = 0; i < 256; i++) { 132 j = (j + rc4_state->S[i] + key[i % sizeof(key)]) % 256; 133 ARES_SWAP_BYTE(&rc4_state->S[i], &rc4_state->S[j]); 134 } 135 136 rc4_state->i = 0; 137 rc4_state->j = 0; 138 /* LCOV_EXCL_STOP */ 139 } 140 141 /* Just outputs the key schedule, no need to XOR with any data since we have 142 * none */ 143 static void ares_rc4_prng(ares_rand_rc4 *rc4_state, unsigned char *buf, 144 size_t len) 145 { 146 /* LCOV_EXCL_START: FallbackCode */ 147 unsigned char *S = rc4_state->S; 148 size_t i = rc4_state->i; 149 size_t j = rc4_state->j; 150 size_t cnt; 151 152 for (cnt = 0; cnt < len; cnt++) { 153 i = (i + 1) % 256; 154 j = (j + S[i]) % 256; 155 156 ARES_SWAP_BYTE(&S[i], &S[j]); 157 buf[cnt] = S[(S[i] + S[j]) % 256]; 158 } 159 160 rc4_state->i = i; 161 rc4_state->j = j; 162 /* LCOV_EXCL_STOP */ 163 } 164 165 struct ares_rand_state { 166 ares_rand_backend type; 167 ares_rand_backend bad_backends; 168 169 union { 170 FILE *rand_file; 171 ares_rand_rc4 rc4; 172 } state; 173 174 /* Since except for RC4, random data will likely result in a syscall, lets 175 * pre-pull 256 bytes at a time. Every query will pull 2 bytes off this so 176 * that means we should only need a syscall every 128 queries. 256bytes 177 * appears to be a sweet spot that may be able to be served without 178 * interruption */ 179 unsigned char cache[256]; 180 size_t cache_remaining; 181 }; 182 183 /* Define RtlGenRandom = SystemFunction036. This is in advapi32.dll. There is 184 * no need to dynamically load this, other software used widely does not. 185 * http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx 186 * https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom 187 */ 188 #ifdef _WIN32 189 BOOLEAN WINAPI SystemFunction036(PVOID RandomBuffer, ULONG RandomBufferLength); 190 # ifndef RtlGenRandom 191 # define RtlGenRandom(a, b) SystemFunction036(a, b) 192 # endif 193 #endif 194 195 196 static ares_bool_t ares_init_rand_engine(ares_rand_state *state) 197 { 198 state->cache_remaining = 0; 199 200 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 201 /* For fuzzing, random should be deterministic */ 202 state->bad_backends |= ARES_RAND_OS | ARES_RAND_FILE; 203 #endif 204 205 #if defined(HAVE_ARC4RANDOM_BUF) || defined(HAVE_GETRANDOM) || defined(_WIN32) 206 if (!(state->bad_backends & ARES_RAND_OS)) { 207 state->type = ARES_RAND_OS; 208 return ARES_TRUE; 209 } 210 #endif 211 212 #if defined(CARES_RANDOM_FILE) 213 /* LCOV_EXCL_START: FallbackCode */ 214 if (!(state->bad_backends & ARES_RAND_FILE)) { 215 state->type = ARES_RAND_FILE; 216 state->state.rand_file = fopen(CARES_RANDOM_FILE, "rb"); 217 if (state->state.rand_file) { 218 setvbuf(state->state.rand_file, NULL, _IONBF, 0); 219 return ARES_TRUE; 220 } 221 } 222 /* LCOV_EXCL_STOP */ 223 224 /* Fall-Thru on failure to RC4 */ 225 #endif 226 227 /* LCOV_EXCL_START: FallbackCode */ 228 state->type = ARES_RAND_RC4; 229 ares_rc4_init(&state->state.rc4); 230 /* LCOV_EXCL_STOP */ 231 232 /* Currently cannot fail */ 233 return ARES_TRUE; /* LCOV_EXCL_LINE: UntestablePath */ 234 } 235 236 ares_rand_state *ares_init_rand_state(void) 237 { 238 ares_rand_state *state = NULL; 239 240 state = ares_malloc_zero(sizeof(*state)); 241 if (!state) { 242 return NULL; 243 } 244 245 if (!ares_init_rand_engine(state)) { 246 ares_free(state); /* LCOV_EXCL_LINE: UntestablePath */ 247 return NULL; /* LCOV_EXCL_LINE: UntestablePath */ 248 } 249 250 return state; 251 } 252 253 static void ares_clear_rand_state(ares_rand_state *state) 254 { 255 if (!state) { 256 return; /* LCOV_EXCL_LINE: DefensiveCoding */ 257 } 258 259 switch (state->type) { 260 case ARES_RAND_OS: 261 break; 262 /* LCOV_EXCL_START: FallbackCode */ 263 case ARES_RAND_FILE: 264 fclose(state->state.rand_file); 265 break; 266 case ARES_RAND_RC4: 267 break; 268 /* LCOV_EXCL_STOP */ 269 } 270 } 271 272 static void ares_reinit_rand(ares_rand_state *state) 273 { 274 /* LCOV_EXCL_START: UntestablePath */ 275 ares_clear_rand_state(state); 276 ares_init_rand_engine(state); 277 /* LCOV_EXCL_STOP */ 278 } 279 280 void ares_destroy_rand_state(ares_rand_state *state) 281 { 282 if (!state) { 283 return; 284 } 285 286 ares_clear_rand_state(state); 287 ares_free(state); 288 } 289 290 static void ares_rand_bytes_fetch(ares_rand_state *state, unsigned char *buf, 291 size_t len) 292 { 293 while (1) { 294 size_t bytes_read = 0; 295 296 switch (state->type) { 297 case ARES_RAND_OS: 298 #ifdef _WIN32 299 RtlGenRandom(buf, (ULONG)len); 300 return; 301 #elif defined(HAVE_ARC4RANDOM_BUF) 302 arc4random_buf(buf, len); 303 return; 304 #elif defined(HAVE_GETRANDOM) 305 while (1) { 306 size_t n = len - bytes_read; 307 /* getrandom() on Linux always succeeds and is never 308 * interrupted by a signal when requesting <= 256 bytes. 309 */ 310 ssize_t rv = getrandom(buf + bytes_read, n > 256 ? 256 : n, 0); 311 if (rv <= 0) { 312 /* We need to fall back to another backend */ 313 if (errno == ENOSYS) { 314 state->bad_backends |= ARES_RAND_OS; 315 break; 316 } 317 continue; /* Just retry. */ 318 } 319 320 bytes_read += (size_t)rv; 321 if (bytes_read == len) { 322 return; 323 } 324 } 325 break; 326 #else 327 /* Shouldn't be possible to be here */ 328 break; 329 #endif 330 331 /* LCOV_EXCL_START: FallbackCode */ 332 333 case ARES_RAND_FILE: 334 while (1) { 335 size_t rv = fread(buf + bytes_read, 1, len - bytes_read, 336 state->state.rand_file); 337 if (rv == 0) { 338 break; /* critical error, will reinit rand state */ 339 } 340 341 bytes_read += rv; 342 if (bytes_read == len) { 343 return; 344 } 345 } 346 break; 347 348 case ARES_RAND_RC4: 349 ares_rc4_prng(&state->state.rc4, buf, len); 350 return; 351 352 /* LCOV_EXCL_STOP */ 353 } 354 355 /* If we didn't return before we got here, that means we had a critical rand 356 * failure and need to reinitialized */ 357 ares_reinit_rand(state); /* LCOV_EXCL_LINE: UntestablePath */ 358 } 359 } 360 361 void ares_rand_bytes(ares_rand_state *state, unsigned char *buf, size_t len) 362 { 363 /* See if we need to refill the cache to serve the request, but if len is 364 * excessive, we're not going to update our cache or serve from cache */ 365 if (len > state->cache_remaining && len < sizeof(state->cache)) { 366 size_t fetch_size = sizeof(state->cache) - state->cache_remaining; 367 ares_rand_bytes_fetch(state, state->cache, fetch_size); 368 state->cache_remaining = sizeof(state->cache); 369 } 370 371 /* Serve from cache */ 372 if (len <= state->cache_remaining) { 373 size_t offset = sizeof(state->cache) - state->cache_remaining; 374 memcpy(buf, state->cache + offset, len); 375 state->cache_remaining -= len; 376 return; 377 } 378 379 /* Serve direct due to excess size of request */ 380 ares_rand_bytes_fetch(state, buf, len); 381 } 382 383 unsigned short ares_generate_new_id(ares_rand_state *state) 384 { 385 unsigned short r = 0; 386 387 ares_rand_bytes(state, (unsigned char *)&r, sizeof(r)); 388 return r; 389 }