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