more fixes
[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
31 static Thread *rng_thread;
32 #define ADC_DATA_AVAILABLE ((eventmask_t)1)
33
34 /* Total number of channels to be sampled by a single ADC operation.*/
35 #define ADC_GRP1_NUM_CHANNELS   1
36  
37 /* Depth of the conversion buffer, channels are sampled one time each.*/
38 #define ADC_GRP1_BUF_DEPTH      256
39
40 void adc2_init (void)
41 {
42   chSysLock ();
43   rccEnableAPB2 (RCC_APB2ENR_ADC2EN, FALSE);
44   ADC2->CR1 = 0;
45   ADC2->CR2 = ADC_CR2_ADON;
46   ADC2->CR2 = ADC_CR2_ADON | ADC_CR2_RSTCAL;
47   while ((ADC2->CR2 & ADC_CR2_RSTCAL) != 0)
48     ;
49   ADC2->CR2 = ADC_CR2_ADON | ADC_CR2_CAL;
50   while ((ADC2->CR2 & ADC_CR2_CAL) != 0)
51     ;
52   ADC2->CR2 = 0;
53   rccDisableAPB2 (RCC_APB2ENR_ADC2EN, FALSE);
54   chSysUnlock ();
55 }
56
57 static void adc2_start (void)
58 {
59   chSysLock ();
60
61   rccEnableAPB2 (RCC_APB2ENR_ADC2EN, FALSE);
62
63   ADC2->CR1 = ADC_CR1_DUALMOD_2 | ADC_CR1_DUALMOD_1 | ADC_CR1_DUALMOD_0;
64   ADC2->CR2 = ADC_CR2_EXTTRIG | ADC_CR2_EXTSEL | ADC_CR2_CONT | ADC_CR2_ADON;
65 #ifdef NEUG_NON_DEFAULT_ADC_CHANNEL
66   ADC2->SMPR1 = 0;
67   ADC2->SMPR2 = ADC_SMPR2_SMP_ANx_B(ADC_SAMPLE_1P5);
68 #else
69   ADC2->SMPR1 = ADC_SMPR1_SMP_AN11(ADC_SAMPLE_1P5);
70   ADC2->SMPR2 = 0;
71 #endif
72   ADC2->SQR1 = ADC_SQR1_NUM_CH(ADC_GRP1_NUM_CHANNELS);
73   ADC2->SQR2 = 0;
74 #ifdef NEUG_NON_DEFAULT_ADC_CHANNEL
75   ADC2->SQR3 = ADC_SQR3_SQ1_N(NEUG_ADC_CHANNEL_B);
76 #else
77   ADC2->SQR3 = ADC_SQR3_SQ1_N(ADC_CHANNEL_IN11);
78 #endif
79
80   chSysUnlock ();
81 }
82
83 static void adc2_start_conversion (void)
84 {
85   ADC2->CR2 = ADC_CR2_EXTTRIG | ADC_CR2_EXTSEL | ADC_CR2_CONT | ADC_CR2_ADON;
86 }
87
88 void adc2_stop_conversion (void)
89 {
90   ADC2->CR2 &= ~ADC_CR2_CONT;
91 }
92
93 static void adc2_stop (void)
94 {
95   rccDisableAPB2 (RCC_APB2ENR_ADC2EN, FALSE);
96 }
97
98 /*
99  * ADC samples buffer.
100  */
101 static adcsample_t samp[ADC_GRP1_NUM_CHANNELS * ADC_GRP1_BUF_DEPTH * 2];
102  
103 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n);
104 static void adccb_err (ADCDriver *adcp, adcerror_t err);
105
106 /*
107  * ADC conversion group.
108  * Mode: Dual fast interleaved mode.
109  *   ADC1: master, 16 samples of 1 channels.
110  *   ADC2: slave,  16 samples of 1 channels.
111  * Channels:
112  *   ADC1:
113  *     IN10 (1.5 cycles sample time, port configured as push pull output 50MHz)
114  *   ADC2:
115  *     IN11 (1.5 cycles sample time, port configured as push pull output 50MHz)
116  */
117 static const ADCConversionGroup adcgrpcfg = {
118   FALSE,
119   ADC_GRP1_NUM_CHANNELS,
120   adccb,
121   adccb_err,
122   ADC_CR1_DUALMOD_2 | ADC_CR1_DUALMOD_1 | ADC_CR1_DUALMOD_0,
123   ADC_CR2_EXTTRIG | ADC_CR2_SWSTART | ADC_CR2_EXTSEL,
124 #ifdef NEUG_NON_DEFAULT_ADC_CHANNEL
125   0,
126   ADC_SMPR2_SMP_ANx_A(ADC_SAMPLE_1P5),
127 #else
128   ADC_SMPR1_SMP_AN10(ADC_SAMPLE_1P5),
129   0,
130 #endif
131   ADC_SQR1_NUM_CH(ADC_GRP1_NUM_CHANNELS),
132   0,
133 #if NEUG_NON_DEFAULT_ADC_CHANNEL
134   ADC_SQR3_SQ1_N(NEUG_ADC_CHANNEL_A)
135 #else
136   ADC_SQR3_SQ1_N(ADC_CHANNEL_IN10)
137 #endif
138 };
139
140 /*
141  * ADC end conversion callback.
142  */
143 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n)
144 {
145   (void) buffer; (void) n;
146
147   chSysLockFromIsr();
148   if (adcp->state == ADC_COMPLETE && rng_thread)
149     chEvtSignalFlagsI (rng_thread, ADC_DATA_AVAILABLE);
150   chSysUnlockFromIsr();
151 }
152
153 static void adccb_err (ADCDriver *adcp, adcerror_t err)
154 {
155   (void)adcp;  (void)err;
156 }
157 \f
158 #include "sha256.h"
159
160 static sha256_context sha256_ctx_data;
161 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
162
163 /*
164  * We did an experiment of measuring entropy of ADC output with MUST.
165  * The entropy of a byte by raw sampling of LSBs has more than 6.0 bit/byte.
166  *
167  * More tests will be required, but for now we assume min-entropy >= 5.0.
168  * 
169  * To be a full entropy source, the requirement is to have N samples for
170  * output of 256-bit, where:
171  *
172  *      N = (256 * 2) / <min-entropy of a sample>
173  *
174  * For min-entropy = 5.0, N should be more than 103.
175  *
176  * On the other hand, in the section 6.2 "Full Entropy Source Requirements",
177  * it says:
178  *
179  *     At least twice the block size of the underlying cryptographic
180  *     primitive shall be provided as input to the conditioning
181  *     function to produce full entropy output.
182  *
183  * For us, cryptographic primitive is SHA-256 and its blocksize is 512-bit
184  * (64-byte), N >= 128.
185  *
186  * We chose N=139, since we love prime number, and we have "additional bits"
187  * of 32-byte for last block (feedback from previous output of SHA-256).
188  *
189  * This corresponds to min-entropy >= 3.68.
190  *
191  */
192 #define NUM_NOISE_INPUTS 139
193
194 #define EP_ROUND_0 0 /* initial-five-byte and 59-sample-input */
195 #define EP_ROUND_1 1 /* 64-sample-input */
196 #define EP_ROUND_2 2 /* 8-sample-input */
197 #define EP_ROUND_RAW 3 /* 8-sample-input */
198
199 #define EP_ROUND_0_INPUTS 59
200 #define EP_ROUND_1_INPUTS 64
201 #define EP_ROUND_2_INPUTS 16
202 #define EP_ROUND_RAW_INPUTS 64
203
204 static uint8_t ep_round;
205
206 /*
207  * Hash_df initial string:
208  *
209  *  1,          : counter = 1
210  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
211  */
212 static void ep_fill_initial_string (void)
213 {
214   memset (samp, 0, 5 * 8 * sizeof (adcsample_t));
215   samp[0] = 1;
216   samp[3*8] = 1;
217 }
218
219 static void ep_init (int raw)
220 {
221   chEvtClearFlags (ADC_DATA_AVAILABLE);
222   if (raw)
223     {
224       ep_round = EP_ROUND_RAW;
225       adc2_start_conversion ();
226       adcStartConversion (&ADCD1, &adcgrpcfg, samp, EP_ROUND_RAW_INPUTS*8/2);
227     }
228   else
229     {
230       ep_round = EP_ROUND_0;
231       ep_fill_initial_string ();
232       /*
233        * We get two samples for a single transaction of DMA.
234        * We take LSBs of each samples.
235        * Thus, we need tansactions of: required_number_of_input_in_byte*8/2 
236        */
237       adc2_start_conversion ();
238       adcStartConversion (&ADCD1, &adcgrpcfg,
239                           &samp[5*8], EP_ROUND_0_INPUTS*8/2);
240     }
241 }
242
243 static uint8_t ep_get_byte_from_samples (int i)
244 {
245   return (  ((samp[i*8+0] & 1) << 0) | ((samp[i*8+1] & 1) << 1)
246           | ((samp[i*8+2] & 1) << 2) | ((samp[i*8+3] & 1) << 3)
247           | ((samp[i*8+4] & 1) << 4) | ((samp[i*8+5] & 1) << 5)
248           | ((samp[i*8+6] & 1) << 6) | ((samp[i*8+7] & 1) << 7));
249 }
250
251 static void noise_source_continuous_test (uint8_t noise);
252
253 static void ep_fill_wbuf (int i, int flip)
254 {
255   uint8_t b0, b1, b2, b3;
256
257   b0 = ep_get_byte_from_samples (i*4 + 0);
258   b1 = ep_get_byte_from_samples (i*4 + 1);
259   b2 = ep_get_byte_from_samples (i*4 + 2);
260   b3 = ep_get_byte_from_samples (i*4 + 3);
261   noise_source_continuous_test (b0);
262   noise_source_continuous_test (b1);
263   noise_source_continuous_test (b2);
264   noise_source_continuous_test (b3);
265
266   if (flip)
267     sha256_ctx_data.wbuf[i] = (b0 << 24) | (b1 << 16) | (b2 << 8) | b3;
268   else
269     sha256_ctx_data.wbuf[i] = (b3 << 24) | (b2 << 16) | (b1 << 8) | b0;
270 }
271
272 /* Here assumes little endian architecture.  */
273 static int ep_process (int raw)
274 {
275   int i, n, flip;
276
277   if (ep_round == EP_ROUND_0 || ep_round == EP_ROUND_1)
278     {
279       n = 64 / 4;
280       flip = 1;
281     }
282   else if (ep_round == EP_ROUND_2)
283     {
284       n = EP_ROUND_2_INPUTS / 4;
285       flip = 0;
286     }
287   else /* ep_round == EP_ROUND_RAW */
288     {
289       n = EP_ROUND_RAW_INPUTS / 4;
290       flip = 0;
291     }
292
293   for (i = 0; i < n; i++)
294     ep_fill_wbuf (i, flip);
295
296   if (raw)
297     {
298       ep_init (1);
299       return n;
300     }
301   else
302     {
303       if (ep_round == EP_ROUND_0)
304         {
305           adc2_start_conversion ();
306           adcStartConversion (&ADCD1, &adcgrpcfg, samp, EP_ROUND_1_INPUTS*8/2);
307           sha256_start (&sha256_ctx_data);
308           sha256_process (&sha256_ctx_data);
309           ep_round++;
310           return 0;
311         }
312       else if (ep_round == EP_ROUND_1)
313         {
314           adc2_start_conversion ();
315           adcStartConversion (&ADCD1, &adcgrpcfg, samp, EP_ROUND_2_INPUTS*8/2);
316           sha256_process (&sha256_ctx_data);
317           ep_round++;
318           return 0;
319         }
320       else
321         {
322           n = SHA256_DIGEST_SIZE / 2;
323           ep_init (0);
324           memcpy (((uint8_t *)sha256_ctx_data.wbuf)+EP_ROUND_2_INPUTS,
325                   sha256_output, n);
326           sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
327           sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
328           return SHA256_DIGEST_SIZE / sizeof (uint32_t);
329         }
330     }
331 }
332
333
334 static const uint32_t *ep_output (int raw)
335 {
336   if (raw)
337     return sha256_ctx_data.wbuf;
338   else
339     return sha256_output;
340 }
341 \f
342 #define REPETITION_COUNT           1
343 #define ADAPTIVE_PROPORTION_64     2
344 #define ADAPTIVE_PROPORTION_4096   4
345
346 uint8_t neug_err_state;
347 uint16_t neug_err_count;
348
349 static void noise_source_error_reset (void)
350 {
351   neug_err_state = 0;
352 }
353
354 static void noise_source_error (uint32_t err)
355 {
356   neug_err_state |= err;
357   neug_err_count++;
358
359 #include "board.h"
360 #if defined(BOARD_FST_01)
361   palSetPad (IOPORT1, 2);
362 #endif
363 #if defined(BOARD_STBEE_MINI)
364   palClearPad (IOPORT1, GPIOA_LED2);
365 #endif
366 }
367
368
369 /* Cuttoff = 10, when min-entropy = 3.7, W= 2^-30 */
370 /* ceiling of (1+30/3.7) */
371 #define REPITITION_COUNT_TEST_CUTOFF 10
372
373 static uint8_t rct_a;
374 static uint8_t rct_b;
375
376 static void repetition_count_test (uint8_t sample)
377 {
378   if (rct_a == sample)
379     {
380       rct_b++;
381       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
382         noise_source_error (REPETITION_COUNT);
383    }
384   else
385     {
386       rct_a = sample;
387       rct_b = 1;
388     }
389 }
390
391 /* Cuttoff = 22, when min-entropy = 3.7, W= 2^-30 */
392 /* With R, qbinom(1-2^-30,64,2^-3.7) */
393 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 22
394
395 static uint8_t ap64t_a;
396 static uint8_t ap64t_b;
397 static uint8_t ap64t_s;
398
399 static void adaptive_proportion_64_test (uint8_t sample)
400 {
401   if (ap64t_s >= 64)
402     {
403       ap64t_a = sample;
404       ap64t_s = 0;
405       ap64t_b = 0;
406     }
407   else
408     {
409       ap64t_s++;
410       if (ap64t_a == sample)
411         {
412           ap64t_b++;
413           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
414             noise_source_error (ADAPTIVE_PROPORTION_64);
415         }
416     }
417 }
418
419 /* Cuttoff = 422, when min-entropy = 3.7, W= 2^-30 */
420 /* With R, qbinom(1-2^-30,4096,2^-3.7) */
421 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 422
422
423 static uint8_t ap4096t_a;
424 static uint16_t ap4096t_b;
425 static uint16_t ap4096t_s;
426
427 static void adaptive_proportion_4096_test (uint8_t sample)
428 {
429   if (ap4096t_s >= 4096)
430     {
431       ap4096t_a = sample;
432       ap4096t_s = 0;
433       ap4096t_b = 0;
434     }
435   else
436     {
437       ap4096t_s++;
438       if (ap4096t_a == sample)
439         {
440           ap4096t_b++;
441           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
442             noise_source_error (ADAPTIVE_PROPORTION_4096);
443         }
444     }
445 }
446
447 static void noise_source_continuous_test (uint8_t noise)
448 {
449   repetition_count_test (noise);
450   adaptive_proportion_64_test (noise);
451   adaptive_proportion_4096_test (noise);
452 }
453 \f
454 /*
455  * Ring buffer, filled by generator, consumed by neug_get routine.
456  */
457 struct rng_rb {
458   uint32_t *buf;
459   Mutex m;
460   CondVar data_available;
461   CondVar space_available;
462   uint8_t head, tail;
463   uint8_t size;
464   unsigned int full :1;
465   unsigned int empty :1;
466 };
467
468 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
469 {
470   rb->buf = p;
471   rb->size = size;
472   chMtxInit (&rb->m);
473   chCondInit (&rb->data_available);
474   chCondInit (&rb->space_available);
475   rb->head = rb->tail = 0;
476   rb->full = 0;
477   rb->empty = 1;
478 }
479
480 static void rb_add (struct rng_rb *rb, uint32_t v)
481 {
482   rb->buf[rb->tail++] = v;
483   if (rb->tail == rb->size)
484     rb->tail = 0;
485   if (rb->tail == rb->head)
486     rb->full = 1;
487   rb->empty = 0;
488 }
489
490 static uint32_t rb_del (struct rng_rb *rb)
491 {
492   uint32_t v = rb->buf[rb->head++];
493
494   if (rb->head == rb->size)
495     rb->head = 0;
496   if (rb->head == rb->tail)
497     rb->empty = 1;
498   rb->full = 0;
499
500   return v;
501 }
502
503 static uint8_t neug_raw;
504
505 /**
506  * @brief  Random number generation from ADC sampling.
507  * @param  RB: Pointer to ring buffer structure
508  * @return -1 when failure, 0 otherwise.
509  * @note   Called holding the mutex, with RB->full == 0.
510  *         Keep generating until RB->full == 1.
511  */
512 static int rng_gen (struct rng_rb *rb)
513 {
514   int n;
515   int raw = neug_raw;
516
517   while (1)
518     {
519       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Got a series of ADC sampling.  */
520
521       if ((n = ep_process (raw)))
522         {
523           int i;
524           const uint32_t *vp;
525
526           vp = ep_output (raw);
527           for (i = 0; i < n; i++)
528             {
529               rb_add (rb, *vp);
530               vp++;
531               if (rb->full)
532                 return 0;
533             }
534         }
535     }
536
537   return 0;                     /* success */
538 }
539
540 /**
541  * @brief Random number generation thread.
542  */
543 static msg_t rng (void *arg)
544 {
545   struct rng_rb *rb = (struct rng_rb *)arg;
546
547   rng_thread = chThdSelf ();
548
549   adcStart (&ADCD1, NULL);
550   /* Override DMA settings. */
551   ADCD1.dmamode = STM32_DMA_CR_PL(STM32_ADC_ADC1_DMA_PRIORITY)
552     | STM32_DMA_CR_MSIZE_WORD | STM32_DMA_CR_PSIZE_WORD | STM32_DMA_CR_MINC
553     | STM32_DMA_CR_TCIE       | STM32_DMA_CR_TEIE       | STM32_DMA_CR_EN;
554   /* Enable ADC2 */
555   adc2_start ();
556
557   ep_init (0);
558
559   while (!chThdShouldTerminate ())
560     {
561       chMtxLock (&rb->m);
562       while (rb->full)
563         chCondWait (&rb->space_available);
564       while (1)
565         {
566           rng_gen (rb);
567           if (neug_err_state != 0)
568             {
569               if (!neug_raw)
570                 while (!rb->empty)
571                   (void)rb_del (rb);
572               noise_source_error_reset ();
573             }
574           else
575             break;
576         }
577       chCondSignal (&rb->data_available);
578       chMtxUnlock ();
579     }
580
581   adc2_stop ();
582   adcStop (&ADCD1);
583
584   return 0;
585 }
586
587 static struct rng_rb the_ring_buffer;
588 static WORKING_AREA(wa_rng, 128);
589
590 /**
591  * @brief Initialize NeuG.
592  */
593 void
594 neug_init (uint32_t *buf, uint8_t size)
595 {
596   struct rng_rb *rb = &the_ring_buffer;
597
598   neug_raw = 0;
599   rb_init (rb, buf, size);
600   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
601 }
602
603 /**
604  * @breif Flush random bytes.
605  */
606 void
607 neug_flush (void)
608 {
609   struct rng_rb *rb = &the_ring_buffer;
610
611   chMtxLock (&rb->m);
612   while (!rb->empty)
613     (void)rb_del (rb);
614   chCondSignal (&rb->space_available);
615   chMtxUnlock ();
616 }
617
618
619 /**
620  * @brief  Wakes up RNG thread to generate random numbers.
621  */
622 void
623 neug_kick_filling (void)
624 {
625   struct rng_rb *rb = &the_ring_buffer;
626
627   chMtxLock (&rb->m);
628   if (!rb->full)
629     chCondSignal (&rb->space_available);
630   chMtxUnlock ();
631 }
632
633 /**
634  * @brief  Get random word (32-bit) from NeuG.
635  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
636  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
637  *         it is needed to call neug_kick_filling later.
638  */
639 uint32_t
640 neug_get (int kick)
641 {
642   struct rng_rb *rb = &the_ring_buffer;
643   uint32_t v;
644
645   chMtxLock (&rb->m);
646   while (rb->empty)
647     chCondWait (&rb->data_available);
648   v = rb_del (rb);
649   if (kick)
650     chCondSignal (&rb->space_available);
651   chMtxUnlock ();
652
653   return v;
654 }
655
656 void
657 neug_wait_full (void)
658 {
659   struct rng_rb *rb = &the_ring_buffer;
660
661   chMtxLock (&rb->m);
662   while (!rb->full)
663     chCondWait (&rb->data_available);
664   chMtxUnlock ();
665 }
666
667 void
668 neug_fini (void)
669 {
670   if (rng_thread)
671     {
672       chThdTerminate (rng_thread);
673       neug_get (1);
674       chThdWait (rng_thread);
675       rng_thread = NULL;
676     }
677 }
678
679 void
680 neug_select (uint8_t raw)
681 {
682   neug_wait_full ();
683   if (neug_raw != raw)
684     ep_init (raw);
685   neug_raw = raw;
686   neug_flush ();
687 }