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