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 }