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