Home | History | Annotate | Download | only in jpake 
      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 
     13 typedef 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 
     24 struct 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 
     34 static void JPAKE_ZKP_init(JPAKE_ZKP *zkp)
     35     {
     36     zkp->gr = BN_new();
     37     zkp->b = BN_new();
     38     }
     39 
     40 static 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 
     50 void JPAKE_STEP_PART_init(JPAKE_STEP_PART *p)
     51     {
     52     p->gx = BN_new();
     53     JPAKE_ZKP_init(&p->zkpx);
     54     }
     55 
     56 void JPAKE_STEP_PART_release(JPAKE_STEP_PART *p)
     57     {
     58     JPAKE_ZKP_release(&p->zkpx);
     59     BN_free(p->gx);
     60     }
     61 
     62 void JPAKE_STEP1_init(JPAKE_STEP1 *s1)
     63     {
     64     JPAKE_STEP_PART_init(&s1->p1);
     65     JPAKE_STEP_PART_init(&s1->p2);
     66     }
     67 
     68 void JPAKE_STEP1_release(JPAKE_STEP1 *s1)
     69     {
     70     JPAKE_STEP_PART_release(&s1->p2);
     71     JPAKE_STEP_PART_release(&s1->p1);
     72     }
     73 
     74 static 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 
     95 static 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 
    115 JPAKE_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 
    126 void JPAKE_CTX_free(JPAKE_CTX *ctx)
    127     {
    128     JPAKE_CTX_release(ctx);
    129     OPENSSL_free(ctx);
    130     }
    131 
    132 static 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 
    142 static 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 
    150 static 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) */
    162 static 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  */
    186 static 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 
    214 static 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 
    247 static 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). */
    255 static 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 
    276 int 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 */
    286 static 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 
    302 int 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 
    345 int 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 */
    381 static 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 
    414 int 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 
    444 static 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 
    453 void JPAKE_STEP3A_init(JPAKE_STEP3A *s3a)
    454     {}
    455 
    456 int 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 
    464 int 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 
    478 void JPAKE_STEP3A_release(JPAKE_STEP3A *s3a)
    479     {}
    480 
    481 void JPAKE_STEP3B_init(JPAKE_STEP3B *s3b)
    482     {}
    483 
    484 int JPAKE_STEP3B_generate(JPAKE_STEP3B *send, JPAKE_CTX *ctx)
    485     {
    486     quickhashbn(send->hk, ctx->key);
    487 
    488     return 1;
    489     }
    490 
    491 int 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 
    504 void JPAKE_STEP3B_release(JPAKE_STEP3B *s3b)
    505     {}
    506 
    507 const BIGNUM *JPAKE_get_shared_key(JPAKE_CTX *ctx)
    508     {
    509     return ctx->key;
    510     }
    511 
    512