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