d0_blind_id.c

   1 /*
   2  * FILE:        d0_blind_id.c
   3  * AUTHOR:      Rudolf Polzer - divVerent@xonotic.org
   4  *
   5  * Copyright (c) 2010, Rudolf Polzer
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the copyright holder nor the names of contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTOR(S) ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTOR(S) BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $Format:commit %H$
  33  * $Id$
  34  */
  35
  36 #include "d0_blind_id.h"
  37
  38 #include <stdio.h>
  39 #include <string.h>
  40 #include "d0_bignum.h"
  41 #include "sha2.h"
  42
  43 // old "positive" protocol, uses one extra mod_inv in verify stages
  44 // #define D0_BLIND_ID_POSITIVE_PROTOCOL
  45
  46 // our SHA is SHA-256
  47 #define SHA_DIGESTSIZE 32
  48 const char *sha(const unsigned char *in, size_t len)
  49 {
  50         static char h[32];
  51         d0_blind_id_util_sha256(h, (const char *) in, len);
  52         return h;
  53 }
  54
  55 // for zero knowledge, we need multiple instances of schnorr ID scheme... should normally be sequential
  56 // parallel schnorr ID is not provably zero knowledge :(
  57 //   (evil verifier can know all questions in advance, so sequential is disadvantage for him)
  58 // we'll just live with a 1:1048576 chance of cheating, and support reauthenticating
  59
  60 #define SCHNORR_BITS 20
  61 // probability of cheat: 2^(-bits+1)
  62
  63 #define SCHNORR_HASHSIZE SHA_DIGESTSIZE
  64 // cannot be >= SHA_DIGESTSIZE
  65 // *8 must be >= SCHNORR_BITS
  66 // no need to save bits here
  67
  68 #define MSGSIZE 640 // ought to be enough for anyone
  69
  70 struct d0_blind_id_s
  71 {
  72         // signing (Xonotic pub and priv key)
  73         d0_bignum_t *rsa_n, *rsa_e, *rsa_d;
  74
  75         // public data (Schnorr ID)
  76         d0_bignum_t *schnorr_G;
  77
  78         // private data (player ID private key)
  79         d0_bignum_t *schnorr_s;
  80
  81         // public data (player ID public key, this is what the server gets to know)
  82         d0_bignum_t *schnorr_g_to_s;
  83         d0_bignum_t *schnorr_H_g_to_s_signature; // 0 when signature is invalid
  84         // as hash function H, we get the SHA1 and reinterpret as bignum - yes, it always is < 160 bits
  85
  86         // temp data
  87         d0_bignum_t *rsa_blind_signature_camouflage; // random number blind signature
  88
  89         d0_bignum_t *r; // random number for schnorr ID
  90         d0_bignum_t *t; // for DH key exchange
  91         d0_bignum_t *g_to_t; // for DH key exchange
  92         d0_bignum_t *other_g_to_t; // for DH key exchange
  93         d0_bignum_t *challenge; // challenge
  94
  95         char msghash[SCHNORR_HASHSIZE]; // init hash
  96         char msg[MSGSIZE]; // message
  97         size_t msglen; // message length
  98 };
  99
 100 //#define CHECKDEBUG
 101 #ifdef CHECKDEBUG
 102 #define CHECK(x) do { if(!(x)) { fprintf(stderr, "CHECK FAILED (%s:%d): %s\n", __FILE__, __LINE__, #x); goto fail; } } while(0)
 103 #define CHECK_ASSIGN(var, value) do { d0_bignum_t *val; val = value; if(!val) { fprintf(stderr, "CHECK FAILED (%s:%d): %s\n", __FILE__, __LINE__, #value); goto fail; } var = val; } while(0)
 104 #else
 105 #define CHECK(x) do { if(!(x)) goto fail; } while(0)
 106 #define CHECK_ASSIGN(var, value) do { d0_bignum_t *val; val = value; if(!val) goto fail; var = val; } while(0)
 107 #endif
 108
 109 #define USING(x) if(!(ctx->x)) return 0
 110 #define REPLACING(x)
 111
 112 static d0_bignum_t *zero, *one, *four, *temp0, *temp1, *temp2, *temp3, *temp4;
 113
 114 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_INITIALIZE(void)
 115 {
 116         CHECK(d0_bignum_INITIALIZE());
 117         CHECK_ASSIGN(zero, d0_bignum_int(zero, 0));
 118         CHECK_ASSIGN(one, d0_bignum_int(one, 1));
 119         CHECK_ASSIGN(four, d0_bignum_int(four, 4));
 120         CHECK_ASSIGN(temp0, d0_bignum_int(temp0, 0));
 121         CHECK_ASSIGN(temp1, d0_bignum_int(temp1, 0));
 122         CHECK_ASSIGN(temp2, d0_bignum_int(temp2, 0));
 123         CHECK_ASSIGN(temp3, d0_bignum_int(temp3, 0));
 124         CHECK_ASSIGN(temp4, d0_bignum_int(temp4, 0));
 125         return 1;
 126 fail:
 127         return 0;
 128 }
 129
 130 void d0_blind_id_SHUTDOWN(void)
 131 {
 132         d0_bignum_free(zero);
 133         d0_bignum_free(one);
 134         d0_bignum_free(four);
 135         d0_bignum_free(temp0);
 136         d0_bignum_free(temp1);
 137         d0_bignum_free(temp2);
 138         d0_bignum_free(temp3);
 139         d0_bignum_free(temp4);
 140         d0_bignum_SHUTDOWN();
 141 }
 142
 143 // (G-1)/2
 144 d0_bignum_t *d0_dl_get_order(d0_bignum_t *o, const d0_bignum_t *G)
 145 {
 146         CHECK_ASSIGN(o, d0_bignum_sub(o, G, one));
 147         CHECK(d0_bignum_shl(o, o, -1)); // order o = (G-1)/2
 148         return o;
 149 fail:
 150         return NULL;
 151 }
 152 // 2o+1
 153 d0_bignum_t *d0_dl_get_from_order(d0_bignum_t *G, const d0_bignum_t *o)
 154 {
 155         CHECK_ASSIGN(G, d0_bignum_shl(G, o, 1));
 156         CHECK(d0_bignum_add(G, G, one));
 157         return G;
 158 fail:
 159         return NULL;
 160 }
 161
 162 D0_BOOL d0_dl_generate_key(size_t size, d0_bignum_t *G)
 163 {
 164         // using: temp0
 165         if(size < 16)
 166                 size = 16;
 167         for(;;)
 168         {
 169                 CHECK(d0_bignum_rand_bit_exact(temp0, size-1));
 170                 if(d0_bignum_isprime(temp0, 0) == 0)
 171                         continue;
 172                 CHECK(d0_dl_get_from_order(G, temp0));
 173                 if(d0_bignum_isprime(G, 10) == 0)
 174                         continue;
 175                 if(d0_bignum_isprime(temp0, 10) == 0) // finish the previous test
 176                         continue;
 177                 break;
 178         }
 179         return 1;
 180 fail:
 181         return 0;
 182 }
 183
 184 D0_BOOL d0_rsa_generate_key(size_t size, const d0_bignum_t *challenge, d0_bignum_t *d, d0_bignum_t *n)
 185 {
 186         // uses temp0 to temp4
 187         int fail = 0;
 188         int gcdfail = 0;
 189         int pb = (size + 1)/2;
 190         int qb = size - pb;
 191         if(pb < 8)
 192                 pb = 8;
 193         if(qb < 8)
 194                 qb = 8;
 195         for (;;)
 196         {
 197                 CHECK(d0_bignum_rand_bit_exact(temp0, pb));
 198                 if(d0_bignum_isprime(temp0, 10) == 0)
 199                         continue;
 200                 CHECK(d0_bignum_sub(temp2, temp0, one));
 201                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp2, challenge));
 202                 if(!d0_bignum_cmp(temp4, one))
 203                         break;
 204                 if(++gcdfail == 3)
 205                         return 0;
 206                 ++gcdfail;
 207         }
 208         gcdfail = 0;
 209         for (;;)
 210         {
 211                 CHECK(d0_bignum_rand_bit_exact(temp1, qb));
 212                 if(!d0_bignum_cmp(temp1, temp0))
 213                 {
 214                         if(++fail == 3)
 215                                 return 0;
 216                 }
 217                 fail = 0;
 218                 if(d0_bignum_isprime(temp1, 10) == 0)
 219                         continue;
 220                 CHECK(d0_bignum_sub(temp3, temp1, one));
 221                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp3, challenge));
 222                 if(!d0_bignum_cmp(temp4, one))
 223                         break;
 224                 if(++gcdfail == 3)
 225                         return 0;
 226                 ++gcdfail;
 227         }
 228
 229         // n = temp0*temp1
 230         CHECK(d0_bignum_mul(n, temp0, temp1));
 231
 232         // d = challenge^-1 mod (temp0-1)(temp1-1)
 233         CHECK(d0_bignum_mul(temp0, temp2, temp3));
 234         CHECK(d0_bignum_mod_inv(d, challenge, temp0));
 235         return 1;
 236 fail:
 237         return 0;
 238 }
 239
 240 D0_BOOL d0_rsa_generate_key_fastreject(size_t size, d0_fastreject_function reject, d0_blind_id_t *ctx, void *pass)
 241 {
 242         // uses temp0 to temp4
 243         int fail = 0;
 244         int gcdfail = 0;
 245         int pb = (size + 1)/2;
 246         int qb = size - pb;
 247         if(pb < 8)
 248                 pb = 8;
 249         if(qb < 8)
 250                 qb = 8;
 251         for (;;)
 252         {
 253                 CHECK(d0_bignum_rand_bit_exact(temp0, pb));
 254                 if(d0_bignum_isprime(temp0, 10) == 0)
 255                         continue;
 256                 CHECK(d0_bignum_sub(temp2, temp0, one));
 257                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp2, ctx->rsa_e));
 258                 if(!d0_bignum_cmp(temp4, one))
 259                         break;
 260                 if(++gcdfail == 3)
 261                         return 0;
 262                 ++gcdfail;
 263         }
 264         gcdfail = 0;
 265         for (;;)
 266         {
 267                 CHECK(d0_bignum_rand_bit_exact(temp1, qb));
 268                 if(!d0_bignum_cmp(temp1, temp0))
 269                 {
 270                         if(++fail == 3)
 271                                 return 0;
 272                 }
 273                 fail = 0;
 274
 275                 // n = temp0*temp1
 276                 CHECK(d0_bignum_mul(ctx->rsa_n, temp0, temp1));
 277                 if(reject(ctx, pass))
 278                         continue;
 279
 280                 if(d0_bignum_isprime(temp1, 10) == 0)
 281                         continue;
 282                 CHECK(d0_bignum_sub(temp3, temp1, one));
 283                 CHECK(d0_bignum_gcd(temp4, NULL, NULL, temp3, ctx->rsa_e));
 284                 if(!d0_bignum_cmp(temp4, one))
 285                         break;
 286                 if(++gcdfail == 3)
 287                         return 0;
 288                 ++gcdfail;
 289         }
 290
 291         // ctx->rsa_d = ctx->rsa_e^-1 mod (temp0-1)(temp1-1)
 292         CHECK(d0_bignum_mul(temp0, temp2, temp3));
 293         CHECK(d0_bignum_mod_inv(ctx->rsa_d, ctx->rsa_e, temp0));
 294         return 1;
 295 fail:
 296         return 0;
 297 }
 298
 299 D0_WARN_UNUSED_RESULT D0_BOOL d0_longhash_destructive(unsigned char *convbuf, size_t sz, unsigned char *outbuf, size_t outbuflen)
 300 {
 301         size_t n, i;
 302
 303         n = outbuflen;
 304         while(n > SHA_DIGESTSIZE)
 305         {
 306                 memcpy(outbuf, sha(convbuf, sz), SHA_DIGESTSIZE);
 307                 outbuf += SHA_DIGESTSIZE;
 308                 n -= SHA_DIGESTSIZE;
 309                 for(i = 0; i < sz; ++i)
 310                         if(++convbuf[i])
 311                                 break; // stop until no carry
 312         }
 313         memcpy(outbuf, sha(convbuf, sz), n);
 314         return 1;
 315 }
 316
 317 D0_WARN_UNUSED_RESULT D0_BOOL d0_longhash_bignum(const d0_bignum_t *in, unsigned char *outbuf, size_t outbuflen)
 318 {
 319         static unsigned char convbuf[1024];
 320         size_t sz;
 321
 322         CHECK(d0_bignum_export_unsigned(in, convbuf, sizeof(convbuf)) >= 0);
 323         sz = (d0_bignum_size(in) + 7) / 8;
 324         CHECK(d0_longhash_destructive(convbuf, sz, outbuf, outbuflen));
 325         return 1;
 326
 327 fail:
 328         return 0;
 329 }
 330
 331 void d0_blind_id_clear(d0_blind_id_t *ctx)
 332 {
 333         if(ctx->rsa_n) d0_bignum_free(ctx->rsa_n);
 334         if(ctx->rsa_e) d0_bignum_free(ctx->rsa_e);
 335         if(ctx->rsa_d) d0_bignum_free(ctx->rsa_d);
 336         if(ctx->schnorr_G) d0_bignum_free(ctx->schnorr_G);
 337         if(ctx->schnorr_s) d0_bignum_free(ctx->schnorr_s);
 338         if(ctx->schnorr_g_to_s) d0_bignum_free(ctx->schnorr_g_to_s);
 339         if(ctx->schnorr_H_g_to_s_signature) d0_bignum_free(ctx->schnorr_H_g_to_s_signature);
 340         if(ctx->rsa_blind_signature_camouflage) d0_bignum_free(ctx->rsa_blind_signature_camouflage);
 341         if(ctx->r) d0_bignum_free(ctx->r);
 342         if(ctx->challenge) d0_bignum_free(ctx->challenge);
 343         if(ctx->t) d0_bignum_free(ctx->t);
 344         if(ctx->g_to_t) d0_bignum_free(ctx->g_to_t);
 345         if(ctx->other_g_to_t) d0_bignum_free(ctx->other_g_to_t);
 346         memset(ctx, 0, sizeof(*ctx));
 347 }
 348
 349 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_copy(d0_blind_id_t *ctx, const d0_blind_id_t *src)
 350 {
 351         d0_blind_id_clear(ctx);
 352         if(src->rsa_n) CHECK_ASSIGN(ctx->rsa_n, d0_bignum_mov(NULL, src->rsa_n));
 353         if(src->rsa_e) CHECK_ASSIGN(ctx->rsa_e, d0_bignum_mov(NULL, src->rsa_e));
 354         if(src->rsa_d) CHECK_ASSIGN(ctx->rsa_d, d0_bignum_mov(NULL, src->rsa_d));
 355         if(src->schnorr_G) CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_mov(NULL, src->schnorr_G));
 356         if(src->schnorr_s) CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_mov(NULL, src->schnorr_s));
 357         if(src->schnorr_g_to_s) CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_bignum_mov(NULL, src->schnorr_g_to_s));
 358         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));
 359         if(src->rsa_blind_signature_camouflage) CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_mov(NULL, src->rsa_blind_signature_camouflage));
 360         if(src->r) CHECK_ASSIGN(ctx->r, d0_bignum_mov(NULL, src->r));
 361         if(src->challenge) CHECK_ASSIGN(ctx->challenge, d0_bignum_mov(NULL, src->challenge));
 362         if(src->t) CHECK_ASSIGN(ctx->t, d0_bignum_mov(NULL, src->t));
 363         if(src->g_to_t) CHECK_ASSIGN(ctx->g_to_t, d0_bignum_mov(NULL, src->g_to_t));
 364         if(src->other_g_to_t) CHECK_ASSIGN(ctx->other_g_to_t, d0_bignum_mov(NULL, src->other_g_to_t));
 365         memcpy(ctx->msg, src->msg, sizeof(ctx->msg));
 366         ctx->msglen = src->msglen;
 367         memcpy(ctx->msghash, src->msghash, sizeof(ctx->msghash));
 368         return 1;
 369 fail:
 370         d0_blind_id_clear(ctx);
 371         return 0;
 372 }
 373
 374 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_generate_private_key_fastreject(d0_blind_id_t *ctx, int k, d0_fastreject_function reject, void *pass)
 375 {
 376         REPLACING(rsa_e); REPLACING(rsa_d); REPLACING(rsa_n);
 377
 378         CHECK_ASSIGN(ctx->rsa_e, d0_bignum_int(ctx->rsa_e, 65537));
 379         CHECK_ASSIGN(ctx->rsa_d, d0_bignum_zero(ctx->rsa_d));
 380         CHECK_ASSIGN(ctx->rsa_n, d0_bignum_zero(ctx->rsa_n));
 381         if(reject)
 382                 CHECK(d0_rsa_generate_key_fastreject(k+1, reject, ctx, pass)); // must fit G for sure
 383         else
 384                 CHECK(d0_rsa_generate_key(k+1, ctx->rsa_e, ctx->rsa_d, ctx->rsa_n)); // must fit G for sure
 385         return 1;
 386 fail:
 387         return 0;
 388 }
 389
 390 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_generate_private_key(d0_blind_id_t *ctx, int k)
 391 {
 392         return d0_blind_id_generate_private_key_fastreject(ctx, k, NULL, NULL);
 393 }
 394
 395 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_private_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 396 {
 397         d0_iobuf_t *in = NULL;
 398
 399         REPLACING(rsa_n); REPLACING(rsa_e); REPLACING(rsa_d);
 400
 401         in = d0_iobuf_open_read(inbuf, inbuflen);
 402
 403         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
 404         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
 405         CHECK_ASSIGN(ctx->rsa_d, d0_iobuf_read_bignum(in, ctx->rsa_d));
 406         return d0_iobuf_close(in, NULL);
 407
 408 fail:
 409         d0_iobuf_close(in, NULL);
 410         return 0;
 411 }
 412
 413 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_public_key(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 414 {
 415         d0_iobuf_t *in = NULL;
 416
 417         REPLACING(rsa_n); REPLACING(rsa_e);
 418
 419         in = d0_iobuf_open_read(inbuf, inbuflen);
 420         CHECK_ASSIGN(ctx->rsa_n, d0_iobuf_read_bignum(in, ctx->rsa_n));
 421         CHECK_ASSIGN(ctx->rsa_e, d0_iobuf_read_bignum(in, ctx->rsa_e));
 422         return d0_iobuf_close(in, NULL);
 423
 424 fail:
 425         d0_iobuf_close(in, NULL);
 426         return 0;
 427 }
 428
 429 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_private_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 430 {
 431         d0_iobuf_t *out = NULL;
 432
 433         USING(rsa_n); USING(rsa_e); USING(rsa_d);
 434
 435         out = d0_iobuf_open_write(outbuf, *outbuflen);
 436         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
 437         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
 438         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_d));
 439         return d0_iobuf_close(out, outbuflen);
 440
 441 fail:
 442         d0_iobuf_close(out, outbuflen);
 443         return 0;
 444 }
 445
 446 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 447 {
 448         d0_iobuf_t *out = NULL;
 449
 450         USING(rsa_n); USING(rsa_e);
 451
 452         out = d0_iobuf_open_write(outbuf, *outbuflen);
 453         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_n));
 454         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_e));
 455         return d0_iobuf_close(out, outbuflen);
 456
 457 fail:
 458         if(!d0_iobuf_close(out, outbuflen))
 459                 return 0;
 460         return 0;
 461 }
 462
 463 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_fingerprint64_public_key(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 464 {
 465         d0_iobuf_t *out = NULL;
 466         static unsigned char convbuf[2048];
 467         d0_iobuf_t *conv = NULL;
 468         size_t sz, n;
 469
 470         USING(rsa_n); USING(rsa_e);
 471
 472         out = d0_iobuf_open_write(outbuf, *outbuflen);
 473         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 474
 475         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_n));
 476         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_e));
 477         CHECK(d0_iobuf_close(conv, &sz));
 478         conv = NULL;
 479
 480         n = (*outbuflen / 4) * 3;
 481         if(n > SHA_DIGESTSIZE)
 482                 n = SHA_DIGESTSIZE;
 483         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
 484         CHECK(d0_iobuf_conv_base64_out(out));
 485
 486         return d0_iobuf_close(out, outbuflen);
 487
 488 fail:
 489         if(conv)
 490                 d0_iobuf_close(conv, &sz);
 491         d0_iobuf_close(out, outbuflen);
 492         return 0;
 493 }
 494
 495 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_generate_private_id_modulus(d0_blind_id_t *ctx)
 496 {
 497         USING(rsa_n);
 498         REPLACING(schnorr_G);
 499
 500         CHECK_ASSIGN(ctx->schnorr_G, d0_bignum_zero(ctx->schnorr_G));
 501         CHECK(d0_dl_generate_key(d0_bignum_size(ctx->rsa_n)-1, ctx->schnorr_G));
 502         return 1;
 503 fail:
 504         return 0;
 505 }
 506
 507 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_private_id_modulus(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 508 {
 509         d0_iobuf_t *in = NULL;
 510
 511         REPLACING(schnorr_G);
 512
 513         in = d0_iobuf_open_read(inbuf, inbuflen);
 514         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
 515         return d0_iobuf_close(in, NULL);
 516
 517 fail:
 518         d0_iobuf_close(in, NULL);
 519         return 0;
 520 }
 521
 522 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_private_id_modulus(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 523 {
 524         d0_iobuf_t *out = NULL;
 525
 526         USING(schnorr_G);
 527
 528         out = d0_iobuf_open_write(outbuf, *outbuflen);
 529         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
 530         return d0_iobuf_close(out, outbuflen);
 531
 532 fail:
 533         d0_iobuf_close(out, outbuflen);
 534         return 0;
 535 }
 536
 537 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_generate_private_id_start(d0_blind_id_t *ctx)
 538 {
 539         // temps: temp0 = order
 540         USING(schnorr_G);
 541         REPLACING(schnorr_s); REPLACING(schnorr_g_to_s);
 542
 543         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 544         CHECK_ASSIGN(ctx->schnorr_s, d0_bignum_rand_range(ctx->schnorr_s, zero, temp0));
 545         CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_bignum_mod_pow(ctx->schnorr_g_to_s, four, ctx->schnorr_s, ctx->schnorr_G));
 546         CHECK_ASSIGN(ctx->schnorr_H_g_to_s_signature, d0_bignum_zero(ctx->schnorr_H_g_to_s_signature));
 547         return 1;
 548
 549 fail:
 550         return 0;
 551 }
 552
 553 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_generate_private_id_request(d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 554 {
 555         d0_iobuf_t *out = NULL;
 556         static unsigned char shabuf[2048];
 557         size_t sz;
 558
 559         // temps: temp0 rsa_blind_signature_camouflage^challenge, temp1 (4^s)*rsa_blind_signature_camouflage^challenge
 560         USING(rsa_n); USING(rsa_e); USING(schnorr_g_to_s);
 561         REPLACING(rsa_blind_signature_camouflage);
 562
 563         out = d0_iobuf_open_write(outbuf, *outbuflen);
 564
 565         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_bignum_rand_bit_atmost(ctx->rsa_blind_signature_camouflage, d0_bignum_size(ctx->rsa_n)));
 566         CHECK(d0_bignum_mod_pow(temp0, ctx->rsa_blind_signature_camouflage, ctx->rsa_e, ctx->rsa_n));
 567
 568         // we will actually sign HA(4^s) to prevent a malleability attack!
 569         CHECK(d0_bignum_mov(temp2, ctx->schnorr_g_to_s));
 570         sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
 571         if(sz > sizeof(shabuf))
 572                 sz = sizeof(shabuf);
 573         CHECK(d0_longhash_bignum(temp2, shabuf, sz));
 574         CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
 575
 576         // hash complete
 577         CHECK(d0_bignum_mod_mul(temp1, temp2, temp0, ctx->rsa_n));
 578         CHECK(d0_iobuf_write_bignum(out, temp1));
 579         return d0_iobuf_close(out, outbuflen);
 580
 581 fail:
 582         d0_iobuf_close(out, outbuflen);
 583         return 0;
 584 }
 585
 586 D0_WARN_UNUSED_RESULT D0_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)
 587 {
 588         d0_iobuf_t *in = NULL;
 589         d0_iobuf_t *out = NULL;
 590
 591         // temps: temp0 input, temp1 temp0^d
 592         USING(rsa_d); USING(rsa_n);
 593
 594         in = d0_iobuf_open_read(inbuf, inbuflen);
 595         out = d0_iobuf_open_write(outbuf, *outbuflen);
 596
 597         CHECK(d0_iobuf_read_bignum(in, temp0));
 598         CHECK(d0_bignum_mod_pow(temp1, temp0, ctx->rsa_d, ctx->rsa_n));
 599         CHECK(d0_iobuf_write_bignum(out, temp1));
 600
 601         d0_iobuf_close(in, NULL);
 602         return d0_iobuf_close(out, outbuflen);
 603
 604 fail:
 605         d0_iobuf_close(in, NULL);
 606         d0_iobuf_close(out, outbuflen);
 607         return 0;
 608 }
 609
 610 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_finish_private_id_request(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 611 {
 612         d0_iobuf_t *in = NULL;
 613
 614         // temps: temp0 input, temp1 rsa_blind_signature_camouflage^-1
 615         USING(rsa_blind_signature_camouflage); USING(rsa_n);
 616         REPLACING(schnorr_H_g_to_s_signature);
 617
 618         in = d0_iobuf_open_read(inbuf, inbuflen);
 619
 620         CHECK(d0_iobuf_read_bignum(in, temp0));
 621         CHECK(d0_bignum_mod_inv(temp1, ctx->rsa_blind_signature_camouflage, ctx->rsa_n));
 622         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));
 623
 624         return d0_iobuf_close(in, NULL);
 625
 626 fail:
 627         d0_iobuf_close(in, NULL);
 628         return 0;
 629 }
 630
 631 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_private_id_request_camouflage(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 632 {
 633         d0_iobuf_t *in = NULL;
 634
 635         REPLACING(rsa_blind_signature_camouflage);
 636
 637         in = d0_iobuf_open_read(inbuf, inbuflen);
 638
 639         CHECK_ASSIGN(ctx->rsa_blind_signature_camouflage, d0_iobuf_read_bignum(in, ctx->rsa_blind_signature_camouflage));
 640
 641         return d0_iobuf_close(in, NULL);
 642
 643 fail:
 644         d0_iobuf_close(in, NULL);
 645         return 0;
 646 }
 647
 648 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_private_id_request_camouflage(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 649 {
 650         d0_iobuf_t *out = NULL;
 651
 652         USING(rsa_blind_signature_camouflage);
 653
 654         out = d0_iobuf_open_write(outbuf, *outbuflen);
 655
 656         CHECK(d0_iobuf_write_bignum(out, ctx->rsa_blind_signature_camouflage));
 657
 658         return d0_iobuf_close(out, outbuflen);
 659
 660 fail:
 661         d0_iobuf_close(out, outbuflen);
 662         return 0;
 663 }
 664
 665 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_private_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 666 {
 667         d0_iobuf_t *in = NULL;
 668
 669         REPLACING(schnorr_s); REPLACING(schnorr_g_to_s); REPLACING(schnorr_H_g_to_s_signature);
 670
 671         in = d0_iobuf_open_read(inbuf, inbuflen);
 672
 673         CHECK_ASSIGN(ctx->schnorr_s, d0_iobuf_read_bignum(in, ctx->schnorr_s));
 674         CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_g_to_s));
 675         CHECK_ASSIGN(ctx->schnorr_H_g_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_g_to_s_signature));
 676
 677         return d0_iobuf_close(in, NULL);
 678
 679 fail:
 680         d0_iobuf_close(in, NULL);
 681         return 0;
 682 }
 683
 684 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_read_public_id(d0_blind_id_t *ctx, const char *inbuf, size_t inbuflen)
 685 {
 686         d0_iobuf_t *in = NULL;
 687
 688         REPLACING(schnorr_g_to_s); REPLACING(schnorr_H_g_to_s_signature);
 689
 690         in = d0_iobuf_open_read(inbuf, inbuflen);
 691
 692         CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_g_to_s));
 693         CHECK_ASSIGN(ctx->schnorr_H_g_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_g_to_s_signature));
 694
 695         return d0_iobuf_close(in, NULL);
 696
 697 fail:
 698         d0_iobuf_close(in, NULL);
 699         return 0;
 700 }
 701
 702 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_private_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 703 {
 704         d0_iobuf_t *out = NULL;
 705
 706         USING(schnorr_s); USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
 707
 708         out = d0_iobuf_open_write(outbuf, *outbuflen);
 709
 710         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_s));
 711         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_g_to_s));
 712         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_g_to_s_signature));
 713
 714         return d0_iobuf_close(out, outbuflen);
 715
 716 fail:
 717         d0_iobuf_close(out, outbuflen);
 718         return 0;
 719 }
 720
 721 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_write_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
 722 {
 723         d0_iobuf_t *out = NULL;
 724
 725         USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
 726
 727         out = d0_iobuf_open_write(outbuf, *outbuflen);
 728
 729         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_g_to_s));
 730         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_g_to_s_signature));
 731
 732         return d0_iobuf_close(out, outbuflen);
 733
 734 fail:
 735         d0_iobuf_close(out, outbuflen);
 736         return 0;
 737 }
 738
 739 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_authenticate_with_private_id_start(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL send_modulus, const char *msg, size_t msglen, char *outbuf, size_t *outbuflen)
 740 // start =
 741 //   first run: send 4^s, 4^s signature
 742 //   1. get random r, send HASH(4^r)
 743 {
 744         d0_iobuf_t *out = NULL;
 745         static unsigned char convbuf[1024];
 746         d0_iobuf_t *conv = NULL;
 747         size_t sz = 0;
 748         D0_BOOL failed = 0;
 749
 750         // temps: temp0 order, temp0 4^r
 751         if(is_first)
 752         {
 753                 USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
 754         }
 755         USING(schnorr_G);
 756         REPLACING(r); REPLACING(t); REPLACING(g_to_t);
 757
 758         out = d0_iobuf_open_write(outbuf, *outbuflen);
 759
 760         if(is_first)
 761         {
 762                 // send ID
 763                 if(send_modulus)
 764                         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
 765                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_g_to_s));
 766                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_g_to_s_signature));
 767         }
 768
 769         // start schnorr ID scheme
 770         // generate random number r; x = g^r; send hash of x, remember r, forget x
 771         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 772 #ifdef RNG_XKCD
 773         CHECK_ASSIGN(ctx->r, d0_bignum_int(ctx->r, 4)); // decided by fair dice roll
 774 #else
 775         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
 776 #endif
 777
 778         // initialize Signed Diffie Hellmann
 779         // we already have the group order in temp1
 780 #ifdef RNG_XKCD
 781         CHECK_ASSIGN(ctx->t, d0_bignum_int(ctx->t, 4)); // decided by fair dice roll
 782 #else
 783         CHECK_ASSIGN(ctx->t, d0_bignum_rand_range(ctx->t, zero, temp0));
 784 #endif
 785         // can we SOMEHOW do this with just one mod_pow?
 786
 787         CHECK(d0_bignum_mod_pow(temp0, four, ctx->r, ctx->schnorr_G));
 788         CHECK_ASSIGN(ctx->g_to_t, d0_bignum_mod_pow(ctx->g_to_t, four, ctx->t, ctx->schnorr_G));
 789         CHECK(!failed);
 790
 791         // hash it, hash it, everybody hash it
 792         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 793         CHECK(d0_iobuf_write_bignum(conv, temp0));
 794         CHECK(d0_iobuf_write_bignum(conv, ctx->g_to_t));
 795         CHECK(d0_iobuf_write_packet(conv, msg, msglen));
 796         CHECK(d0_iobuf_write_bignum(conv, temp0));
 797         CHECK(d0_iobuf_write_bignum(conv, ctx->g_to_t));
 798         d0_iobuf_close(conv, &sz);
 799         conv = NULL;
 800         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), SCHNORR_HASHSIZE) == SCHNORR_HASHSIZE);
 801         CHECK(d0_iobuf_write_packet(out, msg, msglen));
 802
 803         return d0_iobuf_close(out, outbuflen);
 804
 805 fail:
 806         d0_iobuf_close(out, outbuflen);
 807         return 0;
 808 }
 809
 810 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_authenticate_with_private_id_challenge(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL recv_modulus, const char *inbuf, size_t inbuflen, char *outbuf, size_t *outbuflen, D0_BOOL *status)
 811 //   first run: get 4^s, 4^s signature
 812 //   1. check sig
 813 //   2. save HASH(4^r)
 814 //   3. send challenge challenge of SCHNORR_BITS
 815 {
 816         d0_iobuf_t *in = NULL;
 817         d0_iobuf_t *out = NULL;
 818         static unsigned char shabuf[2048];
 819         size_t sz;
 820
 821         // temps: temp0 order, temp0 signature check
 822         if(is_first)
 823         {
 824                 REPLACING(schnorr_g_to_s); REPLACING(schnorr_H_g_to_s_signature);
 825                 if(recv_modulus)
 826                         REPLACING(schnorr_G);
 827                 else
 828                         USING(schnorr_G);
 829         }
 830         else
 831         {
 832                 USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
 833                 USING(schnorr_G);
 834         }
 835         USING(rsa_e); USING(rsa_n);
 836         REPLACING(challenge); REPLACING(msg); REPLACING(msglen); REPLACING(msghash); REPLACING(r); REPLACING(t);
 837
 838         in = d0_iobuf_open_read(inbuf, inbuflen);
 839         out = d0_iobuf_open_write(outbuf, *outbuflen);
 840
 841         if(is_first)
 842         {
 843                 if(recv_modulus)
 844                 {
 845                         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
 846                         CHECK(d0_bignum_cmp(ctx->schnorr_G, zero) > 0);
 847                         CHECK(d0_bignum_cmp(ctx->schnorr_G, ctx->rsa_n) < 0);
 848                 }
 849                 CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_g_to_s));
 850                 CHECK(d0_bignum_cmp(ctx->schnorr_g_to_s, zero) >= 0);
 851                 CHECK(d0_bignum_cmp(ctx->schnorr_g_to_s, ctx->schnorr_G) < 0);
 852                 CHECK_ASSIGN(ctx->schnorr_H_g_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_g_to_s_signature));
 853                 CHECK(d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, zero) >= 0);
 854                 CHECK(d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, ctx->rsa_n) < 0);
 855
 856                 // check signature of key (t = k^d, so, t^challenge = k)
 857                 CHECK(d0_bignum_mod_pow(temp0, ctx->schnorr_H_g_to_s_signature, ctx->rsa_e, ctx->rsa_n));
 858
 859                 // we will actually sign SHA(4^s) to prevent a malleability attack!
 860                 CHECK(d0_bignum_mov(temp2, ctx->schnorr_g_to_s));
 861                 sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
 862                 if(sz > sizeof(shabuf))
 863                         sz = sizeof(shabuf);
 864                 CHECK(d0_longhash_bignum(temp2, shabuf, sz));
 865                 CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
 866
 867                 // + 7 / 8 is too large, so let's mod it
 868                 CHECK(d0_bignum_divmod(NULL, temp1, temp2, ctx->rsa_n));
 869
 870                 // hash complete
 871                 if(d0_bignum_cmp(temp0, temp1))
 872                 {
 873                         // accept the key anyway, but mark as failed signature! will later return 0 in status
 874                         CHECK(d0_bignum_zero(ctx->schnorr_H_g_to_s_signature));
 875                 }
 876         }
 877
 878         CHECK(d0_iobuf_read_raw(in, ctx->msghash, SCHNORR_HASHSIZE));
 879         ctx->msglen = MSGSIZE;
 880         CHECK(d0_iobuf_read_packet(in, ctx->msg, &ctx->msglen));
 881
 882         // send challenge
 883 #ifdef RNG_XKCD
 884         CHECK_ASSIGN(ctx->challenge, d0_bignum_int(ctx->challenge, 4)); // decided by fair dice roll
 885 #else
 886         CHECK_ASSIGN(ctx->challenge, d0_bignum_rand_bit_atmost(ctx->challenge, SCHNORR_BITS));
 887 #endif
 888         CHECK(d0_iobuf_write_bignum(out, ctx->challenge));
 889
 890         // Diffie Hellmann send
 891         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 892 #ifdef RNG_XKCD
 893         CHECK_ASSIGN(ctx->t, d0_bignum_int(ctx->t, 4)); // decided by fair dice roll
 894 #else
 895         CHECK_ASSIGN(ctx->t, d0_bignum_rand_range(ctx->t, zero, temp0));
 896 #endif
 897         CHECK(d0_bignum_mod_pow(temp0, four, ctx->t, ctx->schnorr_G));
 898         CHECK(d0_iobuf_write_bignum(out, temp0));
 899
 900         if(status)
 901                 *status = !!d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, zero);
 902
 903         d0_iobuf_close(in, NULL);
 904         return d0_iobuf_close(out, outbuflen);
 905
 906 fail:
 907         d0_iobuf_close(in, NULL);
 908         d0_iobuf_close(out, outbuflen);
 909         return 0;
 910 }
 911
 912 D0_WARN_UNUSED_RESULT D0_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)
 913 //   1. read challenge challenge of SCHNORR_BITS
 914 //   2. reply with r + s * challenge mod order
 915 {
 916         d0_iobuf_t *in = NULL;
 917         d0_iobuf_t *out = NULL;
 918
 919         // temps: 0 order, 1 prod, 2 y, 3 challenge
 920         REPLACING(other_g_to_t); REPLACING(t);
 921         USING(schnorr_G); USING(schnorr_s); USING(r); USING(g_to_t);
 922
 923         in = d0_iobuf_open_read(inbuf, inbuflen);
 924         out = d0_iobuf_open_write(outbuf, *outbuflen);
 925
 926         CHECK(d0_iobuf_read_bignum(in, temp3));
 927         CHECK(d0_bignum_cmp(temp3, zero) >= 0);
 928         CHECK(d0_bignum_size(temp3) <= SCHNORR_BITS);
 929
 930         // send response for schnorr ID scheme
 931         // i.challenge. r + ctx->schnorr_s * temp3
 932         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
 933         CHECK(d0_bignum_mod_mul(temp1, ctx->schnorr_s, temp3, temp0));
 934 #ifdef D0_BLIND_ID_POSITIVE_PROTOCOL
 935         CHECK(d0_bignum_mod_add(temp2, ctx->r, temp1, temp0));
 936 #else
 937         CHECK(d0_bignum_mod_sub(temp2, ctx->r, temp1, temp0));
 938 #endif
 939         CHECK(d0_iobuf_write_bignum(out, temp2));
 940
 941         // Diffie Hellmann recv
 942         CHECK_ASSIGN(ctx->other_g_to_t, d0_iobuf_read_bignum(in, ctx->other_g_to_t));
 943         CHECK(d0_bignum_cmp(ctx->other_g_to_t, zero) > 0);
 944         CHECK(d0_bignum_cmp(ctx->other_g_to_t, ctx->schnorr_G) < 0);
 945         // Diffie Hellmann send
 946         CHECK(d0_iobuf_write_bignum(out, ctx->g_to_t));
 947
 948         d0_iobuf_close(in, NULL);
 949         return d0_iobuf_close(out, outbuflen);
 950
 951 fail:
 952         d0_iobuf_close(in, NULL);
 953         d0_iobuf_close(out, outbuflen);
 954         return 0;
 955 }
 956
 957 D0_WARN_UNUSED_RESULT D0_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, D0_BOOL *status)
 958 //   1. read y = r + s * challenge mod order
 959 //   2. verify: g^y (g^s)^-challenge = g^(r+s*challenge-s*challenge) = g^r
 960 //      (check using H(g^r) which we know)
 961 {
 962         d0_iobuf_t *in = NULL;
 963         static unsigned char convbuf[1024];
 964         d0_iobuf_t *conv = NULL;
 965         size_t sz;
 966
 967         // temps: 0 y 1 order
 968         USING(challenge); USING(schnorr_G);
 969         REPLACING(other_g_to_t);
 970
 971         in = d0_iobuf_open_read(inbuf, inbuflen);
 972
 973         CHECK(d0_dl_get_order(temp1, ctx->schnorr_G));
 974         CHECK(d0_iobuf_read_bignum(in, temp0));
 975         CHECK(d0_bignum_cmp(temp0, zero) >= 0);
 976         CHECK(d0_bignum_cmp(temp0, temp1) < 0);
 977
 978         // verify schnorr ID scheme
 979 #ifdef D0_BLIND_ID_POSITIVE_PROTOCOL
 980         // we need 4^r = 4^temp0 (g^s)^-challenge
 981         CHECK(d0_bignum_mod_inv(temp1, ctx->schnorr_g_to_s, ctx->schnorr_G));
 982         CHECK(d0_bignum_mod_pow(temp2, temp1, ctx->challenge, ctx->schnorr_G));
 983 #else
 984         // we need 4^r = 4^temp0 (g^s)^challenge
 985         CHECK(d0_bignum_mod_pow(temp2, ctx->schnorr_g_to_s, ctx->challenge, ctx->schnorr_G));
 986 #endif
 987         CHECK(d0_bignum_mod_pow(temp1, four, temp0, ctx->schnorr_G));
 988         CHECK_ASSIGN(temp3, d0_bignum_mod_mul(temp3, temp1, temp2, ctx->schnorr_G));
 989
 990         // Diffie Hellmann recv
 991         CHECK_ASSIGN(ctx->other_g_to_t, d0_iobuf_read_bignum(in, ctx->other_g_to_t));
 992         CHECK(d0_bignum_cmp(ctx->other_g_to_t, zero) > 0);
 993         CHECK(d0_bignum_cmp(ctx->other_g_to_t, ctx->schnorr_G) < 0);
 994
 995         // hash it, hash it, everybody hash it
 996         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
 997         CHECK(d0_iobuf_write_bignum(conv, temp3));
 998         CHECK(d0_iobuf_write_bignum(conv, ctx->other_g_to_t));
 999         CHECK(d0_iobuf_write_packet(conv, ctx->msg, ctx->msglen));
1000         CHECK(d0_iobuf_write_bignum(conv, temp3));
1001         CHECK(d0_iobuf_write_bignum(conv, ctx->other_g_to_t));
1002         d0_iobuf_close(conv, &sz);
1003         conv = NULL;
1004         if(memcmp(sha(convbuf, sz), ctx->msghash, SCHNORR_HASHSIZE))
1005         {
1006                 // FAIL (not owned by player)
1007                 goto fail;
1008         }
1009
1010         if(status)
1011                 *status = !!d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, zero);
1012
1013         if(ctx->msglen <= *msglen)
1014                 memcpy(msg, ctx->msg, ctx->msglen);
1015         else
1016                 memcpy(msg, ctx->msg, *msglen);
1017         *msglen = ctx->msglen;
1018
1019         d0_iobuf_close(in, NULL);
1020         return 1;
1021
1022 fail:
1023         d0_iobuf_close(in, NULL);
1024         return 0;
1025 }
1026
1027 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_authenticate_with_private_id_generate_missing_signature(d0_blind_id_t *ctx)
1028 {
1029         size_t sz;
1030         static unsigned char shabuf[2048];
1031
1032         REPLACING(schnorr_H_g_to_s_signature);
1033         USING(schnorr_g_to_s); USING(rsa_d); USING(rsa_n);
1034
1035         // we will actually sign SHA(4^s) to prevent a malleability attack!
1036         CHECK(d0_bignum_mov(temp2, ctx->schnorr_g_to_s));
1037         sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
1038         if(sz > sizeof(shabuf))
1039                 sz = sizeof(shabuf);
1040         CHECK(d0_longhash_bignum(temp2, shabuf, sz));
1041         CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
1042
1043         // + 7 / 8 is too large, so let's mod it
1044         CHECK(d0_bignum_divmod(NULL, temp1, temp2, ctx->rsa_n));
1045         CHECK(d0_bignum_mod_pow(ctx->schnorr_H_g_to_s_signature, temp1, ctx->rsa_d, ctx->rsa_n));
1046         return 1;
1047
1048 fail:
1049         return 0;
1050 }
1051
1052 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_sign_internal(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL send_modulus, D0_BOOL with_msg, const char *message, size_t msglen, char *outbuf, size_t *outbuflen)
1053 {
1054         d0_iobuf_t *out = NULL;
1055         static unsigned char convbuf[1024];
1056         static unsigned char shabuf[1024];
1057         d0_iobuf_t *conv = NULL;
1058         size_t sz = 0;
1059
1060         if(is_first)
1061         {
1062                 USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
1063         }
1064         USING(schnorr_G);
1065         USING(schnorr_s);
1066         REPLACING(r);
1067
1068         out = d0_iobuf_open_write(outbuf, *outbuflen);
1069
1070         if(is_first)
1071         {
1072                 // send ID
1073                 if(send_modulus)
1074                         CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_G));
1075                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_g_to_s));
1076                 CHECK(d0_iobuf_write_bignum(out, ctx->schnorr_H_g_to_s_signature));
1077         }
1078
1079         // start schnorr SIGNATURE scheme
1080         // generate random number r; x = g^r; send hash of H(m||r), remember r, forget x
1081         CHECK(d0_dl_get_order(temp0, ctx->schnorr_G));
1082         CHECK_ASSIGN(ctx->r, d0_bignum_rand_range(ctx->r, zero, temp0));
1083         CHECK(d0_bignum_mod_pow(temp1, four, ctx->r, ctx->schnorr_G));
1084
1085         // hash it, hash it, everybody hash it
1086         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
1087         CHECK(d0_iobuf_write_packet(conv, message, msglen));
1088         CHECK(d0_iobuf_write_bignum(conv, temp1));
1089         d0_iobuf_close(conv, &sz);
1090         conv = NULL;
1091         CHECK(d0_longhash_destructive(convbuf, sz, shabuf, (d0_bignum_size(temp0) + 7) / 8));
1092         CHECK(d0_bignum_import_unsigned(temp2, shabuf, (d0_bignum_size(temp0) + 7) / 8));
1093         CHECK(d0_iobuf_write_bignum(out, temp2));
1094
1095         // multiply with secret, sub k, modulo order
1096         CHECK(d0_bignum_mod_mul(temp1, temp2, ctx->schnorr_s, temp0));
1097 #ifdef D0_BLIND_ID_POSITIVE_PROTOCOL
1098         CHECK(d0_bignum_mod_add(temp2, ctx->r, temp1, temp0));
1099 #else
1100         CHECK(d0_bignum_mod_sub(temp2, ctx->r, temp1, temp0));
1101 #endif
1102         CHECK(d0_iobuf_write_bignum(out, temp2));
1103
1104         // write the message itself
1105         if(with_msg)
1106                 CHECK(d0_iobuf_write_packet(out, message, msglen));
1107
1108         return d0_iobuf_close(out, outbuflen);
1109
1110 fail:
1111         d0_iobuf_close(out, outbuflen);
1112         return 0;
1113 }
1114 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_sign(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL send_modulus, const char *message, size_t msglen, char *outbuf, size_t *outbuflen)
1115 {
1116         return d0_blind_id_sign_with_private_id_sign_internal(ctx, is_first, send_modulus, 1, message, msglen, outbuf, outbuflen);
1117 }
1118 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_sign_detached(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL send_modulus, const char *message, size_t msglen, char *outbuf, size_t *outbuflen)
1119 {
1120         return d0_blind_id_sign_with_private_id_sign_internal(ctx, is_first, send_modulus, 0, message, msglen, outbuf, outbuflen);
1121 }
1122
1123 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_verify_internal(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL recv_modulus, D0_BOOL with_msg, const char *inbuf, size_t inbuflen, char *msg, size_t *msglen, D0_BOOL *status)
1124 {
1125         d0_iobuf_t *in = NULL;
1126         d0_iobuf_t *conv = NULL;
1127         static unsigned char convbuf[2048];
1128         static unsigned char shabuf[2048];
1129         size_t sz;
1130
1131         if(is_first)
1132         {
1133                 REPLACING(schnorr_g_to_s); REPLACING(schnorr_H_g_to_s_signature);
1134                 if(recv_modulus)
1135                         REPLACING(schnorr_G);
1136                 else
1137                         USING(schnorr_G);
1138         }
1139         else
1140         {
1141                 USING(schnorr_g_to_s); USING(schnorr_H_g_to_s_signature);
1142                 USING(schnorr_G);
1143         }
1144         USING(rsa_e); USING(rsa_n);
1145
1146         in = d0_iobuf_open_read(inbuf, inbuflen);
1147
1148         if(is_first)
1149         {
1150                 if(recv_modulus)
1151                 {
1152                         CHECK_ASSIGN(ctx->schnorr_G, d0_iobuf_read_bignum(in, ctx->schnorr_G));
1153                         CHECK(d0_bignum_cmp(ctx->schnorr_G, zero) > 0);
1154                         CHECK(d0_bignum_cmp(ctx->schnorr_G, ctx->rsa_n) < 0);
1155                 }
1156                 CHECK_ASSIGN(ctx->schnorr_g_to_s, d0_iobuf_read_bignum(in, ctx->schnorr_g_to_s));
1157                 CHECK(d0_bignum_cmp(ctx->schnorr_g_to_s, zero) >= 0);
1158                 CHECK(d0_bignum_cmp(ctx->schnorr_g_to_s, ctx->schnorr_G) < 0);
1159                 CHECK_ASSIGN(ctx->schnorr_H_g_to_s_signature, d0_iobuf_read_bignum(in, ctx->schnorr_H_g_to_s_signature));
1160                 CHECK(d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, zero) >= 0);
1161                 CHECK(d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, ctx->rsa_n) < 0);
1162
1163                 // check signature of key (t = k^d, so, t^challenge = k)
1164                 CHECK(d0_bignum_mod_pow(temp0, ctx->schnorr_H_g_to_s_signature, ctx->rsa_e, ctx->rsa_n));
1165
1166                 // we will actually sign SHA(4^s) to prevent a malleability attack!
1167                 CHECK(d0_bignum_mov(temp2, ctx->schnorr_g_to_s));
1168                 sz = (d0_bignum_size(ctx->rsa_n) + 7) / 8; // this is too long, so we have to take the value % rsa_n when "decrypting"
1169                 if(sz > sizeof(shabuf))
1170                         sz = sizeof(shabuf);
1171                 CHECK(d0_longhash_bignum(temp2, shabuf, sz));
1172                 CHECK(d0_bignum_import_unsigned(temp2, shabuf, sz));
1173
1174                 // + 7 / 8 is too large, so let's mod it
1175                 CHECK(d0_bignum_divmod(NULL, temp1, temp2, ctx->rsa_n));
1176
1177                 // hash complete
1178                 if(d0_bignum_cmp(temp0, temp1))
1179                 {
1180                         // accept the key anyway, but mark as failed signature! will later return 0 in status
1181                         CHECK(d0_bignum_zero(ctx->schnorr_H_g_to_s_signature));
1182                 }
1183         }
1184
1185         CHECK(d0_dl_get_order(temp4, ctx->schnorr_G));
1186         CHECK(d0_iobuf_read_bignum(in, temp0)); // e == H(m || g^r)
1187         CHECK(d0_iobuf_read_bignum(in, temp1)); // x == (r - s*e) mod |G|
1188         if(with_msg)
1189                 CHECK(d0_iobuf_read_packet(in, msg, msglen));
1190
1191         // VERIFY: g^x * (g^s)^-e = g^(x - s*e) = g^r
1192
1193         // verify schnorr ID scheme
1194         // we need g^r = g^x (g^s)^e
1195         CHECK(d0_bignum_mod_pow(temp2, four, temp1, ctx->schnorr_G));
1196 #ifdef D0_BLIND_ID_POSITIVE_PROTOCOL
1197         CHECK(d0_bignum_mod_inv(temp3, ctx->schnorr_g_to_s, ctx->schnorr_G));
1198         CHECK(d0_bignum_mod_pow(temp1, temp3, temp0, ctx->schnorr_G));
1199 #else
1200         CHECK(d0_bignum_mod_pow(temp1, ctx->schnorr_g_to_s, temp0, ctx->schnorr_G));
1201 #endif
1202         CHECK_ASSIGN(temp3, d0_bignum_mod_mul(temp3, temp1, temp2, ctx->schnorr_G)); // temp3 now is g^r
1203
1204         // hash it, hash it, everybody hash it
1205         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
1206         CHECK(d0_iobuf_write_packet(conv, msg, *msglen));
1207         CHECK(d0_iobuf_write_bignum(conv, temp3));
1208         d0_iobuf_close(conv, &sz);
1209         conv = NULL;
1210         CHECK(d0_longhash_destructive(convbuf, sz, shabuf, (d0_bignum_size(temp4) + 7) / 8));
1211         CHECK(d0_bignum_import_unsigned(temp1, shabuf, (d0_bignum_size(temp4) + 7) / 8));
1212
1213         // verify signature
1214         CHECK(!d0_bignum_cmp(temp0, temp1));
1215
1216         if(status)
1217                 *status = !!d0_bignum_cmp(ctx->schnorr_H_g_to_s_signature, zero);
1218
1219         d0_iobuf_close(in, NULL);
1220         return 1;
1221
1222 fail:
1223         d0_iobuf_close(in, NULL);
1224         return 0;
1225 }
1226 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_verify(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL recv_modulus, const char *inbuf, size_t inbuflen, char *msg, size_t *msglen, D0_BOOL *status)
1227 {
1228         return d0_blind_id_sign_with_private_id_verify_internal(ctx, is_first, recv_modulus, 1, inbuf, inbuflen, msg, msglen, status);
1229 }
1230 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_sign_with_private_id_verify_detached(d0_blind_id_t *ctx, D0_BOOL is_first, D0_BOOL recv_modulus, const char *inbuf, size_t inbuflen, const char *msg, size_t msglen, D0_BOOL *status)
1231 {
1232         return d0_blind_id_sign_with_private_id_verify_internal(ctx, is_first, recv_modulus, 0, inbuf, inbuflen, (char *) msg, &msglen, status);
1233 }
1234
1235 D0_WARN_UNUSED_RESULT D0_BOOL d0_blind_id_fingerprint64_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
1236 {
1237         d0_iobuf_t *out = NULL;
1238         static unsigned char convbuf[1024];
1239         d0_iobuf_t *conv = NULL;
1240         size_t sz, n;
1241
1242         USING(rsa_n);
1243         USING(rsa_e);
1244         USING(schnorr_g_to_s);
1245
1246         out = d0_iobuf_open_write(outbuf, *outbuflen);
1247         conv = d0_iobuf_open_write(convbuf, sizeof(convbuf));
1248
1249         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_n));
1250         CHECK(d0_iobuf_write_bignum(conv, ctx->rsa_e));
1251         CHECK(d0_iobuf_write_bignum(conv, ctx->schnorr_g_to_s));
1252         CHECK(d0_iobuf_close(conv, &sz));
1253         conv = NULL;
1254
1255         n = (*outbuflen / 4) * 3;
1256         if(n > SHA_DIGESTSIZE)
1257                 n = SHA_DIGESTSIZE;
1258         CHECK(d0_iobuf_write_raw(out, sha(convbuf, sz), n) == n);
1259         CHECK(d0_iobuf_conv_base64_out(out));
1260
1261         return d0_iobuf_close(out, outbuflen);
1262
1263 fail:
1264         if(conv)
1265                 d0_iobuf_close(conv, &sz);
1266         d0_iobuf_close(out, outbuflen);
1267         return 0;
1268 }
1269
1270 D0_BOOL d0_blind_id_sessionkey_public_id(const d0_blind_id_t *ctx, char *outbuf, size_t *outbuflen)
1271 {
1272         USING(t); USING(other_g_to_t); USING(schnorr_G);
1273
1274         // temps: temp0 result
1275         CHECK(d0_bignum_mod_pow(temp0, ctx->other_g_to_t, ctx->t, ctx->schnorr_G));
1276         return d0_longhash_bignum(temp0, (unsigned char *) outbuf, *outbuflen);
1277
1278 fail:
1279         return 0;
1280 }
1281
1282 d0_blind_id_t *d0_blind_id_new(void)
1283 {
1284         d0_blind_id_t *b = d0_malloc(sizeof(d0_blind_id_t));
1285         memset(b, 0, sizeof(*b));
1286         return b;
1287 }
1288
1289 void d0_blind_id_free(d0_blind_id_t *a)
1290 {
1291         d0_blind_id_clear(a);
1292         d0_free(a);
1293 }
1294
1295 void d0_blind_id_util_sha256(char *out, const char *in, size_t n)
1296 {
1297         SHA256_CTX context;
1298         SHA256_Init(&context);
1299         SHA256_Update(&context, (const unsigned char *) in, n);
1300         return SHA256_Final((unsigned char *) out, &context);
1301 }