7eaadccfdbc1a963125aa9759316b0e1166b70fc
[gnuk/neug.git] / src / random.c
1 /*
2  * random.c - random number generation
3  *
4  * Copyright (C) 2011, 2012 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 <string.h>             /* for memcpy */
26 #include "config.h"
27
28 #include "ch.h"
29 #include "hal.h"
30 #include "sys.h"
31 #include "neug.h"
32 #include "adc.h"
33 #include "sha256.h"
34
35 Thread *rng_thread;
36 #define ADC_DATA_AVAILABLE ((eventmask_t)1)
37
38 static uint32_t adc_buf[SHA256_BLOCK_SIZE/sizeof (uint32_t)];
39
40 static sha256_context sha256_ctx_data;
41 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
42
43 /*
44  * To be a full entropy source, the requirement is to have N samples
45  * for output of 256-bit, where:
46  *
47  *      N = (256 * 2) / <min-entropy of a sample>
48  *
49  * For example, N should be more than 103 for min-entropy = 5.0.
50  *
51  * On the other hand, in the section 6.2 "Full Entropy Source
52  * Requirements", it says:
53  *
54  *     At least twice the block size of the underlying cryptographic
55  *     primitive shall be provided as input to the conditioning
56  *     function to produce full entropy output.
57  *
58  * For us, cryptographic primitive is SHA-256 and its blocksize is
59  * 512-bit (64-byte), thus, N >= 128.
60  *
61  * We chose N=140.  Note that we have "additional bits" of 16-byte for
62  * last block (feedback from previous output of SHA-256) to feed
63  * hash_df function of SHA-256, together with sample data of 140-byte.
64  *
65  * N=140 corresponds to min-entropy >= 3.68.
66  *
67  */
68 #define NUM_NOISE_INPUTS 140
69
70 #define EP_ROUND_0 0 /* initial-five-byte and 3-byte, then 56-byte-input */
71 #define EP_ROUND_1 1 /* 64-byte-input */
72 #define EP_ROUND_2 2 /* 17-byte-input */
73 #define EP_ROUND_RAW      3 /* 32-byte-input */
74 #define EP_ROUND_RAW_DATA 4 /* 32-byte-input */
75
76 #define EP_ROUND_0_INPUTS 56
77 #define EP_ROUND_1_INPUTS 64
78 #define EP_ROUND_2_INPUTS 17
79 #define EP_ROUND_RAW_INPUTS 32
80 #define EP_ROUND_RAW_DATA_INPUTS 32
81
82 static uint8_t ep_round;
83
84 /*
85  * Hash_df initial string:
86  *
87  *  1,          : counter = 1
88  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
89  */
90 static void ep_fill_initial_string (void)
91 {
92   adc_buf[0] = 0x01000001; /* Regardless of endian */
93   adc_buf[1] = (CRC->DR & 0xffffff00);
94 }
95
96 static void ep_init (int mode)
97 {
98   chEvtClearFlags (ADC_DATA_AVAILABLE);
99   if (mode == NEUG_MODE_RAW)
100     {
101       ep_round = EP_ROUND_RAW;
102       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
103     }
104   else if (mode == NEUG_MODE_RAW_DATA)
105     {
106       ep_round = EP_ROUND_RAW_DATA;
107       adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
108     }
109   else
110     {
111       ep_round = EP_ROUND_0;
112       ep_fill_initial_string ();
113       adc_start_conversion (ADC_CRC32_MODE,
114                             &adc_buf[2], EP_ROUND_0_INPUTS);
115     }
116 }
117
118 static void noise_source_continuous_test (uint8_t noise);
119
120 static void ep_fill_wbuf (int i, int flip, int test)
121 {
122   uint32_t v = adc_buf[i];
123
124   if (test)
125     {
126       uint8_t b0, b1, b2, b3;
127
128       b3 = v >> 24;
129       b2 = v >> 16;
130       b1 = v >> 8;
131       b0 = v;
132
133       noise_source_continuous_test (b0);
134       noise_source_continuous_test (b1);
135       noise_source_continuous_test (b2);
136       noise_source_continuous_test (b3);
137     }
138
139   if (flip)
140     v = __builtin_bswap32 (v);
141
142   sha256_ctx_data.wbuf[i] = v;
143 }
144
145 /* Here assumes little endian architecture.  */
146 static int ep_process (int mode)
147 {
148   int i, n;
149
150   if (ep_round == EP_ROUND_RAW)
151     {
152       for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
153         ep_fill_wbuf (i, 0, 1);
154
155       ep_init (mode);
156       return EP_ROUND_RAW_INPUTS / 4;
157     }
158   else if (ep_round == EP_ROUND_RAW_DATA)
159     {
160       for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
161         ep_fill_wbuf (i, 0, 0);
162
163       ep_init (mode);
164       return EP_ROUND_RAW_DATA_INPUTS / 4;
165     }
166
167   if (ep_round == EP_ROUND_0)
168     {
169       for (i = 0; i < 64 / 4; i++)
170         ep_fill_wbuf (i, 1, 1);
171
172       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_1_INPUTS);
173       sha256_start (&sha256_ctx_data);
174       sha256_process (&sha256_ctx_data);
175       ep_round++;
176       return 0;
177     }
178   else if (ep_round == EP_ROUND_1)
179     {
180       for (i = 0; i < 64 / 4; i++)
181         ep_fill_wbuf (i, 1, 1);
182
183       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
184       sha256_process (&sha256_ctx_data);
185       ep_round++;
186       return 0;
187     }
188   else
189     {
190       for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
191         ep_fill_wbuf (i, 0, 1);
192
193       n = SHA256_DIGEST_SIZE / 2;
194       ep_init (NEUG_MODE_CONDITIONED); /* The three-byte is used here.  */
195       memcpy (((uint8_t *)sha256_ctx_data.wbuf)
196               + ((NUM_NOISE_INPUTS+5)%SHA256_BLOCK_SIZE),
197               sha256_output, n); /* Don't use the last three-byte.  */
198       sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
199       sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
200       return SHA256_DIGEST_SIZE / sizeof (uint32_t);
201     }
202 }
203
204
205 static const uint32_t *ep_output (int mode)
206 {
207   if (mode)
208     return sha256_ctx_data.wbuf;
209   else
210     return sha256_output;
211 }
212 \f
213 #define REPETITION_COUNT           1
214 #define ADAPTIVE_PROPORTION_64     2
215 #define ADAPTIVE_PROPORTION_4096   4
216
217 uint8_t neug_err_state;
218 uint16_t neug_err_cnt;
219 uint16_t neug_err_cnt_rc;
220 uint16_t neug_err_cnt_p64;
221 uint16_t neug_err_cnt_p4k;
222
223 uint16_t neug_rc_max;
224 uint16_t neug_p64_max;
225 uint16_t neug_p4k_max;
226
227 #include "board.h"
228
229 static void noise_source_cnt_max_reset (void)
230 {
231   neug_err_cnt = neug_err_cnt_rc = neug_err_cnt_p64 = neug_err_cnt_p4k = 0;
232   neug_rc_max = neug_p64_max = neug_p4k_max = 0;
233
234 #if defined(BOARD_FST_01)
235   palClearPad (IOPORT1, 2);
236 #endif
237 #if defined(BOARD_STBEE_MINI)
238   palSetPad (IOPORT1, GPIOA_LED2);
239 #endif
240 }
241
242 static void noise_source_error_reset (void)
243 {
244   neug_err_state = 0;
245 }
246
247 static void noise_source_error (uint32_t err)
248 {
249   neug_err_state |= err;
250   neug_err_cnt++;
251
252   if ((err & REPETITION_COUNT))
253     neug_err_cnt_rc++;
254   if ((err & ADAPTIVE_PROPORTION_64))
255     neug_err_cnt_p64++;
256   if ((err & ADAPTIVE_PROPORTION_4096))
257     neug_err_cnt_p4k++;
258
259 #if defined(BOARD_FST_01)
260   palSetPad (IOPORT1, 2);
261 #endif
262 #if defined(BOARD_STBEE_MINI)
263   palClearPad (IOPORT1, GPIOA_LED2);
264 #endif
265 }
266
267 /*
268  * For health tests, we assume that the device noise source has
269  * min-entropy >= 4.2.  Observing raw data stream (before CRC-32) has
270  * more than 4.2 bit/byte entropy.  When the data stream after CRC-32
271  * filter will be less than 4.2 bit/byte entropy, that must be
272  * something wrong.  Note that even we observe < 4.2, we still have
273  * some margin, since we use NUM_NOISE_INPUTS=140.
274  *
275  */
276
277 /* Cuttoff = 9, when min-entropy = 4.2, W= 2^-30 */
278 /* ceiling of (1+30/4.2) */
279 #define REPITITION_COUNT_TEST_CUTOFF 9
280
281 static uint8_t rct_a;
282 static uint8_t rct_b;
283
284 static void repetition_count_test (uint8_t sample)
285 {
286   if (rct_a == sample)
287     {
288       rct_b++;
289       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
290         noise_source_error (REPETITION_COUNT);
291       if (rct_b > neug_rc_max)
292         neug_rc_max = rct_b;
293    }
294   else
295     {
296       rct_a = sample;
297       rct_b = 1;
298     }
299 }
300
301 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
302 /* With R, qbinom(1-2^-30,64,2^-4.2) */
303 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
304
305 static uint8_t ap64t_a;
306 static uint8_t ap64t_b;
307 static uint8_t ap64t_s;
308
309 static void adaptive_proportion_64_test (uint8_t sample)
310 {
311   if (ap64t_s >= 64)
312     {
313       ap64t_a = sample;
314       ap64t_s = 0;
315       ap64t_b = 0;
316     }
317   else
318     {
319       ap64t_s++;
320       if (ap64t_a == sample)
321         {
322           ap64t_b++;
323           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
324             noise_source_error (ADAPTIVE_PROPORTION_64);
325           if (ap64t_b > neug_p64_max)
326             neug_p64_max = ap64t_b;
327         }
328     }
329 }
330
331 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
332 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
333 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
334
335 static uint8_t ap4096t_a;
336 static uint16_t ap4096t_b;
337 static uint16_t ap4096t_s;
338
339 static void adaptive_proportion_4096_test (uint8_t sample)
340 {
341   if (ap4096t_s >= 4096)
342     {
343       ap4096t_a = sample;
344       ap4096t_s = 0;
345       ap4096t_b = 0;
346     }
347   else
348     {
349       ap4096t_s++;
350       if (ap4096t_a == sample)
351         {
352           ap4096t_b++;
353           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
354             noise_source_error (ADAPTIVE_PROPORTION_4096);
355           if (ap4096t_b > neug_p4k_max)
356             neug_p4k_max = ap4096t_b;
357         }
358     }
359 }
360
361 static void noise_source_continuous_test (uint8_t noise)
362 {
363   repetition_count_test (noise);
364   adaptive_proportion_64_test (noise);
365   adaptive_proportion_4096_test (noise);
366 }
367 \f
368 /*
369  * Ring buffer, filled by generator, consumed by neug_get routine.
370  */
371 struct rng_rb {
372   uint32_t *buf;
373   Mutex m;
374   CondVar data_available;
375   CondVar space_available;
376   uint8_t head, tail;
377   uint8_t size;
378   unsigned int full :1;
379   unsigned int empty :1;
380 };
381
382 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
383 {
384   rb->buf = p;
385   rb->size = size;
386   chMtxInit (&rb->m);
387   chCondInit (&rb->data_available);
388   chCondInit (&rb->space_available);
389   rb->head = rb->tail = 0;
390   rb->full = 0;
391   rb->empty = 1;
392 }
393
394 static void rb_add (struct rng_rb *rb, uint32_t v)
395 {
396   rb->buf[rb->tail++] = v;
397   if (rb->tail == rb->size)
398     rb->tail = 0;
399   if (rb->tail == rb->head)
400     rb->full = 1;
401   rb->empty = 0;
402 }
403
404 static uint32_t rb_del (struct rng_rb *rb)
405 {
406   uint32_t v = rb->buf[rb->head++];
407
408   if (rb->head == rb->size)
409     rb->head = 0;
410   if (rb->head == rb->tail)
411     rb->empty = 1;
412   rb->full = 0;
413
414   return v;
415 }
416
417 uint8_t neug_mode;
418
419 /**
420  * @brief Random number generation thread.
421  */
422 static msg_t rng (void *arg)
423 {
424   struct rng_rb *rb = (struct rng_rb *)arg;
425
426   rng_thread = chThdSelf ();
427
428   /* Enable ADCs */
429   adc_start ();
430
431   ep_init (NEUG_MODE_CONDITIONED);
432
433   while (!chThdShouldTerminate ())
434     {
435       int n;
436       int mode = neug_mode;
437
438       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Get ADC sampling.  */
439
440       if ((n = ep_process (mode)))
441         {
442           int i;
443           const uint32_t *vp;
444
445           if (neug_err_state != 0
446               && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
447             {
448               /* Don't use the result and do it again.  */
449               noise_source_error_reset ();
450               continue;
451             }
452
453           vp = ep_output (mode);
454
455           chMtxLock (&rb->m);
456           while (rb->full)
457             chCondWait (&rb->space_available);
458
459           for (i = 0; i < n; i++)
460             {
461               rb_add (rb, *vp++);
462               if (rb->full)
463                 break;
464             }
465
466           chCondSignal (&rb->data_available);
467           chMtxUnlock ();
468         }
469     }
470
471   adc_stop ();
472
473   return 0;
474 }
475
476 static struct rng_rb the_ring_buffer;
477 static WORKING_AREA(wa_rng, 256);
478
479 /**
480  * @brief Initialize NeuG.
481  */
482 void
483 neug_init (uint32_t *buf, uint8_t size)
484 {
485   const uint32_t *u = (const uint32_t *)unique_device_id ();
486   struct rng_rb *rb = &the_ring_buffer;
487   int i;
488
489   RCC->AHBENR |= RCC_AHBENR_CRCEN;
490   CRC->CR = CRC_CR_RESET;
491
492   /*
493    * This initialization ensures that it generates different sequence
494    * even if all physical conditions are same.
495    */
496   for (i = 0; i < 3; i++)
497     CRC->DR = *u++;
498
499   neug_mode = NEUG_MODE_CONDITIONED;
500   rb_init (rb, buf, size);
501   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
502 }
503
504 /**
505  * @breif Flush random bytes.
506  */
507 void
508 neug_flush (void)
509 {
510   struct rng_rb *rb = &the_ring_buffer;
511
512   chMtxLock (&rb->m);
513   while (!rb->empty)
514     (void)rb_del (rb);
515   chCondSignal (&rb->space_available);
516   chMtxUnlock ();
517 }
518
519
520 /**
521  * @brief  Wakes up RNG thread to generate random numbers.
522  */
523 void
524 neug_kick_filling (void)
525 {
526   struct rng_rb *rb = &the_ring_buffer;
527
528   chMtxLock (&rb->m);
529   if (!rb->full)
530     chCondSignal (&rb->space_available);
531   chMtxUnlock ();
532 }
533
534 /**
535  * @brief  Get random word (32-bit) from NeuG.
536  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
537  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
538  *         it is needed to call neug_kick_filling later.
539  */
540 uint32_t
541 neug_get (int kick)
542 {
543   struct rng_rb *rb = &the_ring_buffer;
544   uint32_t v;
545
546   chMtxLock (&rb->m);
547   while (rb->empty)
548     chCondWait (&rb->data_available);
549   v = rb_del (rb);
550   if (kick)
551     chCondSignal (&rb->space_available);
552   chMtxUnlock ();
553
554   return v;
555 }
556
557 int
558 neug_get_nonblock (uint32_t *p)
559 {
560   struct rng_rb *rb = &the_ring_buffer;
561   int r = 0;
562
563   chMtxLock (&rb->m);
564   if (rb->empty)
565     {
566       r = -1;
567       chCondSignal (&rb->space_available);
568     }
569   else
570     *p = rb_del (rb);
571   chMtxUnlock ();
572
573   return r;
574 }
575
576 int neug_consume_random (void (*proc) (uint32_t, int))
577 {
578   int i = 0;
579   struct rng_rb *rb = &the_ring_buffer;
580
581   chMtxLock (&rb->m);
582   while (!rb->empty)
583     {
584       uint32_t v;
585
586       v = rb_del (rb);
587       proc (v, i);
588       i++;
589     }
590   chCondSignal (&rb->space_available);
591   chMtxUnlock ();
592
593   return i;
594 }
595
596 void
597 neug_wait_full (void)
598 {
599   struct rng_rb *rb = &the_ring_buffer;
600
601   chMtxLock (&rb->m);
602   while (!rb->full)
603     chCondWait (&rb->data_available);
604   chMtxUnlock ();
605 }
606
607 void
608 neug_fini (void)
609 {
610   if (rng_thread)
611     {
612       chThdTerminate (rng_thread);
613       neug_get (1);
614       chThdWait (rng_thread);
615       rng_thread = NULL;
616     }
617 }
618
619 void
620 neug_mode_select (uint8_t mode)
621 {
622   if (neug_mode == mode)
623     return;
624
625   neug_wait_full ();
626
627   while (rng_thread->p_state != THD_STATE_WTCOND)
628     chThdSleep (MS2ST (1));
629
630   ep_init (mode);
631   noise_source_cnt_max_reset ();
632   neug_mode = mode;
633   neug_flush ();
634 }