e426da5ba7e19dc066e93318d5529b26833dade2
[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
235 static void noise_source_error_reset (void)
236 {
237   neug_err_state = 0;
238 }
239
240 static void noise_source_error (uint32_t err)
241 {
242   neug_err_state |= err;
243   neug_err_cnt++;
244
245   if ((err & REPETITION_COUNT))
246     neug_err_cnt_rc++;
247   if ((err & ADAPTIVE_PROPORTION_64))
248     neug_err_cnt_p64++;
249   if ((err & ADAPTIVE_PROPORTION_4096))
250     neug_err_cnt_p4k++;
251 }
252
253 /*
254  * For health tests, we assume that the device noise source has
255  * min-entropy >= 4.2.  Observing raw data stream (before CRC-32) has
256  * more than 4.2 bit/byte entropy.  When the data stream after CRC-32
257  * filter will be less than 4.2 bit/byte entropy, that must be
258  * something wrong.  Note that even we observe < 4.2, we still have
259  * some margin, since we use NUM_NOISE_INPUTS=140.
260  *
261  */
262
263 /* Cuttoff = 9, when min-entropy = 4.2, W= 2^-30 */
264 /* ceiling of (1+30/4.2) */
265 #define REPITITION_COUNT_TEST_CUTOFF 9
266
267 static uint8_t rct_a;
268 static uint8_t rct_b;
269
270 static void repetition_count_test (uint8_t sample)
271 {
272   if (rct_a == sample)
273     {
274       rct_b++;
275       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
276         noise_source_error (REPETITION_COUNT);
277       if (rct_b > neug_rc_max)
278         neug_rc_max = rct_b;
279    }
280   else
281     {
282       rct_a = sample;
283       rct_b = 1;
284     }
285 }
286
287 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
288 /* With R, qbinom(1-2^-30,64,2^-4.2) */
289 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
290
291 static uint8_t ap64t_a;
292 static uint8_t ap64t_b;
293 static uint8_t ap64t_s;
294
295 static void adaptive_proportion_64_test (uint8_t sample)
296 {
297   if (ap64t_s >= 64)
298     {
299       ap64t_a = sample;
300       ap64t_s = 0;
301       ap64t_b = 0;
302     }
303   else
304     {
305       ap64t_s++;
306       if (ap64t_a == sample)
307         {
308           ap64t_b++;
309           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
310             noise_source_error (ADAPTIVE_PROPORTION_64);
311           if (ap64t_b > neug_p64_max)
312             neug_p64_max = ap64t_b;
313         }
314     }
315 }
316
317 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
318 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
319 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
320
321 static uint8_t ap4096t_a;
322 static uint16_t ap4096t_b;
323 static uint16_t ap4096t_s;
324
325 static void adaptive_proportion_4096_test (uint8_t sample)
326 {
327   if (ap4096t_s >= 4096)
328     {
329       ap4096t_a = sample;
330       ap4096t_s = 0;
331       ap4096t_b = 0;
332     }
333   else
334     {
335       ap4096t_s++;
336       if (ap4096t_a == sample)
337         {
338           ap4096t_b++;
339           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
340             noise_source_error (ADAPTIVE_PROPORTION_4096);
341           if (ap4096t_b > neug_p4k_max)
342             neug_p4k_max = ap4096t_b;
343         }
344     }
345 }
346
347 static void noise_source_continuous_test (uint8_t noise)
348 {
349   repetition_count_test (noise);
350   adaptive_proportion_64_test (noise);
351   adaptive_proportion_4096_test (noise);
352 }
353 \f
354 /*
355  * Ring buffer, filled by generator, consumed by neug_get routine.
356  */
357 struct rng_rb {
358   uint32_t *buf;
359   Mutex m;
360   CondVar data_available;
361   CondVar space_available;
362   uint8_t head, tail;
363   uint8_t size;
364   unsigned int full :1;
365   unsigned int empty :1;
366 };
367
368 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
369 {
370   rb->buf = p;
371   rb->size = size;
372   chMtxInit (&rb->m);
373   chCondInit (&rb->data_available);
374   chCondInit (&rb->space_available);
375   rb->head = rb->tail = 0;
376   rb->full = 0;
377   rb->empty = 1;
378 }
379
380 static void rb_add (struct rng_rb *rb, uint32_t v)
381 {
382   rb->buf[rb->tail++] = v;
383   if (rb->tail == rb->size)
384     rb->tail = 0;
385   if (rb->tail == rb->head)
386     rb->full = 1;
387   rb->empty = 0;
388 }
389
390 static uint32_t rb_del (struct rng_rb *rb)
391 {
392   uint32_t v = rb->buf[rb->head++];
393
394   if (rb->head == rb->size)
395     rb->head = 0;
396   if (rb->head == rb->tail)
397     rb->empty = 1;
398   rb->full = 0;
399
400   return v;
401 }
402
403 uint8_t neug_mode;
404
405 /**
406  * @brief Random number generation thread.
407  */
408 static msg_t rng (void *arg)
409 {
410   struct rng_rb *rb = (struct rng_rb *)arg;
411
412   rng_thread = chThdSelf ();
413
414   /* Enable ADCs */
415   adc_start ();
416
417   ep_init (NEUG_MODE_CONDITIONED);
418
419   while (!chThdShouldTerminate ())
420     {
421       int n;
422       int mode = neug_mode;
423
424       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Get ADC sampling.  */
425
426       if ((n = ep_process (mode)))
427         {
428           int i;
429           const uint32_t *vp;
430
431           if (neug_err_state != 0
432               && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
433             {
434               /* Don't use the result and do it again.  */
435               noise_source_error_reset ();
436               continue;
437             }
438
439           vp = ep_output (mode);
440
441           chMtxLock (&rb->m);
442           while (rb->full)
443             chCondWait (&rb->space_available);
444
445           for (i = 0; i < n; i++)
446             {
447               rb_add (rb, *vp++);
448               if (rb->full)
449                 break;
450             }
451
452           chCondSignal (&rb->data_available);
453           chMtxUnlock ();
454         }
455     }
456
457   adc_stop ();
458
459   return 0;
460 }
461
462 static struct rng_rb the_ring_buffer;
463 static WORKING_AREA(wa_rng, 256);
464
465 /**
466  * @brief Initialize NeuG.
467  */
468 void
469 neug_init (uint32_t *buf, uint8_t size)
470 {
471   const uint32_t *u = (const uint32_t *)unique_device_id ();
472   struct rng_rb *rb = &the_ring_buffer;
473   int i;
474
475   RCC->AHBENR |= RCC_AHBENR_CRCEN;
476   CRC->CR = CRC_CR_RESET;
477
478   /*
479    * This initialization ensures that it generates different sequence
480    * even if all physical conditions are same.
481    */
482   for (i = 0; i < 3; i++)
483     CRC->DR = *u++;
484
485   neug_mode = NEUG_MODE_CONDITIONED;
486   rb_init (rb, buf, size);
487   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
488 }
489
490 /**
491  * @breif Flush random bytes.
492  */
493 void
494 neug_flush (void)
495 {
496   struct rng_rb *rb = &the_ring_buffer;
497
498   chMtxLock (&rb->m);
499   while (!rb->empty)
500     (void)rb_del (rb);
501   chCondSignal (&rb->space_available);
502   chMtxUnlock ();
503 }
504
505
506 /**
507  * @brief  Wakes up RNG thread to generate random numbers.
508  */
509 void
510 neug_kick_filling (void)
511 {
512   struct rng_rb *rb = &the_ring_buffer;
513
514   chMtxLock (&rb->m);
515   if (!rb->full)
516     chCondSignal (&rb->space_available);
517   chMtxUnlock ();
518 }
519
520 /**
521  * @brief  Get random word (32-bit) from NeuG.
522  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
523  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
524  *         it is needed to call neug_kick_filling later.
525  */
526 uint32_t
527 neug_get (int kick)
528 {
529   struct rng_rb *rb = &the_ring_buffer;
530   uint32_t v;
531
532   chMtxLock (&rb->m);
533   while (rb->empty)
534     chCondWait (&rb->data_available);
535   v = rb_del (rb);
536   if (kick)
537     chCondSignal (&rb->space_available);
538   chMtxUnlock ();
539
540   return v;
541 }
542
543 int
544 neug_get_nonblock (uint32_t *p)
545 {
546   struct rng_rb *rb = &the_ring_buffer;
547   int r = 0;
548
549   chMtxLock (&rb->m);
550   if (rb->empty)
551     {
552       r = -1;
553       chCondSignal (&rb->space_available);
554     }
555   else
556     *p = rb_del (rb);
557   chMtxUnlock ();
558
559   return r;
560 }
561
562 int neug_consume_random (void (*proc) (uint32_t, int))
563 {
564   int i = 0;
565   struct rng_rb *rb = &the_ring_buffer;
566
567   chMtxLock (&rb->m);
568   while (!rb->empty)
569     {
570       uint32_t v;
571
572       v = rb_del (rb);
573       proc (v, i);
574       i++;
575     }
576   chCondSignal (&rb->space_available);
577   chMtxUnlock ();
578
579   return i;
580 }
581
582 void
583 neug_wait_full (void)
584 {
585   struct rng_rb *rb = &the_ring_buffer;
586
587   chMtxLock (&rb->m);
588   while (!rb->full)
589     chCondWait (&rb->data_available);
590   chMtxUnlock ();
591 }
592
593 void
594 neug_fini (void)
595 {
596   if (rng_thread)
597     {
598       chThdTerminate (rng_thread);
599       neug_get (1);
600       chThdWait (rng_thread);
601       rng_thread = NULL;
602     }
603 }
604
605 void
606 neug_mode_select (uint8_t mode)
607 {
608   if (neug_mode == mode)
609     return;
610
611   neug_wait_full ();
612
613   while (rng_thread->p_state != THD_STATE_WTCOND)
614     chThdSleep (MS2ST (1));
615
616   ep_init (mode);
617   noise_source_cnt_max_reset ();
618   neug_mode = mode;
619   neug_flush ();
620 }