]>
Commit | Line | Data |
---|---|---|
d9215cd8 ZJS |
1 | /* SPDX-License-Identifier: LGPL-2.1+ |
2 | * | |
7560fffc | 3 | * fsprg v0.1 - (seekable) forward-secure pseudorandom generator |
810adae9 | 4 | * Copyright © 2012 B. Poettering |
7560fffc LP |
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 | |
fe004b7c LP |
21 | */ |
22 | ||
23 | /* | |
24 | * See "Practical Secure Logging: Seekable Sequential Key Generators" | |
25 | * by G. A. Marson, B. Poettering for details: | |
7560fffc | 26 | * |
fe004b7c | 27 | * http://eprint.iacr.org/2013/397 |
7560fffc LP |
28 | */ |
29 | ||
7560fffc | 30 | #include <string.h> |
7560fffc LP |
31 | |
32 | #include "fsprg.h" | |
91e023d8 | 33 | #include "gcrypt-util.h" |
0a970718 | 34 | #include "memory-util.h" |
7560fffc LP |
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 | ||
521e7c3a ZJS |
44 | #pragma GCC diagnostic ignored "-Wpointer-arith" |
45 | /* TODO: remove void* arithmetic and this work-around */ | |
46 | ||
7560fffc LP |
47 | /******************************************************************************/ |
48 | ||
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); | |
29804cc1 | 56 | memzero(buf, buflen); |
7560fffc LP |
57 | gcry_mpi_print(GCRYMPI_FMT_USG, buf + (buflen - len), len, &nwritten, x); |
58 | assert(nwritten == len); | |
59 | } | |
60 | ||
61 | static gcry_mpi_t mpi_import(const void *buf, size_t buflen) { | |
62 | gcry_mpi_t h; | |
0a0e594a | 63 | _unused_ unsigned len; |
7560fffc | 64 | |
ddea4462 | 65 | assert_se(gcry_mpi_scan(&h, GCRYMPI_FMT_USG, buf, buflen, NULL) == 0); |
7560fffc LP |
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 | ||
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 | ||
44a6b1b6 | 85 | _pure_ static uint64_t uint64_import(const void *buf, size_t buflen) { |
7560fffc LP |
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 */ | |
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 | uint32_t ctr; | |
103 | ||
104 | olen = gcry_md_get_algo_dlen(RND_HASH); | |
105 | gcry_md_open(&hd, RND_HASH, 0); | |
106 | gcry_md_write(hd, seed, seedlen); | |
107 | gcry_md_putc(hd, (idx >> 24) & 0xff); | |
108 | gcry_md_putc(hd, (idx >> 16) & 0xff); | |
109 | gcry_md_putc(hd, (idx >> 8) & 0xff); | |
110 | gcry_md_putc(hd, (idx >> 0) & 0xff); | |
111 | ||
112 | for (ctr = 0; buflen; ctr++) { | |
113 | gcry_md_copy(&hd2, hd); | |
114 | gcry_md_putc(hd2, (ctr >> 24) & 0xff); | |
115 | gcry_md_putc(hd2, (ctr >> 16) & 0xff); | |
116 | gcry_md_putc(hd2, (ctr >> 8) & 0xff); | |
117 | gcry_md_putc(hd2, (ctr >> 0) & 0xff); | |
118 | gcry_md_final(hd2); | |
119 | cpylen = (buflen < olen) ? buflen : olen; | |
120 | memcpy(buf, gcry_md_read(hd2, RND_HASH), cpylen); | |
121 | gcry_md_close(hd2); | |
122 | buf += cpylen; | |
123 | buflen -= cpylen; | |
124 | } | |
125 | gcry_md_close(hd); | |
126 | } | |
127 | ||
128 | /* deterministically generate from seed/idx a prime of length `bits' that is 3 (mod 4) */ | |
129 | static gcry_mpi_t genprime3mod4(int bits, const void *seed, size_t seedlen, uint32_t idx) { | |
130 | size_t buflen = bits / 8; | |
131 | uint8_t buf[buflen]; | |
132 | gcry_mpi_t p; | |
133 | ||
134 | assert(bits % 8 == 0); | |
135 | assert(buflen > 0); | |
136 | ||
137 | det_randomize(buf, buflen, seed, seedlen, idx); | |
138 | buf[0] |= 0xc0; /* set upper two bits, so that n=pq has maximum size */ | |
139 | buf[buflen - 1] |= 0x03; /* set lower two bits, to have result 3 (mod 4) */ | |
140 | ||
141 | p = mpi_import(buf, buflen); | |
142 | while (gcry_prime_check(p, 0)) | |
143 | gcry_mpi_add_ui(p, p, 4); | |
144 | ||
145 | return p; | |
146 | } | |
147 | ||
148 | /* deterministically generate from seed/idx a quadratic residue (mod n) */ | |
149 | static gcry_mpi_t gensquare(const gcry_mpi_t n, const void *seed, size_t seedlen, uint32_t idx, unsigned secpar) { | |
150 | size_t buflen = secpar / 8; | |
151 | uint8_t buf[buflen]; | |
152 | gcry_mpi_t x; | |
153 | ||
154 | det_randomize(buf, buflen, seed, seedlen, idx); | |
155 | buf[0] &= 0x7f; /* clear upper bit, so that we have x < n */ | |
156 | x = mpi_import(buf, buflen); | |
157 | assert(gcry_mpi_cmp(x, n) < 0); | |
158 | gcry_mpi_mulm(x, x, x, n); | |
159 | return x; | |
160 | } | |
161 | ||
162 | /* compute 2^m (mod phi(p)), for a prime p */ | |
163 | static gcry_mpi_t twopowmodphi(uint64_t m, const gcry_mpi_t p) { | |
164 | gcry_mpi_t phi, r; | |
165 | int n; | |
166 | ||
167 | phi = gcry_mpi_new(0); | |
168 | gcry_mpi_sub_ui(phi, p, 1); | |
169 | ||
170 | /* count number of used bits in m */ | |
fc89a139 | 171 | for (n = 0; (1ULL << n) <= m; n++) |
7560fffc LP |
172 | ; |
173 | ||
174 | r = gcry_mpi_new(0); | |
175 | gcry_mpi_set_ui(r, 1); | |
176 | while (n) { /* square and multiply algorithm for fast exponentiation */ | |
177 | n--; | |
178 | gcry_mpi_mulm(r, r, r, phi); | |
179 | if (m & ((uint64_t)1 << n)) { | |
180 | gcry_mpi_add(r, r, r); | |
181 | if (gcry_mpi_cmp(r, phi) >= 0) | |
182 | gcry_mpi_sub(r, r, phi); | |
183 | } | |
184 | } | |
185 | ||
186 | gcry_mpi_release(phi); | |
187 | return r; | |
188 | } | |
189 | ||
190 | /* Decompose $x \in Z_n$ into $(xp,xq) \in Z_p \times Z_q$ using Chinese Remainder Theorem */ | |
191 | 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) { | |
192 | *xp = gcry_mpi_new(0); | |
193 | *xq = gcry_mpi_new(0); | |
194 | gcry_mpi_mod(*xp, x, p); | |
195 | gcry_mpi_mod(*xq, x, q); | |
196 | } | |
197 | ||
198 | /* Compose $(xp,xq) \in Z_p \times Z_q$ into $x \in Z_n$ using Chinese Remainder Theorem */ | |
199 | 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) { | |
200 | gcry_mpi_t a, u; | |
201 | ||
202 | a = gcry_mpi_new(0); | |
203 | u = gcry_mpi_new(0); | |
204 | *x = gcry_mpi_new(0); | |
205 | gcry_mpi_subm(a, xq, xp, q); | |
206 | gcry_mpi_invm(u, p, q); | |
207 | gcry_mpi_mulm(a, a, u, q); /* a = (xq - xp) / p (mod q) */ | |
208 | gcry_mpi_mul(*x, p, a); | |
209 | gcry_mpi_add(*x, *x, xp); /* x = p * ((xq - xp) / p mod q) + xp */ | |
210 | gcry_mpi_release(a); | |
211 | gcry_mpi_release(u); | |
212 | } | |
213 | ||
7560fffc LP |
214 | /******************************************************************************/ |
215 | ||
216 | size_t FSPRG_mskinbytes(unsigned _secpar) { | |
217 | VALIDATE_SECPAR(_secpar); | |
218 | return 2 + 2 * (_secpar / 2) / 8; /* to store header,p,q */ | |
219 | } | |
220 | ||
221 | size_t FSPRG_mpkinbytes(unsigned _secpar) { | |
222 | VALIDATE_SECPAR(_secpar); | |
223 | return 2 + _secpar / 8; /* to store header,n */ | |
224 | } | |
225 | ||
226 | size_t FSPRG_stateinbytes(unsigned _secpar) { | |
227 | VALIDATE_SECPAR(_secpar); | |
228 | return 2 + 2 * _secpar / 8 + 8; /* to store header,n,x,epoch */ | |
229 | } | |
230 | ||
231 | static void store_secpar(void *buf, uint16_t secpar) { | |
232 | secpar = secpar / 16 - 1; | |
233 | ((uint8_t*) buf)[0] = (secpar >> 8) & 0xff; | |
234 | ((uint8_t*) buf)[1] = (secpar >> 0) & 0xff; | |
235 | } | |
236 | ||
237 | static uint16_t read_secpar(const void *buf) { | |
238 | uint16_t secpar; | |
239 | secpar = | |
240 | (uint16_t)(((uint8_t*) buf)[0]) << 8 | | |
241 | (uint16_t)(((uint8_t*) buf)[1]) << 0; | |
242 | return 16 * (secpar + 1); | |
243 | } | |
244 | ||
245 | void FSPRG_GenMK(void *msk, void *mpk, const void *seed, size_t seedlen, unsigned _secpar) { | |
246 | uint8_t iseed[FSPRG_RECOMMENDED_SEEDLEN]; | |
247 | gcry_mpi_t n, p, q; | |
248 | uint16_t secpar; | |
249 | ||
250 | VALIDATE_SECPAR(_secpar); | |
251 | secpar = _secpar; | |
252 | ||
91e023d8 | 253 | initialize_libgcrypt(false); |
7560fffc LP |
254 | |
255 | if (!seed) { | |
256 | gcry_randomize(iseed, FSPRG_RECOMMENDED_SEEDLEN, GCRY_STRONG_RANDOM); | |
257 | seed = iseed; | |
258 | seedlen = FSPRG_RECOMMENDED_SEEDLEN; | |
259 | } | |
260 | ||
261 | p = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_P); | |
262 | q = genprime3mod4(secpar / 2, seed, seedlen, RND_GEN_Q); | |
263 | ||
264 | if (msk) { | |
265 | store_secpar(msk + 0, secpar); | |
266 | mpi_export(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8, p); | |
267 | mpi_export(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8, q); | |
268 | } | |
269 | ||
270 | if (mpk) { | |
271 | n = gcry_mpi_new(0); | |
272 | gcry_mpi_mul(n, p, q); | |
273 | assert(gcry_mpi_get_nbits(n) == secpar); | |
274 | ||
275 | store_secpar(mpk + 0, secpar); | |
276 | mpi_export(mpk + 2, secpar / 8, n); | |
277 | ||
278 | gcry_mpi_release(n); | |
279 | } | |
280 | ||
281 | gcry_mpi_release(p); | |
282 | gcry_mpi_release(q); | |
283 | } | |
284 | ||
285 | void FSPRG_GenState0(void *state, const void *mpk, const void *seed, size_t seedlen) { | |
286 | gcry_mpi_t n, x; | |
287 | uint16_t secpar; | |
288 | ||
91e023d8 | 289 | initialize_libgcrypt(false); |
7560fffc LP |
290 | |
291 | secpar = read_secpar(mpk + 0); | |
292 | n = mpi_import(mpk + 2, secpar / 8); | |
293 | x = gensquare(n, seed, seedlen, RND_GEN_X, secpar); | |
294 | ||
295 | memcpy(state, mpk, 2 + secpar / 8); | |
296 | mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x); | |
29804cc1 | 297 | memzero(state + 2 + 2 * secpar / 8, 8); |
7560fffc LP |
298 | |
299 | gcry_mpi_release(n); | |
300 | gcry_mpi_release(x); | |
301 | } | |
302 | ||
303 | void FSPRG_Evolve(void *state) { | |
304 | gcry_mpi_t n, x; | |
305 | uint16_t secpar; | |
306 | uint64_t epoch; | |
307 | ||
91e023d8 | 308 | initialize_libgcrypt(false); |
7560fffc LP |
309 | |
310 | secpar = read_secpar(state + 0); | |
311 | n = mpi_import(state + 2 + 0 * secpar / 8, secpar / 8); | |
312 | x = mpi_import(state + 2 + 1 * secpar / 8, secpar / 8); | |
313 | epoch = uint64_import(state + 2 + 2 * secpar / 8, 8); | |
314 | ||
315 | gcry_mpi_mulm(x, x, x, n); | |
316 | epoch++; | |
317 | ||
318 | mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, x); | |
319 | uint64_export(state + 2 + 2 * secpar / 8, 8, epoch); | |
320 | ||
321 | gcry_mpi_release(n); | |
322 | gcry_mpi_release(x); | |
323 | } | |
324 | ||
325 | uint64_t FSPRG_GetEpoch(const void *state) { | |
326 | uint16_t secpar; | |
327 | secpar = read_secpar(state + 0); | |
328 | return uint64_import(state + 2 + 2 * secpar / 8, 8); | |
329 | } | |
330 | ||
331 | void FSPRG_Seek(void *state, uint64_t epoch, const void *msk, const void *seed, size_t seedlen) { | |
332 | gcry_mpi_t p, q, n, x, xp, xq, kp, kq, xm; | |
333 | uint16_t secpar; | |
334 | ||
91e023d8 | 335 | initialize_libgcrypt(false); |
7560fffc LP |
336 | |
337 | secpar = read_secpar(msk + 0); | |
338 | p = mpi_import(msk + 2 + 0 * (secpar / 2) / 8, (secpar / 2) / 8); | |
339 | q = mpi_import(msk + 2 + 1 * (secpar / 2) / 8, (secpar / 2) / 8); | |
340 | ||
341 | n = gcry_mpi_new(0); | |
342 | gcry_mpi_mul(n, p, q); | |
343 | ||
344 | x = gensquare(n, seed, seedlen, RND_GEN_X, secpar); | |
345 | CRT_decompose(&xp, &xq, x, p, q); /* split (mod n) into (mod p) and (mod q) using CRT */ | |
346 | ||
347 | kp = twopowmodphi(epoch, p); /* compute 2^epoch (mod phi(p)) */ | |
348 | kq = twopowmodphi(epoch, q); /* compute 2^epoch (mod phi(q)) */ | |
349 | ||
350 | gcry_mpi_powm(xp, xp, kp, p); /* compute x^(2^epoch) (mod p) */ | |
351 | gcry_mpi_powm(xq, xq, kq, q); /* compute x^(2^epoch) (mod q) */ | |
352 | ||
353 | CRT_compose(&xm, xp, xq, p, q); /* combine (mod p) and (mod q) to (mod n) using CRT */ | |
354 | ||
355 | store_secpar(state + 0, secpar); | |
356 | mpi_export(state + 2 + 0 * secpar / 8, secpar / 8, n); | |
357 | mpi_export(state + 2 + 1 * secpar / 8, secpar / 8, xm); | |
358 | uint64_export(state + 2 + 2 * secpar / 8, 8, epoch); | |
359 | ||
360 | gcry_mpi_release(p); | |
361 | gcry_mpi_release(q); | |
362 | gcry_mpi_release(n); | |
363 | gcry_mpi_release(x); | |
364 | gcry_mpi_release(xp); | |
365 | gcry_mpi_release(xq); | |
366 | gcry_mpi_release(kp); | |
367 | gcry_mpi_release(kq); | |
368 | gcry_mpi_release(xm); | |
369 | } | |
370 | ||
371 | void FSPRG_GetKey(const void *state, void *key, size_t keylen, uint32_t idx) { | |
372 | uint16_t secpar; | |
373 | ||
91e023d8 | 374 | initialize_libgcrypt(false); |
7560fffc LP |
375 | |
376 | secpar = read_secpar(state + 0); | |
377 | det_randomize(key, keylen, state + 2, 2 * secpar / 8 + 8, idx); | |
378 | } |