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