improvement with Chopstx
[gnuk/neug.git] / src / neug.c
1 /*
2  * neug.c - true random number generation
3  *
4  * Copyright (C) 2011, 2012, 2013 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 <stdint.h>
26 #include <string.h>
27 #include <chopstx.h>
28
29 #include "sys.h"
30 #include "neug.h"
31 #include "stm32f103.h"
32 #include "adc.h"
33 #include "sha256.h"
34
35 static chopstx_mutex_t mode_mtx;
36 static chopstx_cond_t  mode_cond;
37
38 /*
39  * ADC finish interrupt
40  */
41 #define INTR_REQ_DMA1_Channel1 11
42
43
44 static uint32_t adc_buf[SHA256_BLOCK_SIZE/sizeof (uint32_t)];
45
46 static sha256_context sha256_ctx_data;
47 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
48
49 /*
50  * To be a full entropy source, the requirement is to have N samples
51  * for output of 256-bit, where:
52  *
53  *      N = (256 * 2) / <min-entropy of a sample>
54  *
55  * For example, N should be more than 103 for min-entropy = 5.0.
56  *
57  * On the other hand, in the section 6.2 "Full Entropy Source
58  * Requirements", it says:
59  *
60  *     At least twice the block size of the underlying cryptographic
61  *     primitive shall be provided as input to the conditioning
62  *     function to produce full entropy output.
63  *
64  * For us, cryptographic primitive is SHA-256 and its blocksize is
65  * 512-bit (64-byte), thus, N >= 128.
66  *
67  * We chose N=140.  Note that we have "additional bits" of 16-byte for
68  * last block (feedback from previous output of SHA-256) to feed
69  * hash_df function of SHA-256, together with sample data of 140-byte.
70  *
71  * N=140 corresponds to min-entropy >= 3.68.
72  *
73  */
74 #define NUM_NOISE_INPUTS 140
75
76 #define EP_ROUND_0 0 /* initial-five-byte and 3-byte, then 56-byte-input */
77 #define EP_ROUND_1 1 /* 64-byte-input */
78 #define EP_ROUND_2 2 /* 17-byte-input */
79 #define EP_ROUND_RAW      3 /* 32-byte-input */
80 #define EP_ROUND_RAW_DATA 4 /* 32-byte-input */
81
82 #define EP_ROUND_0_INPUTS 56
83 #define EP_ROUND_1_INPUTS 64
84 #define EP_ROUND_2_INPUTS 17
85 #define EP_ROUND_RAW_INPUTS 32
86 #define EP_ROUND_RAW_DATA_INPUTS 32
87
88 static uint8_t ep_round;
89
90 /*
91  * Hash_df initial string:
92  *
93  *  1,          : counter = 1
94  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
95  */
96 static void ep_fill_initial_string (void)
97 {
98   adc_buf[0] = 0x01000001; /* Regardless of endian */
99   adc_buf[1] = (CRC->DR & 0xffffff00);
100 }
101
102 static void ep_init (int mode)
103 {
104   if (mode == NEUG_MODE_RAW)
105     {
106       ep_round = EP_ROUND_RAW;
107       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
108     }
109   else if (mode == NEUG_MODE_RAW_DATA)
110     {
111       ep_round = EP_ROUND_RAW_DATA;
112       adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
113     }
114   else
115     {
116       ep_round = EP_ROUND_0;
117       ep_fill_initial_string ();
118       adc_start_conversion (ADC_CRC32_MODE,
119                             &adc_buf[2], EP_ROUND_0_INPUTS);
120     }
121 }
122
123 static void noise_source_continuous_test (uint8_t noise);
124
125 static void ep_fill_wbuf (int i, int flip, int test)
126 {
127   uint32_t v = adc_buf[i];
128
129   if (test)
130     {
131       uint8_t b0, b1, b2, b3;
132
133       b3 = v >> 24;
134       b2 = v >> 16;
135       b1 = v >> 8;
136       b0 = v;
137
138       noise_source_continuous_test (b0);
139       noise_source_continuous_test (b1);
140       noise_source_continuous_test (b2);
141       noise_source_continuous_test (b3);
142     }
143
144   if (flip)
145     v = __builtin_bswap32 (v);
146
147   sha256_ctx_data.wbuf[i] = v;
148 }
149
150 /* Here assumes little endian architecture.  */
151 static int ep_process (int mode)
152 {
153   int i, n;
154
155   if (ep_round == EP_ROUND_RAW)
156     {
157       for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
158         ep_fill_wbuf (i, 0, 1);
159
160       ep_init (mode);
161       return EP_ROUND_RAW_INPUTS / 4;
162     }
163   else if (ep_round == EP_ROUND_RAW_DATA)
164     {
165       for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
166         ep_fill_wbuf (i, 0, 0);
167
168       ep_init (mode);
169       return EP_ROUND_RAW_DATA_INPUTS / 4;
170     }
171
172   if (ep_round == EP_ROUND_0)
173     {
174       for (i = 0; i < 64 / 4; i++)
175         ep_fill_wbuf (i, 1, 1);
176
177       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_1_INPUTS);
178       sha256_start (&sha256_ctx_data);
179       sha256_process (&sha256_ctx_data);
180       ep_round++;
181       return 0;
182     }
183   else if (ep_round == EP_ROUND_1)
184     {
185       for (i = 0; i < 64 / 4; i++)
186         ep_fill_wbuf (i, 1, 1);
187
188       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
189       sha256_process (&sha256_ctx_data);
190       ep_round++;
191       return 0;
192     }
193   else
194     {
195       for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
196         ep_fill_wbuf (i, 0, 1);
197
198       n = SHA256_DIGEST_SIZE / 2;
199       ep_init (NEUG_MODE_CONDITIONED); /* The three-byte is used here.  */
200       memcpy (((uint8_t *)sha256_ctx_data.wbuf)
201               + ((NUM_NOISE_INPUTS+5)%SHA256_BLOCK_SIZE),
202               sha256_output, n); /* Don't use the last three-byte.  */
203       sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
204       sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
205       return SHA256_DIGEST_SIZE / sizeof (uint32_t);
206     }
207 }
208
209
210 static const uint32_t *ep_output (int mode)
211 {
212   if (mode)
213     return sha256_ctx_data.wbuf;
214   else
215     return sha256_output;
216 }
217 \f
218 #define REPETITION_COUNT           1
219 #define ADAPTIVE_PROPORTION_64     2
220 #define ADAPTIVE_PROPORTION_4096   4
221
222 uint8_t neug_err_state;
223 uint16_t neug_err_cnt;
224 uint16_t neug_err_cnt_rc;
225 uint16_t neug_err_cnt_p64;
226 uint16_t neug_err_cnt_p4k;
227
228 uint16_t neug_rc_max;
229 uint16_t neug_p64_max;
230 uint16_t neug_p4k_max;
231
232 #include "board.h"
233
234 static void noise_source_cnt_max_reset (void)
235 {
236   neug_err_cnt = neug_err_cnt_rc = neug_err_cnt_p64 = neug_err_cnt_p4k = 0;
237   neug_rc_max = neug_p64_max = neug_p4k_max = 0;
238 }
239
240 static void noise_source_error_reset (void)
241 {
242   neug_err_state = 0;
243 }
244
245 static void noise_source_error (uint32_t err)
246 {
247   neug_err_state |= err;
248   neug_err_cnt++;
249
250   if ((err & REPETITION_COUNT))
251     neug_err_cnt_rc++;
252   if ((err & ADAPTIVE_PROPORTION_64))
253     neug_err_cnt_p64++;
254   if ((err & ADAPTIVE_PROPORTION_4096))
255     neug_err_cnt_p4k++;
256 }
257
258 /*
259  * For health tests, we assume that the device noise source has
260  * min-entropy >= 4.2.  Observing raw data stream (before CRC-32) has
261  * more than 4.2 bit/byte entropy.  When the data stream after CRC-32
262  * filter will be less than 4.2 bit/byte entropy, that must be
263  * something wrong.  Note that even we observe < 4.2, we still have
264  * some margin, since we use NUM_NOISE_INPUTS=140.
265  *
266  */
267
268 /* Cuttoff = 9, when min-entropy = 4.2, W= 2^-30 */
269 /* ceiling of (1+30/4.2) */
270 #define REPITITION_COUNT_TEST_CUTOFF 9
271
272 static uint8_t rct_a;
273 static uint8_t rct_b;
274
275 static void repetition_count_test (uint8_t sample)
276 {
277   if (rct_a == sample)
278     {
279       rct_b++;
280       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
281         noise_source_error (REPETITION_COUNT);
282       if (rct_b > neug_rc_max)
283         neug_rc_max = rct_b;
284    }
285   else
286     {
287       rct_a = sample;
288       rct_b = 1;
289     }
290 }
291
292 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
293 /* With R, qbinom(1-2^-30,64,2^-4.2) */
294 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
295
296 static uint8_t ap64t_a;
297 static uint8_t ap64t_b;
298 static uint8_t ap64t_s;
299
300 static void adaptive_proportion_64_test (uint8_t sample)
301 {
302   if (ap64t_s >= 64)
303     {
304       ap64t_a = sample;
305       ap64t_s = 0;
306       ap64t_b = 0;
307     }
308   else
309     {
310       ap64t_s++;
311       if (ap64t_a == sample)
312         {
313           ap64t_b++;
314           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
315             noise_source_error (ADAPTIVE_PROPORTION_64);
316           if (ap64t_b > neug_p64_max)
317             neug_p64_max = ap64t_b;
318         }
319     }
320 }
321
322 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
323 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
324 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
325
326 static uint8_t ap4096t_a;
327 static uint16_t ap4096t_b;
328 static uint16_t ap4096t_s;
329
330 static void adaptive_proportion_4096_test (uint8_t sample)
331 {
332   if (ap4096t_s >= 4096)
333     {
334       ap4096t_a = sample;
335       ap4096t_s = 0;
336       ap4096t_b = 0;
337     }
338   else
339     {
340       ap4096t_s++;
341       if (ap4096t_a == sample)
342         {
343           ap4096t_b++;
344           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
345             noise_source_error (ADAPTIVE_PROPORTION_4096);
346           if (ap4096t_b > neug_p4k_max)
347             neug_p4k_max = ap4096t_b;
348         }
349     }
350 }
351
352 static void noise_source_continuous_test (uint8_t noise)
353 {
354   repetition_count_test (noise);
355   adaptive_proportion_64_test (noise);
356   adaptive_proportion_4096_test (noise);
357 }
358 \f
359 /*
360  * Ring buffer, filled by generator, consumed by neug_get routine.
361  */
362 struct rng_rb {
363   uint32_t *buf;
364   chopstx_mutex_t m;
365   chopstx_cond_t data_available;
366   chopstx_cond_t space_available;
367   uint8_t head, tail;
368   uint8_t size;
369   unsigned int full :1;
370   unsigned int empty :1;
371 };
372
373 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
374 {
375   rb->buf = p;
376   rb->size = size;
377   chopstx_mutex_init (&rb->m);
378   chopstx_cond_init (&rb->data_available);
379   chopstx_cond_init (&rb->space_available);
380   rb->head = rb->tail = 0;
381   rb->full = 0;
382   rb->empty = 1;
383 }
384
385 static void rb_add (struct rng_rb *rb, uint32_t v)
386 {
387   rb->buf[rb->tail++] = v;
388   if (rb->tail == rb->size)
389     rb->tail = 0;
390   if (rb->tail == rb->head)
391     rb->full = 1;
392   rb->empty = 0;
393 }
394
395 static uint32_t rb_del (struct rng_rb *rb)
396 {
397   uint32_t v = rb->buf[rb->head++];
398
399   if (rb->head == rb->size)
400     rb->head = 0;
401   if (rb->head == rb->tail)
402     rb->empty = 1;
403   rb->full = 0;
404
405   return v;
406 }
407
408 uint8_t neug_mode;
409 static int rng_should_terminate;
410 static chopstx_t rng_thread;
411
412
413 /**
414  * @brief Random number generation thread.
415  */
416 static void *
417 rng (void *arg)
418 {
419   struct rng_rb *rb = (struct rng_rb *)arg;
420   chopstx_intr_t adc_intr;
421   int mode = neug_mode;
422
423   rng_should_terminate = 0;
424   chopstx_mutex_init (&mode_mtx);
425   chopstx_cond_init (&mode_cond);
426
427   /* Enable ADCs */
428   adc_start ();
429   chopstx_claim_irq (&adc_intr, INTR_REQ_DMA1_Channel1);
430
431   ep_init (mode);
432   while (!rng_should_terminate)
433     {
434       int n;
435
436       adc_wait (&adc_intr);
437
438       chopstx_mutex_lock (&mode_mtx);
439       if (mode != neug_mode)
440         {
441           mode = neug_mode;
442
443           noise_source_cnt_max_reset ();
444
445           /* Discarding data available, re-initiate from the start.  */
446           ep_init (mode);
447           chopstx_cond_signal (&mode_cond);
448         }
449       chopstx_mutex_unlock (&mode_mtx);
450
451       if ((n = ep_process (mode)))
452         {
453           int i;
454           const uint32_t *vp;
455
456           if (neug_err_state != 0
457               && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
458             {
459               /* Don't use the result and do it again.  */
460               noise_source_error_reset ();
461               continue;
462             }
463
464           vp = ep_output (mode);
465
466           chopstx_mutex_lock (&rb->m);
467           while (rb->full)
468             chopstx_cond_wait (&rb->space_available, &rb->m);
469
470           for (i = 0; i < n; i++)
471             {
472               rb_add (rb, *vp++);
473               if (rb->full)
474                 break;
475             }
476
477           chopstx_cond_signal (&rb->data_available);
478           chopstx_mutex_unlock (&rb->m);
479         }
480     }
481
482   adc_stop ();
483   chopstx_release_irq (&adc_intr);
484
485   return NULL;
486 }
487
488 static struct rng_rb the_ring_buffer;
489
490 extern uint8_t __process2_stack_base__, __process2_stack_size__;
491 const uint32_t __stackaddr_rng = (uint32_t)&__process2_stack_base__;
492 const size_t __stacksize_rng = (size_t)&__process2_stack_size__;
493 #define PRIO_RNG 2
494
495 /**
496  * @brief Initialize NeuG.
497  */
498 void
499 neug_init (uint32_t *buf, uint8_t size)
500 {
501   const uint32_t *u = (const uint32_t *)unique_device_id ();
502   struct rng_rb *rb = &the_ring_buffer;
503   int i;
504
505   RCC->AHBENR |= RCC_AHBENR_CRCEN;
506   CRC->CR = CRC_CR_RESET;
507
508   /*
509    * This initialization ensures that it generates different sequence
510    * even if all physical conditions are same.
511    */
512   for (i = 0; i < 3; i++)
513     CRC->DR = *u++;
514
515   neug_mode = NEUG_MODE_CONDITIONED;
516   rb_init (rb, buf, size);
517
518   rng_thread = chopstx_create (PRIO_RNG, __stackaddr_rng, __stacksize_rng,
519                                rng, rb);
520 }
521
522 /**
523  * @breif Flush random bytes.
524  */
525 void
526 neug_flush (void)
527 {
528   struct rng_rb *rb = &the_ring_buffer;
529
530   chopstx_mutex_lock (&rb->m);
531   while (!rb->empty)
532     (void)rb_del (rb);
533   chopstx_cond_signal (&rb->space_available);
534   chopstx_mutex_unlock (&rb->m);
535 }
536
537
538 /**
539  * @brief  Wakes up RNG thread to generate random numbers.
540  */
541 void
542 neug_kick_filling (void)
543 {
544   struct rng_rb *rb = &the_ring_buffer;
545
546   chopstx_mutex_lock (&rb->m);
547   if (!rb->full)
548     chopstx_cond_signal (&rb->space_available);
549   chopstx_mutex_unlock (&rb->m);
550 }
551
552 /**
553  * @brief  Get random word (32-bit) from NeuG.
554  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
555  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
556  *         it is needed to call neug_kick_filling later.
557  */
558 uint32_t
559 neug_get (int kick)
560 {
561   struct rng_rb *rb = &the_ring_buffer;
562   uint32_t v;
563
564   chopstx_mutex_lock (&rb->m);
565   while (rb->empty)
566     chopstx_cond_wait (&rb->data_available, &rb->m);
567   v = rb_del (rb);
568   if (kick)
569     chopstx_cond_signal (&rb->space_available);
570   chopstx_mutex_unlock (&rb->m);
571
572   return v;
573 }
574
575 int
576 neug_get_nonblock (uint32_t *p)
577 {
578   struct rng_rb *rb = &the_ring_buffer;
579   int r = 0;
580
581   chopstx_mutex_lock (&rb->m);
582   if (rb->empty)
583     {
584       r = -1;
585       chopstx_cond_signal (&rb->space_available);
586     }
587   else
588     *p = rb_del (rb);
589   chopstx_mutex_unlock (&rb->m);
590
591   return r;
592 }
593
594 int neug_consume_random (void (*proc) (uint32_t, int))
595 {
596   int i = 0;
597   struct rng_rb *rb = &the_ring_buffer;
598
599   chopstx_mutex_lock (&rb->m);
600   while (!rb->empty)
601     {
602       uint32_t v;
603
604       v = rb_del (rb);
605       proc (v, i);
606       i++;
607     }
608   chopstx_cond_signal (&rb->space_available);
609   chopstx_mutex_unlock (&rb->m);
610
611   return i;
612 }
613
614 void
615 neug_wait_full (void)
616 {
617   struct rng_rb *rb = &the_ring_buffer;
618
619   chopstx_mutex_lock (&rb->m);
620   while (!rb->full)
621     chopstx_cond_wait (&rb->data_available, &rb->m);
622   chopstx_mutex_unlock (&rb->m);
623 }
624
625 void
626 neug_fini (void)
627 {
628   rng_should_terminate = 1;
629   neug_get (1);
630   chopstx_join (rng_thread, NULL);
631 }
632
633 void
634 neug_mode_select (uint8_t mode)
635 {
636   if (neug_mode == mode)
637     return;
638
639   neug_wait_full ();
640
641   chopstx_mutex_lock (&mode_mtx);
642   neug_mode = mode;
643   neug_flush ();
644   chopstx_cond_wait (&mode_cond, &mode_mtx);
645   chopstx_mutex_unlock (&mode_mtx);
646
647   neug_wait_full ();
648   neug_flush ();
649 }