a1786f294342ef56acabd2f6e9cdebf914dac438
[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 /* 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, 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 thread.
397  */
398 static msg_t rng (void *arg)
399 {
400   struct rng_rb *rb = (struct rng_rb *)arg;
401
402   rng_thread = chThdSelf ();
403
404   /* Enable ADCs */
405   adc_start ();
406
407   ep_init (NEUG_MODE_CONDITIONED);
408
409   while (!chThdShouldTerminate ())
410     {
411       int n;
412       int mode = neug_mode;
413
414       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Get ADC sampling.  */
415
416       if ((n = ep_process (mode)))
417         {
418           int i;
419           const uint32_t *vp;
420
421           if (neug_err_state != 0
422               && neug_mode == NEUG_MODE_CONDITIONED)
423             {
424               /* Don't use the result and do it again.  */
425               noise_source_error_reset ();
426               continue;
427             }
428
429           vp = ep_output (mode);
430
431           chMtxLock (&rb->m);
432           while (rb->full)
433             chCondWait (&rb->space_available);
434
435           for (i = 0; i < n; i++)
436             {
437               rb_add (rb, *vp++);
438               if (rb->full)
439                 break;
440             }
441
442           chCondSignal (&rb->data_available);
443           chMtxUnlock ();
444         }
445     }
446
447   adc_stop ();
448
449   return 0;
450 }
451
452 static struct rng_rb the_ring_buffer;
453 static WORKING_AREA(wa_rng, 256);
454
455 /**
456  * @brief Initialize NeuG.
457  */
458 void
459 neug_init (uint32_t *buf, uint8_t size)
460 {
461   const uint32_t *u = (const uint32_t *)unique_device_id ();
462   struct rng_rb *rb = &the_ring_buffer;
463   int i;
464
465   RCC->AHBENR |= RCC_AHBENR_CRCEN;
466   CRC->CR = CRC_CR_RESET;
467
468   /*
469    * This initialization ensures that it generates different sequence
470    * even if all physical conditions are same.
471    */
472   for (i = 0; i < 3; i++)
473     CRC->DR = *u++;
474
475   neug_mode = NEUG_MODE_CONDITIONED;
476   rb_init (rb, buf, size);
477   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
478 }
479
480 /**
481  * @breif Flush random bytes.
482  */
483 void
484 neug_flush (void)
485 {
486   struct rng_rb *rb = &the_ring_buffer;
487
488   chMtxLock (&rb->m);
489   while (!rb->empty)
490     (void)rb_del (rb);
491   chCondSignal (&rb->space_available);
492   chMtxUnlock ();
493 }
494
495
496 /**
497  * @brief  Wakes up RNG thread to generate random numbers.
498  */
499 void
500 neug_kick_filling (void)
501 {
502   struct rng_rb *rb = &the_ring_buffer;
503
504   chMtxLock (&rb->m);
505   if (!rb->full)
506     chCondSignal (&rb->space_available);
507   chMtxUnlock ();
508 }
509
510 /**
511  * @brief  Get random word (32-bit) from NeuG.
512  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
513  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
514  *         it is needed to call neug_kick_filling later.
515  */
516 uint32_t
517 neug_get (int kick)
518 {
519   struct rng_rb *rb = &the_ring_buffer;
520   uint32_t v;
521
522   chMtxLock (&rb->m);
523   while (rb->empty)
524     chCondWait (&rb->data_available);
525   v = rb_del (rb);
526   if (kick)
527     chCondSignal (&rb->space_available);
528   chMtxUnlock ();
529
530   return v;
531 }
532
533 void
534 neug_wait_full (void)
535 {
536   struct rng_rb *rb = &the_ring_buffer;
537
538   chMtxLock (&rb->m);
539   while (!rb->full)
540     chCondWait (&rb->data_available);
541   chMtxUnlock ();
542 }
543
544 void
545 neug_fini (void)
546 {
547   if (rng_thread)
548     {
549       chThdTerminate (rng_thread);
550       neug_get (1);
551       chThdWait (rng_thread);
552       rng_thread = NULL;
553     }
554 }
555
556 void
557 neug_mode_select (uint8_t mode)
558 {
559   neug_wait_full ();
560   while (rng_thread->p_state != THD_STATE_WTCOND)
561     chThdSleep (MS2ST (1));
562
563   if (neug_mode != mode)
564     ep_init (mode);
565
566 #if defined(BOARD_FST_01)
567   palClearPad (IOPORT1, 2);
568 #endif
569
570   neug_mode = mode;
571   neug_flush ();
572 }