src/random.c

   1 /*
   2  * random.c - random number generation
   3  *
   4  * Copyright (C) 2011, 2012, 2013 Free Software Initiative of Japan
   5  * Author: NIIBE Yutaka <gniibe@fsij.org>
   6  *
   7  * This file is a part of NeuG, a True 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 <stdint.h>
  26 #include <string.h>
  27 #include <chopstx.h>
  28
  29 #include "sys.h"
  30 #include "neug.h"
  31 #include "stm32f103.h"
  32 #include "adc.h"
  33 #include "sha256.h"
  34
  35 chopstx_mutex_t adc_mtx;
  36 chopstx_cond_t adc_cond;
  37 int adc_waiting;
  38 int adc_data_available;
  39
  40 static uint32_t adc_buf[SHA256_BLOCK_SIZE/sizeof (uint32_t)];
  41
  42 static sha256_context sha256_ctx_data;
  43 static uint32_t sha256_output[SHA256_DIGEST_SIZE/sizeof (uint32_t)];
  44
  45 /*
  46  * To be a full entropy source, the requirement is to have N samples
  47  * for output of 256-bit, where:
  48  *
  49  *      N = (256 * 2) / <min-entropy of a sample>
  50  *
  51  * For example, N should be more than 103 for min-entropy = 5.0.
  52  *
  53  * On the other hand, in the section 6.2 "Full Entropy Source
  54  * Requirements", it says:
  55  *
  56  *     At least twice the block size of the underlying cryptographic
  57  *     primitive shall be provided as input to the conditioning
  58  *     function to produce full entropy output.
  59  *
  60  * For us, cryptographic primitive is SHA-256 and its blocksize is
  61  * 512-bit (64-byte), thus, N >= 128.
  62  *
  63  * We chose N=140.  Note that we have "additional bits" of 16-byte for
  64  * last block (feedback from previous output of SHA-256) to feed
  65  * hash_df function of SHA-256, together with sample data of 140-byte.
  66  *
  67  * N=140 corresponds to min-entropy >= 3.68.
  68  *
  69  */
  70 #define NUM_NOISE_INPUTS 140
  71
  72 #define EP_ROUND_0 0 /* initial-five-byte and 3-byte, then 56-byte-input */
  73 #define EP_ROUND_1 1 /* 64-byte-input */
  74 #define EP_ROUND_2 2 /* 17-byte-input */
  75 #define EP_ROUND_RAW      3 /* 32-byte-input */
  76 #define EP_ROUND_RAW_DATA 4 /* 32-byte-input */
  77
  78 #define EP_ROUND_0_INPUTS 56
  79 #define EP_ROUND_1_INPUTS 64
  80 #define EP_ROUND_2_INPUTS 17
  81 #define EP_ROUND_RAW_INPUTS 32
  82 #define EP_ROUND_RAW_DATA_INPUTS 32
  83
  84 static uint8_t ep_round;
  85
  86 /*
  87  * Hash_df initial string:
  88  *
  89  *  1,          : counter = 1
  90  *  0, 0, 1, 0  : no_of_bits_returned (in big endian)
  91  */
  92 static void ep_fill_initial_string (void)
  93 {
  94   adc_buf[0] = 0x01000001; /* Regardless of endian */
  95   adc_buf[1] = (CRC->DR & 0xffffff00);
  96 }
  97
  98 static void ep_init (int mode)
  99 {
 100   adc_data_available = 0;
 101
 102   if (mode == NEUG_MODE_RAW)
 103     {
 104       ep_round = EP_ROUND_RAW;
 105       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_RAW_INPUTS);
 106     }
 107   else if (mode == NEUG_MODE_RAW_DATA)
 108     {
 109       ep_round = EP_ROUND_RAW_DATA;
 110       adc_start_conversion (ADC_SAMPLE_MODE, adc_buf, EP_ROUND_RAW_DATA_INPUTS);
 111     }
 112   else
 113     {
 114       ep_round = EP_ROUND_0;
 115       ep_fill_initial_string ();
 116       adc_start_conversion (ADC_CRC32_MODE,
 117                             &adc_buf[2], EP_ROUND_0_INPUTS);
 118     }
 119 }
 120
 121 static void noise_source_continuous_test (uint8_t noise);
 122
 123 static void ep_fill_wbuf (int i, int flip, int test)
 124 {
 125   uint32_t v = adc_buf[i];
 126
 127   if (test)
 128     {
 129       uint8_t b0, b1, b2, b3;
 130
 131       b3 = v >> 24;
 132       b2 = v >> 16;
 133       b1 = v >> 8;
 134       b0 = v;
 135
 136       noise_source_continuous_test (b0);
 137       noise_source_continuous_test (b1);
 138       noise_source_continuous_test (b2);
 139       noise_source_continuous_test (b3);
 140     }
 141
 142   if (flip)
 143     v = __builtin_bswap32 (v);
 144
 145   sha256_ctx_data.wbuf[i] = v;
 146 }
 147
 148 /* Here assumes little endian architecture.  */
 149 static int ep_process (int mode)
 150 {
 151   int i, n;
 152
 153   if (ep_round == EP_ROUND_RAW)
 154     {
 155       for (i = 0; i < EP_ROUND_RAW_INPUTS / 4; i++)
 156         ep_fill_wbuf (i, 0, 1);
 157
 158       ep_init (mode);
 159       return EP_ROUND_RAW_INPUTS / 4;
 160     }
 161   else if (ep_round == EP_ROUND_RAW_DATA)
 162     {
 163       for (i = 0; i < EP_ROUND_RAW_DATA_INPUTS / 4; i++)
 164         ep_fill_wbuf (i, 0, 0);
 165
 166       ep_init (mode);
 167       return EP_ROUND_RAW_DATA_INPUTS / 4;
 168     }
 169
 170   if (ep_round == EP_ROUND_0)
 171     {
 172       for (i = 0; i < 64 / 4; i++)
 173         ep_fill_wbuf (i, 1, 1);
 174
 175       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_1_INPUTS);
 176       sha256_start (&sha256_ctx_data);
 177       sha256_process (&sha256_ctx_data);
 178       ep_round++;
 179       return 0;
 180     }
 181   else if (ep_round == EP_ROUND_1)
 182     {
 183       for (i = 0; i < 64 / 4; i++)
 184         ep_fill_wbuf (i, 1, 1);
 185
 186       adc_start_conversion (ADC_CRC32_MODE, adc_buf, EP_ROUND_2_INPUTS);
 187       sha256_process (&sha256_ctx_data);
 188       ep_round++;
 189       return 0;
 190     }
 191   else
 192     {
 193       for (i = 0; i < (EP_ROUND_2_INPUTS + 3) / 4; i++)
 194         ep_fill_wbuf (i, 0, 1);
 195
 196       n = SHA256_DIGEST_SIZE / 2;
 197       ep_init (NEUG_MODE_CONDITIONED); /* The three-byte is used here.  */
 198       memcpy (((uint8_t *)sha256_ctx_data.wbuf)
 199               + ((NUM_NOISE_INPUTS+5)%SHA256_BLOCK_SIZE),
 200               sha256_output, n); /* Don't use the last three-byte.  */
 201       sha256_ctx_data.total[0] = 5 + NUM_NOISE_INPUTS + n;
 202       sha256_finish (&sha256_ctx_data, (uint8_t *)sha256_output);
 203       return SHA256_DIGEST_SIZE / sizeof (uint32_t);
 204     }
 205 }
 206
 207
 208 static const uint32_t *ep_output (int mode)
 209 {
 210   if (mode)
 211     return sha256_ctx_data.wbuf;
 212   else
 213     return sha256_output;
 214 }
 215 \f
 216 #define REPETITION_COUNT           1
 217 #define ADAPTIVE_PROPORTION_64     2
 218 #define ADAPTIVE_PROPORTION_4096   4
 219
 220 uint8_t neug_err_state;
 221 uint16_t neug_err_cnt;
 222 uint16_t neug_err_cnt_rc;
 223 uint16_t neug_err_cnt_p64;
 224 uint16_t neug_err_cnt_p4k;
 225
 226 uint16_t neug_rc_max;
 227 uint16_t neug_p64_max;
 228 uint16_t neug_p4k_max;
 229
 230 #include "board.h"
 231
 232 static void noise_source_cnt_max_reset (void)
 233 {
 234   neug_err_cnt = neug_err_cnt_rc = neug_err_cnt_p64 = neug_err_cnt_p4k = 0;
 235   neug_rc_max = neug_p64_max = neug_p4k_max = 0;
 236 }
 237
 238 static void noise_source_error_reset (void)
 239 {
 240   neug_err_state = 0;
 241 }
 242
 243 static void noise_source_error (uint32_t err)
 244 {
 245   neug_err_state |= err;
 246   neug_err_cnt++;
 247
 248   if ((err & REPETITION_COUNT))
 249     neug_err_cnt_rc++;
 250   if ((err & ADAPTIVE_PROPORTION_64))
 251     neug_err_cnt_p64++;
 252   if ((err & ADAPTIVE_PROPORTION_4096))
 253     neug_err_cnt_p4k++;
 254 }
 255
 256 /*
 257  * For health tests, we assume that the device noise source has
 258  * min-entropy >= 4.2.  Observing raw data stream (before CRC-32) has
 259  * more than 4.2 bit/byte entropy.  When the data stream after CRC-32
 260  * filter will be less than 4.2 bit/byte entropy, that must be
 261  * something wrong.  Note that even we observe < 4.2, we still have
 262  * some margin, since we use NUM_NOISE_INPUTS=140.
 263  *
 264  */
 265
 266 /* Cuttoff = 9, when min-entropy = 4.2, W= 2^-30 */
 267 /* ceiling of (1+30/4.2) */
 268 #define REPITITION_COUNT_TEST_CUTOFF 9
 269
 270 static uint8_t rct_a;
 271 static uint8_t rct_b;
 272
 273 static void repetition_count_test (uint8_t sample)
 274 {
 275   if (rct_a == sample)
 276     {
 277       rct_b++;
 278       if (rct_b >= REPITITION_COUNT_TEST_CUTOFF)
 279         noise_source_error (REPETITION_COUNT);
 280       if (rct_b > neug_rc_max)
 281         neug_rc_max = rct_b;
 282    }
 283   else
 284     {
 285       rct_a = sample;
 286       rct_b = 1;
 287     }
 288 }
 289
 290 /* Cuttoff = 18, when min-entropy = 4.2, W= 2^-30 */
 291 /* With R, qbinom(1-2^-30,64,2^-4.2) */
 292 #define ADAPTIVE_PROPORTION_64_TEST_CUTOFF 18
 293
 294 static uint8_t ap64t_a;
 295 static uint8_t ap64t_b;
 296 static uint8_t ap64t_s;
 297
 298 static void adaptive_proportion_64_test (uint8_t sample)
 299 {
 300   if (ap64t_s >= 64)
 301     {
 302       ap64t_a = sample;
 303       ap64t_s = 0;
 304       ap64t_b = 0;
 305     }
 306   else
 307     {
 308       ap64t_s++;
 309       if (ap64t_a == sample)
 310         {
 311           ap64t_b++;
 312           if (ap64t_b > ADAPTIVE_PROPORTION_64_TEST_CUTOFF)
 313             noise_source_error (ADAPTIVE_PROPORTION_64);
 314           if (ap64t_b > neug_p64_max)
 315             neug_p64_max = ap64t_b;
 316         }
 317     }
 318 }
 319
 320 /* Cuttoff = 315, when min-entropy = 4.2, W= 2^-30 */
 321 /* With R, qbinom(1-2^-30,4096,2^-4.2) */
 322 #define ADAPTIVE_PROPORTION_4096_TEST_CUTOFF 315
 323
 324 static uint8_t ap4096t_a;
 325 static uint16_t ap4096t_b;
 326 static uint16_t ap4096t_s;
 327
 328 static void adaptive_proportion_4096_test (uint8_t sample)
 329 {
 330   if (ap4096t_s >= 4096)
 331     {
 332       ap4096t_a = sample;
 333       ap4096t_s = 0;
 334       ap4096t_b = 0;
 335     }
 336   else
 337     {
 338       ap4096t_s++;
 339       if (ap4096t_a == sample)
 340         {
 341           ap4096t_b++;
 342           if (ap4096t_b > ADAPTIVE_PROPORTION_4096_TEST_CUTOFF)
 343             noise_source_error (ADAPTIVE_PROPORTION_4096);
 344           if (ap4096t_b > neug_p4k_max)
 345             neug_p4k_max = ap4096t_b;
 346         }
 347     }
 348 }
 349
 350 static void noise_source_continuous_test (uint8_t noise)
 351 {
 352   repetition_count_test (noise);
 353   adaptive_proportion_64_test (noise);
 354   adaptive_proportion_4096_test (noise);
 355 }
 356 \f
 357 /*
 358  * Ring buffer, filled by generator, consumed by neug_get routine.
 359  */
 360 struct rng_rb {
 361   uint32_t *buf;
 362   chopstx_mutex_t m;
 363   chopstx_cond_t data_available;
 364   chopstx_cond_t space_available;
 365   uint8_t head, tail;
 366   uint8_t size;
 367   unsigned int full :1;
 368   unsigned int empty :1;
 369 };
 370
 371 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
 372 {
 373   rb->buf = p;
 374   rb->size = size;
 375   chopstx_mutex_init (&rb->m);
 376   chopstx_cond_init (&rb->data_available);
 377   chopstx_cond_init (&rb->space_available);
 378   rb->head = rb->tail = 0;
 379   rb->full = 0;
 380   rb->empty = 1;
 381 }
 382
 383 static void rb_add (struct rng_rb *rb, uint32_t v)
 384 {
 385   rb->buf[rb->tail++] = v;
 386   if (rb->tail == rb->size)
 387     rb->tail = 0;
 388   if (rb->tail == rb->head)
 389     rb->full = 1;
 390   rb->empty = 0;
 391 }
 392
 393 static uint32_t rb_del (struct rng_rb *rb)
 394 {
 395   uint32_t v = rb->buf[rb->head++];
 396
 397   if (rb->head == rb->size)
 398     rb->head = 0;
 399   if (rb->head == rb->tail)
 400     rb->empty = 1;
 401   rb->full = 0;
 402
 403   return v;
 404 }
 405
 406 uint8_t neug_mode;
 407 static int rng_should_terminate;
 408 static chopstx_t rng_thread;
 409
 410
 411 /**
 412  * @brief Random number generation thread.
 413  */
 414 static void *
 415 rng (void *arg)
 416 {
 417   struct rng_rb *rb = (struct rng_rb *)arg;
 418
 419   rng_should_terminate = 0;
 420   chopstx_mutex_init (&adc_mtx);
 421   chopstx_cond_init (&adc_cond);
 422
 423   /* Enable ADCs */
 424   adc_start ();
 425
 426   ep_init (NEUG_MODE_CONDITIONED);
 427
 428   while (!rng_should_terminate)
 429     {
 430       int n;
 431       int mode = neug_mode;
 432
 433       chopstx_mutex_lock (&adc_mtx);
 434       if (!adc_data_available)
 435         {
 436           adc_waiting = 1;
 437           chopstx_cond_wait (&adc_cond, &adc_mtx);
 438           adc_waiting = 0;
 439         }
 440       adc_data_available = 0;
 441       chopstx_mutex_unlock (&adc_mtx);
 442
 443       if ((n = ep_process (mode)))
 444         {
 445           int i;
 446           const uint32_t *vp;
 447
 448           if (neug_err_state != 0
 449               && (mode == NEUG_MODE_CONDITIONED || mode == NEUG_MODE_RAW))
 450             {
 451               /* Don't use the result and do it again.  */
 452               noise_source_error_reset ();
 453               continue;
 454             }
 455
 456           vp = ep_output (mode);
 457
 458           chopstx_mutex_lock (&rb->m);
 459           while (rb->full)
 460             chopstx_cond_wait (&rb->space_available, &rb->m);
 461
 462           for (i = 0; i < n; i++)
 463             {
 464               rb_add (rb, *vp++);
 465               if (rb->full)
 466                 break;
 467             }
 468
 469           chopstx_cond_signal (&rb->data_available);
 470           chopstx_mutex_unlock (&rb->m);
 471         }
 472     }
 473
 474   adc_stop ();
 475
 476   return NULL;
 477 }
 478
 479 static struct rng_rb the_ring_buffer;
 480
 481 extern uint8_t __process2_stack_base__, __process2_stack_size__;
 482 const uint32_t __stackaddr_rng = (uint32_t)&__process2_stack_base__;
 483 const size_t __stacksize_rng = (size_t)&__process2_stack_size__;
 484 #define PRIO_RNG 2
 485
 486 /**
 487  * @brief Initialize NeuG.
 488  */
 489 void
 490 neug_init (uint32_t *buf, uint8_t size)
 491 {
 492   const uint32_t *u = (const uint32_t *)unique_device_id ();
 493   struct rng_rb *rb = &the_ring_buffer;
 494   int i;
 495
 496   RCC->AHBENR |= RCC_AHBENR_CRCEN;
 497   CRC->CR = CRC_CR_RESET;
 498
 499   /*
 500    * This initialization ensures that it generates different sequence
 501    * even if all physical conditions are same.
 502    */
 503   for (i = 0; i < 3; i++)
 504     CRC->DR = *u++;
 505
 506   neug_mode = NEUG_MODE_CONDITIONED;
 507   rb_init (rb, buf, size);
 508
 509   rng_thread = chopstx_create (PRIO_RNG, __stackaddr_rng, __stacksize_rng,
 510                                rng, rb);
 511 }
 512
 513 /**
 514  * @breif Flush random bytes.
 515  */
 516 void
 517 neug_flush (void)
 518 {
 519   struct rng_rb *rb = &the_ring_buffer;
 520
 521   chopstx_mutex_lock (&rb->m);
 522   while (!rb->empty)
 523     (void)rb_del (rb);
 524   chopstx_cond_signal (&rb->space_available);
 525   chopstx_mutex_unlock (&rb->m);
 526 }
 527
 528
 529 /**
 530  * @brief  Wakes up RNG thread to generate random numbers.
 531  */
 532 void
 533 neug_kick_filling (void)
 534 {
 535   struct rng_rb *rb = &the_ring_buffer;
 536
 537   chopstx_mutex_lock (&rb->m);
 538   if (!rb->full)
 539     chopstx_cond_signal (&rb->space_available);
 540   chopstx_mutex_unlock (&rb->m);
 541 }
 542
 543 /**
 544  * @brief  Get random word (32-bit) from NeuG.
 545  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
 546  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
 547  *         it is needed to call neug_kick_filling later.
 548  */
 549 uint32_t
 550 neug_get (int kick)
 551 {
 552   struct rng_rb *rb = &the_ring_buffer;
 553   uint32_t v;
 554
 555   chopstx_mutex_lock (&rb->m);
 556   while (rb->empty)
 557     chopstx_cond_wait (&rb->data_available, &rb->m);
 558   v = rb_del (rb);
 559   if (kick)
 560     chopstx_cond_signal (&rb->space_available);
 561   chopstx_mutex_unlock (&rb->m);
 562
 563   return v;
 564 }
 565
 566 int
 567 neug_get_nonblock (uint32_t *p)
 568 {
 569   struct rng_rb *rb = &the_ring_buffer;
 570   int r = 0;
 571
 572   chopstx_mutex_lock (&rb->m);
 573   if (rb->empty)
 574     {
 575       r = -1;
 576       chopstx_cond_signal (&rb->space_available);
 577     }
 578   else
 579     *p = rb_del (rb);
 580   chopstx_mutex_unlock (&rb->m);
 581
 582   return r;
 583 }
 584
 585 int neug_consume_random (void (*proc) (uint32_t, int))
 586 {
 587   int i = 0;
 588   struct rng_rb *rb = &the_ring_buffer;
 589
 590   chopstx_mutex_lock (&rb->m);
 591   while (!rb->empty)
 592     {
 593       uint32_t v;
 594
 595       v = rb_del (rb);
 596       proc (v, i);
 597       i++;
 598     }
 599   chopstx_cond_signal (&rb->space_available);
 600   chopstx_mutex_unlock (&rb->m);
 601
 602   return i;
 603 }
 604
 605 void
 606 neug_wait_full (void)
 607 {
 608   struct rng_rb *rb = &the_ring_buffer;
 609
 610   chopstx_mutex_lock (&rb->m);
 611   while (!rb->full)
 612     chopstx_cond_wait (&rb->data_available, &rb->m);
 613   chopstx_mutex_unlock (&rb->m);
 614 }
 615
 616 void
 617 neug_fini (void)
 618 {
 619   rng_should_terminate = 1;
 620   neug_get (1);
 621   chopstx_join (rng_thread, NULL);
 622 }
 623
 624 void
 625 neug_mode_select (uint8_t mode)
 626 {
 627   if (neug_mode == mode)
 628     return;
 629
 630   neug_wait_full ();
 631
 632   chopstx_mutex_lock (&adc_mtx);
 633   while (adc_waiting == 0)
 634     {
 635       chopstx_mutex_unlock (&adc_mtx);
 636       chopstx_usec_wait (1000);
 637       chopstx_mutex_lock (&adc_mtx);
 638     }
 639   chopstx_mutex_unlock (&adc_mtx);
 640
 641   ep_init (mode);
 642   noise_source_cnt_max_reset ();
 643   neug_mode = mode;
 644   neug_flush ();
 645 }