crypto/openssl/demos/jpake/jpakedemo.c

   1 #include "openssl/bn.h"
   2 #include "openssl/sha.h"
   3 #include <assert.h>
   4 #include <string.h>
   5 #include <stdlib.h>
   6
   7 /* Copyright (C) 2008 Ben Laurie (ben@links.org) */
   8
   9 /*
  10  * Implement J-PAKE, as described in
  11  * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
  12  *
  13  * With hints from http://www.cl.cam.ac.uk/~fh240/software/JPAKE2.java.
  14  */
  15
  16 static void showbn(const char *name, const BIGNUM *bn)
  17 {
  18     fputs(name, stdout);
  19     fputs(" = ", stdout);
  20     BN_print_fp(stdout, bn);
  21     putc('\n', stdout);
  22 }
  23
  24 typedef struct {
  25     BN_CTX *ctx;                // Perhaps not the best place for this?
  26     BIGNUM *p;
  27     BIGNUM *q;
  28     BIGNUM *g;
  29 } JPakeParameters;
  30
  31 static void JPakeParametersInit(JPakeParameters * params)
  32 {
  33     params->ctx = BN_CTX_new();
  34
  35     // For now use p, q, g from Java sample code. Later, generate them.
  36     params->p = NULL;
  37     BN_hex2bn(&params->p,
  38               "fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b6512669455d402251fb593d8d58fabfc5f5ba30f6cb9b556cd7813b801d346ff26660b76b9950a5a49f9fe8047b1022c24fbba9d7feb7c61bf83b57e7c6a8a6150f04fb83f6d3c51ec3023554135a169132f675f3ae2b61d72aeff22203199dd14801c7");
  39     params->q = NULL;
  40     BN_hex2bn(&params->q, "9760508f15230bccb292b982a2eb840bf0581cf5");
  41     params->g = NULL;
  42     BN_hex2bn(&params->g,
  43               "f7e1a085d69b3ddecbbcab5c36b857b97994afbbfa3aea82f9574c0b3d0782675159578ebad4594fe67107108180b449167123e84c281613b7cf09328cc8a6e13c167a8b547c8d28e0a3ae1e2bb3a675916ea37f0bfa213562f1fb627a01243bcca4f1bea8519089a883dfe15ae59f06928b665e807b552564014c3bfecf492a");
  44
  45     showbn("p", params->p);
  46     showbn("q", params->q);
  47     showbn("g", params->g);
  48 }
  49
  50 typedef struct {
  51     BIGNUM *gr;                 // g^r (r random)
  52     BIGNUM *b;                  // b = r - x*h, h=hash(g, g^r, g^x, name)
  53 } JPakeZKP;
  54
  55 typedef struct {
  56     BIGNUM *gx;                 // g^x
  57     JPakeZKP zkpx;              // ZKP(x)
  58 } JPakeStep1;
  59
  60 typedef struct {
  61     BIGNUM *X;                  // g^(xa + xc + xd) * xb * s
  62     JPakeZKP zkpxbs;            // ZKP(xb * s)
  63 } JPakeStep2;
  64
  65 typedef struct {
  66     const char *name;           // Must be unique
  67     int base;                   // 1 for Alice, 3 for Bob. Only used for
  68     // printing stuff.
  69     JPakeStep1 s1c;             // Alice's g^x3, ZKP(x3) or Bob's g^x1,
  70     // ZKP(x1)
  71     JPakeStep1 s1d;             // Alice's g^x4, ZKP(x4) or Bob's g^x2,
  72     // ZKP(x2)
  73     JPakeStep2 s2;              // Alice's A, ZKP(x2 * s) or Bob's B, ZKP(x4
  74     // * s)
  75 } JPakeUserPublic;
  76
  77 /*
  78  * The user structure. In the definition, (xa, xb, xc, xd) are Alice's
  79  * (x1, x2, x3, x4) or Bob's (x3, x4, x1, x2). If you see what I mean.
  80  */
  81 typedef struct {
  82     JPakeUserPublic p;
  83     BIGNUM *secret;             // The shared secret
  84     BIGNUM *key;                // The calculated (shared) key
  85     BIGNUM *xa;                 // Alice's x1 or Bob's x3
  86     BIGNUM *xb;                 // Alice's x2 or Bob's x4
  87 } JPakeUser;
  88
  89 // Generate each party's random numbers. xa is in [0, q), xb is in [1, q).
  90 static void genrand(JPakeUser * user, const JPakeParameters * params)
  91 {
  92     BIGNUM *qm1;
  93
  94     // xa in [0, q)
  95     user->xa = BN_new();
  96     BN_rand_range(user->xa, params->q);
  97
  98     // q-1
  99     qm1 = BN_new();
 100     BN_copy(qm1, params->q);
 101     BN_sub_word(qm1, 1);
 102
 103     // ... and xb in [0, q-1)
 104     user->xb = BN_new();
 105     BN_rand_range(user->xb, qm1);
 106     // [1, q)
 107     BN_add_word(user->xb, 1);
 108
 109     // cleanup
 110     BN_free(qm1);
 111
 112     // Show
 113     printf("x%d", user->p.base);
 114     showbn("", user->xa);
 115     printf("x%d", user->p.base + 1);
 116     showbn("", user->xb);
 117 }
 118
 119 static void hashlength(SHA_CTX *sha, size_t l)
 120 {
 121     unsigned char b[2];
 122
 123     assert(l <= 0xffff);
 124     b[0] = l >> 8;
 125     b[1] = l & 0xff;
 126     SHA1_Update(sha, b, 2);
 127 }
 128
 129 static void hashstring(SHA_CTX *sha, const char *string)
 130 {
 131     size_t l = strlen(string);
 132
 133     hashlength(sha, l);
 134     SHA1_Update(sha, string, l);
 135 }
 136
 137 static void hashbn(SHA_CTX *sha, const BIGNUM *bn)
 138 {
 139     size_t l = BN_num_bytes(bn);
 140     unsigned char *bin = alloca(l);
 141
 142     hashlength(sha, l);
 143     BN_bn2bin(bn, bin);
 144     SHA1_Update(sha, bin, l);
 145 }
 146
 147 // h=hash(g, g^r, g^x, name)
 148 static void zkpHash(BIGNUM *h, const JPakeZKP * zkp, const BIGNUM *gx,
 149                     const JPakeUserPublic * from,
 150                     const JPakeParameters * params)
 151 {
 152     unsigned char md[SHA_DIGEST_LENGTH];
 153     SHA_CTX sha;
 154
 155     // XXX: hash should not allow moving of the boundaries - Java code
 156     // is flawed in this respect. Length encoding seems simplest.
 157     SHA1_Init(&sha);
 158     hashbn(&sha, params->g);
 159     hashbn(&sha, zkp->gr);
 160     hashbn(&sha, gx);
 161     hashstring(&sha, from->name);
 162     SHA1_Final(md, &sha);
 163     BN_bin2bn(md, SHA_DIGEST_LENGTH, h);
 164 }
 165
 166 // Prove knowledge of x
 167 // Note that we don't send g^x because, as it happens, we've always
 168 // sent it elsewhere. Also note that because of that, we could avoid
 169 // calculating it here, but we don't, for clarity...
 170 static void CreateZKP(JPakeZKP * zkp, const BIGNUM *x, const JPakeUser * us,
 171                       const BIGNUM *zkpg, const JPakeParameters * params,
 172                       int n, const char *suffix)
 173 {
 174     BIGNUM *r = BN_new();
 175     BIGNUM *gx = BN_new();
 176     BIGNUM *h = BN_new();
 177     BIGNUM *t = BN_new();
 178
 179     // r in [0,q)
 180     // XXX: Java chooses r in [0, 2^160) - i.e. distribution not uniform
 181     BN_rand_range(r, params->q);
 182     // g^r
 183     zkp->gr = BN_new();
 184     BN_mod_exp(zkp->gr, zkpg, r, params->p, params->ctx);
 185     // g^x
 186     BN_mod_exp(gx, zkpg, x, params->p, params->ctx);
 187
 188     // h=hash...
 189     zkpHash(h, zkp, gx, &us->p, params);
 190
 191     // b = r - x*h
 192     BN_mod_mul(t, x, h, params->q, params->ctx);
 193     zkp->b = BN_new();
 194     BN_mod_sub(zkp->b, r, t, params->q, params->ctx);
 195
 196     // show
 197     printf("  ZKP(x%d%s)\n", n, suffix);
 198     showbn("   zkpg", zkpg);
 199     showbn("    g^x", gx);
 200     showbn("    g^r", zkp->gr);
 201     showbn("      b", zkp->b);
 202
 203     // cleanup
 204     BN_free(t);
 205     BN_free(h);
 206     BN_free(gx);
 207     BN_free(r);
 208 }
 209
 210 static int VerifyZKP(const JPakeZKP * zkp, BIGNUM *gx,
 211                      const JPakeUserPublic * them, const BIGNUM *zkpg,
 212                      const JPakeParameters * params, int n,
 213                      const char *suffix)
 214 {
 215     BIGNUM *h = BN_new();
 216     BIGNUM *t1 = BN_new();
 217     BIGNUM *t2 = BN_new();
 218     BIGNUM *t3 = BN_new();
 219     int ret = 0;
 220
 221     zkpHash(h, zkp, gx, them, params);
 222
 223     // t1 = g^b
 224     BN_mod_exp(t1, zkpg, zkp->b, params->p, params->ctx);
 225     // t2 = (g^x)^h = g^{hx}
 226     BN_mod_exp(t2, gx, h, params->p, params->ctx);
 227     // t3 = t1 * t2 = g^{hx} * g^b = g^{hx+b} = g^r (allegedly)
 228     BN_mod_mul(t3, t1, t2, params->p, params->ctx);
 229
 230     printf("  ZKP(x%d%s)\n", n, suffix);
 231     showbn("    zkpg", zkpg);
 232     showbn("    g^r'", t3);
 233
 234     // verify t3 == g^r
 235     if (BN_cmp(t3, zkp->gr) == 0)
 236         ret = 1;
 237
 238     // cleanup
 239     BN_free(t3);
 240     BN_free(t2);
 241     BN_free(t1);
 242     BN_free(h);
 243
 244     if (ret)
 245         puts("    OK");
 246     else
 247         puts("    FAIL");
 248
 249     return ret;
 250 }
 251
 252 static void sendstep1_substep(JPakeStep1 * s1, const BIGNUM *x,
 253                               const JPakeUser * us,
 254                               const JPakeParameters * params, int n)
 255 {
 256     s1->gx = BN_new();
 257     BN_mod_exp(s1->gx, params->g, x, params->p, params->ctx);
 258     printf("  g^{x%d}", n);
 259     showbn("", s1->gx);
 260
 261     CreateZKP(&s1->zkpx, x, us, params->g, params, n, "");
 262 }
 263
 264 static void sendstep1(const JPakeUser * us, JPakeUserPublic * them,
 265                       const JPakeParameters * params)
 266 {
 267     printf("\n%s sends %s:\n\n", us->p.name, them->name);
 268
 269     // from's g^xa (which becomes to's g^xc) and ZKP(xa)
 270     sendstep1_substep(&them->s1c, us->xa, us, params, us->p.base);
 271     // from's g^xb (which becomes to's g^xd) and ZKP(xb)
 272     sendstep1_substep(&them->s1d, us->xb, us, params, us->p.base + 1);
 273 }
 274
 275 static int verifystep1(const JPakeUser * us, const JPakeUserPublic * them,
 276                        const JPakeParameters * params)
 277 {
 278     printf("\n%s verifies %s:\n\n", us->p.name, them->name);
 279
 280     // verify their ZKP(xc)
 281     if (!VerifyZKP(&us->p.s1c.zkpx, us->p.s1c.gx, them, params->g, params,
 282                    them->base, ""))
 283         return 0;
 284
 285     // verify their ZKP(xd)
 286     if (!VerifyZKP(&us->p.s1d.zkpx, us->p.s1d.gx, them, params->g, params,
 287                    them->base + 1, ""))
 288         return 0;
 289
 290     // g^xd != 1
 291     printf("  g^{x%d} != 1: ", them->base + 1);
 292     if (BN_is_one(us->p.s1d.gx)) {
 293         puts("FAIL");
 294         return 0;
 295     }
 296     puts("OK");
 297
 298     return 1;
 299 }
 300
 301 static void sendstep2(const JPakeUser * us, JPakeUserPublic * them,
 302                       const JPakeParameters * params)
 303 {
 304     BIGNUM *t1 = BN_new();
 305     BIGNUM *t2 = BN_new();
 306
 307     printf("\n%s sends %s:\n\n", us->p.name, them->name);
 308
 309     // X = g^{(xa + xc + xd) * xb * s}
 310     // t1 = g^xa
 311     BN_mod_exp(t1, params->g, us->xa, params->p, params->ctx);
 312     // t2 = t1 * g^{xc} = g^{xa} * g^{xc} = g^{xa + xc}
 313     BN_mod_mul(t2, t1, us->p.s1c.gx, params->p, params->ctx);
 314     // t1 = t2 * g^{xd} = g^{xa + xc + xd}
 315     BN_mod_mul(t1, t2, us->p.s1d.gx, params->p, params->ctx);
 316     // t2 = xb * s
 317     BN_mod_mul(t2, us->xb, us->secret, params->q, params->ctx);
 318     // X = t1^{t2} = t1^{xb * s} = g^{(xa + xc + xd) * xb * s}
 319     them->s2.X = BN_new();
 320     BN_mod_exp(them->s2.X, t1, t2, params->p, params->ctx);
 321
 322     // Show
 323     printf("  g^{(x%d + x%d + x%d) * x%d * s)", us->p.base, them->base,
 324            them->base + 1, us->p.base + 1);
 325     showbn("", them->s2.X);
 326
 327     // ZKP(xb * s)
 328     // XXX: this is kinda funky, because we're using
 329     //
 330     // g' = g^{xa + xc + xd}
 331     //
 332     // as the generator, which means X is g'^{xb * s}
 333     CreateZKP(&them->s2.zkpxbs, t2, us, t1, params, us->p.base + 1, " * s");
 334
 335     // cleanup
 336     BN_free(t1);
 337     BN_free(t2);
 338 }
 339
 340 static int verifystep2(const JPakeUser * us, const JPakeUserPublic * them,
 341                        const JPakeParameters * params)
 342 {
 343     BIGNUM *t1 = BN_new();
 344     BIGNUM *t2 = BN_new();
 345     int ret = 0;
 346
 347     printf("\n%s verifies %s:\n\n", us->p.name, them->name);
 348
 349     // g' = g^{xc + xa + xb} [from our POV]
 350     // t1 = xa + xb
 351     BN_mod_add(t1, us->xa, us->xb, params->q, params->ctx);
 352     // t2 = g^{t1} = g^{xa+xb}
 353     BN_mod_exp(t2, params->g, t1, params->p, params->ctx);
 354     // t1 = g^{xc} * t2 = g^{xc + xa + xb}
 355     BN_mod_mul(t1, us->p.s1c.gx, t2, params->p, params->ctx);
 356
 357     if (VerifyZKP
 358         (&us->p.s2.zkpxbs, us->p.s2.X, them, t1, params, them->base + 1,
 359          " * s"))
 360         ret = 1;
 361
 362     // cleanup
 363     BN_free(t2);
 364     BN_free(t1);
 365
 366     return ret;
 367 }
 368
 369 static void computekey(JPakeUser * us, const JPakeParameters * params)
 370 {
 371     BIGNUM *t1 = BN_new();
 372     BIGNUM *t2 = BN_new();
 373     BIGNUM *t3 = BN_new();
 374
 375     printf("\n%s calculates the shared key:\n\n", us->p.name);
 376
 377     // K = (X/g^{xb * xd * s})^{xb}
 378     // = (g^{(xc + xa + xb) * xd * s - xb * xd *s})^{xb}
 379     // = (g^{(xa + xc) * xd * s})^{xb}
 380     // = g^{(xa + xc) * xb * xd * s}
 381     // [which is the same regardless of who calculates it]
 382
 383     // t1 = (g^{xd})^{xb} = g^{xb * xd}
 384     BN_mod_exp(t1, us->p.s1d.gx, us->xb, params->p, params->ctx);
 385     // t2 = -s = q-s
 386     BN_sub(t2, params->q, us->secret);
 387     // t3 = t1^t2 = g^{-xb * xd * s}
 388     BN_mod_exp(t3, t1, t2, params->p, params->ctx);
 389     // t1 = X * t3 = X/g^{xb * xd * s}
 390     BN_mod_mul(t1, us->p.s2.X, t3, params->p, params->ctx);
 391     // K = t1^{xb}
 392     us->key = BN_new();
 393     BN_mod_exp(us->key, t1, us->xb, params->p, params->ctx);
 394
 395     // show
 396     showbn("  K", us->key);
 397
 398     // cleanup
 399     BN_free(t3);
 400     BN_free(t2);
 401     BN_free(t1);
 402 }
 403
 404 int main(int argc, char **argv)
 405 {
 406     JPakeParameters params;
 407     JPakeUser alice, bob;
 408
 409     alice.p.name = "Alice";
 410     alice.p.base = 1;
 411     bob.p.name = "Bob";
 412     bob.p.base = 3;
 413
 414     JPakeParametersInit(&params);
 415
 416     // Shared secret
 417     alice.secret = BN_new();
 418     BN_rand(alice.secret, 32, -1, 0);
 419     bob.secret = alice.secret;
 420     showbn("secret", alice.secret);
 421
 422     assert(BN_cmp(alice.secret, params.q) < 0);
 423
 424     // Alice's x1, x2
 425     genrand(&alice, &params);
 426
 427     // Bob's x3, x4
 428     genrand(&bob, &params);
 429
 430     // Now send stuff to each other...
 431     sendstep1(&alice, &bob.p, &params);
 432     sendstep1(&bob, &alice.p, &params);
 433
 434     // And verify what each other sent
 435     if (!verifystep1(&alice, &bob.p, &params))
 436         return 1;
 437     if (!verifystep1(&bob, &alice.p, &params))
 438         return 2;
 439
 440     // Second send
 441     sendstep2(&alice, &bob.p, &params);
 442     sendstep2(&bob, &alice.p, &params);
 443
 444     // And second verify
 445     if (!verifystep2(&alice, &bob.p, &params))
 446         return 3;
 447     if (!verifystep2(&bob, &alice.p, &params))
 448         return 4;
 449
 450     // Compute common key
 451     computekey(&alice, &params);
 452     computekey(&bob, &params);
 453
 454     // Confirm the common key is identical
 455     // XXX: if the two secrets are not the same, everything works up
 456     // to this point, so the only way to detect a failure is by the
 457     // difference in the calculated keys.
 458     // Since we're all the same code, just compare them directly. In a
 459     // real system, Alice sends Bob H(H(K)), Bob checks it, then sends
 460     // back H(K), which Alice checks, or something equivalent.
 461     puts("\nAlice and Bob check keys are the same:");
 462     if (BN_cmp(alice.key, bob.key) == 0)
 463         puts("  OK");
 464     else {
 465         puts("  FAIL");
 466         return 5;
 467     }
 468
 469     return 0;
 470 }