Falcon source files (reference implementation)


frng.c

    1 /*
    2  * Interface to the system RNG.
    3  *
    4  * ==========================(LICENSE BEGIN)============================
    5  *
    6  * Copyright (c) 2017  Falcon Project
    7  *
    8  * Permission is hereby granted, free of charge, to any person obtaining
    9  * a copy of this software and associated documentation files (the
   10  * "Software"), to deal in the Software without restriction, including
   11  * without limitation the rights to use, copy, modify, merge, publish,
   12  * distribute, sublicense, and/or sell copies of the Software, and to
   13  * permit persons to whom the Software is furnished to do so, subject to
   14  * the following conditions:
   15  *
   16  * The above copyright notice and this permission notice shall be
   17  * included in all copies or substantial portions of the Software.
   18  *
   19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
   22  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
   23  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
   24  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
   25  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   26  *
   27  * ===========================(LICENSE END)=============================
   28  *
   29  * @author   Thomas Pornin <thomas.pornin@nccgroup.trust>
   30  */
   31 
   32 #include <assert.h>
   33 
   34 #include "internal.h"
   35 
   36 /*
   37  * PRNG
   38  * ----
   39  *
   40  * The Falcon implementation uses an architecture-specific PRNG for the
   41  * sampling (the PRNG is seeded from a SHAKE-256 instance, itself seeded
   42  * with hardware/OS bytes and/or user-provided seeds). This file contains
   43  * a single, portable PRNG based on ChaCha20. Other PRNG implementations,
   44  * e.g. using SSE2 or AES-NI intrinsics, could provide a speed-up.
   45  *
   46  * (NIST_API_REMOVE_BEGIN)
   47  *
   48  * Seeding
   49  * -------
   50  *
   51  * Two sources of seeding are used:
   52  *
   53  *  - The /dev/urandom file, on Unix-like systems.
   54  *
   55  *  - CryptGenRandom(), on Windows systems (Win32).
   56  *
   57  *
   58  * Configuration
   59  * -------------
   60  *
   61  * Normally everything is auto-detected. To override detection, define
   62  * macros explicitly, with a value of 1 (to enable) or 0 (to disable).
   63  * Available macros are:
   64  *
   65  *  USE_URANDOM      /dev/urandom seeding
   66  *  USE_WIN32_RAND   CryptGenRandom() seeding
   67  *
   68  * (NIST_API_REMOVE_END)
   69  */
   70 
   71 /* NIST_API_REMOVE_BEGIN */
   72 /*
   73  * /dev/urandom is accessible on a variety of Unix-like systems.
   74  */
   75 #ifndef USE_URANDOM
   76 #if defined _AIX \
   77         || defined __ANDROID__ \
   78         || defined __FreeBSD__ \
   79         || defined __NetBSD__ \
   80         || defined __OpenBSD__ \
   81         || defined __DragonFly__ \
   82         || defined __linux__ \
   83         || (defined __sun && (defined __SVR4 || defined __svr4__)) \
   84         || (defined __APPLE__ && defined __MACH__)
   85 #define USE_URANDOM   1
   86 #endif
   87 #endif
   88 
   89 /*
   90  * CryptGenRandom() exists on Windows.
   91  */
   92 #ifndef USE_WIN32_RAND
   93 #if defined _WIN32 || defined _WIN64
   94 #define USE_WIN32_RAND   1
   95 #endif
   96 #endif
   97 
   98 /*
   99  * Accessing /dev/urandom requires using some file descriptors.
  100  */
  101 #if USE_URANDOM
  102 #include <sys/types.h>
  103 #include <unistd.h>
  104 #include <fcntl.h>
  105 #include <errno.h>
  106 #endif
  107 
  108 /*
  109  * CryptGenRandom() is defined in specific headers and requires linking
  110  * with advapi32.lib (to use advapi32.dll).
  111  */
  112 #if USE_WIN32_RAND
  113 #include <windows.h>
  114 #include <wincrypt.h>
  115 #pragma comment(lib, "advapi32")
  116 #endif
  117 
  118 #if USE_URANDOM
  119 static int
  120 urandom_get_seed(void *seed, size_t len)
  121 {
  122         int f;
  123 
  124         if (len == 0) {
  125                 return 1;
  126         }
  127         f = open("/dev/urandom", O_RDONLY);
  128         if (f >= 0) {
  129                 while (len > 0) {
  130                         ssize_t rlen;
  131 
  132                         rlen = read(f, seed, len);
  133                         if (rlen < 0) {
  134                                 if (errno == EINTR) {
  135                                         continue;
  136                                 }
  137                                 break;
  138                         }
  139                         seed = (unsigned char *)seed + rlen;
  140                         len -= (size_t)rlen;
  141                 }
  142                 close(f);
  143                 return len == 0;
  144         } else {
  145                 return 0;
  146         }
  147 }
  148 #endif
  149 
  150 #if USE_WIN32_RAND
  151 static int
  152 win32_get_seed(void *seed, size_t len)
  153 {
  154         HCRYPTPROV hp;
  155 
  156         if (CryptAcquireContext(&hp, 0, 0, PROV_RSA_FULL,
  157                 CRYPT_VERIFYCONTEXT | CRYPT_SILENT))
  158         {
  159                 BOOL r;
  160 
  161                 r = CryptGenRandom(hp, len, seed);
  162                 CryptReleaseContext(hp, 0);
  163                 return r != 0;
  164         }
  165         return 0;
  166 }
  167 #endif
  168 /* NIST_API_REMOVE_END */
  169 
  170 /* see internal.h */
  171 int
  172 falcon_get_seed(void *seed, size_t len)
  173 {
  174         /* (NIST_API_REMOVE_BEGIN) */
  175 #if USE_URANDOM
  176         if (urandom_get_seed(seed, len)) {
  177                 return 1;
  178         }
  179 #endif
  180 #if USE_WIN32_RAND
  181         if (win32_get_seed(seed, len)) {
  182                 return 1;
  183         }
  184 #endif
  185         /* (NIST_API_REMOVE_END) */
  186         return 0;
  187 }
  188 
  189 /*
  190  * PRNG based on ChaCha20.
  191  *
  192  * State consists in key (32 bytes) then IV (16 bytes) and block
  193  * counter (8 bytes). Normally, we should not care about local endianness
  194  * (this is for a PRNG), but for the NIST competition we need reproducible
  195  * KAT vectors that work across architectures, so we enforce little-endian
  196  * interpretation where applicable.
  197  *
  198  * The block counter is XORed into the first 8 bytes of the IV.
  199  */
  200 static void
  201 refill_chacha20(prng *p)
  202 {
  203         static const uint32_t CW[] = {
  204                 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574
  205         };
  206 
  207         uint64_t cc;
  208         size_t u;
  209 
  210         /*
  211          * State uses local endianness. Only the output bytes must be
  212          * converted to little endian (if used on a big-endian machine).
  213          */
  214         cc = *(uint64_t *)(p->state.d + 48);
  215         for (u = 0; u < sizeof p->buf.d; u += 64) {
  216                 uint32_t state[16];
  217                 size_t v;
  218                 int i;
  219 
  220                 memcpy(&state[0], CW, sizeof CW);
  221                 memcpy(&state[4], p->state.d, 48);
  222                 state[14] ^= (uint32_t)cc;
  223                 state[15] ^= (uint32_t)(cc >> 32);
  224                 for (i = 0; i < 10; i ++) {
  225 
  226 #define QROUND(a, b, c, d)   do { \
  227                 state[a] += state[b]; \
  228                 state[d] ^= state[a]; \
  229                 state[d] = (state[d] << 16) | (state[d] >> 16); \
  230                 state[c] += state[d]; \
  231                 state[b] ^= state[c]; \
  232                 state[b] = (state[b] << 12) | (state[b] >> 20); \
  233                 state[a] += state[b]; \
  234                 state[d] ^= state[a]; \
  235                 state[d] = (state[d] <<  8) | (state[d] >> 24); \
  236                 state[c] += state[d]; \
  237                 state[b] ^= state[c]; \
  238                 state[b] = (state[b] <<  7) | (state[b] >> 25); \
  239         } while (0)
  240 
  241                         QROUND( 0,  4,  8, 12);
  242                         QROUND( 1,  5,  9, 13);
  243                         QROUND( 2,  6, 10, 14);
  244                         QROUND( 3,  7, 11, 15);
  245                         QROUND( 0,  5, 10, 15);
  246                         QROUND( 1,  6, 11, 12);
  247                         QROUND( 2,  7,  8, 13);
  248                         QROUND( 3,  4,  9, 14);
  249 
  250 #undef QROUND
  251 
  252                 }
  253 
  254                 for (v = 0; v < 4; v ++) {
  255                         state[v] += CW[v];
  256                 }
  257                 for (v = 4; v < 14; v ++) {
  258                         state[v] += ((uint32_t *)p->state.d)[v - 4];
  259                 }
  260                 state[14] += ((uint32_t *)p->state.d)[10]
  261                         ^ (uint32_t)cc;
  262                 state[15] += ((uint32_t *)p->state.d)[11]
  263                         ^ (uint32_t)(cc >> 32);
  264                 cc ++;
  265 
  266 #if FALCON_LE_U
  267                 memcpy(p->buf.d + u, state, sizeof state);
  268 #else
  269                 for (v = 0; v < 16; v ++) {
  270                         p->buf.d[u + (v << 2) + 0] = state[v];
  271                         p->buf.d[u + (v << 2) + 1] = (state[v] >> 8);
  272                         p->buf.d[u + (v << 2) + 2] = (state[v] >> 16);
  273                         p->buf.d[u + (v << 2) + 3] = (state[v] >> 24);
  274                 }
  275 #endif
  276         }
  277         *(uint64_t *)(p->state.d + 48) = cc;
  278 }
  279 
  280 /* see internal.h */
  281 int
  282 falcon_prng_init(prng *p, shake_context *src, int type)
  283 {
  284         if (type == 0) {
  285                 type = PRNG_CHACHA20;
  286         }
  287         switch (type) {
  288         case PRNG_CHACHA20:
  289 #if FALCON_LE_U
  290                 shake_extract(src, p->state.d, 56);
  291 #else
  292                 {
  293                         /*
  294                          * To ensure reproducibility for a given seed, we
  295                          * must enforce little-endian interpretation of
  296                          * the state words.
  297                          */
  298                         unsigned char tmp[56];
  299                         uint64_t th, tl;
  300                         int i;
  301 
  302                         shake_extract(src, tmp, 56);
  303                         for (i = 0; i < 14; i ++) {
  304                                 uint32_t w;
  305 
  306                                 w = (uint32_t)tmp[(i << 2) + 0]
  307                                         | ((uint32_t)tmp[(i << 2) + 1] << 8)
  308                                         | ((uint32_t)tmp[(i << 2) + 2] << 16)
  309                                         | ((uint32_t)tmp[(i << 2) + 3] << 24);
  310                                 *(uint32_t *)(p->state.d + (i << 2)) = w;
  311                         }
  312                         tl = *(uint32_t *)(p->state.d + 48);
  313                         th = *(uint32_t *)(p->state.d + 52);
  314                         *(uint64_t *)(p->state.d + 48) = tl + (th << 32);
  315                 }
  316 #endif
  317                 break;
  318         default:
  319                 return 0;
  320         }
  321         p->type = type;
  322         falcon_prng_refill(p);
  323         return type;
  324 }
  325 
  326 /* see internal.h */
  327 void
  328 falcon_prng_refill(prng *p)
  329 {
  330         switch (p->type) {
  331         case PRNG_CHACHA20:
  332                 refill_chacha20(p);
  333                 break;
  334         default:
  335                 assert(0);
  336                 break;
  337         }
  338         p->ptr = 0;
  339 }
  340 
  341 /* see internal.h */
  342 void
  343 falcon_prng_get_bytes(prng *p, void *dst, size_t len)
  344 {
  345         unsigned char *buf;
  346 
  347         buf = dst;
  348         while (len > 0) {
  349                 size_t clen;
  350 
  351                 clen = (sizeof p->buf.d) - p->ptr;
  352                 if (clen > len) {
  353                         clen = len;
  354                 }
  355                 memcpy(buf, p->buf.d, clen);
  356                 buf += clen;
  357                 len -= clen;
  358                 p->ptr += clen;
  359                 if (p->ptr == sizeof p->buf.d) {
  360                         falcon_prng_refill(p);
  361                 }
  362         }
  363 }