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         size_t n, sz;
 266
 267         n = outbuflen;
 268         while(n > SHA_DIGESTSIZE)
 269         {
 270                 sz = (d0_bignum_size(clobberme) + 7) / 8;
 271                 CHECK(d0_bignum_export_unsigned(clobberme, convbuf, sizeof(convbuf)) >= 0);
 272                 memcpy(outbuf, sha(convbuf, sz), SHA_DIGESTSIZE);
 273                 outbuf += SHA_DIGESTSIZE;
 274                 n -= SHA_DIGESTSIZE;
 275                 CHECK(d0_bignum_add(clobberme, clobberme, one));
 276         }
 277         sz = (d0_bignum_size(clobberme) + 7) / 8;
 278         CHECK(d0_bignum_export_unsigned(clobberme, convbuf, sizeof(convbuf)) >= 0);
 279         memcpy(outbuf, sha(convbuf, sz), n);
 280         return 1;
 281
 282 fail:
 283         return 0;
 284 }
 285
 286 void d0_blind_id_clear(d0_blind_id_t *ctx)
 287 {
 288         if(ctx->rsa_n) d0_bignum_free(ctx->rsa_n);
 289         if(ctx->rsa_e) d0_bignum_free(ctx->rsa_e);
 290         if(ctx->rsa_d) d0_bignum_free(ctx->rsa_d);
 291         if(ctx->schnorr_G) d0_bignum_free(ctx->schnorr_G);
 292         if(ctx->schnorr_s) d0_bignum_free(ctx->schnorr_s);
 293         if(ctx->schnorr_4_to_s) d0_bignum_free(ctx->schnorr_4_to_s);
 294         if(ctx->schnorr_H_4_to_s_signature) d0_bignum_free(ctx->schnorr_H_4_to_s_signature);
 295         if(ctx->rsa_blind_signature_camouflage) d0_bignum_free(ctx->rsa_blind_signature_camouflage);
 296         if(ctx->r) d0_bignum_free(ctx->r);
 297         if(ctx->challenge) d0_bignum_free(ctx->challenge);
 298         if(ctx->other_4_to_r) d0_bignum_free(ctx->other_4_to_r);
 299         memset(ctx, 0, sizeof(*ctx));
 300 }
 301
 302 WARN_UNUSED_RESULT BOOL d0_blind_id_copy(d0_blind_id_t *ctx, const d0_blind_id_t *src)
 303 {
 304         d0_blind_id_clear(ctx);
 305         if(src->rsa_n) CHECK_ASSIGN(ctx->rsa_n, d0_bignum_mov(NULL, src->rsa_n));
 306         if(src->rsa_e) CHECK_ASSIGN(ctx->rsa_e, d0_bignum_mov(NULL, src->rsa_e));
 307         if(src->rsa_d) CHECK_ASSIGN(ctx->rsa_d, d0_bignum_mov(NULL, src->rsa_d));
 308         if(src->schnorr_G) CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_mov(NULL, src->schnorr_G));
 309         if(src->schnorr_s) CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_mov(NULL, src->schnorr_s));
 310         if(src->schnorr_4_to_s) CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_bignum_mov(NULL, src->schnorr_4_to_s));
 311         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));
 312         if(src->rsa_blind_signature_camouflage) CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_mov(NULL, src->rsa_blind_signature_camouflage));
 313         if(src->r) CHECK_ASSIGN(ctx->r, d0_bignum_mov(NULL, src->r));
 314         if(src->challenge) CHECK_ASSIGN(ctx->challenge, d0_bignum_mov(NULL, src->challenge));
 315         if(src->other_4_to_r) CHECK_ASSIGN(ctx->other_4_to_r, d0_bignum_mov(NULL, src->other_4_to_r));
 316         memcpy(ctx->msg, src->msg, sizeof(ctx->msg));
 317         ctx->msglen = src->msglen;
 318         memcpy(ctx->msghash, src->msghash, sizeof(ctx->msghash));
 319         return 1;
 320 fail:
 321         d0_blind_id_clear(ctx);
 322         return 0;
 323 }
 324
 325 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_key_fastreject(d0_blind_id_t *ctx, int k, d0_fastreject_function reject, void *pass)
 326 {
 327         REPLACING(rsa_e); REPLACING(rsa_d); REPLACING(rsa_n);
 328
 329         CHECK_ASSIGN(ctx->rsa_e, d0_bignum_int(ctx->rsa_e, 65537));
 330         CHECK_ASSIGN(ctx->rsa_d, d0_bignum_zero(ctx->rsa_d));
 331         CHECK_ASSIGN(ctx->rsa_n, d0_bignum_zero(ctx->rsa_n));
 332         if(reject)
 333                 CHECK(d0_rsa_generate_key_fastreject(k+1, reject, ctx, pass)); // must fit G for sure
 334         else
 335                 CHECK(d0_rsa_generate_key(k+1, ctx->rsa_e, ctx->rsa_d, ctx->rsa_n)); // must fit G for sure
 336         return 1;
 337 fail:
 338         return 0;
 339 }
 340
 341 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_key(d0_blind_id_t *ctx, int k)
 342 {
 343         return d0_blind_id_generate_private_key_fastreject(ctx, k, NULL, NULL);
 344 }
 345
 346 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 347 {
 348         d0_iobuf_t *in = NULL;
 349
 350         REPLACING(rsa_n); REPLACING(rsa_e); REPLACING(rsa_d);
 351
 352         in = d0_iobuf_open_read(inbuf, inbuflen);
 353
 354         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
 355         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
 356         CHECK_ASSIGN(ctx->rsa_d, d0_iobuf_read_bignum(in, ctx->rsa_d));
 357         return d0_iobuf_close(in, NULL);
 358
 359 fail:
 360         d0_iobuf_close(in, NULL);
 361         return 0;
 362 }
 363
 364 WARN_UNUSED_RESULT BOOL d0_blind_id_read_public_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 365 {
 366         d0_iobuf_t *in = NULL;
 367
 368         REPLACING(rsa_n); REPLACING(rsa_e);
 369
 370         in = d0_iobuf_open_read(inbuf, inbuflen);
 371         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
 372         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
 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_write_private_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 381 {
 382         d0_iobuf_t *out = NULL;
 383
 384         USING(rsa_n); USING(rsa_e); USING(rsa_d);
 385
 386         out = d0_iobuf_open_write(outbuf, *outbuflen);
 387         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
 388         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
 389         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_d));
 390         return d0_iobuf_close(out, outbuflen);
 391
 392 fail:
 393         d0_iobuf_close(out, outbuflen);
 394         return 0;
 395 }
 396
 397 WARN_UNUSED_RESULT BOOL d0_blind_id_write_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 398 {
 399         d0_iobuf_t *out = NULL;
 400
 401         USING(rsa_n); USING(rsa_e);
 402
 403         out = d0_iobuf_open_write(outbuf, *outbuflen);
 404         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
 405         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
 406         return d0_iobuf_close(out, outbuflen);
 407
 408 fail:
 409         if(!d0_iobuf_close(out, outbuflen))
 410                 return 0;
 411         return 0;
 412 }
 413
 414 WARN_UNUSED_RESULT BOOL d0_blind_id_fingerprint64_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 415 {
 416         d0_iobuf_t *out = NULL;
 417         static unsigned char convbuf[2048];
 418         d0_iobuf_t *conv = NULL;
 419         size_t sz, n;
 420
 421         USING(rsa_n); USING(rsa_e);
 422
 423         out = d0_iobuf_open_write(outbuf, *outbuflen);
 424         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 425
 426         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_n));
 427         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_e));
 428         CHECK(d0_iobuf_close(conv, &sz));
 429         conv = NULL;
 430
 431         n = (*outbuflen / 4) * 3;
 432         if(n > SHA_DIGESTSIZE)
 433                 n = SHA_DIGESTSIZE;
 434         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
 435         CHECK(d0_iobuf_conv_base64_out(out));
 436
 437         return d0_iobuf_close(out, outbuflen);
 438
 439 fail:
 440         if(conv)
 441                 d0_iobuf_close(conv, &sz);
 442         d0_iobuf_close(out, outbuflen);
 443         return 0;
 444 }
 445
 446 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_modulus(d0_blind_id_t *ctx)
 447 {
 448         USING(rsa_n);
 449         REPLACING(schnorr_G);
 450
 451         CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_zero(ctx->schnorr_G));
 452         CHECK(d0_dl_generate_key(d0_bignum_size(ctx->rsa_n)-1, ctx->schnorr_G));
 453         return 1;
 454 fail:
 455         return 0;
 456 }
 457
 458 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id_modulus(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 459 {
 460         d0_iobuf_t *in = NULL;
 461
 462         REPLACING(schnorr_G);
 463
 464         in = d0_iobuf_open_read(inbuf, inbuflen);
 465         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
 466         return d0_iobuf_close(in, NULL);
 467
 468 fail:
 469         d0_iobuf_close(in, NULL);
 470         return 0;
 471 }
 472
 473 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id_modulus(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 474 {
 475         d0_iobuf_t *out = NULL;
 476
 477         USING(schnorr_G);
 478
 479         out = d0_iobuf_open_write(outbuf, *outbuflen);
 480         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
 481         return d0_iobuf_close(out, outbuflen);
 482
 483 fail:
 484         d0_iobuf_close(out, outbuflen);
 485         return 0;
 486 }
 487
 488 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_start(d0_blind_id_t *ctx)
 489 {
 490         // temps: temp0 = order
 491         USING(schnorr_G);
 492         REPLACING(schnorr_s); REPLACING(schnorr_4_to_s);
 493
 494         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 495         CHECK(d0_bignum_shl(temp1, ctx->schnorr_G, -1));
 496         CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_rand_range(ctx->schnorr_s, zero, temp0));
 497         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_bignum_mod_pow(ctx->schnorr_4_to_s, four, ctx->schnorr_s, ctx->schnorr_G));
 498         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_bignum_zero(ctx->schnorr_H_4_to_s_signature));
 499         return 1;
 500
 501 fail:
 502         return 0;
 503 }
 504
 505 WARN_UNUSED_RESULT BOOL d0_blind_id_generate_private_id_request(d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 506 {
 507         d0_iobuf_t *out = NULL;
 508         static unsigned char convbuf[2048], shabuf[2048];
 509         size_t sz;
 510
 511         // temps: temp0 rsa_blind_signature_camouflage^challenge, temp1 (4^s)*rsa_blind_signature_camouflage^challenge
 512         USING(rsa_n); USING(rsa_e); USING(schnorr_4_to_s);
 513         REPLACING(rsa_blind_signature_camouflage);
 514
 515         out = d0_iobuf_open_write(outbuf, *outbuflen);
 516
 517         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_rand_bit_atmost(ctx->rsa_blind_signature_camouflage, d0_bignum_size(ctx->rsa_n)));
 518         CHECK(d0_bignum_mod_pow(temp0, ctx->rsa_blind_signature_camouflage, ctx->rsa_e, ctx->rsa_n));
 519
 520         // we will actually sign HA(4^s) to prevent a malleability attack!
 521         CHECK(d0_bignum_mov(temp2, ctx->schnorr_4_to_s));
 522         sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
 523         if(sz > sizeof(shabuf))
 524                 sz = sizeof(shabuf);
 525         CHECK(d0_longhash_destructive(temp2, shabuf, sz));
 526         CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
 527
 528         // hash complete
 529         CHECK(d0_bignum_mod_mul(temp1, temp2, temp0, ctx->rsa_n));
 530         CHECK(d0_iobuf_write_bignum(out, temp1));
 531         return d0_iobuf_close(out, outbuflen);
 532
 533 fail:
 534         d0_iobuf_close(out, outbuflen);
 535         return 0;
 536 }
 537
 538 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)
 539 {
 540         d0_iobuf_t *in = NULL;
 541         d0_iobuf_t *out = NULL;
 542
 543         // temps: temp0 input, temp1 temp0^d
 544         USING(rsa_d); USING(rsa_n);
 545
 546         in = d0_iobuf_open_read(inbuf, inbuflen);
 547         out = d0_iobuf_open_write(outbuf, *outbuflen);
 548
 549         CHECK(d0_iobuf_read_bignum(in, temp0));
 550         CHECK(d0_bignum_mod_pow(temp1, temp0, ctx->rsa_d, ctx->rsa_n));
 551         CHECK(d0_iobuf_write_bignum(out, temp1));
 552
 553         d0_iobuf_close(in, NULL);
 554         return d0_iobuf_close(out, outbuflen);
 555
 556 fail:
 557         d0_iobuf_close(in, NULL);
 558         d0_iobuf_close(out, outbuflen);
 559         return 0;
 560 }
 561
 562 WARN_UNUSED_RESULT BOOL d0_blind_id_finish_private_id_request(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 563 {
 564         d0_iobuf_t *in = NULL;
 565
 566         // temps: temp0 input, temp1 rsa_blind_signature_camouflage^-1
 567         USING(rsa_blind_signature_camouflage); USING(rsa_n);
 568         REPLACING(schnorr_H_4_to_s_signature);
 569
 570         in = d0_iobuf_open_read(inbuf, inbuflen);
 571
 572         CHECK(d0_iobuf_read_bignum(in, temp0));
 573         CHECK(d0_bignum_mod_inv(temp1, ctx->rsa_blind_signature_camouflage, ctx->rsa_n));
 574         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));
 575
 576         return d0_iobuf_close(in, NULL);
 577
 578 fail:
 579         d0_iobuf_close(in, NULL);
 580         return 0;
 581 }
 582
 583 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id_request_camouflage(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 584 {
 585         d0_iobuf_t *in = NULL;
 586
 587         REPLACING(rsa_blind_signature_camouflage);
 588
 589         in = d0_iobuf_open_read(inbuf, inbuflen);
 590
 591         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_iobuf_read_bignum(in, ctx->rsa_blind_signature_camouflage));
 592
 593         return d0_iobuf_close(in, NULL);
 594
 595 fail:
 596         d0_iobuf_close(in, NULL);
 597         return 0;
 598 }
 599
 600 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id_request_camouflage(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 601 {
 602         d0_iobuf_t *out = NULL;
 603
 604         USING(rsa_blind_signature_camouflage);
 605
 606         out = d0_iobuf_open_write(outbuf, *outbuflen);
 607
 608         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_blind_signature_camouflage));
 609
 610         return d0_iobuf_close(out, outbuflen);
 611
 612 fail:
 613         d0_iobuf_close(out, outbuflen);
 614         return 0;
 615 }
 616
 617 WARN_UNUSED_RESULT BOOL d0_blind_id_read_private_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 618 {
 619         d0_iobuf_t *in = NULL;
 620
 621         REPLACING(schnorr_s); REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
 622
 623         in = d0_iobuf_open_read(inbuf, inbuflen);
 624
 625         CHECK_ASSIGN(ctx->schnorr_s, d0_iobuf_read_bignum(in, ctx->schnorr_s));
 626         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
 627         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
 628
 629         return d0_iobuf_close(in, NULL);
 630
 631 fail:
 632         d0_iobuf_close(in, NULL);
 633         return 0;
 634 }
 635
 636 WARN_UNUSED_RESULT BOOL d0_blind_id_read_public_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 637 {
 638         d0_iobuf_t *in = NULL;
 639
 640         REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
 641
 642         in = d0_iobuf_open_read(inbuf, inbuflen);
 643
 644         CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
 645         CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
 646
 647         return d0_iobuf_close(in, NULL);
 648
 649 fail:
 650         d0_iobuf_close(in, NULL);
 651         return 0;
 652 }
 653
 654 WARN_UNUSED_RESULT BOOL d0_blind_id_write_private_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 655 {
 656         d0_iobuf_t *out = NULL;
 657
 658         USING(schnorr_s); USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
 659
 660         out = d0_iobuf_open_write(outbuf, *outbuflen);
 661
 662         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_s));
 663         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
 664         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
 665
 666         return d0_iobuf_close(out, outbuflen);
 667
 668 fail:
 669         d0_iobuf_close(out, outbuflen);
 670         return 0;
 671 }
 672
 673 WARN_UNUSED_RESULT BOOL d0_blind_id_write_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 674 {
 675         d0_iobuf_t *out = NULL;
 676
 677         USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
 678
 679         out = d0_iobuf_open_write(outbuf, *outbuflen);
 680
 681         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
 682         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
 683
 684         return d0_iobuf_close(out, outbuflen);
 685
 686 fail:
 687         d0_iobuf_close(out, outbuflen);
 688         return 0;
 689 }
 690
 691 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)
 692 // start =
 693 //   first run: send 4^s, 4^s signature
 694 //   1. get random r, send HASH(4^r)
 695 {
 696         d0_iobuf_t *out = NULL;
 697         static unsigned char convbuf[1024];
 698         d0_iobuf_t *conv = NULL;
 699         size_t sz = 0;
 700
 701         // temps: temp0 order, temp0 4^r
 702         if(is_first)
 703         {
 704                 USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
 705         }
 706         USING(schnorr_G);
 707         REPLACING(r);
 708
 709         out = d0_iobuf_open_write(outbuf, *outbuflen);
 710
 711         if(is_first)
 712         {
 713                 // send ID
 714                 if(send_modulus)
 715                         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
 716                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_4_to_s));
 717                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_4_to_s_signature));
 718         }
 719
 720         // start schnorr ID scheme
 721         // generate random number r; x = g^r; send hash of x, remember r, forget x
 722         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 723         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
 724         CHECK(d0_bignum_mod_pow(temp0, four, ctx->r, ctx->schnorr_G));
 725
 726         // hash it, hash it, everybody hash it
 727         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 728         CHECK(d0_iobuf_write_bignum(conv, temp0));
 729         CHECK(d0_iobuf_write_packet(conv, msg, msglen));
 730         CHECK(d0_iobuf_write_bignum(conv, temp0));
 731         d0_iobuf_close(conv, &sz);
 732         conv = NULL;
 733         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), SCHNORR_HASHSIZE) == SCHNORR_HASHSIZE);
 734         CHECK(d0_iobuf_write_packet(out, msg, msglen));
 735
 736         return d0_iobuf_close(out, outbuflen);
 737
 738 fail:
 739         d0_iobuf_close(out, outbuflen);
 740         return 0;
 741 }
 742
 743 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)
 744 //   first run: get 4^s, 4^s signature
 745 //   1. check sig
 746 //   2. save HASH(4^r)
 747 //   3. send challenge challenge of SCHNORR_BITS
 748 {
 749         d0_iobuf_t *in = NULL;
 750         d0_iobuf_t *out = NULL;
 751         static unsigned char shabuf[2048];
 752         size_t sz;
 753
 754         // temps: temp0 order, temp0 signature check
 755         if(is_first)
 756         {
 757                 REPLACING(schnorr_4_to_s); REPLACING(schnorr_H_4_to_s_signature);
 758                 if(recv_modulus)
 759                         REPLACING(schnorr_G);
 760                 else
 761                         USING(schnorr_G);
 762         }
 763         else
 764         {
 765                 USING(schnorr_4_to_s); USING(schnorr_H_4_to_s_signature);
 766                 USING(schnorr_G);
 767         }
 768         USING(rsa_e); USING(rsa_n);
 769         REPLACING(challenge); REPLACING(msg); REPLACING(msglen); REPLACING(msghash); REPLACING(r);
 770
 771         in = d0_iobuf_open_read(inbuf, inbuflen);
 772         out = d0_iobuf_open_write(outbuf, *outbuflen);
 773
 774         if(is_first)
 775         {
 776                 if(recv_modulus)
 777                 {
 778                         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
 779                         CHECK(d0_bignum_cmp(ctx->schnorr_G, zero) > 0);
 780                         CHECK(d0_bignum_cmp(ctx->schnorr_G, ctx->rsa_n) < 0);
 781                 }
 782                 CHECK_ASSIGN(ctx->schnorr_4_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_4_to_s));
 783                 CHECK(d0_bignum_cmp(ctx->schnorr_4_to_s, zero) >= 0);
 784                 CHECK(d0_bignum_cmp(ctx->schnorr_4_to_s, ctx->schnorr_G) < 0);
 785                 CHECK_ASSIGN(ctx->schnorr_H_4_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_4_to_s_signature));
 786                 CHECK(d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero) >= 0);
 787                 CHECK(d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, ctx->rsa_n) < 0);
 788
 789                 // check signature of key (t = k^d, so, t^challenge = k)
 790                 CHECK(d0_bignum_mod_pow(temp0, ctx->schnorr_H_4_to_s_signature, ctx->rsa_e, ctx->rsa_n));
 791
 792                 // we will actually sign SHA(4^s) to prevent a malleability attack!
 793                 CHECK(d0_bignum_mov(temp2, ctx->schnorr_4_to_s));
 794                 sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
 795                 if(sz > sizeof(shabuf))
 796                         sz = sizeof(shabuf);
 797                 CHECK(d0_longhash_destructive(temp2, shabuf, sz));
 798                 CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
 799
 800                 // + 7 / 8 is too large, so let's mod it
 801                 CHECK(d0_bignum_divmod(NULL, temp1, temp2, ctx->rsa_n));
 802
 803                 // hash complete
 804                 if(d0_bignum_cmp(temp0, temp1))
 805                 {
 806                         // accept the key anyway, but mark as failed signature! will later return 0 in status
 807                         CHECK(d0_bignum_zero(ctx->schnorr_H_4_to_s_signature));
 808                 }
 809         }
 810
 811         CHECK(d0_iobuf_read_raw(in, ctx->msghash, SCHNORR_HASHSIZE));
 812         ctx->msglen = MSGSIZE;
 813         CHECK(d0_iobuf_read_packet(in, ctx->msg, &ctx->msglen));
 814
 815         // send challenge
 816         CHECK_ASSIGN(ctx->challenge, d0_bignum_rand_bit_atmost(ctx->challenge, SCHNORR_BITS));
 817
 818         CHECK(d0_iobuf_write_bignum(out, ctx->challenge));
 819
 820         // Diffie Hellmann
 821         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 822         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
 823         CHECK(d0_bignum_mod_pow(temp0, four, ctx->r, ctx->schnorr_G));
 824         CHECK(d0_iobuf_write_bignum(out, temp0));
 825
 826         if(status)
 827                 *status = !!d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero);
 828
 829         d0_iobuf_close(in, NULL);
 830         return d0_iobuf_close(out, outbuflen);
 831
 832 fail:
 833         d0_iobuf_close(in, NULL);
 834         d0_iobuf_close(out, outbuflen);
 835         return 0;
 836 }
 837
 838 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)
 839 //   1. read challenge challenge of SCHNORR_BITS
 840 //   2. reply with r + s * challenge mod order
 841 {
 842         d0_iobuf_t *in = NULL;
 843         d0_iobuf_t *out = NULL;
 844
 845         // temps: 0 order, 1 prod, 2 y, 3 challenge
 846         REPLACING(other_4_to_r);
 847         USING(schnorr_G); USING(schnorr_s); USING(r);
 848
 849         in = d0_iobuf_open_read(inbuf, inbuflen);
 850         out = d0_iobuf_open_write(outbuf, *outbuflen);
 851
 852         CHECK(d0_iobuf_read_bignum(in, temp3));
 853         CHECK(d0_bignum_cmp(temp3, zero) >= 0);
 854         CHECK(d0_bignum_size(temp3) <= SCHNORR_BITS);
 855
 856         // Diffie Hellmann
 857         CHECK_ASSIGN(ctx->other_4_to_r, d0_iobuf_read_bignum(in, ctx->other_4_to_r));
 858         CHECK(d0_bignum_cmp(ctx->other_4_to_r, zero) > 0);
 859         CHECK(d0_bignum_cmp(ctx->other_4_to_r, ctx->schnorr_G) < 0);
 860
 861         // send response for schnorr ID scheme
 862         // i.challenge. r + ctx->schnorr_s * temp3
 863         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 864         CHECK(d0_bignum_mod_mul(temp1, ctx->schnorr_s, temp3, temp0));
 865         CHECK(d0_bignum_mod_add(temp2, temp1, ctx->r, temp0));
 866         CHECK(d0_iobuf_write_bignum(out, temp2));
 867
 868         d0_iobuf_close(in, NULL);
 869         return d0_iobuf_close(out, outbuflen);
 870
 871 fail:
 872         d0_iobuf_close(in, NULL);
 873         d0_iobuf_close(out, outbuflen);
 874         return 0;
 875 }
 876
 877 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)
 878 //   1. read y = r + s * challenge mod order
 879 //   2. verify: g^y (g^s)^-challenge = g^(r+s*challenge-s*challenge) = g^r
 880 //      (check using H(g^r) which we know)
 881 {
 882         d0_iobuf_t *in = NULL;
 883         static unsigned char convbuf[1024];
 884         d0_iobuf_t *conv = NULL;
 885         size_t sz;
 886
 887         // temps: 0 y 1 order
 888         USING(challenge); USING(schnorr_G);
 889         REPLACING(other_4_to_r);
 890
 891         in = d0_iobuf_open_read(inbuf, inbuflen);
 892
 893         CHECK(d0_dl_get_order(temp1, ctx->schnorr_G));
 894         CHECK(d0_iobuf_read_bignum(in, temp0));
 895         CHECK(d0_bignum_cmp(temp0, zero) >= 0);
 896         CHECK(d0_bignum_cmp(temp0, temp1) < 0);
 897
 898         // verify schnorr ID scheme
 899         // we need 4^temp0 (g^s)^-challenge
 900         CHECK(d0_bignum_neg(temp1, ctx->challenge));
 901         CHECK(d0_bignum_mod_pow(temp2, ctx->schnorr_4_to_s, temp1, ctx->schnorr_G));
 902         CHECK(d0_bignum_mod_pow(temp1, four, temp0, ctx->schnorr_G));
 903         CHECK_ASSIGN(ctx->other_4_to_r, d0_bignum_mod_mul(ctx->other_4_to_r, temp1, temp2, ctx->schnorr_G));
 904         // hash must be equal to msghash
 905
 906         // hash it, hash it, everybody hash it
 907         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 908         CHECK(d0_iobuf_write_bignum(conv, ctx->other_4_to_r));
 909         CHECK(d0_iobuf_write_packet(conv, ctx->msg, ctx->msglen));
 910         CHECK(d0_iobuf_write_bignum(conv, ctx->other_4_to_r));
 911         d0_iobuf_close(conv, &sz);
 912         conv = NULL;
 913         if(memcmp(sha(convbuf, sz), ctx->msghash, SCHNORR_HASHSIZE))
 914         {
 915                 // FAIL (not owned by player)
 916                 goto fail;
 917         }
 918
 919         if(status)
 920                 *status = !!d0_bignum_cmp(ctx->schnorr_H_4_to_s_signature, zero);
 921
 922         if(ctx->msglen <= *msglen)
 923                 memcpy(msg, ctx->msg, ctx->msglen);
 924         else
 925                 memcpy(msg, ctx->msg, *msglen);
 926         *msglen = ctx->msglen;
 927
 928         d0_iobuf_close(in, NULL);
 929         return 1;
 930
 931 fail:
 932         d0_iobuf_close(in, NULL);
 933         return 0;
 934 }
 935
 936 WARN_UNUSED_RESULT BOOL d0_blind_id_fingerprint64_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 937 {
 938         d0_iobuf_t *out = NULL;
 939         static unsigned char convbuf[1024];
 940         d0_iobuf_t *conv = NULL;
 941         size_t sz, n;
 942
 943         USING(schnorr_4_to_s);
 944
 945         out = d0_iobuf_open_write(outbuf, *outbuflen);
 946         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 947
 948         CHECK(d0_iobuf_write_bignum(conv, ctx->schnorr_4_to_s));
 949         CHECK(d0_iobuf_close(conv, &sz));
 950         conv = NULL;
 951
 952         n = (*outbuflen / 4) * 3;
 953         if(n > SHA_DIGESTSIZE)
 954                 n = SHA_DIGESTSIZE;
 955         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
 956         CHECK(d0_iobuf_conv_base64_out(out));
 957
 958         return d0_iobuf_close(out, outbuflen);
 959
 960 fail:
 961         if(conv)
 962                 d0_iobuf_close(conv, &sz);
 963         d0_iobuf_close(out, outbuflen);
 964         return 0;
 965 }
 966
 967 BOOL d0_blind_id_sessionkey_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 968 {
 969         USING(r); USING(other_4_to_r); USING(schnorr_G);
 970
 971         // temps: temp0 result
 972         CHECK(d0_bignum_mod_pow(temp0, ctx->other_4_to_r, ctx->r, ctx->schnorr_G));
 973         return d0_longhash_destructive(temp0, outbuf, *outbuflen);
 974
 975 fail:
 976         return 0;
 977 }
 978
 979 d0_blind_id_t *d0_blind_id_new(void)
 980 {
 981         d0_blind_id_t *b = d0_malloc(sizeof(d0_blind_id_t));
 982         memset(b, 0, sizeof(*b));
 983         return b;
 984 }
 985
 986 void d0_blind_id_free(d0_blind_id_t *a)
 987 {
 988         d0_blind_id_clear(a);
 989         d0_free(a);
 990 }