src/journal/fsprg.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /*
   4  * fsprg v0.1  -  (seekable) forward-secure pseudorandom generator
   5  * Copyright (C) 2012 B. Poettering
   6  * Contact: fsprg@point-at-infinity.org
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21  * 02110-1301  USA
  22  */
  23
  24 /*
  25  * See "Practical Secure Logging: Seekable Sequential Key Generators"
  26  * by G. A. Marson, B. Poettering for details:
  27  *
  28  * http://eprint.iacr.org/2013/397
  29  */
  30
  31 #include <gcrypt.h>
  32 #include <string.h>
  33
  34 #include "fsprg.h"
  35
  36 #define ISVALID_SECPAR(secpar) (((secpar) % 16 == 0) && ((secpar) >= 16) && ((secpar) <= 16384))
  37 #define VALIDATE_SECPAR(secpar) assert(ISVALID_SECPAR(secpar));
  38
  39 #define RND_HASH GCRY_MD_SHA256
  40 #define RND_GEN_P 0x01
  41 #define RND_GEN_Q 0x02
  42 #define RND_GEN_X 0x03
  43
  44 /******************************************************************************/
  45
  46 static void mpi_export(void *buf, size_t buflen, const gcry_mpi_t x) {
  47         unsigned len;
  48         size_t nwritten;
  49
  50         assert(gcry_mpi_cmp_ui(x, 0) >= 0);
  51         len = (gcry_mpi_get_nbits(x) + 7) / 8;
  52         assert(len <= buflen);
  53         memzero(buf, buflen);
  54         gcry_mpi_print(GCRYMPI_FMT_USG, buf + (buflen - len), len, &nwritten, x);
  55         assert(nwritten == len);
  56 }
  57
  58 static gcry_mpi_t mpi_import(const void *buf, size_t buflen) {
  59         gcry_mpi_t h;
  60         unsigned len;
  61
  62         gcry_mpi_scan(&h, GCRYMPI_FMT_USG, buf, buflen, NULL);
  63         len = (gcry_mpi_get_nbits(h) + 7) / 8;
  64         assert(len <= buflen);
  65         assert(gcry_mpi_cmp_ui(h, 0) >= 0);
  66
  67         return h;
  68 }
  69
  70 static void uint64_export(void *buf, size_t buflen, uint64_t x) {
  71         assert(buflen == 8);
  72         ((uint8_t*) buf)[0] = (x >> 56) & 0xff;
  73         ((uint8_t*) buf)[1] = (x >> 48) & 0xff;
  74         ((uint8_t*) buf)[2] = (x >> 40) & 0xff;
  75         ((uint8_t*) buf)[3] = (x >> 32) & 0xff;
  76         ((uint8_t*) buf)[4] = (x >> 24) & 0xff;
  77         ((uint8_t*) buf)[5] = (x >> 16) & 0xff;
  78         ((uint8_t*) buf)[6] = (x >>  8) & 0xff;
  79         ((uint8_t*) buf)[7] = (x >>  0) & 0xff;
  80 }
  81
  82 _pure_ static uint64_t uint64_import(const void *buf, size_t buflen) {
  83         assert(buflen == 8);
  84         return
  85                 (uint64_t)(((uint8_t*) buf)[0]) << 56 |
  86                 (uint64_t)(((uint8_t*) buf)[1]) << 48 |
  87                 (uint64_t)(((uint8_t*) buf)[2]) << 40 |
  88                 (uint64_t)(((uint8_t*) buf)[3]) << 32 |
  89                 (uint64_t)(((uint8_t*) buf)[4]) << 24 |
  90                 (uint64_t)(((uint8_t*) buf)[5]) << 16 |
  91                 (uint64_t)(((uint8_t*) buf)[6]) <<  8 |
  92                 (uint64_t)(((uint8_t*) buf)[7]) <<  0;
  93 }
  94
  95 /* deterministically generate from seed/idx a string of buflen pseudorandom bytes */
  96 static void det_randomize(void *buf, size_t buflen, const void *seed, size_t seedlen, uint32_t idx) {
  97         gcry_md_hd_t hd, hd2;
  98         size_t olen, cpylen;
  99         uint32_t ctr;
 100
 101         olen = gcry_md_get_algo_dlen(RND_HASH);
 102         gcry_md_open(&hd, RND_HASH, 0);
 103         gcry_md_write(hd, seed, seedlen);
 104         gcry_md_putc(hd, (idx >> 24) & 0xff);
 105         gcry_md_putc(hd, (idx >> 16) & 0xff);
 106         gcry_md_putc(hd, (idx >>  8) & 0xff);
 107         gcry_md_putc(hd, (idx >>  0) & 0xff);
 108
 109         for (ctr = 0; buflen; ctr++) {
 110                 gcry_md_copy(&hd2, hd);
 111                 gcry_md_putc(hd2, (ctr >> 24) & 0xff);
 112                 gcry_md_putc(hd2, (ctr >> 16) & 0xff);
 113                 gcry_md_putc(hd2, (ctr >>  8) & 0xff);
 114                 gcry_md_putc(hd2, (ctr >>  0) & 0xff);
 115                 gcry_md_final(hd2);
 116                 cpylen = (buflen < olen) ? buflen : olen;
 117                 memcpy(buf, gcry_md_read(hd2, RND_HASH), cpylen);
 118                 gcry_md_close(hd2);
 119                 buf += cpylen;
 120                 buflen -= cpylen;
 121         }
 122         gcry_md_close(hd);
 123 }
 124
 125 /* deterministically generate from seed/idx a prime of length `bits' that is 3 (mod 4) */
 126 static gcry_mpi_t genprime3mod4(int bits, const void *seed, size_t seedlen, uint32_t idx) {
 127         size_t buflen = bits / 8;
 128         uint8_t buf[buflen];
 129         gcry_mpi_t p;
 130
 131         assert(bits % 8 == 0);
 132         assert(buflen > 0);
 133
 134         det_randomize(buf, buflen, seed, seedlen, idx);
 135         buf[0] |= 0xc0; /* set upper two bits, so that n=pq has maximum size */
 136         buf[buflen - 1] |= 0x03; /* set lower two bits, to have result 3 (mod 4) */
 137
 138         p = mpi_import(buf, buflen);
 139         while (gcry_prime_check(p, 0))
 140                 gcry_mpi_add_ui(p, p, 4);
 141
 142         return p;
 143 }
 144
 145 /* deterministically generate from seed/idx a quadratic residue (mod n) */
 146 static gcry_mpi_t gensquare(const gcry_mpi_t n, const void *seed, size_t seedlen, uint32_t idx, unsigned secpar) {
 147         size_t buflen = secpar / 8;
 148         uint8_t buf[buflen];
 149         gcry_mpi_t x;
 150
 151         det_randomize(buf, buflen, seed, seedlen, idx);
 152         buf[0] &= 0x7f; /* clear upper bit, so that we have x < n */
 153         x = mpi_import(buf, buflen);
 154         assert(gcry_mpi_cmp(x, n) < 0);
 155         gcry_mpi_mulm(x, x, x, n);
 156         return x;
 157 }
 158
 159 /* compute 2^m (mod phi(p)), for a prime p */
 160 static gcry_mpi_t twopowmodphi(uint64_t m, const gcry_mpi_t p) {
 161         gcry_mpi_t phi, r;
 162         int n;
 163
 164         phi = gcry_mpi_new(0);
 165         gcry_mpi_sub_ui(phi, p, 1);
 166
 167         /* count number of used bits in m */
 168         for (n = 0; (1ULL << n) <= m; n++)
 169                 ;
 170
 171         r = gcry_mpi_new(0);
 172         gcry_mpi_set_ui(r, 1);
 173         while (n) { /* square and multiply algorithm for fast exponentiation */
 174                 n--;
 175                 gcry_mpi_mulm(r, r, r, phi);
 176                 if (m & ((uint64_t)1 << n)) {
 177                         gcry_mpi_add(r, r, r);
 178                         if (gcry_mpi_cmp(r, phi) >= 0)
 179                                 gcry_mpi_sub(r, r, phi);
 180                 }
 181         }
 182
 183         gcry_mpi_release(phi);
 184         return r;
 185 }
 186
 187 /* Decompose $x \in Z_n$ into $(xp,xq) \in Z_p \times Z_q$ using Chinese Remainder Theorem */
 188 static void CRT_decompose(gcry_mpi_t *xp, gcry_mpi_t *xq, const gcry_mpi_t x, const gcry_mpi_t p, const gcry_mpi_t q) {
 189         *xp = gcry_mpi_new(0);
 190         *xq = gcry_mpi_new(0);
 191         gcry_mpi_mod(*xp, x, p);
 192         gcry_mpi_mod(*xq, x, q);
 193 }
 194
 195 /* Compose $(xp,xq) \in Z_p \times Z_q$ into $x \in Z_n$ using Chinese Remainder Theorem */
 196 static void CRT_compose(gcry_mpi_t *x, const gcry_mpi_t xp, const gcry_mpi_t xq, const gcry_mpi_t p, const gcry_mpi_t q) {
 197         gcry_mpi_t a, u;
 198
 199         a = gcry_mpi_new(0);
 200         u = gcry_mpi_new(0);
 201         *x = gcry_mpi_new(0);
 202         gcry_mpi_subm(a, xq, xp, q);
 203         gcry_mpi_invm(u, p, q);
 204         gcry_mpi_mulm(a, a, u, q); /* a = (xq - xp) / p  (mod q) */
 205         gcry_mpi_mul(*x, p, a);
 206         gcry_mpi_add(*x, *x, xp); /* x = p * ((xq - xp) / p mod q) + xp */
 207         gcry_mpi_release(a);
 208         gcry_mpi_release(u);
 209 }
 210
 211 static void initialize_libgcrypt(void) {
 212         const char *p;
 213         if (gcry_control(GCRYCTL_INITIALIZATION_FINISHED_P))
 214                 return;
 215
 216         p = gcry_check_version("1.4.5");
 217         assert(p);
 218
 219         /* Turn off "secmem". Clients which whish to make use of this
 220          * feature should initialize the library manually */
 221         gcry_control(GCRYCTL_DISABLE_SECMEM);
 222         gcry_control(GCRYCTL_INITIALIZATION_FINISHED, 0);
 223 }
 224
 225 /******************************************************************************/
 226
 227 size_t FSPRG_mskinbytes(unsigned _secpar) {
 228         VALIDATE_SECPAR(_secpar);
 229         return 2 + 2 * (_secpar / 2) / 8; /* to store header,p,q */
 230 }
 231
 232 size_t FSPRG_mpkinbytes(unsigned _secpar) {
 233         VALIDATE_SECPAR(_secpar);
 234         return 2 + _secpar / 8; /* to store header,n */
 235 }
 236
 237 size_t FSPRG_stateinbytes(unsigned _secpar) {
 238         VALIDATE_SECPAR(_secpar);
 239         return 2 + 2 * _secpar / 8 + 8; /* to store header,n,x,epoch */
 240 }
 241
 242 static void store_secpar(void *buf, uint16_t secpar) {
 243         secpar = secpar / 16 - 1;
 244         ((uint8_t*) buf)[0] = (secpar >> 8) & 0xff;
 245         ((uint8_t*) buf)[1] = (secpar >> 0) & 0xff;
 246 }
 247
 248 static uint16_t read_secpar(const void *buf) {
 249         uint16_t secpar;
 250         secpar =
 251                 (uint16_t)(((uint8_t*) buf)[0]) << 8 |
 252                 (uint16_t)(((uint8_t*) buf)[1]) << 0;
 253         return 16 * (secpar + 1);
 254 }
 255
 256 void FSPRG_GenMK(void *msk, void *mpk, const void *seed, size_t seedlen, unsigned _secpar) {
 257         uint8_t iseed[FSPRG_RECOMMENDED_SEEDLEN];
 258         gcry_mpi_t n, p, q;
 259         uint16_t secpar;
 260
 261         VALIDATE_SECPAR(_secpar);
 262         secpar = _secpar;
 263
 264         initialize_libgcrypt();
 265
 266         if (!seed) {
 267                 gcry_randomize(iseed, FSPRG_RECOMMENDED_SEEDLEN, GCRY_STRONG_RANDOM);
 268                 seed = iseed;
 269                 seedlen = FSPRG_RECOMMENDED_SEEDLEN;
 270         }
 271
 272         p = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_P);
 273         q = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_Q);
 274
 275         if (msk) {
 276                 store_secpar(msk + 0, secpar);
 277                 mpi_export(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8, p);
 278                 mpi_export(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8, q);
 279         }
 280
 281         if (mpk) {
 282                 n = gcry_mpi_new(0);
 283                 gcry_mpi_mul(n, p, q);
 284                 assert(gcry_mpi_get_nbits(n) == secpar);
 285
 286                 store_secpar(mpk + 0, secpar);
 287                 mpi_export(mpk + 2, secpar / 8, n);
 288
 289                 gcry_mpi_release(n);
 290         }
 291
 292         gcry_mpi_release(p);
 293         gcry_mpi_release(q);
 294 }
 295
 296 void FSPRG_GenState0(void *state, const void *mpk, const void *seed, size_t seedlen) {
 297         gcry_mpi_t n, x;
 298         uint16_t secpar;
 299
 300         initialize_libgcrypt();
 301
 302         secpar = read_secpar(mpk + 0);
 303         n = mpi_import(mpk + 2, secpar / 8);
 304         x = gensquare(n, seed, seedlen, RND_GEN_X, secpar);
 305
 306         memcpy(state, mpk, 2 + secpar / 8);
 307         mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x);
 308         memzero(state + 2 + 2 * secpar / 8, 8);
 309
 310         gcry_mpi_release(n);
 311         gcry_mpi_release(x);
 312 }
 313
 314 void FSPRG_Evolve(void *state) {
 315         gcry_mpi_t n, x;
 316         uint16_t secpar;
 317         uint64_t epoch;
 318
 319         initialize_libgcrypt();
 320
 321         secpar = read_secpar(state + 0);
 322         n = mpi_import(state + 2 + 0 * secpar / 8, secpar / 8);
 323         x = mpi_import(state + 2 + 1 * secpar / 8, secpar / 8);
 324         epoch = uint64_import(state + 2 + 2 * secpar / 8, 8);
 325
 326         gcry_mpi_mulm(x, x, x, n);
 327         epoch++;
 328
 329         mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x);
 330         uint64_export(state + 2 + 2 * secpar / 8, 8, epoch);
 331
 332         gcry_mpi_release(n);
 333         gcry_mpi_release(x);
 334 }
 335
 336 uint64_t FSPRG_GetEpoch(const void *state) {
 337         uint16_t secpar;
 338         secpar = read_secpar(state + 0);
 339         return uint64_import(state + 2 + 2 * secpar / 8, 8);
 340 }
 341
 342 void FSPRG_Seek(void *state, uint64_t epoch, const void *msk, const void *seed, size_t seedlen) {
 343         gcry_mpi_t p, q, n, x, xp, xq, kp, kq, xm;
 344         uint16_t secpar;
 345
 346         initialize_libgcrypt();
 347
 348         secpar = read_secpar(msk + 0);
 349         p  = mpi_import(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8);
 350         q  = mpi_import(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8);
 351
 352         n = gcry_mpi_new(0);
 353         gcry_mpi_mul(n, p, q);
 354
 355         x = gensquare(n, seed, seedlen, RND_GEN_X, secpar);
 356         CRT_decompose(&xp, &xq, x, p, q); /* split (mod n) into (mod p) and (mod q) using CRT */
 357
 358         kp = twopowmodphi(epoch, p); /* compute 2^epoch (mod phi(p)) */
 359         kq = twopowmodphi(epoch, q); /* compute 2^epoch (mod phi(q)) */
 360
 361         gcry_mpi_powm(xp, xp, kp, p); /* compute x^(2^epoch) (mod p) */
 362         gcry_mpi_powm(xq, xq, kq, q); /* compute x^(2^epoch) (mod q) */
 363
 364         CRT_compose(&xm, xp, xq, p, q); /* combine (mod p) and (mod q) to (mod n) using CRT */
 365
 366         store_secpar(state + 0, secpar);
 367         mpi_export(state + 2 + 0 * secpar / 8, secpar / 8, n);
 368         mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, xm);
 369         uint64_export(state + 2 + 2 * secpar / 8, 8, epoch);
 370
 371         gcry_mpi_release(p);
 372         gcry_mpi_release(q);
 373         gcry_mpi_release(n);
 374         gcry_mpi_release(x);
 375         gcry_mpi_release(xp);
 376         gcry_mpi_release(xq);
 377         gcry_mpi_release(kp);
 378         gcry_mpi_release(kq);
 379         gcry_mpi_release(xm);
 380 }
 381
 382 void FSPRG_GetKey(const void *state, void *key, size_t keylen, uint32_t idx) {
 383         uint16_t secpar;
 384
 385         initialize_libgcrypt();
 386
 387         secpar = read_secpar(state + 0);
 388         det_randomize(key, keylen, state + 2, 2 * secpar / 8 + 8, idx);
 389 }