1 /* SPDX-License-Identifier: LGPL-2.1-or-later
3 * fsprg v0.1 - (seekable) forward-secure pseudorandom generator
4 * Copyright © 2012 B. Poettering
5 * Contact: fsprg@point-at-infinity.org
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.
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.
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
24 * See "Practical Secure Logging: Seekable Sequential Key Generators"
25 * by G. A. Marson, B. Poettering for details:
27 * http://eprint.iacr.org/2013/397
33 #include "gcrypt-util.h"
34 #include "memory-util.h"
36 #define ISVALID_SECPAR(secpar) (((secpar) % 16 == 0) && ((secpar) >= 16) && ((secpar) <= 16384))
37 #define VALIDATE_SECPAR(secpar) assert(ISVALID_SECPAR(secpar));
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
44 #pragma GCC diagnostic ignored "-Wpointer-arith"
45 /* TODO: remove void* arithmetic and this work-around */
47 /******************************************************************************/
49 static void mpi_export(void *buf
, size_t buflen
, const gcry_mpi_t x
) {
53 assert(gcry_mpi_cmp_ui(x
, 0) >= 0);
54 len
= (gcry_mpi_get_nbits(x
) + 7) / 8;
55 assert(len
<= buflen
);
57 gcry_mpi_print(GCRYMPI_FMT_USG
, buf
+ (buflen
- len
), len
, &nwritten
, x
);
58 assert(nwritten
== len
);
61 static gcry_mpi_t
mpi_import(const void *buf
, size_t buflen
) {
63 _unused_
unsigned len
;
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);
73 static void uint64_export(void *buf
, size_t buflen
, uint64_t x
) {
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;
85 static uint64_t uint64_import(const void *buf
, size_t buflen
) {
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;
98 /* deterministically generate from seed/idx a string of buflen pseudorandom bytes */
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
;
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);
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);
122 cpylen
= (buflen
< olen
) ? buflen
: olen
;
123 memcpy(buf
, gcry_md_read(hd2
, RND_HASH
), cpylen
);
131 /* deterministically generate from seed/idx a prime of length `bits' that is 3 (mod 4) */
132 static gcry_mpi_t
genprime3mod4(int bits
, const void *seed
, size_t seedlen
, uint32_t idx
) {
133 size_t buflen
= bits
/ 8;
137 assert(bits
% 8 == 0);
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) */
144 p
= mpi_import(buf
, buflen
);
145 while (gcry_prime_check(p
, 0))
146 gcry_mpi_add_ui(p
, p
, 4);
151 /* deterministically generate from seed/idx a quadratic residue (mod n) */
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;
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
);
165 /* compute 2^m (mod phi(p)), for a prime p */
166 static gcry_mpi_t
twopowmodphi(uint64_t m
, const gcry_mpi_t p
) {
170 phi
= gcry_mpi_new(0);
171 gcry_mpi_sub_ui(phi
, p
, 1);
173 /* count number of used bits in m */
174 for (n
= 0; (1ULL << n
) <= m
; n
++)
178 gcry_mpi_set_ui(r
, 1);
179 while (n
) { /* square and multiply algorithm for fast exponentiation */
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
);
189 gcry_mpi_release(phi
);
193 /* Decompose $x \in Z_n$ into $(xp,xq) \in Z_p \times Z_q$ using Chinese Remainder Theorem */
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
);
201 /* Compose $(xp,xq) \in Z_p \times Z_q$ into $x \in Z_n$ using Chinese Remainder Theorem */
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
) {
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 */
217 /******************************************************************************/
219 size_t FSPRG_mskinbytes(unsigned _secpar
) {
220 VALIDATE_SECPAR(_secpar
);
221 return 2 + 2 * (_secpar
/ 2) / 8; /* to store header,p,q */
224 size_t FSPRG_mpkinbytes(unsigned _secpar
) {
225 VALIDATE_SECPAR(_secpar
);
226 return 2 + _secpar
/ 8; /* to store header,n */
229 size_t FSPRG_stateinbytes(unsigned _secpar
) {
230 VALIDATE_SECPAR(_secpar
);
231 return 2 + 2 * _secpar
/ 8 + 8; /* to store header,n,x,epoch */
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;
240 static uint16_t read_secpar(const void *buf
) {
243 (uint16_t)(((uint8_t*) buf
)[0]) << 8 |
244 (uint16_t)(((uint8_t*) buf
)[1]) << 0;
245 return 16 * (secpar
+ 1);
248 void FSPRG_GenMK(void *msk
, void *mpk
, const void *seed
, size_t seedlen
, unsigned _secpar
) {
249 uint8_t iseed
[FSPRG_RECOMMENDED_SEEDLEN
];
253 VALIDATE_SECPAR(_secpar
);
256 initialize_libgcrypt(false);
259 gcry_randomize(iseed
, FSPRG_RECOMMENDED_SEEDLEN
, GCRY_STRONG_RANDOM
);
261 seedlen
= FSPRG_RECOMMENDED_SEEDLEN
;
264 p
= genprime3mod4(secpar
/ 2, seed
, seedlen
, RND_GEN_P
);
265 q
= genprime3mod4(secpar
/ 2, seed
, seedlen
, RND_GEN_Q
);
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
);
275 gcry_mpi_mul(n
, p
, q
);
276 assert(gcry_mpi_get_nbits(n
) == secpar
);
278 store_secpar(mpk
+ 0, secpar
);
279 mpi_export(mpk
+ 2, secpar
/ 8, n
);
288 void FSPRG_GenState0(void *state
, const void *mpk
, const void *seed
, size_t seedlen
) {
292 initialize_libgcrypt(false);
294 secpar
= read_secpar(mpk
+ 0);
295 n
= mpi_import(mpk
+ 2, secpar
/ 8);
296 x
= gensquare(n
, seed
, seedlen
, RND_GEN_X
, secpar
);
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);
306 void FSPRG_Evolve(void *state
) {
311 initialize_libgcrypt(false);
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);
318 gcry_mpi_mulm(x
, x
, x
, n
);
321 mpi_export(state
+ 2 + 1 * secpar
/ 8, secpar
/ 8, x
);
322 uint64_export(state
+ 2 + 2 * secpar
/ 8, 8, epoch
);
328 uint64_t FSPRG_GetEpoch(const void *state
) {
330 secpar
= read_secpar(state
+ 0);
331 return uint64_import(state
+ 2 + 2 * secpar
/ 8, 8);
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
;
338 initialize_libgcrypt(false);
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);
345 gcry_mpi_mul(n
, p
, q
);
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 */
350 kp
= twopowmodphi(epoch
, p
); /* compute 2^epoch (mod phi(p)) */
351 kq
= twopowmodphi(epoch
, q
); /* compute 2^epoch (mod phi(q)) */
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) */
356 CRT_compose(&xm
, xp
, xq
, p
, q
); /* combine (mod p) and (mod q) to (mod n) using CRT */
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
);
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
);
374 void FSPRG_GetKey(const void *state
, void *key
, size_t keylen
, uint32_t idx
) {
377 initialize_libgcrypt(false);
379 secpar
= read_secpar(state
+ 0);
380 det_randomize(key
, keylen
, state
+ 2, 2 * secpar
/ 8 + 8, idx
);