6b317babc191bacbd88f310a92791ef71797a8e3
[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 for
45  * output of 256-bit, where:
46  *
47  *      N = (256 * 2) / <min-entropy of a sample>
48  *
49  * For min-entropy = 5.0, N should be more than 103.
50  *
51  * On the other hand, in the section 6.2 "Full Entropy Source Requirements",
52  * 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 512-bit
59  * (64-byte), N >= 128.
60  *
61  * We chose N=140.  We have "additional bits" of 32-byte for last
62  * block (feedback from previous output of SHA-256).
63  *
64  * This corresponds to min-entropy >= 3.68.
65  *
66  */
67 #define NUM_NOISE_INPUTS 140
68
69 #define EP_ROUND_0 0 /* initial-five-byte and 3-byte, then 56-byte-input */
70 #define EP_ROUND_1 1 /* 64-byte-input */
71 #define EP_ROUND_2 2 /* 17-byte-input */
72 #define EP_ROUND_RAW      3 /* 32-byte-input */
73 #define EP_ROUND_RAW_DATA 4 /* 8-byte-input */
74
75 #define EP_ROUND_0_INPUTS 56
76 #define EP_ROUND_1_INPUTS 64
77 #define EP_ROUND_2_INPUTS 17
78 #define EP_ROUND_RAW_INPUTS 32
79 #define EP_ROUND_RAW_DATA_INPUTS 8
80
81 static uint8_t ep_round;
82
83 /*
84  * Hash_df initial string:
85  *
86  *  1,          : counter = 1
87  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
88  */
89 static void ep_fill_initial_string (void)
90 {
91   adc_buf[0] = 0x01000001; /* Regardless of endian */
92   adc_buf[1] = (CRC->DR & 0xffffff00);
93 }
94
95 static void ep_init (int mode)
96 {
97   chEvtClearFlags (ADC_DATA_AVAILABLE);
98   if (mode == NEUG_MODE_RAW)
99     {
100       ep_round = EP_ROUND_RAW;
101       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
102     }
103   else if (mode == NEUG_MODE_RAW_DATA)
104     {
105       ep_round = EP_ROUND_RAW_DATA;
106       adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
107     }
108   else
109     {
110       ep_round = EP_ROUND_0;
111       ep_fill_initial_string ();
112       adc_start_conversion (ADC_CRC32_MODE,
113                             &adc_buf[2], EP_ROUND_0_INPUTS);
114     }
115 }
116
117 static void noise_source_continuous_test (uint8_t noise);
118
119 static void ep_fill_wbuf (int i, int flip, int test)
120 {
121   uint32_t v = adc_buf[i];
122
123   if (test)
124     {
125       uint8_t b0, b1, b2, b3;
126
127       b3 = v >> 24;
128       b2 = v >> 16;
129       b1 = v >> 8;
130       b0 = v;
131
132       noise_source_continuous_test (b0);
133       noise_source_continuous_test (b1);
134       noise_source_continuous_test (b2);
135       noise_source_continuous_test (b3);
136     }
137
138   if (flip)
139     v = __builtin_bswap32 (v);
140
141   sha256_ctx_data.wbuf[i] = v;
142 }
143
144 /* Here assumes little endian architecture.  */
145 static int ep_process (int mode)
146 {
147   int i, n;
148
149   if (ep_round == EP_ROUND_RAW)
150     {
151       for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
152         ep_fill_wbuf (i, 0, 0);
153
154       ep_init (mode);
155       return EP_ROUND_RAW_INPUTS / 4;
156     }
157   else if (ep_round == EP_ROUND_RAW_DATA)
158     {
159       for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
160         ep_fill_wbuf (i, 0, 0);
161
162       ep_init (mode);
163       return EP_ROUND_RAW_DATA_INPUTS / 4;
164     }
165
166   if (ep_round == EP_ROUND_0)
167     {
168       for (i = 0; i < 64 / 4; i++)
169         ep_fill_wbuf (i, 1, 1);
170
171       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_1_INPUTS);
172       sha256_start (&sha256_ctx_data);
173       sha256_process (&sha256_ctx_data);
174       ep_round++;
175       return 0;
176     }
177   else if (ep_round == EP_ROUND_1)
178     {
179       for (i = 0; i < 64 / 4; i++)
180         ep_fill_wbuf (i, 1, 1);
181
182       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
183       sha256_process (&sha256_ctx_data);
184       ep_round++;
185       return 0;
186     }
187   else
188     {
189       for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
190         ep_fill_wbuf (i, 0, 1);
191
192       n = SHA256_DIGEST_SIZE / 2;
193       ep_init (NEUG_MODE_CONDITIONED); /* The three-byte is used here.  */
194       memcpy (((uint8_t *)sha256_ctx_data.wbuf)
195               + ((NUM_NOISE_INPUTS+5)%SHA256_BLOCK_SIZE),
196               sha256_output, n); /* Don't use the last three-byte.  */
197       sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
198       sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
199       return SHA256_DIGEST_SIZE / sizeof (uint32_t);
200     }
201 }
202
203
204 static const uint32_t *ep_output (int mode)
205 {
206   if (mode)
207     return sha256_ctx_data.wbuf;
208   else
209     return sha256_output;
210 }
211 \f
212 #define REPETITION_COUNT           1
213 #define ADAPTIVE_PROPORTION_64     2
214 #define ADAPTIVE_PROPORTION_4096   4
215
216 uint8_t neug_err_state;
217 uint16_t neug_err_cnt;
218 uint16_t neug_err_cnt_rc;
219 uint16_t neug_err_cnt_p64;
220 uint16_t neug_err_cnt_p4k;
221
222 static void noise_source_error_reset (void)
223 {
224   neug_err_state = 0;
225 }
226
227 static void noise_source_error (uint32_t err)
228 {
229   neug_err_state |= err;
230   neug_err_cnt++;
231
232   if ((err & REPETITION_COUNT))
233     neug_err_cnt_rc++;
234   if ((err & ADAPTIVE_PROPORTION_64))
235     neug_err_cnt_p64++;
236   if ((err & ADAPTIVE_PROPORTION_4096))
237     neug_err_cnt_p4k++;
238
239 #include "board.h"
240 #if defined(BOARD_FST_01)
241   palSetPad (IOPORT1, 2);
242 #endif
243 #if defined(BOARD_STBEE_MINI)
244   palClearPad (IOPORT1, GPIOA_LED2);
245 #endif
246 }
247
248 /*
249  * For health tests, we assumes that the device noise source has
250  * min-entropy >= 4.2, since observing raw data stream (before CRC-32)
251  * has more than 4.2 bit/byte entropy.
252  *
253  */
254
255 /* Cuttoff = 6, when min-entropy = 4.2, W= 2^-30 */
256 /* ceiling of (1+30/4.2) */
257 #define REPITITION_COUNT_TEST_CUTOFF 8
258
259 static uint8_t rct_a;
260 static uint8_t rct_b;
261
262 static void repetition_count_test (uint8_t sample)
263 {
264   if (rct_a == sample)
265     {
266       rct_b++;
267       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
268         noise_source_error (REPETITION_COUNT);
269    }
270   else
271     {
272       rct_a = sample;
273       rct_b = 1;
274     }
275 }
276
277 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
278 /* With R, qbinom(1-2^-30,64,2^-4.2) */
279 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
280
281 static uint8_t ap64t_a;
282 static uint8_t ap64t_b;
283 static uint8_t ap64t_s;
284
285 static void adaptive_proportion_64_test (uint8_t sample)
286 {
287   if (ap64t_s >= 64)
288     {
289       ap64t_a = sample;
290       ap64t_s = 0;
291       ap64t_b = 0;
292     }
293   else
294     {
295       ap64t_s++;
296       if (ap64t_a == sample)
297         {
298           ap64t_b++;
299           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
300             noise_source_error (ADAPTIVE_PROPORTION_64);
301         }
302     }
303 }
304
305 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
306 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
307 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
308
309 static uint8_t ap4096t_a;
310 static uint16_t ap4096t_b;
311 static uint16_t ap4096t_s;
312
313 static void adaptive_proportion_4096_test (uint8_t sample)
314 {
315   if (ap4096t_s >= 4096)
316     {
317       ap4096t_a = sample;
318       ap4096t_s = 0;
319       ap4096t_b = 0;
320     }
321   else
322     {
323       ap4096t_s++;
324       if (ap4096t_a == sample)
325         {
326           ap4096t_b++;
327           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
328             noise_source_error (ADAPTIVE_PROPORTION_4096);
329         }
330     }
331 }
332
333 static void noise_source_continuous_test (uint8_t noise)
334 {
335   repetition_count_test (noise);
336   adaptive_proportion_64_test (noise);
337   adaptive_proportion_4096_test (noise);
338 }
339 \f
340 /*
341  * Ring buffer, filled by generator, consumed by neug_get routine.
342  */
343 struct rng_rb {
344   uint32_t *buf;
345   Mutex m;
346   CondVar data_available;
347   CondVar space_available;
348   uint8_t head, tail;
349   uint8_t size;
350   unsigned int full :1;
351   unsigned int empty :1;
352 };
353
354 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
355 {
356   rb->buf = p;
357   rb->size = size;
358   chMtxInit (&rb->m);
359   chCondInit (&rb->data_available);
360   chCondInit (&rb->space_available);
361   rb->head = rb->tail = 0;
362   rb->full = 0;
363   rb->empty = 1;
364 }
365
366 static void rb_add (struct rng_rb *rb, uint32_t v)
367 {
368   rb->buf[rb->tail++] = v;
369   if (rb->tail == rb->size)
370     rb->tail = 0;
371   if (rb->tail == rb->head)
372     rb->full = 1;
373   rb->empty = 0;
374 }
375
376 static uint32_t rb_del (struct rng_rb *rb)
377 {
378   uint32_t v = rb->buf[rb->head++];
379
380   if (rb->head == rb->size)
381     rb->head = 0;
382   if (rb->head == rb->tail)
383     rb->empty = 1;
384   rb->full = 0;
385
386   return v;
387 }
388
389 uint8_t neug_mode;
390
391 /**
392  * @brief  Random number generation from ADC sampling.
393  * @param  RB: Pointer to ring buffer structure
394  * @return -1 when failure, 0 otherwise.
395  * @note   Called holding the mutex, with RB->full == 0.
396  *         Keep generating until RB->full == 1.
397  */
398 static int rng_gen (struct rng_rb *rb)
399 {
400   int n;
401   int mode = neug_mode;
402
403   while (1)
404     {
405       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Got a series of ADC sampling.  */
406
407       if ((n = ep_process (mode)))
408         {
409           int i;
410           const uint32_t *vp;
411
412           vp = ep_output (mode);
413           for (i = 0; i < n; i++)
414             {
415               rb_add (rb, *vp);
416               vp++;
417               if (rb->full)
418                 return 0;
419             }
420         }
421     }
422
423   return 0;                     /* success */
424 }
425
426 /**
427  * @brief Random number generation thread.
428  */
429 static msg_t rng (void *arg)
430 {
431   struct rng_rb *rb = (struct rng_rb *)arg;
432
433   rng_thread = chThdSelf ();
434
435   /* Enable ADCs */
436   adc_start ();
437
438   ep_init (NEUG_MODE_CONDITIONED);
439
440   while (!chThdShouldTerminate ())
441     {
442       chMtxLock (&rb->m);
443       while (rb->full)
444         chCondWait (&rb->space_available);
445       while (1)
446         {
447           rng_gen (rb);
448           if (neug_err_state != 0)
449             {
450               if (neug_mode == NEUG_MODE_CONDITIONED)
451                 while (!rb->empty)
452                   (void)rb_del (rb);
453               noise_source_error_reset ();
454             }
455           else
456             break;
457         }
458       chCondSignal (&rb->data_available);
459       chMtxUnlock ();
460     }
461
462   adc_stop ();
463
464   return 0;
465 }
466
467 static struct rng_rb the_ring_buffer;
468 static WORKING_AREA(wa_rng, 256);
469
470 /**
471  * @brief Initialize NeuG.
472  */
473 void
474 neug_init (uint32_t *buf, uint8_t size)
475 {
476   const uint32_t *u = (const uint32_t *)unique_device_id ();
477   struct rng_rb *rb = &the_ring_buffer;
478   int i;
479
480   RCC->AHBENR |= RCC_AHBENR_CRCEN;
481   CRC->CR = CRC_CR_RESET;
482
483   /*
484    * This initialization ensures that it generates different sequence
485    * even if all physical conditions are same.
486    */
487   for (i = 0; i < 3; i++)
488     CRC->DR = *u++;
489
490   neug_mode = NEUG_MODE_CONDITIONED;
491   rb_init (rb, buf, size);
492   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
493 }
494
495 /**
496  * @breif Flush random bytes.
497  */
498 void
499 neug_flush (void)
500 {
501   struct rng_rb *rb = &the_ring_buffer;
502
503   chMtxLock (&rb->m);
504   while (!rb->empty)
505     (void)rb_del (rb);
506   chCondSignal (&rb->space_available);
507   chMtxUnlock ();
508 }
509
510
511 /**
512  * @brief  Wakes up RNG thread to generate random numbers.
513  */
514 void
515 neug_kick_filling (void)
516 {
517   struct rng_rb *rb = &the_ring_buffer;
518
519   chMtxLock (&rb->m);
520   if (!rb->full)
521     chCondSignal (&rb->space_available);
522   chMtxUnlock ();
523 }
524
525 /**
526  * @brief  Get random word (32-bit) from NeuG.
527  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
528  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
529  *         it is needed to call neug_kick_filling later.
530  */
531 uint32_t
532 neug_get (int kick)
533 {
534   struct rng_rb *rb = &the_ring_buffer;
535   uint32_t v;
536
537   chMtxLock (&rb->m);
538   while (rb->empty)
539     chCondWait (&rb->data_available);
540   v = rb_del (rb);
541   if (kick)
542     chCondSignal (&rb->space_available);
543   chMtxUnlock ();
544
545   return v;
546 }
547
548 void
549 neug_wait_full (void)
550 {
551   struct rng_rb *rb = &the_ring_buffer;
552
553   chMtxLock (&rb->m);
554   while (!rb->full)
555     chCondWait (&rb->data_available);
556   chMtxUnlock ();
557 }
558
559 void
560 neug_fini (void)
561 {
562   if (rng_thread)
563     {
564       chThdTerminate (rng_thread);
565       neug_get (1);
566       chThdWait (rng_thread);
567       rng_thread = NULL;
568     }
569 }
570
571 void
572 neug_mode_select (uint8_t mode)
573 {
574   neug_wait_full ();
575   if (neug_mode != mode)
576     ep_init (mode);
577 #if defined(BOARD_FST_01)
578   palClearPad (IOPORT1, 2);
579 #endif
580   neug_mode = mode;
581   neug_flush ();
582 }