User our own ADC driver
[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  * Gnuk 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 "neug.h"
31 #include "adc.h"
32
33 Thread *rng_thread;
34 #define ADC_DATA_AVAILABLE ((eventmask_t)1)
35
36 #include "sha256.h"
37
38 static sha256_context sha256_ctx_data;
39 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
40
41 /*
42  * We did an experiment of measuring entropy of ADC output with MUST.
43  * The entropy of a byte by raw sampling of LSBs has more than 6.0 bit/byte.
44  *
45  * More tests will be required, but for now we assume min-entropy >= 5.0.
46  * 
47  * To be a full entropy source, the requirement is to have N samples for
48  * output of 256-bit, where:
49  *
50  *      N = (256 * 2) / <min-entropy of a sample>
51  *
52  * For min-entropy = 5.0, N should be more than 103.
53  *
54  * On the other hand, in the section 6.2 "Full Entropy Source Requirements",
55  * it says:
56  *
57  *     At least twice the block size of the underlying cryptographic
58  *     primitive shall be provided as input to the conditioning
59  *     function to produce full entropy output.
60  *
61  * For us, cryptographic primitive is SHA-256 and its blocksize is 512-bit
62  * (64-byte), N >= 128.
63  *
64  * We chose N=139, since we love prime number, and we have "additional bits"
65  * of 32-byte for last block (feedback from previous output of SHA-256).
66  *
67  * This corresponds to min-entropy >= 3.68.
68  *
69  */
70 #define NUM_NOISE_INPUTS 139
71
72 #define EP_ROUND_0 0 /* initial-five-byte and 59*8-sample-input */
73 #define EP_ROUND_1 1 /* 64*8-sample-input */
74 #define EP_ROUND_2 2 /* 16*8-sample-input */
75 #define EP_ROUND_RAW_LSB  3 /* 64*8-sample-input */
76 #define EP_ROUND_RAW_DATA 4 /* 16-sample-input */
77
78 #define EP_ROUND_0_INPUTS 59
79 #define EP_ROUND_1_INPUTS 64
80 #define EP_ROUND_2_INPUTS 16
81 #define EP_ROUND_RAW_LSB_INPUTS 64
82 #define EP_ROUND_RAW_DATA_INPUTS 2
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   memset (adc_samp, 0, 5 * 8 * sizeof (uint16_t));
95   adc_samp[0] = 1;
96   adc_samp[3*8] = 1;
97 }
98
99 static void ep_init (int mode)
100 {
101   chEvtClearFlags (ADC_DATA_AVAILABLE);
102   if (mode == NEUG_MODE_RAW_LSB)
103     {
104       ep_round = EP_ROUND_RAW_LSB;
105       adc_start_conversion (0, EP_ROUND_RAW_LSB_INPUTS*8/2);
106     }
107   else if (mode == NEUG_MODE_RAW_DATA)
108     {
109       ep_round = EP_ROUND_RAW_DATA;
110       adc_start_conversion (0, EP_ROUND_RAW_DATA_INPUTS*8/2);
111     }
112   else
113     {
114       ep_round = EP_ROUND_0;
115       ep_fill_initial_string ();
116       /*
117        * We get two samples for a single transaction of DMA.
118        * We take LSBs of each samples.
119        * Thus, we need tansactions of: required_number_of_input_in_byte*8/2 
120        */
121       adc_start_conversion (5*8, EP_ROUND_0_INPUTS*8/2);
122     }
123 }
124
125 static uint8_t ep_get_byte_from_samples (int i)
126 {
127   return (  ((adc_samp[i*8+0] & 1) << 0) | ((adc_samp[i*8+1] & 1) << 1)
128           | ((adc_samp[i*8+2] & 1) << 2) | ((adc_samp[i*8+3] & 1) << 3)
129           | ((adc_samp[i*8+4] & 1) << 4) | ((adc_samp[i*8+5] & 1) << 5)
130           | ((adc_samp[i*8+6] & 1) << 6) | ((adc_samp[i*8+7] & 1) << 7));
131 }
132
133 static void noise_source_continuous_test (uint8_t noise);
134
135 static void ep_fill_wbuf (int i, int flip, int mode)
136 {
137   if (mode == NEUG_MODE_RAW_DATA)
138     sha256_ctx_data.wbuf[i] = (adc_samp[i*2+1] << 16) | adc_samp[i*2];
139   else
140     {
141       uint8_t b0, b1, b2, b3;
142
143       b0 = ep_get_byte_from_samples (i*4 + 0);
144       b1 = ep_get_byte_from_samples (i*4 + 1);
145       b2 = ep_get_byte_from_samples (i*4 + 2);
146       b3 = ep_get_byte_from_samples (i*4 + 3);
147       noise_source_continuous_test (b0);
148       noise_source_continuous_test (b1);
149       noise_source_continuous_test (b2);
150       noise_source_continuous_test (b3);
151
152       if (flip)
153         sha256_ctx_data.wbuf[i] = (b0 << 24) | (b1 << 16) | (b2 << 8) | b3;
154       else
155         sha256_ctx_data.wbuf[i] = (b3 << 24) | (b2 << 16) | (b1 << 8) | b0;
156     }
157 }
158
159 /* Here assumes little endian architecture.  */
160 static int ep_process (int mode)
161 {
162   int i, n, flip;
163
164   if (ep_round == EP_ROUND_0 || ep_round == EP_ROUND_1)
165     {
166       n = 64 / 4;
167       flip = 1;
168     }
169   else if (ep_round == EP_ROUND_2)
170     {
171       n = EP_ROUND_2_INPUTS / 4;
172       flip = 0;
173     }
174   else if (ep_round == EP_ROUND_RAW_LSB)
175     {
176       n = EP_ROUND_RAW_LSB_INPUTS / 4;
177       flip = 0;
178     }
179   else /* ep_round == EP_ROUND_RAW_DATA */
180     {
181       n = EP_ROUND_RAW_DATA_INPUTS;
182       flip = 0;
183     }
184
185   for (i = 0; i < n; i++)
186     ep_fill_wbuf (i, flip, mode);
187
188   if (mode != NEUG_MODE_CONDITIONED)
189     {
190       ep_init (mode);
191       return n;
192     }
193   else
194     {
195       if (ep_round == EP_ROUND_0)
196         {
197           adc_start_conversion (0, EP_ROUND_1_INPUTS*8/2);
198           sha256_start (&sha256_ctx_data);
199           sha256_process (&sha256_ctx_data);
200           ep_round++;
201           return 0;
202         }
203       else if (ep_round == EP_ROUND_1)
204         {
205           adc_start_conversion (0, EP_ROUND_2_INPUTS*8/2);
206           sha256_process (&sha256_ctx_data);
207           ep_round++;
208           return 0;
209         }
210       else
211         {
212           n = SHA256_DIGEST_SIZE / 2;
213           ep_init (NEUG_MODE_CONDITIONED);
214           memcpy (((uint8_t *)sha256_ctx_data.wbuf)+EP_ROUND_2_INPUTS,
215                   sha256_output, n);
216           sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
217           sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
218           return SHA256_DIGEST_SIZE / sizeof (uint32_t);
219         }
220     }
221 }
222
223
224 static const uint32_t *ep_output (int mode)
225 {
226   if (mode)
227     return sha256_ctx_data.wbuf;
228   else
229     return sha256_output;
230 }
231 \f
232 #define REPETITION_COUNT           1
233 #define ADAPTIVE_PROPORTION_64     2
234 #define ADAPTIVE_PROPORTION_4096   4
235
236 uint8_t neug_err_state;
237 uint16_t neug_err_count;
238
239 static void noise_source_error_reset (void)
240 {
241   neug_err_state = 0;
242 }
243
244 static void noise_source_error (uint32_t err)
245 {
246   neug_err_state |= err;
247   neug_err_count++;
248
249 #include "board.h"
250 #if defined(BOARD_FST_01)
251   palSetPad (IOPORT1, 2);
252 #endif
253 #if defined(BOARD_STBEE_MINI)
254   palClearPad (IOPORT1, GPIOA_LED2);
255 #endif
256 }
257
258
259 /* Cuttoff = 10, when min-entropy = 3.7, W= 2^-30 */
260 /* ceiling of (1+30/3.7) */
261 #define REPITITION_COUNT_TEST_CUTOFF 10
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 = 22, when min-entropy = 3.7, W= 2^-30 */
282 /* With R, qbinom(1-2^-30,64,2^-3.7) */
283 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 22
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 = 422, when min-entropy = 3.7, W= 2^-30 */
310 /* With R, qbinom(1-2^-30,4096,2^-3.7) */
311 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 422
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 static 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 (0);
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   struct rng_rb *rb = &the_ring_buffer;
481
482   neug_mode = NEUG_MODE_CONDITIONED;
483   rb_init (rb, buf, size);
484   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
485 }
486
487 /**
488  * @breif Flush random bytes.
489  */
490 void
491 neug_flush (void)
492 {
493   struct rng_rb *rb = &the_ring_buffer;
494
495   chMtxLock (&rb->m);
496   while (!rb->empty)
497     (void)rb_del (rb);
498   chCondSignal (&rb->space_available);
499   chMtxUnlock ();
500 }
501
502
503 /**
504  * @brief  Wakes up RNG thread to generate random numbers.
505  */
506 void
507 neug_kick_filling (void)
508 {
509   struct rng_rb *rb = &the_ring_buffer;
510
511   chMtxLock (&rb->m);
512   if (!rb->full)
513     chCondSignal (&rb->space_available);
514   chMtxUnlock ();
515 }
516
517 /**
518  * @brief  Get random word (32-bit) from NeuG.
519  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
520  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
521  *         it is needed to call neug_kick_filling later.
522  */
523 uint32_t
524 neug_get (int kick)
525 {
526   struct rng_rb *rb = &the_ring_buffer;
527   uint32_t v;
528
529   chMtxLock (&rb->m);
530   while (rb->empty)
531     chCondWait (&rb->data_available);
532   v = rb_del (rb);
533   if (kick)
534     chCondSignal (&rb->space_available);
535   chMtxUnlock ();
536
537   return v;
538 }
539
540 void
541 neug_wait_full (void)
542 {
543   struct rng_rb *rb = &the_ring_buffer;
544
545   chMtxLock (&rb->m);
546   while (!rb->full)
547     chCondWait (&rb->data_available);
548   chMtxUnlock ();
549 }
550
551 void
552 neug_fini (void)
553 {
554   if (rng_thread)
555     {
556       chThdTerminate (rng_thread);
557       neug_get (1);
558       chThdWait (rng_thread);
559       rng_thread = NULL;
560     }
561 }
562
563 void
564 neug_mode_select (uint8_t mode)
565 {
566   neug_wait_full ();
567   if (neug_mode != mode)
568     ep_init (mode);
569 #if defined(BOARD_FST_01)
570   palClearPad (IOPORT1, 2);
571 #endif
572   neug_mode = mode;
573   neug_flush ();
574 }