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 }