fix build of rijndael lib
[xonotic/d0_blind_id.git] / d0_blind_id.c
1 /*
2 Blind-ID library for user identification using RSA blind signatures
3 Copyright (C) 2010  Rudolf Polzer
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20 #include "d0_blind_id.h"
21
22 #include <stdio.h>
23 #include <string.h>
24 #include "d0_bignum.h"
25 #include "sha2.h"
26
27 // our SHA is SHA-256
28 #define SHA_DIGESTSIZE 32
29 const char *sha(const char *in, size_t len)
30 {
31         static char h[32];
32         d0_blind_id_util_sha256(h, in, len);
33         return h;
34 }
35
36 // for zero knowledge, we need multiple instances of schnorr ID scheme... should normally be sequential
37 // parallel schnorr ID is not provably zero knowledge :(
38 //   (evil verifier can know all questions in advance, so sequential is disadvantage for him)
39 // we'll just live with a 1:1048576 chance of cheating, and support reauthenticating
40
41 #define SCHNORR_BITS 20
42 // probability of cheat: 2^(-bits+1)
43
44 #define SCHNORR_HASHSIZE SHA_DIGESTSIZE
45 // cannot be >= SHA_DIGESTSIZE
46 // *8 must be >= SCHNORR_BITS
47 // no need to save bits here
48
49 #define MSGSIZE 640 // ought to be enough for anyone
50
51 struct d0_blind_id_s
52 {
53         // signing (Xonotic pub and priv key)
54         d0_bignum_t *rsa_n, *rsa_e, *rsa_d;
55
56         // public data (Schnorr ID)
57         d0_bignum_t *schnorr_G;
58
59         // private data (player ID private key)
60         d0_bignum_t *schnorr_s;
61
62         // public data (player ID public key, this is what the server gets to know)
63         d0_bignum_t *schnorr_4_to_s;
64         d0_bignum_t *schnorr_H_4_to_s_signature; // 0 when signature is invalid
65         // as hash function H, we get the SHA1 and reinterpret as bignum - yes, it always is < 160 bits
66
67         // temp data
68         d0_bignum_t *rsa_blind_signature_camouflage; // random number blind signature
69
70         d0_bignum_t *r; // random number for schnorr ID
71         d0_bignum_t *other_4_to_r; // for DH key exchange
72         d0_bignum_t *challenge; // challenge
73
74         char msghash[SCHNORR_HASHSIZE]; // init hash
75         char msg[MSGSIZE]; // message
76         size_t msglen; // message length
77 };
78
79 #define CHECK(x) do { if(!(x)) goto fail; } while(0)
80 #define CHECK_ASSIGN(var, value) do { d0_bignum_t *val; val = value; if(!val) goto fail; var = val; } while(0)
81
82 #define USING(x) if(!(ctx->x)) return 0
83 #define REPLACING(x)
84
85 static d0_bignum_t *zero, *one, *four, *temp0, *temp1, *temp2, *temp3, *temp4;
86
87 void d0_blind_id_INITIALIZE(void)
88 {
89         d0_bignum_INITIALIZE();
90         CHECK_ASSIGN(zero, d0_bignum_int(zero, 0));
91         CHECK_ASSIGN(one, d0_bignum_int(one, 1));
92         CHECK_ASSIGN(four, d0_bignum_int(four, 4));
93         CHECK_ASSIGN(temp0, d0_bignum_int(temp0, 0));
94         CHECK_ASSIGN(temp1, d0_bignum_int(temp1, 0));
95         CHECK_ASSIGN(temp2, d0_bignum_int(temp2, 0));
96         CHECK_ASSIGN(temp3, d0_bignum_int(temp3, 0));
97         CHECK_ASSIGN(temp4, d0_bignum_int(temp4, 0));
98 fail:
99         ;
100 }
101
102 void d0_blind_id_SHUTDOWN(void)
103 {
104         d0_bignum_free(zero);
105         d0_bignum_free(one);
106         d0_bignum_free(four);
107         d0_bignum_free(temp0);
108         d0_bignum_free(temp1);
109         d0_bignum_free(temp2);
110         d0_bignum_free(temp3);
111         d0_bignum_free(temp4);
112         d0_bignum_SHUTDOWN();
113 }
114
115 // (G-1)/2
116 d0_bignum_t *d0_dl_get_order(d0_bignum_t *o, const d0_bignum_t *G)
117 {
118         CHECK_ASSIGN(o, d0_bignum_sub(o, G, one));
119         CHECK(d0_bignum_shl(o, o, -1)); // order o = (G-1)/2
120         return o;
121 fail:
122         return NULL;
123 }
124 // 2o+1
125 d0_bignum_t *d0_dl_get_from_order(d0_bignum_t *G, const d0_bignum_t *o)
126 {
127         CHECK_ASSIGN(G, d0_bignum_shl(G, o, 1));
128         CHECK(d0_bignum_add(G, G, one));
129         return G;
130 fail:
131         return NULL;
132 }
133
134 BOOL d0_dl_generate_key(size_t size, d0_bignum_t *G)
135 {
136         // using: temp0
137         if(size < 16)
138                 size = 16;
139         for(;;)
140         {
141                 CHECK(d0_bignum_rand_bit_exact(temp0, size-1));
142                 if(d0_bignum_isprime(temp0, 0) == 0)
143                         continue;
144                 CHECK(d0_dl_get_from_order(G, temp0));
145                 if(d0_bignum_isprime(G, 10) == 0)
146                         continue;
147                 if(d0_bignum_isprime(temp0, 10) == 0) // finish the previous test
148                         continue;
149                 break;
150         }
151         return 1;
152 fail:
153         return 0;
154 }
155
156 BOOL d0_rsa_generate_key(size_t size, const d0_bignum_t *challenge, d0_bignum_t *d, d0_bignum_t *n)
157 {
158         // uses temp0 to temp4
159         int fail = 0;
160         int gcdfail = 0;
161         int pb = (size + 1)/2;
162         int qb = size - pb;
163         if(pb < 8)
164                 pb = 8;
165         if(qb < 8)
166                 qb = 8;
167         for (;;)
168         {
169                 CHECK(d0_bignum_rand_bit_exact(temp0, pb));
170                 if(d0_bignum_isprime(temp0, 10) == 0)
171                         continue;
172                 CHECK(d0_bignum_sub(temp2, temp0, one));
173                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp2, challenge));
174                 if(!d0_bignum_cmp(temp4, one))
175                         break;
176                 if(++gcdfail == 3)
177                         return 0;
178                 ++gcdfail;
179         }
180         gcdfail = 0;
181         for (;;)
182         {
183                 CHECK(d0_bignum_rand_bit_exact(temp1, qb));
184                 if(!d0_bignum_cmp(temp1, temp0))
185                 {
186                         if(++fail == 3)
187                                 return 0;
188                 }
189                 fail = 0;
190                 if(d0_bignum_isprime(temp1, 10) == 0)
191                         continue;
192                 CHECK(d0_bignum_sub(temp3, temp1, one));
193                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp3, challenge));
194                 if(!d0_bignum_cmp(temp4, one))
195                         break;
196                 if(++gcdfail == 3)
197                         return 0;
198                 ++gcdfail;
199         }
200
201         // n = temp0*temp1
202         CHECK(d0_bignum_mul(n, temp0, temp1));
203
204         // d = challenge^-1 mod (temp0-1)(temp1-1)
205         CHECK(d0_bignum_mul(temp0, temp2, temp3));
206         CHECK(d0_bignum_mod_inv(d, challenge, temp0));
207         return 1;
208 fail:
209         return 0;
210 }
211
212 BOOL d0_rsa_generate_key_fastreject(size_t size, d0_fastreject_function reject, d0_blind_id_t *ctx, void *pass)
213 {
214         // uses temp0 to temp4
215         int fail = 0;
216         int gcdfail = 0;
217         int pb = (size + 1)/2;
218         int qb = size - pb;
219         if(pb < 8)
220                 pb = 8;
221         if(qb < 8)
222                 qb = 8;
223         for (;;)
224         {
225                 CHECK(d0_bignum_rand_bit_exact(temp0, pb));
226                 if(d0_bignum_isprime(temp0, 10) == 0)
227                         continue;
228                 CHECK(d0_bignum_sub(temp2, temp0, one));
229                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp2, ctx->rsa_e));
230                 if(!d0_bignum_cmp(temp4, one))
231                         break;
232                 if(++gcdfail == 3)
233                         return 0;
234                 ++gcdfail;
235         }
236         gcdfail = 0;
237         for (;;)
238         {
239                 CHECK(d0_bignum_rand_bit_exact(temp1, qb));
240                 if(!d0_bignum_cmp(temp1, temp0))
241                 {
242                         if(++fail == 3)
243                                 return 0;
244                 }
245                 fail = 0;
246
247                 // n = temp0*temp1
248                 CHECK(d0_bignum_mul(ctx->rsa_n, temp0, temp1));
249                 if(reject(ctx, pass))
250                         continue;
251
252                 if(d0_bignum_isprime(temp1, 10) == 0)
253                         continue;
254                 CHECK(d0_bignum_sub(temp3, temp1, one));
255                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp3, ctx->rsa_e));
256                 if(!d0_bignum_cmp(temp4, one))
257                         break;
258                 if(++gcdfail == 3)
259                         return 0;
260                 ++gcdfail;
261         }
262
263         // ctx->rsa_d = ctx->rsa_e^-1 mod (temp0-1)(temp1-1)
264         CHECK(d0_bignum_mul(temp0, temp2, temp3));
265         CHECK(d0_bignum_mod_inv(ctx->rsa_d, ctx->rsa_e, temp0));
266         return 1;
267 fail:
268         return 0;
269 }
270
271 WARN_UNUSED_RESULT BOOL d0_longhash_destructive(d0_bignum_t *clobberme, char *outbuf, size_t outbuflen)
272 {
273         d0_iobuf_t *out = NULL;
274         static unsigned char convbuf[1024];
275         size_t n, sz;
276
277         n = outbuflen;
278         while(n > SHA_DIGESTSIZE)
279         {
280                 sz = (d0_bignum_size(clobberme) + 7) / 8;
281                 CHECK(d0_bignum_export_unsigned(clobberme, convbuf, sizeof(convbuf)) >= 0);
282                 memcpy(outbuf, sha(convbuf, sz), SHA_DIGESTSIZE);
283                 outbuf += SHA_DIGESTSIZE;
284                 n -= SHA_DIGESTSIZE;
285                 CHECK(d0_bignum_add(clobberme, clobberme, one));
286         }
287         sz = (d0_bignum_size(clobberme) + 7) / 8;
288         CHECK(d0_bignum_export_unsigned(clobberme, convbuf, sizeof(convbuf)) >= 0);
289         memcpy(outbuf, sha(convbuf, sz), n);
290         return 1;
291
292 fail:
293         return 0;
294 }
295
296 void d0_blind_id_clear(d0_blind_id_t *ctx)
297 {
298         if(ctx->rsa_n) d0_bignum_free(ctx->rsa_n);
299         if(ctx->rsa_e) d0_bignum_free(ctx->rsa_e);
300         if(ctx->rsa_d) d0_bignum_free(ctx->rsa_d);
301         if(ctx->schnorr_G) d0_bignum_free(ctx->schnorr_G);
302         if(ctx->schnorr_s) d0_bignum_free(ctx->schnorr_s);
303         if(ctx->schnorr_4_to_s) d0_bignum_free(ctx->schnorr_4_to_s);
304         if(ctx->schnorr_H_4_to_s_signature) d0_bignum_free(ctx->schnorr_H_4_to_s_signature);
305         if(ctx->rsa_blind_signature_camouflage) d0_bignum_free(ctx->rsa_blind_signature_camouflage);
306         if(ctx->r) d0_bignum_free(ctx->r);
307         if(ctx->challenge) d0_bignum_free(ctx->challenge);
308         if(ctx->other_4_to_r) d0_bignum_free(ctx->other_4_to_r);
309         memset(ctx, 0, sizeof(*ctx));
310 }
311
312 WARN_UNUSED_RESULT BOOL d0_blind_id_copy(d0_blind_id_t *ctx, const d0_blind_id_t *src)
313 {
314         d0_blind_id_clear(ctx);
315         if(src->rsa_n) CHECK_ASSIGN(ctx->rsa_n, d0_bignum_mov(NULL, src->rsa_n));
316         if(src->rsa_e) CHECK_ASSIGN(ctx->rsa_e, d0_bignum_mov(NULL, src->rsa_e));
317         if(src->rsa_d) CHECK_ASSIGN(ctx->rsa_d, d0_bignum_mov(NULL, src->rsa_d));
318         if(src->schnorr_G) CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_mov(NULL, src->schnorr_G));
319         if(src->schnorr_s) CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_mov(NULL, src->schnorr_s));
320         if(src->schnorr_4_to_s) CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_bignum_mov(NULL, src->schnorr_4_to_s));
321         if(src->schnorr_H_4_to_s_signature) CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_bignum_mov(NULL, src->schnorr_H_4_to_s_signature));
322         if(src->rsa_blind_signature_camouflage) CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_mov(NULL, src->rsa_blind_signature_camouflage));
323         if(src->r) CHECK_ASSIGN(ctx->r, d0_bignum_mov(NULL, src->r));
324         if(src->challenge) CHECK_ASSIGN(ctx->challenge, d0_bignum_mov(NULL, src->challenge));
325         if(src->other_4_to_r) CHECK_ASSIGN(ctx->other_4_to_r, d0_bignum_mov(NULL, src->other_4_to_r));
326         memcpy(ctx->msg, src->msg, sizeof(ctx->msg));
327         ctx->msglen = src->msglen;
328         memcpy(ctx->msghash, src->msghash, sizeof(ctx->msghash));
329         return 1;
330 fail:
331         d0_blind_id_clear(ctx);
332         return 0;
333 }
334
335 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_key_fastreject(d0_blind_id_t *ctx, int k, d0_fastreject_function reject, void *pass)
336 {
337         REPLACING(rsa_e); REPLACING(rsa_d); REPLACING(rsa_n);
338
339         CHECK_ASSIGN(ctx->rsa_e, d0_bignum_int(ctx->rsa_e, 65537));
340         CHECK_ASSIGN(ctx->rsa_d, d0_bignum_zero(ctx->rsa_d));
341         CHECK_ASSIGN(ctx->rsa_n, d0_bignum_zero(ctx->rsa_n));
342         if(reject)
343                 CHECK(d0_rsa_generate_key_fastreject(k+1, reject, ctx, pass)); // must fit G for sure
344         else
345                 CHECK(d0_rsa_generate_key(k+1, ctx->rsa_e, ctx->rsa_d, ctx->rsa_n)); // must fit G for sure
346         return 1;
347 fail:
348         return 0;
349 }
350
351 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_key(d0_blind_id_t *ctx, int k)
352 {
353         return d0_blind_id_generate_private_key_fastreject(ctx, k, NULL, NULL);
354 }
355
356 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
357 {
358         d0_iobuf_t *in = NULL;
359
360         REPLACING(rsa_n); REPLACING(rsa_e); REPLACING(rsa_d);
361
362         in = d0_iobuf_open_read(inbuf, inbuflen);
363
364         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
365         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
366         CHECK_ASSIGN(ctx->rsa_d, d0_iobuf_read_bignum(in, ctx->rsa_d));
367         return d0_iobuf_close(in, NULL);
368
369 fail:
370         d0_iobuf_close(in, NULL);
371         return 0;
372 }
373
374 WARN_UNUSED_RESULT BOOL d0_blind_id_read_public_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
375 {
376         d0_iobuf_t *in = NULL;
377
378         REPLACING(rsa_n); REPLACING(rsa_e);
379
380         in = d0_iobuf_open_read(inbuf, inbuflen);
381         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
382         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
383         return d0_iobuf_close(in, NULL);
384
385 fail:
386         d0_iobuf_close(in, NULL);
387         return 0;
388 }
389
390 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
391 {
392         d0_iobuf_t *out = NULL;
393
394         USING(rsa_n); USING(rsa_e); USING(rsa_d);
395
396         out = d0_iobuf_open_write(outbuf, *outbuflen);
397         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
398         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
399         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_d));
400         return d0_iobuf_close(out, outbuflen);
401
402 fail:
403         d0_iobuf_close(out, outbuflen);
404         return 0;
405 }
406
407 WARN_UNUSED_RESULT BOOL d0_blind_id_write_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
408 {
409         d0_iobuf_t *out = NULL;
410
411         USING(rsa_n); USING(rsa_e);
412
413         out = d0_iobuf_open_write(outbuf, *outbuflen);
414         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
415         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
416         return d0_iobuf_close(out, outbuflen);
417
418 fail:
419         if(!d0_iobuf_close(out, outbuflen))
420                 return 0;
421         return 0;
422 }
423
424 WARN_UNUSED_RESULT BOOL d0_blind_id_fingerprint64_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
425 {
426         d0_iobuf_t *out = NULL;
427         static unsigned char convbuf[2048];
428         d0_iobuf_t *conv = NULL;
429         size_t sz, n;
430
431         USING(rsa_n); USING(rsa_e);
432
433         out = d0_iobuf_open_write(outbuf, *outbuflen);
434         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
435
436         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_n));
437         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_e));
438         CHECK(d0_iobuf_close(conv, &sz));
439         conv = NULL;
440
441         n = (*outbuflen / 4) * 3;
442         if(n > SHA_DIGESTSIZE)
443                 n = SHA_DIGESTSIZE;
444         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
445         CHECK(d0_iobuf_conv_base64_out(out));
446
447         return d0_iobuf_close(out, outbuflen);
448
449 fail:
450         if(conv)
451                 d0_iobuf_close(conv, &sz);
452         d0_iobuf_close(out, outbuflen);
453         return 0;
454 }
455
456 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_modulus(d0_blind_id_t *ctx)
457 {
458         USING(rsa_n);
459         REPLACING(schnorr_G);
460
461         CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_zero(ctx->schnorr_G));
462         CHECK(d0_dl_generate_key(d0_bignum_size(ctx->rsa_n)-1, ctx->schnorr_G));
463         return 1;
464 fail:
465         return 0;
466 }
467
468 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id_modulus(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
469 {
470         d0_iobuf_t *in = NULL;
471
472         REPLACING(schnorr_G);
473
474         in = d0_iobuf_open_read(inbuf, inbuflen);
475         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
476         return d0_iobuf_close(in, NULL);
477
478 fail:
479         d0_iobuf_close(in, NULL);
480         return 0;
481 }
482
483 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id_modulus(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
484 {
485         d0_iobuf_t *out = NULL;
486
487         USING(schnorr_G);
488
489         out = d0_iobuf_open_write(outbuf, *outbuflen);
490         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
491         return d0_iobuf_close(out, outbuflen);
492
493 fail:
494         d0_iobuf_close(out, outbuflen);
495         return 0;
496 }
497
498 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_start(d0_blind_id_t *ctx)
499 {
500         // temps: temp0 = order
501         USING(schnorr_G);
502         REPLACING(schnorr_s); REPLACING(schnorr_4_to_s);
503
504         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
505         CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_rand_range(ctx->schnorr_s, zero, temp0));
506         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_bignum_mod_pow(ctx->schnorr_4_to_s, four, ctx->schnorr_s, ctx->schnorr_G));
507         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_bignum_zero(ctx->schnorr_H_4_to_s_signature));
508         return 1;
509
510 fail:
511         return 0;
512 }
513
514 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_request(d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
515 {
516         d0_iobuf_t *out = NULL;
517         static unsigned char convbuf[2048], shabuf[2048];
518         size_t sz;
519
520         // temps: temp0 rsa_blind_signature_camouflage^challenge, temp1 (4^s)*rsa_blind_signature_camouflage^challenge
521         USING(rsa_n); USING(rsa_e); USING(schnorr_4_to_s);
522         REPLACING(rsa_blind_signature_camouflage);
523
524         out = d0_iobuf_open_write(outbuf, *outbuflen);
525
526         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_rand_bit_atmost(ctx->rsa_blind_signature_camouflage, d0_bignum_size(ctx->rsa_n)));
527         CHECK(d0_bignum_mod_pow(temp0, ctx->rsa_blind_signature_camouflage, ctx->rsa_e, ctx->rsa_n));
528
529         // we will actually sign HA(4^s) to prevent a malleability attack!
530         CHECK(d0_bignum_mov(temp2, ctx->schnorr_4_to_s));
531         sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
532         if(sz > sizeof(shabuf))
533                 sz = sizeof(shabuf);
534         CHECK(d0_longhash_destructive(temp2, shabuf, sz));
535         CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
536
537         // hash complete
538         CHECK(d0_bignum_mod_mul(temp1, temp2, temp0, ctx->rsa_n));
539         CHECK(d0_iobuf_write_bignum(out, temp1));
540         return d0_iobuf_close(out, outbuflen);
541
542 fail:
543         d0_iobuf_close(out, outbuflen);
544         return 0;
545 }
546
547 WARN_UNUSED_RESULT BOOL d0_blind_id_answer_private_id_request(const d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen, char *outbuf, size_t *outbuflen)
548 {
549         d0_iobuf_t *in = NULL;
550         d0_iobuf_t *out = NULL;
551
552         // temps: temp0 input, temp1 temp0^d
553         USING(rsa_d); USING(rsa_n);
554
555         in = d0_iobuf_open_read(inbuf, inbuflen);
556         out = d0_iobuf_open_write(outbuf, *outbuflen);
557
558         CHECK(d0_iobuf_read_bignum(in, temp0));
559         CHECK(d0_bignum_mod_pow(temp1, temp0, ctx->rsa_d, ctx->rsa_n));
560         CHECK(d0_iobuf_write_bignum(out, temp1));
561
562         d0_iobuf_close(in, NULL);
563         return d0_iobuf_close(out, outbuflen);
564
565 fail:
566         d0_iobuf_close(in, NULL);
567         d0_iobuf_close(out, outbuflen);
568         return 0;
569 }
570
571 WARN_UNUSED_RESULT BOOL d0_blind_id_finish_private_id_request(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
572 {
573         d0_iobuf_t *in = NULL;
574
575         // temps: temp0 input, temp1 rsa_blind_signature_camouflage^-1
576         USING(rsa_blind_signature_camouflage); USING(rsa_n);
577         REPLACING(schnorr_H_4_to_s_signature);
578
579         in = d0_iobuf_open_read(inbuf, inbuflen);
580
581         CHECK(d0_iobuf_read_bignum(in, temp0));
582         CHECK(d0_bignum_mod_inv(temp1, ctx->rsa_blind_signature_camouflage, ctx->rsa_n));
583         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_bignum_mod_mul(ctx->schnorr_H_4_to_s_signature, temp0, temp1, ctx->rsa_n));
584
585         return d0_iobuf_close(in, NULL);
586
587 fail:
588         d0_iobuf_close(in, NULL);
589         return 0;
590 }
591
592 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id_request_camouflage(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
593 {
594         d0_iobuf_t *in = NULL;
595
596         REPLACING(rsa_blind_signature_camouflage);
597
598         in = d0_iobuf_open_read(inbuf, inbuflen);
599
600         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_iobuf_read_bignum(in, ctx->rsa_blind_signature_camouflage));
601
602         return d0_iobuf_close(in, NULL);
603
604 fail:
605         d0_iobuf_close(in, NULL);
606         return 0;
607 }
608
609 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id_request_camouflage(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
610 {
611         d0_iobuf_t *out = NULL;
612
613         USING(rsa_blind_signature_camouflage);
614
615         out = d0_iobuf_open_write(outbuf, *outbuflen);
616
617         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_blind_signature_camouflage));
618
619         return d0_iobuf_close(out, outbuflen);
620
621 fail:
622         d0_iobuf_close(out, outbuflen);
623         return 0;
624 }
625
626 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
627 {
628         d0_iobuf_t *in = NULL;
629
630         REPLACING(schnorr_s); REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
631
632         in = d0_iobuf_open_read(inbuf, inbuflen);
633
634         CHECK_ASSIGN(ctx->schnorr_s, d0_iobuf_read_bignum(in, ctx->schnorr_s));
635         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
636         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
637
638         return d0_iobuf_close(in, NULL);
639
640 fail:
641         d0_iobuf_close(in, NULL);
642         return 0;
643 }
644
645 WARN_UNUSED_RESULT BOOL d0_blind_id_read_public_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
646 {
647         d0_iobuf_t *in = NULL;
648
649         REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
650
651         in = d0_iobuf_open_read(inbuf, inbuflen);
652
653         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
654         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
655
656         return d0_iobuf_close(in, NULL);
657
658 fail:
659         d0_iobuf_close(in, NULL);
660         return 0;
661 }
662
663 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
664 {
665         d0_iobuf_t *out = NULL;
666
667         USING(schnorr_s); USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
668
669         out = d0_iobuf_open_write(outbuf, *outbuflen);
670
671         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_s));
672         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
673         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
674
675         return d0_iobuf_close(out, outbuflen);
676
677 fail:
678         d0_iobuf_close(out, outbuflen);
679         return 0;
680 }
681
682 WARN_UNUSED_RESULT BOOL d0_blind_id_write_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
683 {
684         d0_iobuf_t *out = NULL;
685
686         USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
687
688         out = d0_iobuf_open_write(outbuf, *outbuflen);
689
690         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
691         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
692
693         return d0_iobuf_close(out, outbuflen);
694
695 fail:
696         d0_iobuf_close(out, outbuflen);
697         return 0;
698 }
699
700 WARN_UNUSED_RESULT BOOL d0_blind_id_authenticate_with_private_id_start(d0_blind_id_t *ctx, BOOL is_first, BOOL send_modulus, char *msg, size_t msglen, char *outbuf, size_t *outbuflen)
701 // start =
702 //   first run: send 4^s, 4^s signature
703 //   1. get random r, send HASH(4^r)
704 {
705         d0_iobuf_t *out = NULL;
706         static unsigned char convbuf[1024];
707         d0_iobuf_t *conv = NULL;
708         size_t sz = 0;
709
710         // temps: temp0 order, temp0 4^r
711         if(is_first)
712         {
713                 USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
714         }
715         USING(schnorr_G);
716         REPLACING(r);
717
718         out = d0_iobuf_open_write(outbuf, *outbuflen);
719
720         if(is_first)
721         {
722                 // send ID
723                 if(send_modulus)
724                         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
725                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
726                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
727         }
728
729         // start schnorr ID scheme
730         // generate random number r; x = g^r; send hash of x, remember r, forget x
731         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
732         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
733         CHECK(d0_bignum_mod_pow(temp0, four, ctx->r, ctx->schnorr_G));
734
735         // hash it, hash it, everybody hash it
736         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
737         CHECK(d0_iobuf_write_bignum(conv, temp0));
738         CHECK(d0_iobuf_write_packet(conv, msg, msglen));
739         CHECK(d0_iobuf_write_bignum(conv, temp0));
740         d0_iobuf_close(conv, &sz);
741         conv = NULL;
742         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), SCHNORR_HASHSIZE) == SCHNORR_HASHSIZE);
743         CHECK(d0_iobuf_write_packet(out, msg, msglen));
744
745         return d0_iobuf_close(out, outbuflen);
746
747 fail:
748         d0_iobuf_close(out, outbuflen);
749         return 0;
750 }
751
752 WARN_UNUSED_RESULT BOOL d0_blind_id_authenticate_with_private_id_challenge(d0_blind_id_t *ctx, BOOL is_first, BOOL recv_modulus, const char *inbuf, size_t inbuflen, char *outbuf, size_t *outbuflen, BOOL *status)
753 //   first run: get 4^s, 4^s signature
754 //   1. check sig
755 //   2. save HASH(4^r)
756 //   3. send challenge challenge of SCHNORR_BITS
757 {
758         d0_iobuf_t *in = NULL;
759         d0_iobuf_t *out = NULL;
760         static unsigned char shabuf[2048];
761         size_t sz;
762
763         // temps: temp0 order, temp0 signature check
764         if(is_first)
765         {
766                 REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
767                 if(recv_modulus)
768                         REPLACING(schnorr_G);
769                 else
770                         USING(schnorr_G);
771         }
772         else
773         {
774                 USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
775                 USING(schnorr_G);
776         }
777         USING(rsa_e); USING(rsa_n);
778         REPLACING(challenge); REPLACING(msg); REPLACING(msglen); REPLACING(msghash); REPLACING(r);
779
780         in = d0_iobuf_open_read(inbuf, inbuflen);
781         out = d0_iobuf_open_write(outbuf, *outbuflen);
782
783         if(is_first)
784         {
785                 if(recv_modulus)
786                 {
787                         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
788                         CHECK(d0_bignum_cmp(ctx->schnorr_G, zero) > 0);
789                         CHECK(d0_bignum_cmp(ctx->schnorr_G, ctx->rsa_n) < 0);
790                 }
791                 CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
792                 CHECK(d0_bignum_cmp(ctx->schnorr_4_to_s, zero) >= 0);
793                 CHECK(d0_bignum_cmp(ctx->schnorr_4_to_s, ctx->schnorr_G) < 0);
794                 CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
795                 CHECK(d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero) >= 0);
796                 CHECK(d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, ctx->rsa_n) < 0);
797
798                 // check signature of key (t = k^d, so, t^challenge = k)
799                 CHECK(d0_bignum_mod_pow(temp0, ctx->schnorr_H_4_to_s_signature, ctx->rsa_e, ctx->rsa_n));
800
801                 // we will actually sign SHA(4^s) to prevent a malleability attack!
802                 CHECK(d0_bignum_mov(temp2, ctx->schnorr_4_to_s));
803                 sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
804                 if(sz > sizeof(shabuf))
805                         sz = sizeof(shabuf);
806                 CHECK(d0_longhash_destructive(temp2, shabuf, sz));
807                 CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
808
809                 // + 7 / 8 is too large, so let's mod it
810                 CHECK(d0_bignum_divmod(NULL, temp1, temp2, ctx->rsa_n));
811
812                 // hash complete
813                 if(d0_bignum_cmp(temp0, temp1))
814                 {
815                         // accept the key anyway, but mark as failed signature! will later return 0 in status
816                         CHECK(d0_bignum_zero(ctx->schnorr_H_4_to_s_signature));
817                 }
818         }
819
820         CHECK(d0_iobuf_read_raw(in, ctx->msghash, SCHNORR_HASHSIZE));
821         ctx->msglen = MSGSIZE;
822         CHECK(d0_iobuf_read_packet(in, ctx->msg, &ctx->msglen));
823
824         // send challenge
825         CHECK_ASSIGN(ctx->challenge, d0_bignum_rand_bit_atmost(ctx->challenge, SCHNORR_BITS));
826
827         CHECK(d0_iobuf_write_bignum(out, ctx->challenge));
828
829         // Diffie Hellmann
830         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
831         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
832         CHECK(d0_bignum_mod_pow(temp0, four, ctx->r, ctx->schnorr_G));
833         CHECK(d0_iobuf_write_bignum(out, temp0));
834
835         if(status)
836                 *status = !!d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero);
837
838         d0_iobuf_close(in, NULL);
839         return d0_iobuf_close(out, outbuflen);
840
841 fail:
842         d0_iobuf_close(in, NULL);
843         d0_iobuf_close(out, outbuflen);
844         return 0;
845 }
846
847 WARN_UNUSED_RESULT BOOL d0_blind_id_authenticate_with_private_id_response(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen, char *outbuf, size_t *outbuflen)
848 //   1. read challenge challenge of SCHNORR_BITS
849 //   2. reply with r + s * challenge mod order
850 {
851         d0_iobuf_t *in = NULL;
852         d0_iobuf_t *out = NULL;
853
854         // temps: 0 order, 1 prod, 2 y, 3 challenge
855         REPLACING(other_4_to_r);
856         USING(schnorr_G); USING(schnorr_s); USING(r);
857
858         in = d0_iobuf_open_read(inbuf, inbuflen);
859         out = d0_iobuf_open_write(outbuf, *outbuflen);
860
861         CHECK(d0_iobuf_read_bignum(in, temp3));
862         CHECK(d0_bignum_cmp(temp3, zero) >= 0);
863         CHECK(d0_bignum_size(temp3) <= SCHNORR_BITS);
864
865         // Diffie Hellmann
866         CHECK_ASSIGN(ctx->other_4_to_r, d0_iobuf_read_bignum(in, ctx->other_4_to_r));
867         CHECK(d0_bignum_cmp(ctx->other_4_to_r, zero) > 0);
868         CHECK(d0_bignum_cmp(ctx->other_4_to_r, ctx->schnorr_G) < 0);
869
870         // send response for schnorr ID scheme
871         // i.challenge. r + ctx->schnorr_s * temp3
872         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
873         CHECK(d0_bignum_mod_mul(temp1, ctx->schnorr_s, temp3, temp0));
874         CHECK(d0_bignum_mod_add(temp2, temp1, ctx->r, temp0));
875         CHECK(d0_iobuf_write_bignum(out, temp2));
876
877         d0_iobuf_close(in, NULL);
878         return d0_iobuf_close(out, outbuflen);
879
880 fail:
881         d0_iobuf_close(in, NULL);
882         d0_iobuf_close(out, outbuflen);
883         return 0;
884 }
885
886 WARN_UNUSED_RESULT BOOL d0_blind_id_authenticate_with_private_id_verify(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen, char *msg, size_t *msglen, BOOL *status)
887 //   1. read y = r + s * challenge mod order
888 //   2. verify: g^y (g^s)^-challenge = g^(r+s*challenge-s*challenge) = g^r
889 //      (check using H(g^r) which we know)
890 {
891         d0_iobuf_t *in = NULL;
892         static unsigned char convbuf[1024];
893         d0_iobuf_t *conv = NULL;
894         size_t sz;
895
896         // temps: 0 y 1 order
897         USING(challenge); USING(schnorr_G);
898         REPLACING(other_4_to_r);
899
900         in = d0_iobuf_open_read(inbuf, inbuflen);
901
902         CHECK(d0_dl_get_order(temp1, ctx->schnorr_G));
903         CHECK(d0_iobuf_read_bignum(in, temp0));
904         CHECK(d0_bignum_cmp(temp0, zero) >= 0);
905         CHECK(d0_bignum_cmp(temp0, temp1) < 0);
906
907         // verify schnorr ID scheme
908         // we need 4^temp0 (g^s)^-challenge
909         CHECK(d0_bignum_neg(temp1, ctx->challenge));
910         CHECK(d0_bignum_mod_pow(temp2, ctx->schnorr_4_to_s, temp1, ctx->schnorr_G));
911         CHECK(d0_bignum_mod_pow(temp1, four, temp0, ctx->schnorr_G));
912         CHECK_ASSIGN(ctx->other_4_to_r, d0_bignum_mod_mul(ctx->other_4_to_r, temp1, temp2, ctx->schnorr_G));
913         // hash must be equal to msghash
914
915         // hash it, hash it, everybody hash it
916         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
917         CHECK(d0_iobuf_write_bignum(conv, ctx->other_4_to_r));
918         CHECK(d0_iobuf_write_packet(conv, ctx->msg, ctx->msglen));
919         CHECK(d0_iobuf_write_bignum(conv, ctx->other_4_to_r));
920         d0_iobuf_close(conv, &sz);
921         conv = NULL;
922         if(memcmp(sha(convbuf, sz), ctx->msghash, SCHNORR_HASHSIZE))
923         {
924                 // FAIL (not owned by player)
925                 goto fail;
926         }
927
928         if(status)
929                 *status = !!d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero);
930
931         if(ctx->msglen <= *msglen)
932                 memcpy(msg, ctx->msg, ctx->msglen);
933         else
934                 memcpy(msg, ctx->msg, *msglen);
935         *msglen = ctx->msglen;
936
937         d0_iobuf_close(in, NULL);
938         return 1;
939
940 fail:
941         d0_iobuf_close(in, NULL);
942         return 0;
943 }
944
945 WARN_UNUSED_RESULT BOOL d0_blind_id_fingerprint64_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
946 {
947         d0_iobuf_t *out = NULL;
948         static unsigned char convbuf[1024];
949         d0_iobuf_t *conv = NULL;
950         size_t sz, n;
951
952         USING(schnorr_4_to_s);
953
954         out = d0_iobuf_open_write(outbuf, *outbuflen);
955         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
956
957         CHECK(d0_iobuf_write_bignum(conv, ctx->schnorr_4_to_s));
958         CHECK(d0_iobuf_close(conv, &sz));
959         conv = NULL;
960
961         n = (*outbuflen / 4) * 3;
962         if(n > SHA_DIGESTSIZE)
963                 n = SHA_DIGESTSIZE;
964         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
965         CHECK(d0_iobuf_conv_base64_out(out));
966
967         return d0_iobuf_close(out, outbuflen);
968
969 fail:
970         if(conv)
971                 d0_iobuf_close(conv, &sz);
972         d0_iobuf_close(out, outbuflen);
973         return 0;
974 }
975
976 BOOL d0_blind_id_sessionkey_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
977 {
978         USING(r); USING(other_4_to_r); USING(schnorr_G);
979
980         // temps: temp0 result
981         CHECK(d0_bignum_mod_pow(temp0, ctx->other_4_to_r, ctx->r, ctx->schnorr_G));
982         return d0_longhash_destructive(temp0, outbuf, *outbuflen);
983
984 fail:
985         return 0;
986 }
987
988 d0_blind_id_t *d0_blind_id_new(void)
989 {
990         d0_blind_id_t *b = d0_malloc(sizeof(d0_blind_id_t));
991         memset(b, 0, sizeof(*b));
992         return b;
993 }
994
995 void d0_blind_id_free(d0_blind_id_t *a)
996 {
997         d0_blind_id_clear(a);
998         d0_free(a);
999 }
1000
1001 void d0_blind_id_util_sha256(char *out, const char *in, size_t n)
1002 {
1003         SHA256_CTX context;
1004         SHA256_Init(&context);
1005         SHA256_Update(&context, (const unsigned char *) in, n);
1006         return SHA256_Final((unsigned char *) out, &context);
1007 }