Line data Source code
1 : /* SPDX-License-Identifier: MIT OR GPL-3.0-only */
2 : /* rand.c
3 : * strophe XMPP client library -- pseudo-random number generator
4 : *
5 : * Copyright (C) 2014 Dmitry Podgorny <pasis.ua@gmail.com>
6 : *
7 : * This software is provided AS-IS with no warranty, either express
8 : * or implied.
9 : *
10 : * This program is dual licensed under the MIT or GPLv3 licenses.
11 : */
12 :
13 : /** @file
14 : * Pseudo-random number generator.
15 : *
16 : * Implemented Hash_DRBG mechanism according to NIST SP 800-90A.
17 : * Hash function is SHA1.
18 : */
19 :
20 : /** @defgroup Random Pseudo-random number generator
21 : */
22 :
23 : #include <assert.h>
24 : #include <string.h> /* memeset */
25 : #include <time.h> /* clock, time */
26 :
27 : #if !defined(_WIN32)
28 : #include <unistd.h>
29 : #endif
30 :
31 : #if !defined(DONT_USE_GETRANDOM) && defined(__linux__) && \
32 : defined(__GLIBC_PREREQ)
33 : #if __GLIBC_PREREQ(2, 25)
34 : #define USE_GETRANDOM
35 : #include <sys/random.h>
36 : #include <errno.h>
37 : #endif
38 : #endif
39 :
40 : #include "common.h" /* strophe_alloc, strophe_free */
41 : #include "ostypes.h" /* uint8_t, uint32_t, size_t */
42 :
43 : #ifndef USE_GETRANDOM
44 : #include "sha1.h"
45 :
46 : #define outlen SHA1_DIGEST_SIZE
47 : #define seedlen (440 / 8)
48 : #define reseed_interval 0x7fffffff
49 :
50 : /* maximum number of bytes that can be generated per call */
51 : #define GENERATE_MAX (outlen * 10)
52 : #define ENTROPY_MAX 128
53 : #define NONCE_MAX 8
54 :
55 : #define RESEED_NEEDED (-1)
56 :
57 : struct Hash_DRBG_CTX_struc {
58 : uint8_t V[seedlen];
59 : uint8_t C[seedlen];
60 : uint32_t reseed_counter;
61 : };
62 : typedef struct Hash_DRBG_CTX_struc Hash_DRBG_CTX;
63 :
64 : struct _xmpp_rand_t {
65 : int inited;
66 : unsigned reseed_count;
67 : Hash_DRBG_CTX ctx;
68 : };
69 :
70 : /* returns smallest number mupliple of y that not less than x */
71 : #define round_up(x, y) (((x) + (y)-1) / (y) * (y))
72 : /* returns smallest integer number that not less than x/y */
73 : #define div_round_up(x, y) (((x) + (y)-1) / (y))
74 :
75 : /* adds two arrays as numbers in big-endian representation and stores
76 : * result in the first one.
77 : */
78 : static void
79 : arr_add(uint8_t *arr1, size_t arr1_len, uint8_t *arr2, size_t arr2_len)
80 : {
81 : size_t i;
82 : uint32_t acc;
83 : uint32_t carry = 0;
84 :
85 : assert(arr1_len >= arr2_len);
86 :
87 : for (i = 1; (i <= arr2_len) || (carry != 0 && i <= arr1_len); ++i) {
88 : acc = (uint32_t)arr1[arr1_len - i] + carry;
89 : if (i <= arr2_len)
90 : acc += (uint32_t)arr2[arr2_len - i];
91 : carry = acc >> 8;
92 : arr1[arr1_len - i] = (uint8_t)(acc & 0xff);
93 : }
94 : }
95 :
96 : /* stores 32-bit number in big-endian representation */
97 : static void store_be32(uint32_t val, uint8_t be[4])
98 : {
99 : be[0] = (uint8_t)((val >> 24) & 0xff);
100 : be[1] = (uint8_t)((val >> 16) & 0xff);
101 : be[2] = (uint8_t)((val >> 8) & 0xff);
102 : be[3] = (uint8_t)(val & 0xff);
103 : }
104 :
105 : static void Hash_df(uint8_t *input_string,
106 : size_t input_string_len,
107 : uint8_t *output_string,
108 : size_t no_of_bytes_to_return)
109 : {
110 : uint8_t counter;
111 : uint8_t temp[round_up(seedlen, outlen)];
112 : uint8_t conj[ENTROPY_MAX + NONCE_MAX + seedlen + 6];
113 : size_t len;
114 : size_t i;
115 : size_t offset;
116 :
117 : assert(no_of_bytes_to_return <= sizeof(temp));
118 : assert(input_string_len + 5 <= sizeof(conj));
119 :
120 : len = div_round_up(no_of_bytes_to_return, outlen);
121 : for (i = 1; i <= len; ++i) {
122 : offset = (i - 1) * outlen;
123 : counter = (uint8_t)i;
124 : conj[0] = counter;
125 : store_be32((uint32_t)no_of_bytes_to_return * 8, conj + 1);
126 : memcpy(conj + 5, input_string, input_string_len);
127 : crypto_SHA1(conj, input_string_len + 5, temp + offset);
128 : }
129 :
130 : memcpy(output_string, temp, no_of_bytes_to_return);
131 : }
132 :
133 : /* assume personalization_string is zero length string */
134 : static void Hash_DRBG_Instantiate(Hash_DRBG_CTX *ctx,
135 : uint8_t *entropy_input,
136 : size_t entropy_input_len,
137 : uint8_t *nonce,
138 : size_t nonce_len)
139 : {
140 : uint8_t seed_material[ENTROPY_MAX + NONCE_MAX];
141 : uint8_t seed0[seedlen + 1];
142 : uint8_t *seed = seed0 + 1;
143 :
144 : assert(entropy_input_len <= ENTROPY_MAX);
145 : assert(nonce_len <= NONCE_MAX);
146 : assert(nonce != NULL || nonce_len == 0);
147 :
148 : memcpy(seed_material, entropy_input, entropy_input_len);
149 : if (nonce != NULL)
150 : memcpy(seed_material + entropy_input_len, nonce, nonce_len);
151 : Hash_df(seed_material, entropy_input_len + nonce_len, seed, seedlen);
152 : seed0[0] = 0;
153 :
154 : memcpy(ctx->V, seed, seedlen);
155 : Hash_df(seed0, sizeof(seed0), ctx->C, seedlen);
156 : ctx->reseed_counter = 1;
157 : }
158 :
159 : /* assume additional_input is zero length string */
160 : static void Hash_DRBG_Reseed(Hash_DRBG_CTX *ctx,
161 : uint8_t *entropy_input,
162 : size_t entropy_input_len)
163 : {
164 : uint8_t seed_material[1 + seedlen + ENTROPY_MAX];
165 : uint8_t seed0[seedlen + 1];
166 : uint8_t *seed = seed0 + 1;
167 :
168 : assert(entropy_input_len <= ENTROPY_MAX);
169 :
170 : seed_material[0] = 1;
171 : memcpy(seed_material + 1, ctx->V, seedlen);
172 : memcpy(seed_material + 1 + seedlen, entropy_input, entropy_input_len);
173 : Hash_df(seed_material, entropy_input_len + seedlen + 1, seed, seedlen);
174 : seed0[0] = 0;
175 :
176 : memcpy(ctx->V, seed, seedlen);
177 : Hash_df(seed0, sizeof(seed0), ctx->C, seedlen);
178 : ctx->reseed_counter = 1;
179 : }
180 :
181 : static void
182 : Hashgen(uint8_t *V, uint8_t *output, size_t requested_number_of_bytes)
183 : {
184 : uint8_t data[seedlen];
185 : uint8_t W[GENERATE_MAX];
186 : uint8_t i1 = 1;
187 : size_t m;
188 : size_t i;
189 : size_t offset;
190 :
191 : assert(requested_number_of_bytes <= sizeof(W));
192 :
193 : m = div_round_up(requested_number_of_bytes, outlen);
194 : memcpy(data, V, seedlen);
195 : for (i = 1; i <= m; ++i) {
196 : offset = (i - 1) * outlen;
197 : crypto_SHA1(data, seedlen, W + offset);
198 : /* increase data by 1 */
199 : arr_add(data, sizeof(data), &i1, 1);
200 : }
201 :
202 : memcpy(output, W, requested_number_of_bytes);
203 : }
204 :
205 : /* assume additional_input is zero length string */
206 : static int Hash_DRBG_Generate(Hash_DRBG_CTX *ctx,
207 : uint8_t *output,
208 : size_t requested_number_of_bytes)
209 : {
210 : uint8_t H[outlen];
211 : uint8_t V3[seedlen + 1];
212 : uint8_t reseed_counter[4];
213 :
214 : if (ctx->reseed_counter > reseed_interval || ctx->reseed_counter == 0)
215 : return RESEED_NEEDED;
216 :
217 : Hashgen(ctx->V, output, requested_number_of_bytes);
218 :
219 : V3[0] = 3;
220 : memcpy(V3 + 1, ctx->V, seedlen);
221 : crypto_SHA1(V3, sizeof(V3), H);
222 : arr_add(ctx->V, sizeof(ctx->V), ctx->C, sizeof(ctx->C));
223 : arr_add(ctx->V, sizeof(ctx->V), H, sizeof(H));
224 : store_be32(ctx->reseed_counter, reseed_counter);
225 : arr_add(ctx->V, sizeof(ctx->V), reseed_counter, sizeof(reseed_counter));
226 :
227 : ++ctx->reseed_counter;
228 : return 0;
229 : }
230 :
231 : #define ENTROPY_ACCUMULATE(ptr, last, type, arg) \
232 : do { \
233 : type __arg = (type)(arg); \
234 : if ((char *)ptr + sizeof(__arg) < (char *)last) { \
235 : *(type *)ptr = __arg; \
236 : ptr = (void *)((char *)ptr + sizeof(__arg)); \
237 : } \
238 : } while (0)
239 :
240 : static void xmpp_rand_reseed(xmpp_rand_t *rand)
241 : {
242 : uint8_t entropy[ENTROPY_MAX];
243 : uint8_t *ptr = entropy;
244 : const uint8_t *last = entropy + sizeof(entropy);
245 : size_t len;
246 :
247 : /* entropy:
248 : * 1. time_stamp()
249 : * 2. clock(3)
250 : * 3. xmpp_rand_t address to make unique seed within one process
251 : * 4. counter to make unique seed within one context
252 : * 5. stack address
253 : * 6. local ports of every connection in list (getsockname)
254 : * 7. other non-constant info that can be retieved from socket
255 : *
256 : * rand(3) can't be used as it isn't thread-safe.
257 : * XXX 6 and 7 are not implemented yet.
258 : */
259 :
260 : ENTROPY_ACCUMULATE(ptr, last, uint64_t, time_stamp());
261 : ENTROPY_ACCUMULATE(ptr, last, clock_t, clock());
262 : ENTROPY_ACCUMULATE(ptr, last, void *, rand);
263 : ENTROPY_ACCUMULATE(ptr, last, unsigned, ++rand->reseed_count);
264 : ENTROPY_ACCUMULATE(ptr, last, void *, &entropy);
265 : len = ptr - entropy;
266 :
267 : if (rand->inited) {
268 : Hash_DRBG_Reseed(&rand->ctx, entropy, len);
269 : } else {
270 : Hash_DRBG_Instantiate(&rand->ctx, entropy, len, NULL, 0);
271 : rand->inited = 1;
272 : }
273 : }
274 :
275 : xmpp_rand_t *xmpp_rand_new(xmpp_ctx_t *ctx)
276 : {
277 : xmpp_rand_t *out = strophe_alloc(ctx, sizeof(*out));
278 : if (out != NULL) {
279 : memset(out, 0, sizeof(*out));
280 : }
281 : return out;
282 : }
283 :
284 : void xmpp_rand_free(xmpp_ctx_t *ctx, xmpp_rand_t *rand)
285 : {
286 : strophe_free(ctx, rand);
287 : }
288 :
289 : void xmpp_rand_bytes(xmpp_rand_t *rand, unsigned char *output, size_t len)
290 : {
291 : int rc;
292 : size_t gen, tot = 0;
293 : while (tot < len) {
294 : gen = len - tot;
295 : if (gen > GENERATE_MAX)
296 : gen = GENERATE_MAX;
297 : rc = Hash_DRBG_Generate(&rand->ctx, (uint8_t *)output + tot, gen);
298 : if (rc == RESEED_NEEDED) {
299 : xmpp_rand_reseed(rand);
300 : rc = Hash_DRBG_Generate(&rand->ctx, (uint8_t *)output + tot, gen);
301 : assert(rc == 0);
302 : }
303 : tot += gen;
304 : }
305 : }
306 :
307 : #else
308 :
309 0 : static int _read_getrandom(void *p, size_t n)
310 : {
311 0 : unsigned char *q = (unsigned char *)p;
312 0 : while (n > 0u) {
313 0 : ssize_t ret = getrandom(q, n, 0);
314 0 : if (ret < 0) {
315 0 : if (errno == EINTR) {
316 0 : continue;
317 : }
318 : return 1;
319 : }
320 0 : q += ret;
321 0 : n -= (size_t)ret;
322 : }
323 : return 0;
324 : }
325 :
326 : struct _xmpp_rand_t {
327 : char nothing;
328 : };
329 :
330 : static xmpp_rand_t _xmpp_rand;
331 :
332 3 : xmpp_rand_t *xmpp_rand_new(xmpp_ctx_t *ctx)
333 : {
334 3 : UNUSED(ctx);
335 3 : return &_xmpp_rand;
336 : }
337 :
338 3 : void xmpp_rand_free(xmpp_ctx_t *ctx, xmpp_rand_t *rand)
339 : {
340 3 : UNUSED(ctx);
341 3 : assert(rand == &_xmpp_rand);
342 3 : }
343 :
344 0 : void xmpp_rand_bytes(xmpp_rand_t *rand, unsigned char *output, size_t len)
345 : {
346 0 : assert(rand == &_xmpp_rand);
347 0 : assert(_read_getrandom(output, len) == 0);
348 0 : }
349 :
350 : #endif
351 :
352 0 : int xmpp_rand(xmpp_rand_t *rand)
353 : {
354 0 : int result;
355 :
356 0 : xmpp_rand_bytes(rand, (unsigned char *)&result, sizeof(result));
357 0 : return result;
358 : }
359 :
360 0 : static void rand_byte2hex(unsigned char byte, char *hex)
361 : {
362 0 : static const char hex_tbl[16] = {'0', '1', '2', '3', '4', '5', '6', '7',
363 : '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
364 :
365 0 : hex[0] = hex_tbl[(byte >> 4) & 0x0f];
366 0 : hex[1] = hex_tbl[byte & 0x0f];
367 : }
368 :
369 0 : void xmpp_rand_nonce(xmpp_rand_t *rand, char *output, size_t len)
370 : {
371 0 : size_t i;
372 0 : const size_t rand_len = len / 2;
373 :
374 : /*
375 : * We don't want to use any allocation here, because this function
376 : * can't fail. Also we want to avoid VLA.
377 : * Current implementation uses half of the output buffer for random buffer
378 : * generation and then converts it to HEX representation.
379 : */
380 :
381 0 : if (rand_len > 0) {
382 0 : xmpp_rand_bytes(rand, (unsigned char *)output, rand_len);
383 0 : for (i = rand_len; i > 0; --i)
384 0 : rand_byte2hex(output[i - 1], &output[(i - 1) * 2]);
385 : }
386 0 : if (len > 0)
387 0 : output[len - 1] = '\0';
388 0 : }
|