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