jpake.c revision 296341 
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    zkp_hash(h, zkpg, p, ctx->p.peer_name);
222
223    /* t1 = g^b */
224    BN_mod_exp(t1, zkpg, p->zkpx.b, ctx->p.p, ctx->ctx);
225    /* t2 = (g^x)^h = g^{hx} */
226    BN_mod_exp(t2, p->gx, h, ctx->p.p, ctx->ctx);
227    /* t3 = t1 * t2 = g^{hx} * g^b = g^{hx+b} = g^r (allegedly) */
228    BN_mod_mul(t3, t1, t2, ctx->p.p, ctx->ctx);
229
230    /* verify t3 == g^r */
231    if (BN_cmp(t3, p->zkpx.gr) == 0)
232        ret = 1;
233    else
234        JPAKEerr(JPAKE_F_VERIFY_ZKP, JPAKE_R_ZKP_VERIFY_FAILED);
235
236    /* cleanup */
237    BN_free(t3);
238    BN_free(t2);
239    BN_free(t1);
240    BN_free(h);
241
242    return ret;
243}
244
245static void generate_step_part(JPAKE_STEP_PART *p, const BIGNUM *x,
246                               const BIGNUM *g, JPAKE_CTX *ctx)
247{
248    BN_mod_exp(p->gx, g, x, ctx->p.p, ctx->ctx);
249    generate_zkp(p, x, g, ctx);
250}
251
252/* Generate each party's random numbers. xa is in [0, q), xb is in [1, q). */
253static void genrand(JPAKE_CTX *ctx)
254{
255    BIGNUM *qm1;
256
257    /* xa in [0, q) */
258    BN_rand_range(ctx->xa, ctx->p.q);
259
260    /* q-1 */
261    qm1 = BN_new();
262    BN_copy(qm1, ctx->p.q);
263    BN_sub_word(qm1, 1);
264
265    /* ... and xb in [0, q-1) */
266    BN_rand_range(ctx->xb, qm1);
267    /* [1, q) */
268    BN_add_word(ctx->xb, 1);
269
270    /* cleanup */
271    BN_free(qm1);
272}
273
274int JPAKE_STEP1_generate(JPAKE_STEP1 *send, JPAKE_CTX *ctx)
275{
276    genrand(ctx);
277    generate_step_part(&send->p1, ctx->xa, ctx->p.g, ctx);
278    generate_step_part(&send->p2, ctx->xb, ctx->p.g, ctx);
279
280    return 1;
281}
282
283/* g^x is a legal value */
284static int is_legal(const BIGNUM *gx, const JPAKE_CTX *ctx)
285{
286    BIGNUM *t;
287    int res;
288
289    if (BN_is_negative(gx) || BN_is_zero(gx) || BN_cmp(gx, ctx->p.p) >= 0)
290        return 0;
291
292    t = BN_new();
293    BN_mod_exp(t, gx, ctx->p.q, ctx->p.p, ctx->ctx);
294    res = BN_is_one(t);
295    BN_free(t);
296
297    return res;
298}
299
300int JPAKE_STEP1_process(JPAKE_CTX *ctx, const JPAKE_STEP1 *received)
301{
302    if (!is_legal(received->p1.gx, ctx)) {
303        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS,
304                 JPAKE_R_G_TO_THE_X3_IS_NOT_LEGAL);
305        return 0;
306    }
307
308    if (!is_legal(received->p2.gx, ctx)) {
309        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS,
310                 JPAKE_R_G_TO_THE_X4_IS_NOT_LEGAL);
311        return 0;
312    }
313
314    /* verify their ZKP(xc) */
315    if (!verify_zkp(&received->p1, ctx->p.g, ctx)) {
316        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X3_FAILED);
317        return 0;
318    }
319
320    /* verify their ZKP(xd) */
321    if (!verify_zkp(&received->p2, ctx->p.g, ctx)) {
322        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X4_FAILED);
323        return 0;
324    }
325
326    /* g^xd != 1 */
327    if (BN_is_one(received->p2.gx)) {
328        JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_G_TO_THE_X4_IS_ONE);
329        return 0;
330    }
331
332    /* Save the bits we need for later */
333    BN_copy(ctx->p.gxc, received->p1.gx);
334    BN_copy(ctx->p.gxd, received->p2.gx);
335
336    return 1;
337}
338
339int JPAKE_STEP2_generate(JPAKE_STEP2 *send, JPAKE_CTX *ctx)
340{
341    BIGNUM *t1 = BN_new();
342    BIGNUM *t2 = BN_new();
343
344   /*-
345    * X = g^{(xa + xc + xd) * xb * s}
346    * t1 = g^xa
347    */
348    BN_mod_exp(t1, ctx->p.g, ctx->xa, ctx->p.p, ctx->ctx);
349    /* t2 = t1 * g^{xc} = g^{xa} * g^{xc} = g^{xa + xc} */
350    BN_mod_mul(t2, t1, ctx->p.gxc, ctx->p.p, ctx->ctx);
351    /* t1 = t2 * g^{xd} = g^{xa + xc + xd} */
352    BN_mod_mul(t1, t2, ctx->p.gxd, ctx->p.p, ctx->ctx);
353    /* t2 = xb * s */
354    BN_mod_mul(t2, ctx->xb, ctx->secret, ctx->p.q, ctx->ctx);
355
356   /*-
357    * ZKP(xb * s)
358    * XXX: this is kinda funky, because we're using
359    *
360    * g' = g^{xa + xc + xd}
361    *
362    * as the generator, which means X is g'^{xb * s}
363    * X = t1^{t2} = t1^{xb * s} = g^{(xa + xc + xd) * xb * s}
364    */
365    generate_step_part(send, t2, t1, ctx);
366
367    /* cleanup */
368    BN_free(t1);
369    BN_free(t2);
370
371    return 1;
372}
373
374/* gx = g^{xc + xa + xb} * xd * s */
375static int compute_key(JPAKE_CTX *ctx, const BIGNUM *gx)
376{
377    BIGNUM *t1 = BN_new();
378    BIGNUM *t2 = BN_new();
379    BIGNUM *t3 = BN_new();
380
381   /*-
382    * K = (gx/g^{xb * xd * s})^{xb}
383    *   = (g^{(xc + xa + xb) * xd * s - xb * xd *s})^{xb}
384    *   = (g^{(xa + xc) * xd * s})^{xb}
385    *   = g^{(xa + xc) * xb * xd * s}
386    * [which is the same regardless of who calculates it]
387    */
388
389    /* t1 = (g^{xd})^{xb} = g^{xb * xd} */
390    BN_mod_exp(t1, ctx->p.gxd, ctx->xb, ctx->p.p, ctx->ctx);
391    /* t2 = -s = q-s */
392    BN_sub(t2, ctx->p.q, ctx->secret);
393    /* t3 = t1^t2 = g^{-xb * xd * s} */
394    BN_mod_exp(t3, t1, t2, ctx->p.p, ctx->ctx);
395    /* t1 = gx * t3 = X/g^{xb * xd * s} */
396    BN_mod_mul(t1, gx, t3, ctx->p.p, ctx->ctx);
397    /* K = t1^{xb} */
398    BN_mod_exp(ctx->key, t1, ctx->xb, ctx->p.p, ctx->ctx);
399
400    /* cleanup */
401    BN_free(t3);
402    BN_free(t2);
403    BN_free(t1);
404
405    return 1;
406}
407
408int JPAKE_STEP2_process(JPAKE_CTX *ctx, const JPAKE_STEP2 *received)
409{
410    BIGNUM *t1 = BN_new();
411    BIGNUM *t2 = BN_new();
412    int ret = 0;
413
414   /*-
415    * g' = g^{xc + xa + xb} [from our POV]
416    * t1 = xa + xb
417    */
418    BN_mod_add(t1, ctx->xa, ctx->xb, ctx->p.q, ctx->ctx);
419    /* t2 = g^{t1} = g^{xa+xb} */
420    BN_mod_exp(t2, ctx->p.g, t1, ctx->p.p, ctx->ctx);
421    /* t1 = g^{xc} * t2 = g^{xc + xa + xb} */
422    BN_mod_mul(t1, ctx->p.gxc, t2, ctx->p.p, ctx->ctx);
423
424    if (verify_zkp(received, t1, ctx))
425        ret = 1;
426    else
427        JPAKEerr(JPAKE_F_JPAKE_STEP2_PROCESS, JPAKE_R_VERIFY_B_FAILED);
428
429    compute_key(ctx, received->gx);
430
431    /* cleanup */
432    BN_free(t2);
433    BN_free(t1);
434
435    return ret;
436}
437
438static void quickhashbn(unsigned char *md, const BIGNUM *bn)
439{
440    SHA_CTX sha;
441
442    SHA1_Init(&sha);
443    hashbn(&sha, bn);
444    SHA1_Final(md, &sha);
445}
446
447void JPAKE_STEP3A_init(JPAKE_STEP3A *s3a)
448{
449}
450
451int JPAKE_STEP3A_generate(JPAKE_STEP3A *send, JPAKE_CTX *ctx)
452{
453    quickhashbn(send->hhk, ctx->key);
454    SHA1(send->hhk, sizeof send->hhk, send->hhk);
455
456    return 1;
457}
458
459int JPAKE_STEP3A_process(JPAKE_CTX *ctx, const JPAKE_STEP3A *received)
460{
461    unsigned char hhk[SHA_DIGEST_LENGTH];
462
463    quickhashbn(hhk, ctx->key);
464    SHA1(hhk, sizeof hhk, hhk);
465    if (memcmp(hhk, received->hhk, sizeof hhk)) {
466        JPAKEerr(JPAKE_F_JPAKE_STEP3A_PROCESS,
467                 JPAKE_R_HASH_OF_HASH_OF_KEY_MISMATCH);
468        return 0;
469    }
470    return 1;
471}
472
473void JPAKE_STEP3A_release(JPAKE_STEP3A *s3a)
474{
475}
476
477void JPAKE_STEP3B_init(JPAKE_STEP3B *s3b)
478{
479}
480
481int JPAKE_STEP3B_generate(JPAKE_STEP3B *send, JPAKE_CTX *ctx)
482{
483    quickhashbn(send->hk, ctx->key);
484
485    return 1;
486}
487
488int JPAKE_STEP3B_process(JPAKE_CTX *ctx, const JPAKE_STEP3B *received)
489{
490    unsigned char hk[SHA_DIGEST_LENGTH];
491
492    quickhashbn(hk, ctx->key);
493    if (memcmp(hk, received->hk, sizeof hk)) {
494        JPAKEerr(JPAKE_F_JPAKE_STEP3B_PROCESS, JPAKE_R_HASH_OF_KEY_MISMATCH);
495        return 0;
496    }
497    return 1;
498}
499
500void JPAKE_STEP3B_release(JPAKE_STEP3B *s3b)
501{
502}
503
504const BIGNUM *JPAKE_get_shared_key(JPAKE_CTX *ctx)
505{
506    return ctx->key;
507}
508