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