10e5d49c3a9c415745b2025727559c5aa8012dba
[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=149, 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.44.
119  *
120  */
121 #define NUM_NOISE_INPUTS 149
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 #define REPITITION_COUNT_TEST_CUTOFF 9
178
179 static uint8_t rct_a;
180 static uint8_t rct_b;
181
182 static void repetition_count_test (uint8_t sample)
183 {
184   if (rct_a == sample)
185     {
186       rct_b++;
187       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
188         noise_source_error (REPETITION_COUNT);
189    }
190   else
191     {
192       rct_a = sample;
193       rct_b = 1;
194     }
195 }
196
197 /* Cuttoff = 16, when min-entropy = 4.0, W= 2^-30 */
198 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 16
199
200 static uint8_t ap64t_a;
201 static uint8_t ap64t_b;
202 static uint8_t ap64t_s;
203
204 static void adaptive_proportion_64_test (uint8_t sample)
205 {
206   if (ap64t_s >= 64)
207     {
208       ap64t_a = sample;
209       ap64t_s = 0;
210       ap64t_b = 0;
211     }
212   else
213     {
214       ap64t_s++;
215       if (ap64t_a == sample)
216         {
217           ap64t_b++;
218           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
219             noise_source_error (ADAPTIVE_PROPORTION_64);
220         }
221     }
222 }
223
224 /* Cuttoff = 354, when min-entropy = 4.0, W= 2^-30 */
225 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 354
226
227 static uint8_t ap4096t_a;
228 static uint16_t ap4096t_b;
229 static uint16_t ap4096t_s;
230
231 static void adaptive_proportion_4096_test (uint8_t sample)
232 {
233   if (ap4096t_s >= 4096)
234     {
235       ap4096t_a = sample;
236       ap4096t_s = 0;
237       ap4096t_b = 0;
238     }
239   else
240     {
241       ap4096t_s++;
242       if (ap4096t_a == sample)
243         {
244           ap4096t_b++;
245           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
246             noise_source_error (ADAPTIVE_PROPORTION_4096);
247         }
248     }
249 }
250
251 static void noise_source_continuous_test (uint8_t noise)
252 {
253   repetition_count_test (noise);
254   adaptive_proportion_64_test (noise);
255   adaptive_proportion_4096_test (noise);
256 }
257
258 /*
259  * Ring buffer, filled by generator, consumed by neug_get routine.
260  */
261 struct rng_rb {
262   uint32_t *buf;
263   Mutex m;
264   CondVar data_available;
265   CondVar space_available;
266   uint8_t head, tail;
267   uint8_t size;
268   unsigned int full :1;
269   unsigned int empty :1;
270 };
271
272 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
273 {
274   rb->buf = p;
275   rb->size = size;
276   chMtxInit (&rb->m);
277   chCondInit (&rb->data_available);
278   chCondInit (&rb->space_available);
279   rb->head = rb->tail = 0;
280   rb->full = 0;
281   rb->empty = 1;
282 }
283
284 static void rb_add (struct rng_rb *rb, uint32_t v)
285 {
286   rb->buf[rb->tail++] = v;
287   if (rb->tail == rb->size)
288     rb->tail = 0;
289   if (rb->tail == rb->head)
290     rb->full = 1;
291   rb->empty = 0;
292 }
293
294 static uint32_t rb_del (struct rng_rb *rb)
295 {
296   uint32_t v = rb->buf[rb->head++];
297
298   if (rb->head == rb->size)
299     rb->head = 0;
300   if (rb->head == rb->tail)
301     rb->empty = 1;
302   rb->full = 0;
303
304   return v;
305 }
306
307 /**
308  * @brief  Random number generation from ADC sampling.
309  * @param  RB: Pointer to ring buffer structure
310  * @return -1 when failure, 0 otherwise.
311  * @note   Called holding the mutex, with RB->full == 0.
312  *         Keep generating until RB->full == 1.
313  */
314 static int rng_gen (struct rng_rb *rb)
315 {
316   uint8_t round = 0;
317   uint8_t b;
318
319   while (1)
320     {
321       chEvtWaitOne (ADC_DATA_AVAILABLE);
322
323       /* Got, ADC sampling data */
324       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
325            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
326            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
327            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
328
329       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
330
331       /*
332        * Put a random byte to entropy pool.
333        */
334       ep_add (b);
335       noise_source_continuous_test (b);
336       round++;
337       if (round >= NUM_NOISE_INPUTS)
338         {
339           /*
340            * We have enough entropy in the pool.
341            * Thus, we pull the random bits from the pool.
342            */
343           int i;
344           const uint32_t *vp = ep_output ();
345
346           /* We get the random bits, add it to the ring buffer.  */
347           for (i = 0; i < SHA256_DIGEST_SIZE / 4; i++)
348             {
349               rb_add (rb, *vp);
350               vp++;
351               if (rb->full)
352                 /* fully generated */
353                 return 0;       /* success */
354             }
355         }
356     }
357
358   return 0;                     /* success */
359 }
360
361 /**
362  * @brief Random number generation thread.
363  */
364 static msg_t rng (void *arg)
365 {
366   struct rng_rb *rb = (struct rng_rb *)arg;
367
368   rng_thread = chThdSelf ();
369
370   adcStart (&ADCD1, NULL);
371   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
372
373   while (1)
374     {
375       chMtxLock (&rb->m);
376       while (rb->full)
377         chCondWait (&rb->space_available);
378       rng_gen (rb);
379       chCondSignal (&rb->data_available);
380       chMtxUnlock ();
381     }
382
383   return 0;
384 }
385
386 static struct rng_rb the_ring_buffer;
387 static WORKING_AREA(wa_rng, 256);
388
389 /**
390  * @brief Initialize NeuG.
391  */
392 void
393 neug_init (uint32_t *buf, uint8_t size)
394 {
395   struct rng_rb *rb = &the_ring_buffer;
396
397   ep_init ();
398   rb_init (rb, buf, size);
399   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
400 }
401
402 /**
403  * @breif Flush random bytes.
404  */
405 void
406 neug_flush (void)
407 {
408   struct rng_rb *rb = &the_ring_buffer;
409
410   chMtxLock (&rb->m);
411   while (!rb->empty)
412     (void)rb_del (rb);
413   chCondSignal (&rb->space_available);
414   chMtxUnlock ();
415 }
416
417
418 /**
419  * @brief  Wakes up RNG thread to generate random numbers.
420  */
421 void
422 neug_kick_filling (void)
423 {
424   struct rng_rb *rb = &the_ring_buffer;
425
426   chMtxLock (&rb->m);
427   if (!rb->full)
428     chCondSignal (&rb->space_available);
429   chMtxUnlock ();
430 }
431
432 /**
433  * @brief  Get random word (32-bit) from NeuG.
434  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
435  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
436  *         it is needed to call neug_kick_filling later.
437  */
438 uint32_t
439 neug_get (int kick)
440 {
441   struct rng_rb *rb = &the_ring_buffer;
442   uint32_t v;
443
444   chMtxLock (&rb->m);
445   while (rb->empty)
446     chCondWait (&rb->data_available);
447   v = rb_del (rb);
448   if (kick)
449     chCondSignal (&rb->space_available);
450   chMtxUnlock ();
451
452   return v;
453 }
454
455 void
456 neug_wait_full (void)
457 {
458   struct rng_rb *rb = &the_ring_buffer;
459
460   chMtxLock (&rb->m);
461   while (!rb->full)
462     chCondWait (&rb->data_available);
463   chMtxUnlock ();
464 }