| OLD | NEW |
|---|
| (Empty) |
| 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 { | |
| 26 BN_CTX *ctx; // Perhaps not the best place for this? | |
| 27 BIGNUM *p; | |
| 28 BIGNUM *q; | |
| 29 BIGNUM *g; | |
| 30 } JPakeParameters; | |
| 31 | |
| 32 static 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, "fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3
f80b6512669455d402251fb593d8d58fabfc5f5ba30f6cb9b556cd7813b801d346ff26660b76b995
0a5a49f9fe8047b1022c24fbba9d7feb7c61bf83b57e7c6a8a6150f04fb83f6d3c51ec3023554135
a169132f675f3ae2b61d72aeff22203199dd14801c7"); | |
| 39 params->q = NULL; | |
| 40 BN_hex2bn(¶ms->q, "9760508f15230bccb292b982a2eb840bf0581cf5"); | |
| 41 params->g = NULL; | |
| 42 BN_hex2bn(¶ms->g, "f7e1a085d69b3ddecbbcab5c36b857b97994afbbfa3aea82f9574
c0b3d0782675159578ebad4594fe67107108180b449167123e84c281613b7cf09328cc8a6e13c167
a8b547c8d28e0a3ae1e2bb3a675916ea37f0bfa213562f1fb627a01243bcca4f1bea8519089a883d
fe15ae59f06928b665e807b552564014c3bfecf492a"); | |
| 43 | |
| 44 showbn("p", params->p); | |
| 45 showbn("q", params->q); | |
| 46 showbn("g", params->g); | |
| 47 } | |
| 48 | |
| 49 typedef 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 | |
| 55 typedef struct | |
| 56 { | |
| 57 BIGNUM *gx; // g^x | |
| 58 JPakeZKP zkpx; // ZKP(x) | |
| 59 } JPakeStep1; | |
| 60 | |
| 61 typedef struct | |
| 62 { | |
| 63 BIGNUM *X; // g^(xa + xc + xd) * xb * s | |
| 64 JPakeZKP zkpxbs; // ZKP(xb * s) | |
| 65 } JPakeStep2; | |
| 66 | |
| 67 typedef 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 */ | |
| 80 typedef 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). | |
| 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, 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... | |
| 169 static 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 | |
| 209 static 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 | |
| 250 static 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 | |
| 262 static 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 | |
| 273 static 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 | |
| 300 static 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 | |
| 339 static 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 | |
| 367 static 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 | |
| 402 int 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 9254031:
Upgrade chrome's OpenSSL to same version Android ships with. (Closed)
Base URL: http://src.chromium.org/svn/trunk/deps/third_party/openssl/