7fabf85ea807619fe91d608e1d40ae227b8f21f1
[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, 1, 0  /* 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 #if ((SHA256_BLOCK_SIZE - 9) - ((5 + NUM_NOISE_INPUTS) % SHA256_BLOCK_SIZE)) \
144     > SHA256_DIGEST_SIZE
145   int n = SHA256_DIGEST_SIZE;
146 #else
147   int n = (SHA256_BLOCK_SIZE - 9)
148     - ((5 + NUM_NOISE_INPUTS) % SHA256_BLOCK_SIZE);
149 #endif
150
151   if (PROBABILITY_50_BY_TICK ())
152     n = n - 3;
153
154   sha256_update (&sha256_ctx_data, (uint8_t *)sha256_output, n);
155   sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
156   ep_init ();
157   return sha256_output;
158 }
159
160 #define REPETITION_COUNT           1
161 #define ADAPTIVE_PROPORTION_64     2
162 #define ADAPTIVE_PROPORTION_4096   4
163
164 uint32_t neug_err_state;
165
166 static void noise_source_error_reset (void)
167 {
168   neug_err_state = 0;
169 }
170
171 static void noise_source_error (uint32_t err)
172 {
173   neug_err_state |= err;
174 }
175
176
177 /* Cuttoff = 9, when min-entropy = 4.0, W= 2^-30 */
178 /* ceiling of (1+30/4.0) */
179 #define REPITITION_COUNT_TEST_CUTOFF 9
180
181 static uint8_t rct_a;
182 static uint8_t rct_b;
183
184 static void repetition_count_test (uint8_t sample)
185 {
186   if (rct_a == sample)
187     {
188       rct_b++;
189       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
190         noise_source_error (REPETITION_COUNT);
191    }
192   else
193     {
194       rct_a = sample;
195       rct_b = 1;
196     }
197 }
198
199 /* Cuttoff = 20, when min-entropy = 4.0, W= 2^-30 */
200 /* With R, qbinom(1-2^-30,64,2^-4.0) */
201 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 20
202
203 static uint8_t ap64t_a;
204 static uint8_t ap64t_b;
205 static uint8_t ap64t_s;
206
207 static void adaptive_proportion_64_test (uint8_t sample)
208 {
209   if (ap64t_s >= 64)
210     {
211       ap64t_a = sample;
212       ap64t_s = 0;
213       ap64t_b = 0;
214     }
215   else
216     {
217       ap64t_s++;
218       if (ap64t_a == sample)
219         {
220           ap64t_b++;
221           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
222             noise_source_error (ADAPTIVE_PROPORTION_64);
223         }
224     }
225 }
226
227 /* Cuttoff = 354, when min-entropy = 4.0, W= 2^-30 */
228 /* With R, qbinom(1-2^-30,4096,2^-4.0) */
229 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 354
230
231 static uint8_t ap4096t_a;
232 static uint16_t ap4096t_b;
233 static uint16_t ap4096t_s;
234
235 static void adaptive_proportion_4096_test (uint8_t sample)
236 {
237   if (ap4096t_s >= 4096)
238     {
239       ap4096t_a = sample;
240       ap4096t_s = 0;
241       ap4096t_b = 0;
242     }
243   else
244     {
245       ap4096t_s++;
246       if (ap4096t_a == sample)
247         {
248           ap4096t_b++;
249           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
250             noise_source_error (ADAPTIVE_PROPORTION_4096);
251         }
252     }
253 }
254
255 static void noise_source_continuous_test (uint8_t noise)
256 {
257   repetition_count_test (noise);
258   adaptive_proportion_64_test (noise);
259   adaptive_proportion_4096_test (noise);
260 }
261
262 /*
263  * Ring buffer, filled by generator, consumed by neug_get routine.
264  */
265 struct rng_rb {
266   uint32_t *buf;
267   Mutex m;
268   CondVar data_available;
269   CondVar space_available;
270   uint8_t head, tail;
271   uint8_t size;
272   unsigned int full :1;
273   unsigned int empty :1;
274 };
275
276 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
277 {
278   rb->buf = p;
279   rb->size = size;
280   chMtxInit (&rb->m);
281   chCondInit (&rb->data_available);
282   chCondInit (&rb->space_available);
283   rb->head = rb->tail = 0;
284   rb->full = 0;
285   rb->empty = 1;
286 }
287
288 static void rb_add (struct rng_rb *rb, uint32_t v)
289 {
290   rb->buf[rb->tail++] = v;
291   if (rb->tail == rb->size)
292     rb->tail = 0;
293   if (rb->tail == rb->head)
294     rb->full = 1;
295   rb->empty = 0;
296 }
297
298 static uint32_t rb_del (struct rng_rb *rb)
299 {
300   uint32_t v = rb->buf[rb->head++];
301
302   if (rb->head == rb->size)
303     rb->head = 0;
304   if (rb->head == rb->tail)
305     rb->empty = 1;
306   rb->full = 0;
307
308   return v;
309 }
310
311 static uint8_t neug_raw;
312
313 /**
314  * @brief  Random number generation from ADC sampling.
315  * @param  RB: Pointer to ring buffer structure
316  * @return -1 when failure, 0 otherwise.
317  * @note   Called holding the mutex, with RB->full == 0.
318  *         Keep generating until RB->full == 1.
319  */
320 static int rng_gen (struct rng_rb *rb)
321 {
322   uint8_t round = 0;
323   uint32_t v = 0;
324
325   while (1)
326     {
327       uint8_t b;
328
329       chEvtWaitOne (ADC_DATA_AVAILABLE);
330
331       /* Got an ADC sampling data */
332       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
333            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
334            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
335            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
336
337       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
338
339       noise_source_continuous_test (b);
340       if (neug_raw)
341         {
342           v |= (b << (round * 8));
343           round++;
344           if (round >= 4)
345             {
346               rb_add (rb, v);
347               if (rb->full)
348                 return 0;
349               v = 0;
350               round = 0;
351             }
352         }
353       else
354         {
355           /*
356            * Put a random byte to entropy pool.
357            */
358           ep_add (b);
359           round++;
360           if (round >= NUM_NOISE_INPUTS)
361             {
362               /*
363                * We have enough entropy in the pool.
364                * Thus, we pull the random bits from the pool.
365                */
366               int i;
367               const uint32_t *vp = ep_output ();
368
369               /* We get the random bits, add it to the ring buffer.  */
370               for (i = 0; i < SHA256_DIGEST_SIZE / 4; i++)
371                 {
372                   rb_add (rb, *vp);
373                   vp++;
374                   if (rb->full)
375                     return 0;
376                 }
377
378               round = 0;
379             }
380         }
381     }
382
383   return 0;                     /* success */
384 }
385
386 /**
387  * @brief Random number generation thread.
388  */
389 static msg_t rng (void *arg)
390 {
391   struct rng_rb *rb = (struct rng_rb *)arg;
392
393   rng_thread = chThdSelf ();
394
395   adcStart (&ADCD1, NULL);
396   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
397
398   while (!chThdShouldTerminate ())
399     {
400       chMtxLock (&rb->m);
401       while (rb->full)
402         chCondWait (&rb->space_available);
403       while (1)
404         {
405           rng_gen (rb);
406           if (neug_err_state != 0)
407             {
408               while (!rb->empty)
409                 (void)rb_del (rb);
410               noise_source_error_reset ();
411             }
412           else
413             break;
414         }
415       chCondSignal (&rb->data_available);
416       chMtxUnlock ();
417     }
418
419   return 0;
420 }
421
422 static struct rng_rb the_ring_buffer;
423 static WORKING_AREA(wa_rng, 256);
424
425 /**
426  * @brief Initialize NeuG.
427  */
428 void
429 neug_init (uint32_t *buf, uint8_t size)
430 {
431   struct rng_rb *rb = &the_ring_buffer;
432
433   neug_raw = 0;
434   ep_init ();
435   rb_init (rb, buf, size);
436   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
437 }
438
439 /**
440  * @breif Flush random bytes.
441  */
442 void
443 neug_flush (void)
444 {
445   struct rng_rb *rb = &the_ring_buffer;
446
447   chMtxLock (&rb->m);
448   while (!rb->empty)
449     (void)rb_del (rb);
450   chCondSignal (&rb->space_available);
451   chMtxUnlock ();
452 }
453
454
455 /**
456  * @brief  Wakes up RNG thread to generate random numbers.
457  */
458 void
459 neug_kick_filling (void)
460 {
461   struct rng_rb *rb = &the_ring_buffer;
462
463   chMtxLock (&rb->m);
464   if (!rb->full)
465     chCondSignal (&rb->space_available);
466   chMtxUnlock ();
467 }
468
469 /**
470  * @brief  Get random word (32-bit) from NeuG.
471  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
472  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
473  *         it is needed to call neug_kick_filling later.
474  */
475 uint32_t
476 neug_get (int kick)
477 {
478   struct rng_rb *rb = &the_ring_buffer;
479   uint32_t v;
480
481   chMtxLock (&rb->m);
482   while (rb->empty)
483     chCondWait (&rb->data_available);
484   v = rb_del (rb);
485   if (kick)
486     chCondSignal (&rb->space_available);
487   chMtxUnlock ();
488
489   return v;
490 }
491
492 void
493 neug_wait_full (void)
494 {
495   struct rng_rb *rb = &the_ring_buffer;
496
497   chMtxLock (&rb->m);
498   while (!rb->full)
499     chCondWait (&rb->data_available);
500   chMtxUnlock ();
501 }
502
503 void
504 neug_fini (void)
505 {
506   if (rng_thread)
507     {
508       chThdTerminate (rng_thread);
509       neug_get (1);
510       chThdWait (rng_thread);
511       rng_thread = NULL;
512     }
513 }
514
515 void
516 neug_select (uint8_t raw)
517 {
518   neug_wait_full ();
519   neug_raw = raw;
520   neug_flush ();
521 }