jpake.c revision 291721 
1#include "jpake.h"
2
3#include <openssl/crypto.h>
4#include <openssl/sha.h>
5#include <openssl/err.h>
6#include <memory.h>
7
8/*
9 * In the definition, (xa, xb, xc, xd) are Alice's (x1, x2, x3, x4) or
10 * Bob's (x3, x4, x1, x2). If you see what I mean.
11 */
12
13typedef struct {
14    char *name;                 /* Must be unique */
15    char *peer_name;
16    BIGNUM *p;
17    BIGNUM *g;
18    BIGNUM *q;
19    BIGNUM *gxc;                /* Alice's g^{x3} or Bob's g^{x1} */
20    BIGNUM *gxd;                /* Alice's g^{x4} or Bob's g^{x2} */
21} JPAKE_CTX_PUBLIC;
22
23struct JPAKE_CTX {
24    JPAKE_CTX_PUBLIC p;
25    BIGNUM *secret;             /* The shared secret */
26    BN_CTX *ctx;
27    BIGNUM *xa;                 /* Alice's x1 or Bob's x3 */
28    BIGNUM *xb;                 /* Alice's x2 or Bob's x4 */
29    BIGNUM *key;                /* The calculated (shared) key */
30};
31
32static void JPAKE_ZKP_init(JPAKE_ZKP *zkp)
33{
34    zkp->gr = BN_new();
35    zkp->b = BN_new();
36}
37
38static void JPAKE_ZKP_release(JPAKE_ZKP *zkp)
39{
40    BN_free(zkp->b);
41    BN_free(zkp->gr);
42}
43
44/* Two birds with one stone - make the global name as expected */
45#define JPAKE_STEP_PART_init    JPAKE_STEP2_init
46#define JPAKE_STEP_PART_release JPAKE_STEP2_release
47
48void JPAKE_STEP_PART_init(JPAKE_STEP_PART *p)
49{
50    p->gx = BN_new();
51    JPAKE_ZKP_init(&p->zkpx);
52}
53
54void JPAKE_STEP_PART_release(JPAKE_STEP_PART *p)
55{
56    JPAKE_ZKP_release(&p->zkpx);
57    BN_free(p->gx);
58}
59
60void JPAKE_STEP1_init(JPAKE_STEP1 *s1)
61{
62    JPAKE_STEP_PART_init(&s1->p1);
63    JPAKE_STEP_PART_init(&s1->p2);
64}
65
66void JPAKE_STEP1_release(JPAKE_STEP1 *s1)
67{
68    JPAKE_STEP_PART_release(&s1->p2);
69    JPAKE_STEP_PART_release(&s1->p1);
70}
71
72static void JPAKE_CTX_init(JPAKE_CTX *ctx, const char *name,
73                           const char *peer_name, const BIGNUM *p,
74                           const BIGNUM *g, const BIGNUM *q,
75                           const BIGNUM *secret)
76{
77    ctx->p.name = OPENSSL_strdup(name);
78    ctx->p.peer_name = OPENSSL_strdup(peer_name);
79    ctx->p.p = BN_dup(p);
80    ctx->p.g = BN_dup(g);
81    ctx->p.q = BN_dup(q);
82    ctx->secret = BN_dup(secret);
83
84    ctx->p.gxc = BN_new();
85    ctx->p.gxd = BN_new();
86
87    ctx->xa = BN_new();
88    ctx->xb = BN_new();
89    ctx->key = BN_new();
90    ctx->ctx = BN_CTX_new();
91}
92
93static void JPAKE_CTX_release(JPAKE_CTX *ctx)
94{
95    BN_CTX_free(ctx->ctx);
96    BN_clear_free(ctx->key);
97    BN_clear_free(ctx->xb);
98    BN_clear_free(ctx->xa);
99
100    BN_free(ctx->p.gxd);
101    BN_free(ctx->p.gxc);
102
103    BN_clear_free(ctx->secret);
104    BN_free(ctx->p.q);
105    BN_free(ctx->p.g);
106    BN_free(ctx->p.p);
107    OPENSSL_free(ctx->p.peer_name);
108    OPENSSL_free(ctx->p.name);
109
110    memset(ctx, '\0', sizeof *ctx);
111}
112
113JPAKE_CTX *JPAKE_CTX_new(const char *name, const char *peer_name,
114                         const BIGNUM *p, const BIGNUM *g, const BIGNUM *q,
115                         const BIGNUM *secret)
116{
117    JPAKE_CTX *ctx = OPENSSL_malloc(sizeof *ctx);
118
119    JPAKE_CTX_init(ctx, name, peer_name, p, g, q, secret);
120
121    return ctx;
122}
123
124void JPAKE_CTX_free(JPAKE_CTX *ctx)
125{
126    JPAKE_CTX_release(ctx);
127    OPENSSL_free(ctx);
128}
129
130static void hashlength(SHA_CTX *sha, size_t l)
131{
132    unsigned char b[2];
133
134    OPENSSL_assert(l <= 0xffff);
135    b[0] = l >> 8;
136    b[1] = l & 0xff;
137    SHA1_Update(sha, b, 2);
138}
139
140static void hashstring(SHA_CTX *sha, const char *string)
141{
142    size_t l = strlen(string);
143
144    hashlength(sha, l);
145    SHA1_Update(sha, string, l);
146}
147
148static void hashbn(SHA_CTX *sha, const BIGNUM *bn)
149{
150    size_t l = BN_num_bytes(bn);
151    unsigned char *bin = OPENSSL_malloc(l);
152
153    hashlength(sha, l);
154    BN_bn2bin(bn, bin);
155    SHA1_Update(sha, bin, l);
156    OPENSSL_free(bin);
157}
158
159/* h=hash(g, g^r, g^x, name) */
160static void zkp_hash(BIGNUM *h, const BIGNUM *zkpg, const JPAKE_STEP_PART *p,
161                     const char *proof_name)
162{
163    unsigned char md[SHA_DIGEST_LENGTH];
164    SHA_CTX sha;
165
166    /*
167     * XXX: hash should not allow moving of the boundaries - Java code
168     * is flawed in this respect. Length encoding seems simplest.
169     */
170    SHA1_Init(&sha);
171    hashbn(&sha, zkpg);
172    OPENSSL_assert(!BN_is_zero(p->zkpx.gr));
173    hashbn(&sha, p->zkpx.gr);
174    hashbn(&sha, p->gx);
175    hashstring(&sha, proof_name);
176    SHA1_Final(md, &sha);
177    BN_bin2bn(md, SHA_DIGEST_LENGTH, h);
178}
179
180/*
181 * Prove knowledge of x
182 * Note that p->gx has already been calculated
183 */
184static void generate_zkp(JPAKE_STEP_PART *p, const BIGNUM *x,
185                         const BIGNUM *zkpg, JPAKE_CTX *ctx)
186{
187    BIGNUM *r = BN_new();
188    BIGNUM *h = BN_new();
189    BIGNUM *t = BN_new();
190
191   /*-
192    * r in [0,q)
193    * XXX: Java chooses r in [0, 2^160) - i.e. distribution not uniform
194    */
195    BN_rand_range(r, ctx->p.q);
196    /* g^r */
197    BN_mod_exp(p->zkpx.gr, zkpg, r, ctx->p.p, ctx->ctx);
198
199    /* h=hash... */
200    zkp_hash(h, zkpg, p, ctx->p.name);
201
202    /* b = r - x*h */
203    BN_mod_mul(t, x, h, ctx->p.q, ctx->ctx);
204    BN_mod_sub(p->zkpx.b, r, t, ctx->p.q, ctx->ctx);
205
206    /* cleanup */
207    BN_free(t);
208    BN_free(h);
209    BN_free(r);
210}
211
212static int verify_zkp(const JPAKE_STEP_PART *p, const BIGNUM *zkpg,
213                      JPAKE_CTX *ctx)
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    if (h == NULL || t1 == NULL || t2 == NULL || t3 == NULL)
222        goto end;
223
224    zkp_hash(h, zkpg, p, ctx->p.peer_name);
225
226    /* t1 = g^b */
227    BN_mod_exp(t1, zkpg, p->zkpx.b, ctx->p.p, ctx->ctx);
228    /* t2 = (g^x)^h = g^{hx} */
229    BN_mod_exp(t2, p->gx, h, ctx->p.p, ctx->ctx);
230    /* t3 = t1 * t2 = g^{hx} * g^b = g^{hx+b} = g^r (allegedly) */
231    BN_mod_mul(t3, t1, t2, ctx->p.p, ctx->ctx);
232
233    /* verify t3 == g^r */
234    if (BN_cmp(t3, p->zkpx.gr) == 0)
235        ret = 1;
236    else
237        JPAKEerr(JPAKE_F_VERIFY_ZKP, JPAKE_R_ZKP_VERIFY_FAILED);
238
239end:
240    /* cleanup */
241    BN_free(t3);
242    BN_free(t2);
243    BN_free(t1);
244    BN_free(h);
245
246    return ret;
247}
248
249static void generate_step_part(JPAKE_STEP_PART *p, const BIGNUM *x,
250                               const BIGNUM *g, JPAKE_CTX *ctx)
251{
252    BN_mod_exp(p->gx, g, x, ctx->p.p, ctx->ctx);
253    generate_zkp(p, x, g, ctx);
254}
255
256/* Generate each party's random numbers. xa is in [0, q), xb is in [1, q). */
257static void genrand(JPAKE_CTX *ctx)
258{
259    BIGNUM *qm1;
260
261    /* xa in [0, q) */
262    BN_rand_range(ctx->xa, ctx->p.q);
263
264    /* q-1 */
265    qm1 = BN_new();
266    BN_copy(qm1, ctx->p.q);
267    BN_sub_word(qm1, 1);
268
269    /* ... and xb in [0, q-1) */
270    BN_rand_range(ctx->xb, qm1);
271    /* [1, q) */
272    BN_add_word(ctx->xb, 1);
273
274    /* cleanup */
275    BN_free(qm1);
276}
277
278int JPAKE_STEP1_generate(JPAKE_STEP1 *send, JPAKE_CTX *ctx)
279{
280    genrand(ctx);
281    generate_step_part(&send->p1, ctx->xa, ctx->p.g, ctx);
282    generate_step_part(&send->p2, ctx->xb, ctx->p.g, ctx);
283
284    return 1;
285}
286
287/* g^x is a legal value */
288static int is_legal(const BIGNUM *gx, const JPAKE_CTX *ctx)
289{
290    BIGNUM *t;
291    int res;
292
293    if (BN_is_negative(gx) || BN_is_zero(gx) || BN_cmp(gx, ctx->p.p) >= 0)
294        return 0;
295
296    t = BN_new();
297    BN_mod_exp(t, gx, ctx->p.q, ctx->p.p, ctx->ctx);
298    res = BN_is_one(t);
299    BN_free(t);
300
301    return res;
302}
303
304int JPAKE_STEP1_process(JPAKE_CTX *ctx, const JPAKE_STEP1 *received)
305{
306    if (!is_legal(received->p1.gx, ctx)) {
307        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS,
308                 JPAKE_R_G_TO_THE_X3_IS_NOT_LEGAL);
309        return 0;
310    }
311
312    if (!is_legal(received->p2.gx, ctx)) {
313        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS,
314                 JPAKE_R_G_TO_THE_X4_IS_NOT_LEGAL);
315        return 0;
316    }
317
318    /* verify their ZKP(xc) */
319    if (!verify_zkp(&received->p1, ctx->p.g, ctx)) {
320        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X3_FAILED);
321        return 0;
322    }
323
324    /* verify their ZKP(xd) */
325    if (!verify_zkp(&received->p2, ctx->p.g, ctx)) {
326        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X4_FAILED);
327        return 0;
328    }
329
330    /* g^xd != 1 */
331    if (BN_is_one(received->p2.gx)) {
332        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_G_TO_THE_X4_IS_ONE);
333        return 0;
334    }
335
336    /* Save the bits we need for later */
337    BN_copy(ctx->p.gxc, received->p1.gx);
338    BN_copy(ctx->p.gxd, received->p2.gx);
339
340    return 1;
341}
342
343int JPAKE_STEP2_generate(JPAKE_STEP2 *send, JPAKE_CTX *ctx)
344{
345    BIGNUM *t1 = BN_new();
346    BIGNUM *t2 = BN_new();
347
348   /*-
349    * X = g^{(xa + xc + xd) * xb * s}
350    * t1 = g^xa
351    */
352    BN_mod_exp(t1, ctx->p.g, ctx->xa, ctx->p.p, ctx->ctx);
353    /* t2 = t1 * g^{xc} = g^{xa} * g^{xc} = g^{xa + xc} */
354    BN_mod_mul(t2, t1, ctx->p.gxc, ctx->p.p, ctx->ctx);
355    /* t1 = t2 * g^{xd} = g^{xa + xc + xd} */
356    BN_mod_mul(t1, t2, ctx->p.gxd, ctx->p.p, ctx->ctx);
357    /* t2 = xb * s */
358    BN_mod_mul(t2, ctx->xb, ctx->secret, ctx->p.q, ctx->ctx);
359
360   /*-
361    * ZKP(xb * s)
362    * XXX: this is kinda funky, because we're using
363    *
364    * g' = g^{xa + xc + xd}
365    *
366    * as the generator, which means X is g'^{xb * s}
367    * X = t1^{t2} = t1^{xb * s} = g^{(xa + xc + xd) * xb * s}
368    */
369    generate_step_part(send, t2, t1, ctx);
370
371    /* cleanup */
372    BN_free(t1);
373    BN_free(t2);
374
375    return 1;
376}
377
378/* gx = g^{xc + xa + xb} * xd * s */
379static int compute_key(JPAKE_CTX *ctx, const BIGNUM *gx)
380{
381    BIGNUM *t1 = BN_new();
382    BIGNUM *t2 = BN_new();
383    BIGNUM *t3 = BN_new();
384
385   /*-
386    * K = (gx/g^{xb * xd * s})^{xb}
387    *   = (g^{(xc + xa + xb) * xd * s - xb * xd *s})^{xb}
388    *   = (g^{(xa + xc) * xd * s})^{xb}
389    *   = g^{(xa + xc) * xb * xd * s}
390    * [which is the same regardless of who calculates it]
391    */
392
393    /* t1 = (g^{xd})^{xb} = g^{xb * xd} */
394    BN_mod_exp(t1, ctx->p.gxd, ctx->xb, ctx->p.p, ctx->ctx);
395    /* t2 = -s = q-s */
396    BN_sub(t2, ctx->p.q, ctx->secret);
397    /* t3 = t1^t2 = g^{-xb * xd * s} */
398    BN_mod_exp(t3, t1, t2, ctx->p.p, ctx->ctx);
399    /* t1 = gx * t3 = X/g^{xb * xd * s} */
400    BN_mod_mul(t1, gx, t3, ctx->p.p, ctx->ctx);
401    /* K = t1^{xb} */
402    BN_mod_exp(ctx->key, t1, ctx->xb, ctx->p.p, ctx->ctx);
403
404    /* cleanup */
405    BN_free(t3);
406    BN_free(t2);
407    BN_free(t1);
408
409    return 1;
410}
411
412int JPAKE_STEP2_process(JPAKE_CTX *ctx, const JPAKE_STEP2 *received)
413{
414    BIGNUM *t1 = BN_new();
415    BIGNUM *t2 = BN_new();
416    int ret = 0;
417
418   /*-
419    * g' = g^{xc + xa + xb} [from our POV]
420    * t1 = xa + xb
421    */
422    BN_mod_add(t1, ctx->xa, ctx->xb, ctx->p.q, ctx->ctx);
423    /* t2 = g^{t1} = g^{xa+xb} */
424    BN_mod_exp(t2, ctx->p.g, t1, ctx->p.p, ctx->ctx);
425    /* t1 = g^{xc} * t2 = g^{xc + xa + xb} */
426    BN_mod_mul(t1, ctx->p.gxc, t2, ctx->p.p, ctx->ctx);
427
428    if (verify_zkp(received, t1, ctx))
429        ret = 1;
430    else
431        JPAKEerr(JPAKE_F_JPAKE_STEP2_PROCESS, JPAKE_R_VERIFY_B_FAILED);
432
433    compute_key(ctx, received->gx);
434
435    /* cleanup */
436    BN_free(t2);
437    BN_free(t1);
438
439    return ret;
440}
441
442static void quickhashbn(unsigned char *md, const BIGNUM *bn)
443{
444    SHA_CTX sha;
445
446    SHA1_Init(&sha);
447    hashbn(&sha, bn);
448    SHA1_Final(md, &sha);
449}
450
451void JPAKE_STEP3A_init(JPAKE_STEP3A *s3a)
452{
453}
454
455int JPAKE_STEP3A_generate(JPAKE_STEP3A *send, JPAKE_CTX *ctx)
456{
457    quickhashbn(send->hhk, ctx->key);
458    SHA1(send->hhk, sizeof send->hhk, send->hhk);
459
460    return 1;
461}
462
463int JPAKE_STEP3A_process(JPAKE_CTX *ctx, const JPAKE_STEP3A *received)
464{
465    unsigned char hhk[SHA_DIGEST_LENGTH];
466
467    quickhashbn(hhk, ctx->key);
468    SHA1(hhk, sizeof hhk, hhk);
469    if (memcmp(hhk, received->hhk, sizeof hhk)) {
470        JPAKEerr(JPAKE_F_JPAKE_STEP3A_PROCESS,
471                 JPAKE_R_HASH_OF_HASH_OF_KEY_MISMATCH);
472        return 0;
473    }
474    return 1;
475}
476
477void JPAKE_STEP3A_release(JPAKE_STEP3A *s3a)
478{
479}
480
481void JPAKE_STEP3B_init(JPAKE_STEP3B *s3b)
482{
483}
484
485int JPAKE_STEP3B_generate(JPAKE_STEP3B *send, JPAKE_CTX *ctx)
486{
487    quickhashbn(send->hk, ctx->key);
488
489    return 1;
490}
491
492int JPAKE_STEP3B_process(JPAKE_CTX *ctx, const JPAKE_STEP3B *received)
493{
494    unsigned char hk[SHA_DIGEST_LENGTH];
495
496    quickhashbn(hk, ctx->key);
497    if (memcmp(hk, received->hk, sizeof hk)) {
498        JPAKEerr(JPAKE_F_JPAKE_STEP3B_PROCESS, JPAKE_R_HASH_OF_KEY_MISMATCH);
499        return 0;
500    }
501    return 1;
502}
503
504void JPAKE_STEP3B_release(JPAKE_STEP3B *s3b)
505{
506}
507
508const BIGNUM *JPAKE_get_shared_key(JPAKE_CTX *ctx)
509{
510    return ctx->key;
511}
512