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