Gnuk->NeuG
[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_count;
218
219 static void noise_source_error_reset (void)
220 {
221   neug_err_state = 0;
222 }
223
224 static void noise_source_error (uint32_t err)
225 {
226   neug_err_state |= err;
227   neug_err_count++;
228
229 #include "board.h"
230 #if defined(BOARD_FST_01)
231   palSetPad (IOPORT1, 2);
232 #endif
233 #if defined(BOARD_STBEE_MINI)
234   palClearPad (IOPORT1, GPIOA_LED2);
235 #endif
236 }
237
238 /*
239  * For health tests, we assumes that the device noise source has
240  * min-entropy >= 4.2, since observing raw data stream (before CRC-32)
241  * has more than 4.2 bit/byte entropy.
242  *
243  */
244
245 /* Cuttoff = 6, when min-entropy = 4.2, W= 2^-30 */
246 /* ceiling of (1+30/4.2) */
247 #define REPITITION_COUNT_TEST_CUTOFF 8
248
249 static uint8_t rct_a;
250 static uint8_t rct_b;
251
252 static void repetition_count_test (uint8_t sample)
253 {
254   if (rct_a == sample)
255     {
256       rct_b++;
257       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
258         noise_source_error (REPETITION_COUNT);
259    }
260   else
261     {
262       rct_a = sample;
263       rct_b = 1;
264     }
265 }
266
267 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
268 /* With R, qbinom(1-2^-30,64,2^-4.2) */
269 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
270
271 static uint8_t ap64t_a;
272 static uint8_t ap64t_b;
273 static uint8_t ap64t_s;
274
275 static void adaptive_proportion_64_test (uint8_t sample)
276 {
277   if (ap64t_s >= 64)
278     {
279       ap64t_a = sample;
280       ap64t_s = 0;
281       ap64t_b = 0;
282     }
283   else
284     {
285       ap64t_s++;
286       if (ap64t_a == sample)
287         {
288           ap64t_b++;
289           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
290             noise_source_error (ADAPTIVE_PROPORTION_64);
291         }
292     }
293 }
294
295 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
296 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
297 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
298
299 static uint8_t ap4096t_a;
300 static uint16_t ap4096t_b;
301 static uint16_t ap4096t_s;
302
303 static void adaptive_proportion_4096_test (uint8_t sample)
304 {
305   if (ap4096t_s >= 4096)
306     {
307       ap4096t_a = sample;
308       ap4096t_s = 0;
309       ap4096t_b = 0;
310     }
311   else
312     {
313       ap4096t_s++;
314       if (ap4096t_a == sample)
315         {
316           ap4096t_b++;
317           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
318             noise_source_error (ADAPTIVE_PROPORTION_4096);
319         }
320     }
321 }
322
323 static void noise_source_continuous_test (uint8_t noise)
324 {
325   repetition_count_test (noise);
326   adaptive_proportion_64_test (noise);
327   adaptive_proportion_4096_test (noise);
328 }
329 \f
330 /*
331  * Ring buffer, filled by generator, consumed by neug_get routine.
332  */
333 struct rng_rb {
334   uint32_t *buf;
335   Mutex m;
336   CondVar data_available;
337   CondVar space_available;
338   uint8_t head, tail;
339   uint8_t size;
340   unsigned int full :1;
341   unsigned int empty :1;
342 };
343
344 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
345 {
346   rb->buf = p;
347   rb->size = size;
348   chMtxInit (&rb->m);
349   chCondInit (&rb->data_available);
350   chCondInit (&rb->space_available);
351   rb->head = rb->tail = 0;
352   rb->full = 0;
353   rb->empty = 1;
354 }
355
356 static void rb_add (struct rng_rb *rb, uint32_t v)
357 {
358   rb->buf[rb->tail++] = v;
359   if (rb->tail == rb->size)
360     rb->tail = 0;
361   if (rb->tail == rb->head)
362     rb->full = 1;
363   rb->empty = 0;
364 }
365
366 static uint32_t rb_del (struct rng_rb *rb)
367 {
368   uint32_t v = rb->buf[rb->head++];
369
370   if (rb->head == rb->size)
371     rb->head = 0;
372   if (rb->head == rb->tail)
373     rb->empty = 1;
374   rb->full = 0;
375
376   return v;
377 }
378
379 static uint8_t neug_mode;
380
381 /**
382  * @brief  Random number generation from ADC sampling.
383  * @param  RB: Pointer to ring buffer structure
384  * @return -1 when failure, 0 otherwise.
385  * @note   Called holding the mutex, with RB->full == 0.
386  *         Keep generating until RB->full == 1.
387  */
388 static int rng_gen (struct rng_rb *rb)
389 {
390   int n;
391   int mode = neug_mode;
392
393   while (1)
394     {
395       chEvtWaitOne (ADC_DATA_AVAILABLE); /* Got a series of ADC sampling.  */
396
397       if ((n = ep_process (mode)))
398         {
399           int i;
400           const uint32_t *vp;
401
402           vp = ep_output (mode);
403           for (i = 0; i < n; i++)
404             {
405               rb_add (rb, *vp);
406               vp++;
407               if (rb->full)
408                 return 0;
409             }
410         }
411     }
412
413   return 0;                     /* success */
414 }
415
416 /**
417  * @brief Random number generation thread.
418  */
419 static msg_t rng (void *arg)
420 {
421   struct rng_rb *rb = (struct rng_rb *)arg;
422
423   rng_thread = chThdSelf ();
424
425   /* Enable ADCs */
426   adc_start ();
427
428   ep_init (0);
429
430   while (!chThdShouldTerminate ())
431     {
432       chMtxLock (&rb->m);
433       while (rb->full)
434         chCondWait (&rb->space_available);
435       while (1)
436         {
437           rng_gen (rb);
438           if (neug_err_state != 0)
439             {
440               if (neug_mode == NEUG_MODE_CONDITIONED)
441                 while (!rb->empty)
442                   (void)rb_del (rb);
443               noise_source_error_reset ();
444             }
445           else
446             break;
447         }
448       chCondSignal (&rb->data_available);
449       chMtxUnlock ();
450     }
451
452   adc_stop ();
453
454   return 0;
455 }
456
457 static struct rng_rb the_ring_buffer;
458 static WORKING_AREA(wa_rng, 256);
459
460 /**
461  * @brief Initialize NeuG.
462  */
463 void
464 neug_init (uint32_t *buf, uint8_t size)
465 {
466   const uint32_t *u = (const uint32_t *)unique_device_id ();
467   struct rng_rb *rb = &the_ring_buffer;
468   int i;
469
470   RCC->AHBENR |= RCC_AHBENR_CRCEN;
471   CRC->CR = CRC_CR_RESET;
472
473   /*
474    * This initialization ensures that it generates different sequence
475    * even if all physical conditions are same.
476    */
477   for (i = 0; i < 3; i++)
478     CRC->DR = *u++;
479
480   neug_mode = NEUG_MODE_CONDITIONED;
481   rb_init (rb, buf, size);
482   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
483 }
484
485 /**
486  * @breif Flush random bytes.
487  */
488 void
489 neug_flush (void)
490 {
491   struct rng_rb *rb = &the_ring_buffer;
492
493   chMtxLock (&rb->m);
494   while (!rb->empty)
495     (void)rb_del (rb);
496   chCondSignal (&rb->space_available);
497   chMtxUnlock ();
498 }
499
500
501 /**
502  * @brief  Wakes up RNG thread to generate random numbers.
503  */
504 void
505 neug_kick_filling (void)
506 {
507   struct rng_rb *rb = &the_ring_buffer;
508
509   chMtxLock (&rb->m);
510   if (!rb->full)
511     chCondSignal (&rb->space_available);
512   chMtxUnlock ();
513 }
514
515 /**
516  * @brief  Get random word (32-bit) from NeuG.
517  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
518  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
519  *         it is needed to call neug_kick_filling later.
520  */
521 uint32_t
522 neug_get (int kick)
523 {
524   struct rng_rb *rb = &the_ring_buffer;
525   uint32_t v;
526
527   chMtxLock (&rb->m);
528   while (rb->empty)
529     chCondWait (&rb->data_available);
530   v = rb_del (rb);
531   if (kick)
532     chCondSignal (&rb->space_available);
533   chMtxUnlock ();
534
535   return v;
536 }
537
538 void
539 neug_wait_full (void)
540 {
541   struct rng_rb *rb = &the_ring_buffer;
542
543   chMtxLock (&rb->m);
544   while (!rb->full)
545     chCondWait (&rb->data_available);
546   chMtxUnlock ();
547 }
548
549 void
550 neug_fini (void)
551 {
552   if (rng_thread)
553     {
554       chThdTerminate (rng_thread);
555       neug_get (1);
556       chThdWait (rng_thread);
557       rng_thread = NULL;
558     }
559 }
560
561 void
562 neug_mode_select (uint8_t mode)
563 {
564   neug_wait_full ();
565   if (neug_mode != mode)
566     ep_init (mode);
567 #if defined(BOARD_FST_01)
568   palClearPad (IOPORT1, 2);
569 #endif
570   neug_mode = mode;
571   neug_flush ();
572 }