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