1 #include "openssl/bn.h"
2 #include "openssl/sha.h"
7 /* Copyright (C) 2008 Ben Laurie (ben@links.org) */
10 * Implement J-PAKE, as described in
11 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
13 * With hints from http://www.cl.cam.ac.uk/~fh240/software/JPAKE2.java.
16 static void showbn(const char *name, const BIGNUM *bn)
20 BN_print_fp(stdout, bn);
25 BN_CTX *ctx; // Perhaps not the best place for this?
31 static void JPakeParametersInit(JPakeParameters * params)
33 params->ctx = BN_CTX_new();
35 // For now use p, q, g from Java sample code. Later, generate them.
38 "fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b6512669455d402251fb593d8d58fabfc5f5ba30f6cb9b556cd7813b801d346ff26660b76b9950a5a49f9fe8047b1022c24fbba9d7feb7c61bf83b57e7c6a8a6150f04fb83f6d3c51ec3023554135a169132f675f3ae2b61d72aeff22203199dd14801c7");
40 BN_hex2bn(¶ms->q, "9760508f15230bccb292b982a2eb840bf0581cf5");
43 "f7e1a085d69b3ddecbbcab5c36b857b97994afbbfa3aea82f9574c0b3d0782675159578ebad4594fe67107108180b449167123e84c281613b7cf09328cc8a6e13c167a8b547c8d28e0a3ae1e2bb3a675916ea37f0bfa213562f1fb627a01243bcca4f1bea8519089a883dfe15ae59f06928b665e807b552564014c3bfecf492a");
45 showbn("p", params->p);
46 showbn("q", params->q);
47 showbn("g", params->g);
51 BIGNUM *gr; // g^r (r random)
52 BIGNUM *b; // b = r - x*h, h=hash(g, g^r, g^x, name)
57 JPakeZKP zkpx; // ZKP(x)
61 BIGNUM *X; // g^(xa + xc + xd) * xb * s
62 JPakeZKP zkpxbs; // ZKP(xb * s)
66 const char *name; // Must be unique
67 int base; // 1 for Alice, 3 for Bob. Only used for
69 JPakeStep1 s1c; // Alice's g^x3, ZKP(x3) or Bob's g^x1,
71 JPakeStep1 s1d; // Alice's g^x4, ZKP(x4) or Bob's g^x2,
73 JPakeStep2 s2; // Alice's A, ZKP(x2 * s) or Bob's B, ZKP(x4
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.
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
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)
96 BN_rand_range(user->xa, params->q);
100 BN_copy(qm1, params->q);
103 // ... and xb in [0, q-1)
105 BN_rand_range(user->xb, qm1);
107 BN_add_word(user->xb, 1);
113 printf("x%d", user->p.base);
114 showbn("", user->xa);
115 printf("x%d", user->p.base + 1);
116 showbn("", user->xb);
119 static void hashlength(SHA_CTX *sha, size_t l)
126 SHA1_Update(sha, b, 2);
129 static void hashstring(SHA_CTX *sha, const char *string)
131 size_t l = strlen(string);
134 SHA1_Update(sha, string, l);
137 static void hashbn(SHA_CTX *sha, const BIGNUM *bn)
139 size_t l = BN_num_bytes(bn);
140 unsigned char *bin = alloca(l);
144 SHA1_Update(sha, bin, l);
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)
152 unsigned char md[SHA_DIGEST_LENGTH];
155 // XXX: hash should not allow moving of the boundaries - Java code
156 // is flawed in this respect. Length encoding seems simplest.
158 hashbn(&sha, params->g);
159 hashbn(&sha, zkp->gr);
161 hashstring(&sha, from->name);
162 SHA1_Final(md, &sha);
163 BN_bin2bn(md, SHA_DIGEST_LENGTH, h);
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)
174 BIGNUM *r = BN_new();
175 BIGNUM *gx = BN_new();
176 BIGNUM *h = BN_new();
177 BIGNUM *t = BN_new();
180 // XXX: Java chooses r in [0, 2^160) - i.e. distribution not uniform
181 BN_rand_range(r, params->q);
184 BN_mod_exp(zkp->gr, zkpg, r, params->p, params->ctx);
186 BN_mod_exp(gx, zkpg, x, params->p, params->ctx);
189 zkpHash(h, zkp, gx, &us->p, params);
192 BN_mod_mul(t, x, h, params->q, params->ctx);
194 BN_mod_sub(zkp->b, r, t, params->q, params->ctx);
197 printf(" ZKP(x%d%s)\n", n, suffix);
198 showbn(" zkpg", zkpg);
200 showbn(" g^r", zkp->gr);
201 showbn(" b", zkp->b);
210 static int VerifyZKP(const JPakeZKP * zkp, BIGNUM *gx,
211 const JPakeUserPublic * them, const BIGNUM *zkpg,
212 const JPakeParameters * params, int n,
215 BIGNUM *h = BN_new();
216 BIGNUM *t1 = BN_new();
217 BIGNUM *t2 = BN_new();
218 BIGNUM *t3 = BN_new();
221 zkpHash(h, zkp, gx, them, params);
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);
230 printf(" ZKP(x%d%s)\n", n, suffix);
231 showbn(" zkpg", zkpg);
235 if (BN_cmp(t3, zkp->gr) == 0)
252 static void sendstep1_substep(JPakeStep1 * s1, const BIGNUM *x,
253 const JPakeUser * us,
254 const JPakeParameters * params, int n)
257 BN_mod_exp(s1->gx, params->g, x, params->p, params->ctx);
258 printf(" g^{x%d}", n);
261 CreateZKP(&s1->zkpx, x, us, params->g, params, n, "");
264 static void sendstep1(const JPakeUser * us, JPakeUserPublic * them,
265 const JPakeParameters * params)
267 printf("\n%s sends %s:\n\n", us->p.name, them->name);
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);
275 static int verifystep1(const JPakeUser * us, const JPakeUserPublic * them,
276 const JPakeParameters * params)
278 printf("\n%s verifies %s:\n\n", us->p.name, them->name);
280 // verify their ZKP(xc)
281 if (!VerifyZKP(&us->p.s1c.zkpx, us->p.s1c.gx, them, params->g, params,
285 // verify their ZKP(xd)
286 if (!VerifyZKP(&us->p.s1d.zkpx, us->p.s1d.gx, them, params->g, params,
291 printf(" g^{x%d} != 1: ", them->base + 1);
292 if (BN_is_one(us->p.s1d.gx)) {
301 static void sendstep2(const JPakeUser * us, JPakeUserPublic * them,
302 const JPakeParameters * params)
304 BIGNUM *t1 = BN_new();
305 BIGNUM *t2 = BN_new();
307 printf("\n%s sends %s:\n\n", us->p.name, them->name);
309 // X = g^{(xa + xc + xd) * xb * s}
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);
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);
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);
328 // XXX: this is kinda funky, because we're using
330 // g' = g^{xa + xc + xd}
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");
340 static int verifystep2(const JPakeUser * us, const JPakeUserPublic * them,
341 const JPakeParameters * params)
343 BIGNUM *t1 = BN_new();
344 BIGNUM *t2 = BN_new();
347 printf("\n%s verifies %s:\n\n", us->p.name, them->name);
349 // g' = g^{xc + xa + xb} [from our POV]
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);
358 (&us->p.s2.zkpxbs, us->p.s2.X, them, t1, params, them->base + 1,
369 static void computekey(JPakeUser * us, const JPakeParameters * params)
371 BIGNUM *t1 = BN_new();
372 BIGNUM *t2 = BN_new();
373 BIGNUM *t3 = BN_new();
375 printf("\n%s calculates the shared key:\n\n", us->p.name);
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]
383 // t1 = (g^{xd})^{xb} = g^{xb * xd}
384 BN_mod_exp(t1, us->p.s1d.gx, us->xb, params->p, params->ctx);
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);
393 BN_mod_exp(us->key, t1, us->xb, params->p, params->ctx);
396 showbn(" K", us->key);
404 int main(int argc, char **argv)
406 JPakeParameters params;
407 JPakeUser alice, bob;
409 alice.p.name = "Alice";
414 JPakeParametersInit(¶ms);
417 alice.secret = BN_new();
418 BN_rand(alice.secret, 32, -1, 0);
419 bob.secret = alice.secret;
420 showbn("secret", alice.secret);
422 assert(BN_cmp(alice.secret, params.q) < 0);
425 genrand(&alice, ¶ms);
428 genrand(&bob, ¶ms);
430 // Now send stuff to each other...
431 sendstep1(&alice, &bob.p, ¶ms);
432 sendstep1(&bob, &alice.p, ¶ms);
434 // And verify what each other sent
435 if (!verifystep1(&alice, &bob.p, ¶ms))
437 if (!verifystep1(&bob, &alice.p, ¶ms))
441 sendstep2(&alice, &bob.p, ¶ms);
442 sendstep2(&bob, &alice.p, ¶ms);
445 if (!verifystep2(&alice, &bob.p, ¶ms))
447 if (!verifystep2(&bob, &alice.p, ¶ms))
450 // Compute common key
451 computekey(&alice, ¶ms);
452 computekey(&bob, ¶ms);
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)