2 * random.c - random number generation
4 * Copyright (C) 2011, 2012, 2013 Free Software Initiative of Japan
5 * Author: NIIBE Yutaka <gniibe@fsij.org>
7 * This file is a part of NeuG, a True Random Number Generator
8 * implementation based on quantization error of ADC (for STM32F103).
10 * NeuG is free software: you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
15 * NeuG is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
18 * License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program. If not, see <http://www.gnu.org/licenses/>.
31 #include "stm32f103.h"
35 chopstx_mutex_t adc_mtx;
36 chopstx_cond_t adc_cond;
38 int adc_data_available;
40 static uint32_t adc_buf[SHA256_BLOCK_SIZE/sizeof (uint32_t)];
42 static sha256_context sha256_ctx_data;
43 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
46 * To be a full entropy source, the requirement is to have N samples
47 * for output of 256-bit, where:
49 * N = (256 * 2) / <min-entropy of a sample>
51 * For example, N should be more than 103 for min-entropy = 5.0.
53 * On the other hand, in the section 6.2 "Full Entropy Source
54 * Requirements", it says:
56 * At least twice the block size of the underlying cryptographic
57 * primitive shall be provided as input to the conditioning
58 * function to produce full entropy output.
60 * For us, cryptographic primitive is SHA-256 and its blocksize is
61 * 512-bit (64-byte), thus, N >= 128.
63 * We chose N=140. Note that we have "additional bits" of 16-byte for
64 * last block (feedback from previous output of SHA-256) to feed
65 * hash_df function of SHA-256, together with sample data of 140-byte.
67 * N=140 corresponds to min-entropy >= 3.68.
70 #define NUM_NOISE_INPUTS 140
72 #define EP_ROUND_0 0 /* initial-five-byte and 3-byte, then 56-byte-input */
73 #define EP_ROUND_1 1 /* 64-byte-input */
74 #define EP_ROUND_2 2 /* 17-byte-input */
75 #define EP_ROUND_RAW 3 /* 32-byte-input */
76 #define EP_ROUND_RAW_DATA 4 /* 32-byte-input */
78 #define EP_ROUND_0_INPUTS 56
79 #define EP_ROUND_1_INPUTS 64
80 #define EP_ROUND_2_INPUTS 17
81 #define EP_ROUND_RAW_INPUTS 32
82 #define EP_ROUND_RAW_DATA_INPUTS 32
84 static uint8_t ep_round;
87 * Hash_df initial string:
90 * 0, 0, 1, 0 : no_of_bits_returned (in big endian)
92 static void ep_fill_initial_string (void)
94 adc_buf[0] = 0x01000001; /* Regardless of endian */
95 adc_buf[1] = (CRC->DR & 0xffffff00);
98 static void ep_init (int mode)
100 adc_data_available = 0;
102 if (mode == NEUG_MODE_RAW)
104 ep_round = EP_ROUND_RAW;
105 adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
107 else if (mode == NEUG_MODE_RAW_DATA)
109 ep_round = EP_ROUND_RAW_DATA;
110 adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
114 ep_round = EP_ROUND_0;
115 ep_fill_initial_string ();
116 adc_start_conversion (ADC_CRC32_MODE,
117 &adc_buf[2], EP_ROUND_0_INPUTS);
121 static void noise_source_continuous_test (uint8_t noise);
123 static void ep_fill_wbuf (int i, int flip, int test)
125 uint32_t v = adc_buf[i];
129 uint8_t b0, b1, b2, b3;
136 noise_source_continuous_test (b0);
137 noise_source_continuous_test (b1);
138 noise_source_continuous_test (b2);
139 noise_source_continuous_test (b3);
143 v = __builtin_bswap32 (v);
145 sha256_ctx_data.wbuf[i] = v;
148 /* Here assumes little endian architecture. */
149 static int ep_process (int mode)
153 if (ep_round == EP_ROUND_RAW)
155 for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
156 ep_fill_wbuf (i, 0, 1);
159 return EP_ROUND_RAW_INPUTS / 4;
161 else if (ep_round == EP_ROUND_RAW_DATA)
163 for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
164 ep_fill_wbuf (i, 0, 0);
167 return EP_ROUND_RAW_DATA_INPUTS / 4;
170 if (ep_round == EP_ROUND_0)
172 for (i = 0; i < 64 / 4; i++)
173 ep_fill_wbuf (i, 1, 1);
175 adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_1_INPUTS);
176 sha256_start (&sha256_ctx_data);
177 sha256_process (&sha256_ctx_data);
181 else if (ep_round == EP_ROUND_1)
183 for (i = 0; i < 64 / 4; i++)
184 ep_fill_wbuf (i, 1, 1);
186 adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
187 sha256_process (&sha256_ctx_data);
193 for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
194 ep_fill_wbuf (i, 0, 1);
196 n = SHA256_DIGEST_SIZE / 2;
197 ep_init (NEUG_MODE_CONDITIONED); /* The three-byte is used here. */
198 memcpy (((uint8_t *)sha256_ctx_data.wbuf)
199 + ((NUM_NOISE_INPUTS+5)%SHA256_BLOCK_SIZE),
200 sha256_output, n); /* Don't use the last three-byte. */
201 sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
202 sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
203 return SHA256_DIGEST_SIZE / sizeof (uint32_t);
208 static const uint32_t *ep_output (int mode)
211 return sha256_ctx_data.wbuf;
213 return sha256_output;
216 #define REPETITION_COUNT 1
217 #define ADAPTIVE_PROPORTION_64 2
218 #define ADAPTIVE_PROPORTION_4096 4
220 uint8_t neug_err_state;
221 uint16_t neug_err_cnt;
222 uint16_t neug_err_cnt_rc;
223 uint16_t neug_err_cnt_p64;
224 uint16_t neug_err_cnt_p4k;
226 uint16_t neug_rc_max;
227 uint16_t neug_p64_max;
228 uint16_t neug_p4k_max;
232 static void noise_source_cnt_max_reset (void)
234 neug_err_cnt = neug_err_cnt_rc = neug_err_cnt_p64 = neug_err_cnt_p4k = 0;
235 neug_rc_max = neug_p64_max = neug_p4k_max = 0;
238 static void noise_source_error_reset (void)
243 static void noise_source_error (uint32_t err)
245 neug_err_state |= err;
248 if ((err & REPETITION_COUNT))
250 if ((err & ADAPTIVE_PROPORTION_64))
252 if ((err & ADAPTIVE_PROPORTION_4096))
257 * For health tests, we assume that the device noise source has
258 * min-entropy >= 4.2. Observing raw data stream (before CRC-32) has
259 * more than 4.2 bit/byte entropy. When the data stream after CRC-32
260 * filter will be less than 4.2 bit/byte entropy, that must be
261 * something wrong. Note that even we observe < 4.2, we still have
262 * some margin, since we use NUM_NOISE_INPUTS=140.
266 /* Cuttoff = 9, when min-entropy = 4.2, W= 2^-30 */
267 /* ceiling of (1+30/4.2) */
268 #define REPITITION_COUNT_TEST_CUTOFF 9
270 static uint8_t rct_a;
271 static uint8_t rct_b;
273 static void repetition_count_test (uint8_t sample)
278 if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
279 noise_source_error (REPETITION_COUNT);
280 if (rct_b > neug_rc_max)
290 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
291 /* With R, qbinom(1-2^-30,64,2^-4.2) */
292 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
294 static uint8_t ap64t_a;
295 static uint8_t ap64t_b;
296 static uint8_t ap64t_s;
298 static void adaptive_proportion_64_test (uint8_t sample)
309 if (ap64t_a == sample)
312 if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
313 noise_source_error (ADAPTIVE_PROPORTION_64);
314 if (ap64t_b > neug_p64_max)
315 neug_p64_max = ap64t_b;
320 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
321 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
322 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
324 static uint8_t ap4096t_a;
325 static uint16_t ap4096t_b;
326 static uint16_t ap4096t_s;
328 static void adaptive_proportion_4096_test (uint8_t sample)
330 if (ap4096t_s >= 4096)
339 if (ap4096t_a == sample)
342 if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
343 noise_source_error (ADAPTIVE_PROPORTION_4096);
344 if (ap4096t_b > neug_p4k_max)
345 neug_p4k_max = ap4096t_b;
350 static void noise_source_continuous_test (uint8_t noise)
352 repetition_count_test (noise);
353 adaptive_proportion_64_test (noise);
354 adaptive_proportion_4096_test (noise);
358 * Ring buffer, filled by generator, consumed by neug_get routine.
363 chopstx_cond_t data_available;
364 chopstx_cond_t space_available;
367 unsigned int full :1;
368 unsigned int empty :1;
371 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
375 chopstx_mutex_init (&rb->m);
376 chopstx_cond_init (&rb->data_available);
377 chopstx_cond_init (&rb->space_available);
378 rb->head = rb->tail = 0;
383 static void rb_add (struct rng_rb *rb, uint32_t v)
385 rb->buf[rb->tail++] = v;
386 if (rb->tail == rb->size)
388 if (rb->tail == rb->head)
393 static uint32_t rb_del (struct rng_rb *rb)
395 uint32_t v = rb->buf[rb->head++];
397 if (rb->head == rb->size)
399 if (rb->head == rb->tail)
407 static int rng_should_terminate;
408 static chopstx_t rng_thread;
412 * @brief Random number generation thread.
417 struct rng_rb *rb = (struct rng_rb *)arg;
419 rng_should_terminate = 0;
420 chopstx_mutex_init (&adc_mtx);
421 chopstx_cond_init (&adc_cond);
426 ep_init (NEUG_MODE_CONDITIONED);
428 while (!rng_should_terminate)
431 int mode = neug_mode;
433 chopstx_mutex_lock (&adc_mtx);
434 if (!adc_data_available)
437 chopstx_cond_wait (&adc_cond, &adc_mtx);
440 adc_data_available = 0;
441 chopstx_mutex_unlock (&adc_mtx);
443 if ((n = ep_process (mode)))
448 if (neug_err_state != 0
449 && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
451 /* Don't use the result and do it again. */
452 noise_source_error_reset ();
456 vp = ep_output (mode);
458 chopstx_mutex_lock (&rb->m);
460 chopstx_cond_wait (&rb->space_available, &rb->m);
462 for (i = 0; i < n; i++)
469 chopstx_cond_signal (&rb->data_available);
470 chopstx_mutex_unlock (&rb->m);
479 static struct rng_rb the_ring_buffer;
481 extern uint8_t __process2_stack_base__, __process2_stack_size__;
482 const uint32_t __stackaddr_rng = (uint32_t)&__process2_stack_base__;
483 const size_t __stacksize_rng = (size_t)&__process2_stack_size__;
487 * @brief Initialize NeuG.
490 neug_init (uint32_t *buf, uint8_t size)
492 const uint32_t *u = (const uint32_t *)unique_device_id ();
493 struct rng_rb *rb = &the_ring_buffer;
496 RCC->AHBENR |= RCC_AHBENR_CRCEN;
497 CRC->CR = CRC_CR_RESET;
500 * This initialization ensures that it generates different sequence
501 * even if all physical conditions are same.
503 for (i = 0; i < 3; i++)
506 neug_mode = NEUG_MODE_CONDITIONED;
507 rb_init (rb, buf, size);
509 rng_thread = chopstx_create (PRIO_RNG, __stackaddr_rng, __stacksize_rng,
514 * @breif Flush random bytes.
519 struct rng_rb *rb = &the_ring_buffer;
521 chopstx_mutex_lock (&rb->m);
524 chopstx_cond_signal (&rb->space_available);
525 chopstx_mutex_unlock (&rb->m);
530 * @brief Wakes up RNG thread to generate random numbers.
533 neug_kick_filling (void)
535 struct rng_rb *rb = &the_ring_buffer;
537 chopstx_mutex_lock (&rb->m);
539 chopstx_cond_signal (&rb->space_available);
540 chopstx_mutex_unlock (&rb->m);
544 * @brief Get random word (32-bit) from NeuG.
545 * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
546 * With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
547 * it is needed to call neug_kick_filling later.
552 struct rng_rb *rb = &the_ring_buffer;
555 chopstx_mutex_lock (&rb->m);
557 chopstx_cond_wait (&rb->data_available, &rb->m);
560 chopstx_cond_signal (&rb->space_available);
561 chopstx_mutex_unlock (&rb->m);
567 neug_get_nonblock (uint32_t *p)
569 struct rng_rb *rb = &the_ring_buffer;
572 chopstx_mutex_lock (&rb->m);
576 chopstx_cond_signal (&rb->space_available);
580 chopstx_mutex_unlock (&rb->m);
585 int neug_consume_random (void (*proc) (uint32_t, int))
588 struct rng_rb *rb = &the_ring_buffer;
590 chopstx_mutex_lock (&rb->m);
599 chopstx_cond_signal (&rb->space_available);
600 chopstx_mutex_unlock (&rb->m);
606 neug_wait_full (void)
608 struct rng_rb *rb = &the_ring_buffer;
610 chopstx_mutex_lock (&rb->m);
612 chopstx_cond_wait (&rb->data_available, &rb->m);
613 chopstx_mutex_unlock (&rb->m);
619 rng_should_terminate = 1;
621 chopstx_join (rng_thread, NULL);
625 neug_mode_select (uint8_t mode)
627 if (neug_mode == mode)
632 chopstx_mutex_lock (&adc_mtx);
633 while (adc_waiting == 0)
635 chopstx_mutex_unlock (&adc_mtx);
636 chopstx_usec_wait (1000);
637 chopstx_mutex_lock (&adc_mtx);
639 chopstx_mutex_unlock (&adc_mtx);
642 noise_source_cnt_max_reset ();