tweak NUM_NOISE_INPUTS, etc.
[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 (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   2
36  
37 /* Depth of the conversion buffer, channels are sampled one time each.*/
38 #define ADC_GRP1_BUF_DEPTH      4
39  
40 /*
41  * ADC samples buffer.
42  */
43 static adcsample_t samp[ADC_GRP1_NUM_CHANNELS * ADC_GRP1_BUF_DEPTH];
44  
45 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n);
46 static void adccb_err (ADCDriver *adcp, adcerror_t err);
47
48 /*
49  * ADC conversion group.
50  * Mode:        Linear buffer, 4 samples of 2 channels, SW triggered.
51  * Channels:    Vref   (1.5 cycles sample time, violating the spec.)
52  *              Sensor (1.5 cycles sample time, violating the spec.)
53  */
54 static const ADCConversionGroup adcgrpcfg = {
55   FALSE,
56   ADC_GRP1_NUM_CHANNELS,
57   adccb,
58   adccb_err,
59   0,
60   ADC_CR2_TSVREFE,
61   ADC_SMPR1_SMP_SENSOR(ADC_SAMPLE_1P5) | ADC_SMPR1_SMP_VREF(ADC_SAMPLE_1P5),
62   0,
63   ADC_SQR1_NUM_CH(ADC_GRP1_NUM_CHANNELS),
64   0,
65   ADC_SQR3_SQ2_N(ADC_CHANNEL_SENSOR) | ADC_SQR3_SQ1_N(ADC_CHANNEL_VREFINT)
66 };
67
68 /*
69  * ADC end conversion callback.
70  */
71 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n)
72 {
73   (void) buffer; (void) n;
74
75   chSysLockFromIsr();
76   if (adcp->state == ADC_COMPLETE)
77     chEvtSignalFlagsI (rng_thread, ADC_DATA_AVAILABLE);
78   chSysUnlockFromIsr();
79 }
80
81 static void adccb_err (ADCDriver *adcp, adcerror_t err)
82 {
83   (void)adcp;  (void)err;
84 }
85
86 \f
87 #include "sha256.h"
88
89 static sha256_context sha256_ctx_data;
90 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
91
92 /*
93  * We did an experiment of measuring entropy of ADC output with MUST.
94  * The entropy of a byte by raw sampling of LSBs has more than 6.0 bit/byte.
95  *
96  * More tests will be required, but for now we assume min-entropy >= 5.0.
97  * 
98  * To be a full entropy source, the requirement is to have N samples for
99  * output of 256-bit, where:
100  *
101  *      N = (256 * 2) / <min-entropy of a sample>
102  *
103  * For min-entropy = 5.0, N should be more than 103.
104  *
105  * On the other hand, in the section 6.2 "Full Entropy Source Requirements",
106  * it says:
107  *
108  *     At least twice the block size of the underlying cryptographic
109  *     primitive shall be provided as input to the conditioning
110  *     function to produce full entropy output.
111  *
112  * For us, cryptographic primitive is SHA-256 and its blocksize is 512-bit
113  * (64-byte), N >= 128.
114  *
115  * We chose N=131, since we love prime number, and we have "additional bits"
116  * of 32-byte for last block (feedback from previous output of SHA-256).
117  *
118  * This corresponds to min-entropy >= 3.91.
119  *
120  */
121 #define NUM_NOISE_INPUTS 131
122
123 static const uint8_t hash_df_initial_string[5] = {
124   1,          /* counter = 1 */
125   0, 0, 0, 32 /* no_of_bits_returned (big endian) */
126 };
127
128 static void ep_init (void)
129 {
130   sha256_start (&sha256_ctx_data);
131   sha256_update (&sha256_ctx_data, hash_df_initial_string, 5);
132 }
133
134 static void ep_add (uint8_t entropy_bits)
135 {
136   sha256_update (&sha256_ctx_data, &entropy_bits, 1);
137 }
138
139 #define PROBABILITY_50_BY_TICK() ((SysTick->VAL & 0x02) != 0)
140
141 static const uint32_t *ep_output (void)
142 {
143   int n = (SHA256_BLOCK_SIZE - 9) - 
144     ((5 + NUM_NOISE_INPUTS) % SHA256_BLOCK_SIZE);
145
146   if (PROBABILITY_50_BY_TICK ())
147     n = n - 3;
148
149   sha256_update (&sha256_ctx_data, (uint8_t *)sha256_output, n);
150   sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
151   ep_init ();
152   return sha256_output;
153 }
154
155 #define REPETITION_COUNT           1
156 #define ADAPTIVE_PROPORTION_64     2
157 #define ADAPTIVE_PROPORTION_4096   4
158
159 uint32_t neug_err_state;
160
161 static void noise_source_error_reset (void)
162 {
163   neug_err_state = 0;
164 }
165
166 static void noise_source_error (uint32_t err)
167 {
168   neug_err_state |= err;
169 #include "board.h"
170 #if defined(BOARD_STBEE_MINI)
171   palClearPad (GPIOA, GPIOA_LED2);
172 #endif
173 }
174
175
176 /* Cuttoff = 9, when min-entropy = 4.0, W= 2^-30 */
177 /* ceiling of (1+30/4.0) */
178 #define REPITITION_COUNT_TEST_CUTOFF 9
179
180 static uint8_t rct_a;
181 static uint8_t rct_b;
182
183 static void repetition_count_test (uint8_t sample)
184 {
185   if (rct_a == sample)
186     {
187       rct_b++;
188       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
189         noise_source_error (REPETITION_COUNT);
190    }
191   else
192     {
193       rct_a = sample;
194       rct_b = 1;
195     }
196 }
197
198 /* Cuttoff = 20, when min-entropy = 4.0, W= 2^-30 */
199 /* With R, qbinom(1-2^-30,64,2^-4.0) */
200 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 20
201
202 static uint8_t ap64t_a;
203 static uint8_t ap64t_b;
204 static uint8_t ap64t_s;
205
206 static void adaptive_proportion_64_test (uint8_t sample)
207 {
208   if (ap64t_s >= 64)
209     {
210       ap64t_a = sample;
211       ap64t_s = 0;
212       ap64t_b = 0;
213     }
214   else
215     {
216       ap64t_s++;
217       if (ap64t_a == sample)
218         {
219           ap64t_b++;
220           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
221             noise_source_error (ADAPTIVE_PROPORTION_64);
222         }
223     }
224 }
225
226 /* Cuttoff = 354, when min-entropy = 4.0, W= 2^-30 */
227 /* With R, qbinom(1-2^-30,4096,2^-4.0) */
228 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 354
229
230 static uint8_t ap4096t_a;
231 static uint16_t ap4096t_b;
232 static uint16_t ap4096t_s;
233
234 static void adaptive_proportion_4096_test (uint8_t sample)
235 {
236   if (ap4096t_s >= 4096)
237     {
238       ap4096t_a = sample;
239       ap4096t_s = 0;
240       ap4096t_b = 0;
241     }
242   else
243     {
244       ap4096t_s++;
245       if (ap4096t_a == sample)
246         {
247           ap4096t_b++;
248           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
249             noise_source_error (ADAPTIVE_PROPORTION_4096);
250         }
251     }
252 }
253
254 static void noise_source_continuous_test (uint8_t noise)
255 {
256   repetition_count_test (noise);
257   adaptive_proportion_64_test (noise);
258   adaptive_proportion_4096_test (noise);
259 }
260
261 /*
262  * Ring buffer, filled by generator, consumed by neug_get routine.
263  */
264 struct rng_rb {
265   uint32_t *buf;
266   Mutex m;
267   CondVar data_available;
268   CondVar space_available;
269   uint8_t head, tail;
270   uint8_t size;
271   unsigned int full :1;
272   unsigned int empty :1;
273 };
274
275 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
276 {
277   rb->buf = p;
278   rb->size = size;
279   chMtxInit (&rb->m);
280   chCondInit (&rb->data_available);
281   chCondInit (&rb->space_available);
282   rb->head = rb->tail = 0;
283   rb->full = 0;
284   rb->empty = 1;
285 }
286
287 static void rb_add (struct rng_rb *rb, uint32_t v)
288 {
289   rb->buf[rb->tail++] = v;
290   if (rb->tail == rb->size)
291     rb->tail = 0;
292   if (rb->tail == rb->head)
293     rb->full = 1;
294   rb->empty = 0;
295 }
296
297 static uint32_t rb_del (struct rng_rb *rb)
298 {
299   uint32_t v = rb->buf[rb->head++];
300
301   if (rb->head == rb->size)
302     rb->head = 0;
303   if (rb->head == rb->tail)
304     rb->empty = 1;
305   rb->full = 0;
306
307   return v;
308 }
309
310 static uint8_t neug_raw;
311
312 /**
313  * @brief  Random number generation from ADC sampling.
314  * @param  RB: Pointer to ring buffer structure
315  * @return -1 when failure, 0 otherwise.
316  * @note   Called holding the mutex, with RB->full == 0.
317  *         Keep generating until RB->full == 1.
318  */
319 static int rng_gen (struct rng_rb *rb)
320 {
321   uint8_t round = 0;
322   uint32_t v = 0;
323
324   while (1)
325     {
326       uint8_t b;
327
328       chEvtWaitOne (ADC_DATA_AVAILABLE);
329
330       /* Got an ADC sampling data */
331       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
332            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
333            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
334            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
335
336       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
337
338       noise_source_continuous_test (b);
339       if (neug_raw)
340         {
341           v |= (b << (round * 8));
342           round++;
343           if (round >= 4)
344             {
345               rb_add (rb, v);
346               if (rb->full)
347                 return 0;
348               v = 0;
349               round = 0;
350             }
351         }
352       else
353         {
354           /*
355            * Put a random byte to entropy pool.
356            */
357           ep_add (b);
358           round++;
359           if (round >= NUM_NOISE_INPUTS)
360             {
361               /*
362                * We have enough entropy in the pool.
363                * Thus, we pull the random bits from the pool.
364                */
365               int i;
366               const uint32_t *vp = ep_output ();
367
368               /* We get the random bits, add it to the ring buffer.  */
369               for (i = 0; i < SHA256_DIGEST_SIZE / 4; i++)
370                 {
371                   rb_add (rb, *vp);
372                   vp++;
373                   if (rb->full)
374                     return 0;
375                 }
376
377               round = 0;
378             }
379         }
380     }
381
382   return 0;                     /* success */
383 }
384
385 /**
386  * @brief Random number generation thread.
387  */
388 static msg_t rng (void *arg)
389 {
390   struct rng_rb *rb = (struct rng_rb *)arg;
391
392   rng_thread = chThdSelf ();
393
394   adcStart (&ADCD1, NULL);
395   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
396
397   while (!chThdShouldTerminate ())
398     {
399       chMtxLock (&rb->m);
400       while (rb->full)
401         chCondWait (&rb->space_available);
402       rng_gen (rb);
403       chCondSignal (&rb->data_available);
404       chMtxUnlock ();
405     }
406
407   return 0;
408 }
409
410 static struct rng_rb the_ring_buffer;
411 static WORKING_AREA(wa_rng, 256);
412
413 /**
414  * @brief Initialize NeuG.
415  */
416 void
417 neug_init (uint32_t *buf, uint8_t size)
418 {
419   struct rng_rb *rb = &the_ring_buffer;
420
421   neug_raw = 0;
422   ep_init ();
423   rb_init (rb, buf, size);
424   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
425 }
426
427 /**
428  * @breif Flush random bytes.
429  */
430 void
431 neug_flush (void)
432 {
433   struct rng_rb *rb = &the_ring_buffer;
434
435   chMtxLock (&rb->m);
436   while (!rb->empty)
437     (void)rb_del (rb);
438   chCondSignal (&rb->space_available);
439   chMtxUnlock ();
440 }
441
442
443 /**
444  * @brief  Wakes up RNG thread to generate random numbers.
445  */
446 void
447 neug_kick_filling (void)
448 {
449   struct rng_rb *rb = &the_ring_buffer;
450
451   chMtxLock (&rb->m);
452   if (!rb->full)
453     chCondSignal (&rb->space_available);
454   chMtxUnlock ();
455 }
456
457 /**
458  * @brief  Get random word (32-bit) from NeuG.
459  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
460  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
461  *         it is needed to call neug_kick_filling later.
462  */
463 uint32_t
464 neug_get (int kick)
465 {
466   struct rng_rb *rb = &the_ring_buffer;
467   uint32_t v;
468
469   chMtxLock (&rb->m);
470   while (rb->empty)
471     chCondWait (&rb->data_available);
472   v = rb_del (rb);
473   if (kick)
474     chCondSignal (&rb->space_available);
475   chMtxUnlock ();
476
477   return v;
478 }
479
480 void
481 neug_wait_full (void)
482 {
483   struct rng_rb *rb = &the_ring_buffer;
484
485   chMtxLock (&rb->m);
486   while (!rb->full)
487     chCondWait (&rb->data_available);
488   chMtxUnlock ();
489 }
490
491 void
492 neug_fini (void)
493 {
494   if (rng_thread)
495     {
496       chThdTerminate (rng_thread);
497       neug_get (1);
498       chThdWait (rng_thread);
499       rng_thread = NULL;
500     }
501 }
502
503 void
504 neug_select (uint8_t raw)
505 {
506   neug_wait_full ();
507   neug_raw = raw;
508   neug_flush ();
509 }