d8598e5fc70238d013a63c579e35366ee864f0c8
[gnuk/neug.git] / src / random.c
1 /*
2  * random.c - random number generation
3  *
4  * Copyright (C) 2011, 2012, 2013 Free Software Initiative of Japan
5  * Author: NIIBE Yutaka <gniibe@fsij.org>
6  *
7  * This file is a part of NeuG, a True Random Number Generator
8  * implementation based on quantization error of ADC (for STM32F103).
9  *
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.
14  *
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.
19  *
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/>.
22  *
23  */
24
25 #include <stdint.h>
26 #include <string.h>
27 #include <chopstx.h>
28
29 #include "sys.h"
30 #include "neug.h"
31 #include "stm32f103.h"
32 #include "adc.h"
33 #include "sha256.h"
34
35 chopstx_mutex_t adc_mtx;
36 chopstx_cond_t adc_cond;
37 int adc_waiting;
38 int adc_data_available;
39
40 static uint32_t adc_buf[SHA256_BLOCK_SIZE/sizeof (uint32_t)];
41
42 static sha256_context sha256_ctx_data;
43 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
44
45 /*
46  * To be a full entropy source, the requirement is to have N samples
47  * for output of 256-bit, where:
48  *
49  *      N = (256 * 2) / <min-entropy of a sample>
50  *
51  * For example, N should be more than 103 for min-entropy = 5.0.
52  *
53  * On the other hand, in the section 6.2 "Full Entropy Source
54  * Requirements", it says:
55  *
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.
59  *
60  * For us, cryptographic primitive is SHA-256 and its blocksize is
61  * 512-bit (64-byte), thus, N >= 128.
62  *
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.
66  *
67  * N=140 corresponds to min-entropy >= 3.68.
68  *
69  */
70 #define NUM_NOISE_INPUTS 140
71
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 */
77
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
83
84 static uint8_t ep_round;
85
86 /*
87  * Hash_df initial string:
88  *
89  *  1,          : counter = 1
90  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
91  */
92 static void ep_fill_initial_string (void)
93 {
94   adc_buf[0] = 0x01000001; /* Regardless of endian */
95   adc_buf[1] = (CRC->DR & 0xffffff00);
96 }
97
98 static void ep_init (int mode)
99 {
100   adc_data_available = 0;
101
102   if (mode == NEUG_MODE_RAW)
103     {
104       ep_round = EP_ROUND_RAW;
105       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
106     }
107   else if (mode == NEUG_MODE_RAW_DATA)
108     {
109       ep_round = EP_ROUND_RAW_DATA;
110       adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
111     }
112   else
113     {
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);
118     }
119 }
120
121 static void noise_source_continuous_test (uint8_t noise);
122
123 static void ep_fill_wbuf (int i, int flip, int test)
124 {
125   uint32_t v = adc_buf[i];
126
127   if (test)
128     {
129       uint8_t b0, b1, b2, b3;
130
131       b3 = v >> 24;
132       b2 = v >> 16;
133       b1 = v >> 8;
134       b0 = v;
135
136       noise_source_continuous_test (b0);
137       noise_source_continuous_test (b1);
138       noise_source_continuous_test (b2);
139       noise_source_continuous_test (b3);
140     }
141
142   if (flip)
143     v = __builtin_bswap32 (v);
144
145   sha256_ctx_data.wbuf[i] = v;
146 }
147
148 /* Here assumes little endian architecture.  */
149 static int ep_process (int mode)
150 {
151   int i, n;
152
153   if (ep_round == EP_ROUND_RAW)
154     {
155       for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
156         ep_fill_wbuf (i, 0, 1);
157
158       ep_init (mode);
159       return EP_ROUND_RAW_INPUTS / 4;
160     }
161   else if (ep_round == EP_ROUND_RAW_DATA)
162     {
163       for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
164         ep_fill_wbuf (i, 0, 0);
165
166       ep_init (mode);
167       return EP_ROUND_RAW_DATA_INPUTS / 4;
168     }
169
170   if (ep_round == EP_ROUND_0)
171     {
172       for (i = 0; i < 64 / 4; i++)
173         ep_fill_wbuf (i, 1, 1);
174
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);
178       ep_round++;
179       return 0;
180     }
181   else if (ep_round == EP_ROUND_1)
182     {
183       for (i = 0; i < 64 / 4; i++)
184         ep_fill_wbuf (i, 1, 1);
185
186       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
187       sha256_process (&sha256_ctx_data);
188       ep_round++;
189       return 0;
190     }
191   else
192     {
193       for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
194         ep_fill_wbuf (i, 0, 1);
195
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);
204     }
205 }
206
207
208 static const uint32_t *ep_output (int mode)
209 {
210   if (mode)
211     return sha256_ctx_data.wbuf;
212   else
213     return sha256_output;
214 }
215 \f
216 #define REPETITION_COUNT           1
217 #define ADAPTIVE_PROPORTION_64     2
218 #define ADAPTIVE_PROPORTION_4096   4
219
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;
225
226 uint16_t neug_rc_max;
227 uint16_t neug_p64_max;
228 uint16_t neug_p4k_max;
229
230 #include "board.h"
231
232 static void noise_source_cnt_max_reset (void)
233 {
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;
236 }
237
238 static void noise_source_error_reset (void)
239 {
240   neug_err_state = 0;
241 }
242
243 static void noise_source_error (uint32_t err)
244 {
245   neug_err_state |= err;
246   neug_err_cnt++;
247
248   if ((err & REPETITION_COUNT))
249     neug_err_cnt_rc++;
250   if ((err & ADAPTIVE_PROPORTION_64))
251     neug_err_cnt_p64++;
252   if ((err & ADAPTIVE_PROPORTION_4096))
253     neug_err_cnt_p4k++;
254 }
255
256 /*
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.
263  *
264  */
265
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
269
270 static uint8_t rct_a;
271 static uint8_t rct_b;
272
273 static void repetition_count_test (uint8_t sample)
274 {
275   if (rct_a == sample)
276     {
277       rct_b++;
278       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
279         noise_source_error (REPETITION_COUNT);
280       if (rct_b > neug_rc_max)
281         neug_rc_max = rct_b;
282    }
283   else
284     {
285       rct_a = sample;
286       rct_b = 1;
287     }
288 }
289
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
293
294 static uint8_t ap64t_a;
295 static uint8_t ap64t_b;
296 static uint8_t ap64t_s;
297
298 static void adaptive_proportion_64_test (uint8_t sample)
299 {
300   if (ap64t_s >= 64)
301     {
302       ap64t_a = sample;
303       ap64t_s = 0;
304       ap64t_b = 0;
305     }
306   else
307     {
308       ap64t_s++;
309       if (ap64t_a == sample)
310         {
311           ap64t_b++;
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;
316         }
317     }
318 }
319
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
323
324 static uint8_t ap4096t_a;
325 static uint16_t ap4096t_b;
326 static uint16_t ap4096t_s;
327
328 static void adaptive_proportion_4096_test (uint8_t sample)
329 {
330   if (ap4096t_s >= 4096)
331     {
332       ap4096t_a = sample;
333       ap4096t_s = 0;
334       ap4096t_b = 0;
335     }
336   else
337     {
338       ap4096t_s++;
339       if (ap4096t_a == sample)
340         {
341           ap4096t_b++;
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;
346         }
347     }
348 }
349
350 static void noise_source_continuous_test (uint8_t noise)
351 {
352   repetition_count_test (noise);
353   adaptive_proportion_64_test (noise);
354   adaptive_proportion_4096_test (noise);
355 }
356 \f
357 /*
358  * Ring buffer, filled by generator, consumed by neug_get routine.
359  */
360 struct rng_rb {
361   uint32_t *buf;
362   chopstx_mutex_t m;
363   chopstx_cond_t data_available;
364   chopstx_cond_t space_available;
365   uint8_t head, tail;
366   uint8_t size;
367   unsigned int full :1;
368   unsigned int empty :1;
369 };
370
371 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
372 {
373   rb->buf = p;
374   rb->size = 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;
379   rb->full = 0;
380   rb->empty = 1;
381 }
382
383 static void rb_add (struct rng_rb *rb, uint32_t v)
384 {
385   rb->buf[rb->tail++] = v;
386   if (rb->tail == rb->size)
387     rb->tail = 0;
388   if (rb->tail == rb->head)
389     rb->full = 1;
390   rb->empty = 0;
391 }
392
393 static uint32_t rb_del (struct rng_rb *rb)
394 {
395   uint32_t v = rb->buf[rb->head++];
396
397   if (rb->head == rb->size)
398     rb->head = 0;
399   if (rb->head == rb->tail)
400     rb->empty = 1;
401   rb->full = 0;
402
403   return v;
404 }
405
406 uint8_t neug_mode;
407 static int rng_should_terminate;
408 static chopstx_t rng_thread;
409
410
411 /**
412  * @brief Random number generation thread.
413  */
414 static void *
415 rng (void *arg)
416 {
417   struct rng_rb *rb = (struct rng_rb *)arg;
418
419   rng_should_terminate = 0;
420   chopstx_mutex_init (&adc_mtx);
421   chopstx_cond_init (&adc_cond);
422
423   /* Enable ADCs */
424   adc_start ();
425
426   ep_init (NEUG_MODE_CONDITIONED);
427
428   while (!rng_should_terminate)
429     {
430       int n;
431       int mode = neug_mode;
432
433       chopstx_mutex_lock (&adc_mtx);
434       if (!adc_data_available)
435         {
436           adc_waiting = 1;
437           chopstx_cond_wait (&adc_cond, &adc_mtx);
438           adc_waiting = 0;
439         }
440       adc_data_available = 0;
441       chopstx_mutex_unlock (&adc_mtx);
442
443       if ((n = ep_process (mode)))
444         {
445           int i;
446           const uint32_t *vp;
447
448           if (neug_err_state != 0
449               && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
450             {
451               /* Don't use the result and do it again.  */
452               noise_source_error_reset ();
453               continue;
454             }
455
456           vp = ep_output (mode);
457
458           chopstx_mutex_lock (&rb->m);
459           while (rb->full)
460             chopstx_cond_wait (&rb->space_available, &rb->m);
461
462           for (i = 0; i < n; i++)
463             {
464               rb_add (rb, *vp++);
465               if (rb->full)
466                 break;
467             }
468
469           chopstx_cond_signal (&rb->data_available);
470           chopstx_mutex_unlock (&rb->m);
471         }
472     }
473
474   adc_stop ();
475
476   return NULL;
477 }
478
479 static struct rng_rb the_ring_buffer;
480
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__;
484 #define PRIO_RNG 2
485
486 /**
487  * @brief Initialize NeuG.
488  */
489 void
490 neug_init (uint32_t *buf, uint8_t size)
491 {
492   const uint32_t *u = (const uint32_t *)unique_device_id ();
493   struct rng_rb *rb = &the_ring_buffer;
494   int i;
495
496   RCC->AHBENR |= RCC_AHBENR_CRCEN;
497   CRC->CR = CRC_CR_RESET;
498
499   /*
500    * This initialization ensures that it generates different sequence
501    * even if all physical conditions are same.
502    */
503   for (i = 0; i < 3; i++)
504     CRC->DR = *u++;
505
506   neug_mode = NEUG_MODE_CONDITIONED;
507   rb_init (rb, buf, size);
508
509   rng_thread = chopstx_create (PRIO_RNG, __stackaddr_rng, __stacksize_rng,
510                                rng, rb);
511 }
512
513 /**
514  * @breif Flush random bytes.
515  */
516 void
517 neug_flush (void)
518 {
519   struct rng_rb *rb = &the_ring_buffer;
520
521   chopstx_mutex_lock (&rb->m);
522   while (!rb->empty)
523     (void)rb_del (rb);
524   chopstx_cond_signal (&rb->space_available);
525   chopstx_mutex_unlock (&rb->m);
526 }
527
528
529 /**
530  * @brief  Wakes up RNG thread to generate random numbers.
531  */
532 void
533 neug_kick_filling (void)
534 {
535   struct rng_rb *rb = &the_ring_buffer;
536
537   chopstx_mutex_lock (&rb->m);
538   if (!rb->full)
539     chopstx_cond_signal (&rb->space_available);
540   chopstx_mutex_unlock (&rb->m);
541 }
542
543 /**
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.
548  */
549 uint32_t
550 neug_get (int kick)
551 {
552   struct rng_rb *rb = &the_ring_buffer;
553   uint32_t v;
554
555   chopstx_mutex_lock (&rb->m);
556   while (rb->empty)
557     chopstx_cond_wait (&rb->data_available, &rb->m);
558   v = rb_del (rb);
559   if (kick)
560     chopstx_cond_signal (&rb->space_available);
561   chopstx_mutex_unlock (&rb->m);
562
563   return v;
564 }
565
566 int
567 neug_get_nonblock (uint32_t *p)
568 {
569   struct rng_rb *rb = &the_ring_buffer;
570   int r = 0;
571
572   chopstx_mutex_lock (&rb->m);
573   if (rb->empty)
574     {
575       r = -1;
576       chopstx_cond_signal (&rb->space_available);
577     }
578   else
579     *p = rb_del (rb);
580   chopstx_mutex_unlock (&rb->m);
581
582   return r;
583 }
584
585 int neug_consume_random (void (*proc) (uint32_t, int))
586 {
587   int i = 0;
588   struct rng_rb *rb = &the_ring_buffer;
589
590   chopstx_mutex_lock (&rb->m);
591   while (!rb->empty)
592     {
593       uint32_t v;
594
595       v = rb_del (rb);
596       proc (v, i);
597       i++;
598     }
599   chopstx_cond_signal (&rb->space_available);
600   chopstx_mutex_unlock (&rb->m);
601
602   return i;
603 }
604
605 void
606 neug_wait_full (void)
607 {
608   struct rng_rb *rb = &the_ring_buffer;
609
610   chopstx_mutex_lock (&rb->m);
611   while (!rb->full)
612     chopstx_cond_wait (&rb->data_available, &rb->m);
613   chopstx_mutex_unlock (&rb->m);
614 }
615
616 void
617 neug_fini (void)
618 {
619   rng_should_terminate = 1;
620   neug_get (1);
621   chopstx_join (rng_thread, NULL);
622 }
623
624 void
625 neug_mode_select (uint8_t mode)
626 {
627   if (neug_mode == mode)
628     return;
629
630   neug_wait_full ();
631
632   chopstx_mutex_lock (&adc_mtx);
633   while (adc_waiting == 0)
634     {
635       chopstx_mutex_unlock (&adc_mtx);
636       chopstx_usec_wait (1000);
637       chopstx_mutex_lock (&adc_mtx);
638     }
639   chopstx_mutex_unlock (&adc_mtx);
640
641   ep_init (mode);
642   noise_source_cnt_max_reset ();
643   neug_mode = mode;
644   neug_flush ();
645 }