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