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