1 /* $OpenBSD: jpake.c,v 1.1 2008/11/04 08:22:12 djm Exp $ */
3 * Copyright (c) 2008 Damien Miller. All rights reserved.
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 * Shared components of zero-knowledge password auth using J-PAKE protocol
22 * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
23 * 16th Workshop on Security Protocols, Cambridge, April 2008
25 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
30 #include <sys/types.h>
36 #include <openssl/bn.h>
37 #include <openssl/evp.h>
53 /* RFC3526 group 5, 1536 bits */
54 #define JPAKE_GROUP_G "2"
55 #define JPAKE_GROUP_P \
56 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74" \
57 "020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F1437" \
58 "4FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED" \
59 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF05" \
60 "98DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB" \
61 "9ED529077096966D670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF"
64 jpake_default_group(void)
66 struct jpake_group *ret;
68 ret = xmalloc(sizeof(*ret));
69 ret->p = ret->q = ret->g = NULL;
70 if (BN_hex2bn(&ret->p, JPAKE_GROUP_P) == 0 ||
71 BN_hex2bn(&ret->g, JPAKE_GROUP_G) == 0)
72 fatal("%s: BN_hex2bn", __func__);
73 /* Subgroup order is p/2 (p is a safe prime) */
74 if ((ret->q = BN_new()) == NULL)
75 fatal("%s: BN_new", __func__);
76 if (BN_rshift1(ret->q, ret->p) != 1)
77 fatal("%s: BN_rshift1", __func__);
83 * Generate uniformly distributed random number in range (1, high).
84 * Return number on success, NULL on failure.
87 bn_rand_range_gt_one(const BIGNUM *high)
92 if ((tmp = BN_new()) == NULL) {
93 error("%s: BN_new", __func__);
96 if ((r = BN_new()) == NULL) {
97 error("%s: BN_new failed", __func__);
100 if (BN_set_word(tmp, 2) != 1) {
101 error("%s: BN_set_word(tmp, 2)", __func__);
104 if (BN_sub(tmp, high, tmp) == -1) {
105 error("%s: BN_sub failed (tmp = high - 2)", __func__);
108 if (BN_rand_range(r, tmp) == -1) {
109 error("%s: BN_rand_range failed", __func__);
112 if (BN_set_word(tmp, 2) != 1) {
113 error("%s: BN_set_word(tmp, 2)", __func__);
116 if (BN_add(r, r, tmp) == -1) {
117 error("%s: BN_add failed (r = r + 2)", __func__);
130 * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success,
131 * with digest via 'digestp' (caller to free) and length via 'lenp'.
132 * Returns -1 on failure.
135 hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
136 u_char **digestp, u_int *lenp)
138 u_char digest[EVP_MAX_MD_SIZE];
140 EVP_MD_CTX evp_md_ctx;
143 EVP_MD_CTX_init(&evp_md_ctx);
145 if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
146 error("%s: EVP_DigestInit_ex", __func__);
149 if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
150 error("%s: EVP_DigestUpdate", __func__);
153 if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
154 error("%s: EVP_DigestFinal_ex", __func__);
157 *digestp = xmalloc(digest_len);
159 memcpy(*digestp, digest, *lenp);
162 EVP_MD_CTX_cleanup(&evp_md_ctx);
163 bzero(digest, sizeof(digest));
168 /* print formatted string followed by bignum */
170 jpake_debug3_bn(const BIGNUM *n, const char *fmt, ...)
177 vasprintf(&out, fmt, args);
180 fatal("%s: vasprintf failed", __func__);
183 debug3("%s(null)", out);
186 debug3("%s0x%s", out, h);
192 /* print formatted string followed by buffer contents in hex */
194 jpake_debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
202 vasprintf(&out, fmt, args);
205 fatal("%s: vasprintf failed", __func__);
207 debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
213 for (i = j = 0; i < len; i++) {
214 snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
216 if (j >= sizeof(h) - 1 || i == len - 1) {
227 struct jpake_ctx *ret;
229 ret = xcalloc(1, sizeof(*ret));
231 ret->grp = jpake_default_group();
233 ret->s = ret->k = NULL;
234 ret->x1 = ret->x2 = ret->x3 = ret->x4 = NULL;
235 ret->g_x1 = ret->g_x2 = ret->g_x3 = ret->g_x4 = NULL;
236 ret->a = ret->b = NULL;
238 ret->client_id = ret->server_id = NULL;
239 ret->h_k_cid_sessid = ret->h_k_sid_sessid = NULL;
241 debug3("%s: alloc %p", __func__, ret);
248 jpake_free(struct jpake_ctx *pctx)
250 debug3("%s: free %p", __func__, pctx);
252 #define JPAKE_BN_CLEAR_FREE(v) \
259 #define JPAKE_BUF_CLEAR_FREE(v, l) \
269 JPAKE_BN_CLEAR_FREE(pctx->s);
270 JPAKE_BN_CLEAR_FREE(pctx->k);
271 JPAKE_BN_CLEAR_FREE(pctx->x1);
272 JPAKE_BN_CLEAR_FREE(pctx->x2);
273 JPAKE_BN_CLEAR_FREE(pctx->x3);
274 JPAKE_BN_CLEAR_FREE(pctx->x4);
275 JPAKE_BN_CLEAR_FREE(pctx->g_x1);
276 JPAKE_BN_CLEAR_FREE(pctx->g_x2);
277 JPAKE_BN_CLEAR_FREE(pctx->g_x3);
278 JPAKE_BN_CLEAR_FREE(pctx->g_x4);
279 JPAKE_BN_CLEAR_FREE(pctx->a);
280 JPAKE_BN_CLEAR_FREE(pctx->b);
282 JPAKE_BUF_CLEAR_FREE(pctx->client_id, pctx->client_id_len);
283 JPAKE_BUF_CLEAR_FREE(pctx->server_id, pctx->server_id_len);
284 JPAKE_BUF_CLEAR_FREE(pctx->h_k_cid_sessid, pctx->h_k_cid_sessid_len);
285 JPAKE_BUF_CLEAR_FREE(pctx->h_k_sid_sessid, pctx->h_k_sid_sessid_len);
287 #undef JPAKE_BN_CLEAR_FREE
288 #undef JPAKE_BUF_CLEAR_FREE
290 bzero(pctx, sizeof(pctx));
294 /* dump entire jpake_ctx. NB. includes private values! */
296 jpake_dump(struct jpake_ctx *pctx, const char *fmt, ...)
303 vasprintf(&out, fmt, args);
306 fatal("%s: vasprintf failed", __func__);
308 debug3("%s: %s (ctx at %p)", __func__, out, pctx);
314 #define JPAKE_DUMP_BN(a) do { \
316 JPAKE_DEBUG_BN(((a), "%s = ", #a)); \
318 #define JPAKE_DUMP_BUF(a, b) do { \
320 JPAKE_DEBUG_BUF((a, b, "%s", #a)); \
323 JPAKE_DUMP_BN(pctx->s);
324 JPAKE_DUMP_BN(pctx->k);
325 JPAKE_DUMP_BN(pctx->x1);
326 JPAKE_DUMP_BN(pctx->x2);
327 JPAKE_DUMP_BN(pctx->x3);
328 JPAKE_DUMP_BN(pctx->x4);
329 JPAKE_DUMP_BN(pctx->g_x1);
330 JPAKE_DUMP_BN(pctx->g_x2);
331 JPAKE_DUMP_BN(pctx->g_x3);
332 JPAKE_DUMP_BN(pctx->g_x4);
333 JPAKE_DUMP_BN(pctx->a);
334 JPAKE_DUMP_BN(pctx->b);
336 JPAKE_DUMP_BUF(pctx->client_id, pctx->client_id_len);
337 JPAKE_DUMP_BUF(pctx->server_id, pctx->server_id_len);
338 JPAKE_DUMP_BUF(pctx->h_k_cid_sessid, pctx->h_k_cid_sessid_len);
339 JPAKE_DUMP_BUF(pctx->h_k_sid_sessid, pctx->h_k_sid_sessid_len);
341 debug3("%s: %s done", __func__, out);
345 /* Shared parts of step 1 exchange calculation */
347 jpake_step1(struct jpake_group *grp,
348 u_char **id, u_int *id_len,
349 BIGNUM **priv1, BIGNUM **priv2, BIGNUM **g_priv1, BIGNUM **g_priv2,
350 u_char **priv1_proof, u_int *priv1_proof_len,
351 u_char **priv2_proof, u_int *priv2_proof_len)
355 if ((bn_ctx = BN_CTX_new()) == NULL)
356 fatal("%s: BN_CTX_new", __func__);
358 /* Random nonce to prevent replay */
359 *id = xmalloc(KZP_ID_LEN);
360 *id_len = KZP_ID_LEN;
361 arc4random_buf(*id, *id_len);
364 * x1/x3 is a random element of Zq
365 * x2/x4 is a random element of Z*q
366 * We also exclude [1] from x1/x3 candidates and [0, 1] from
367 * x2/x4 candiates to avoid possible degeneracy (i.e. g^0, g^1).
369 if ((*priv1 = bn_rand_range_gt_one(grp->q)) == NULL ||
370 (*priv2 = bn_rand_range_gt_one(grp->q)) == NULL)
371 fatal("%s: bn_rand_range_gt_one", __func__);
374 * client: g_x1 = g^x1 mod p / server: g_x3 = g^x3 mod p
375 * client: g_x2 = g^x2 mod p / server: g_x4 = g^x4 mod p
377 if ((*g_priv1 = BN_new()) == NULL ||
378 (*g_priv2 = BN_new()) == NULL)
379 fatal("%s: BN_new", __func__);
380 if (BN_mod_exp(*g_priv1, grp->g, *priv1, grp->p, bn_ctx) == -1)
381 fatal("%s: BN_mod_exp", __func__);
382 if (BN_mod_exp(*g_priv2, grp->g, *priv2, grp->p, bn_ctx) == -1)
383 fatal("%s: BN_mod_exp", __func__);
385 /* Generate proofs for holding x1/x3 and x2/x4 */
386 if (schnorr_sign(grp->p, grp->q, grp->g,
387 *priv1, *g_priv1, *id, *id_len,
388 priv1_proof, priv1_proof_len) != 0)
389 fatal("%s: schnorr_sign", __func__);
390 if (schnorr_sign(grp->p, grp->q, grp->g,
391 *priv2, *g_priv2, *id, *id_len,
392 priv2_proof, priv2_proof_len) != 0)
393 fatal("%s: schnorr_sign", __func__);
398 /* Shared parts of step 2 exchange calculation */
400 jpake_step2(struct jpake_group *grp, BIGNUM *s,
401 BIGNUM *mypub1, BIGNUM *theirpub1, BIGNUM *theirpub2, BIGNUM *mypriv2,
402 const u_char *theirid, u_int theirid_len,
403 const u_char *myid, u_int myid_len,
404 const u_char *theirpub1_proof, u_int theirpub1_proof_len,
405 const u_char *theirpub2_proof, u_int theirpub2_proof_len,
407 u_char **newpub_exponent_proof, u_int *newpub_exponent_proof_len)
410 BIGNUM *tmp, *exponent;
412 /* Validate peer's step 1 values */
413 if (BN_cmp(theirpub1, BN_value_one()) <= 0)
414 fatal("%s: theirpub1 <= 1", __func__);
415 if (BN_cmp(theirpub2, BN_value_one()) <= 0)
416 fatal("%s: theirpub2 <= 1", __func__);
418 if (schnorr_verify(grp->p, grp->q, grp->g, theirpub1,
419 theirid, theirid_len, theirpub1_proof, theirpub1_proof_len) != 1)
420 fatal("%s: schnorr_verify theirpub1 failed", __func__);
421 if (schnorr_verify(grp->p, grp->q, grp->g, theirpub2,
422 theirid, theirid_len, theirpub2_proof, theirpub2_proof_len) != 1)
423 fatal("%s: schnorr_verify theirpub2 failed", __func__);
425 if ((bn_ctx = BN_CTX_new()) == NULL)
426 fatal("%s: BN_CTX_new", __func__);
428 if ((*newpub = BN_new()) == NULL ||
429 (tmp = BN_new()) == NULL ||
430 (exponent = BN_new()) == NULL)
431 fatal("%s: BN_new", __func__);
434 * client: exponent = x2 * s mod p
435 * server: exponent = x4 * s mod p
437 if (BN_mod_mul(exponent, mypriv2, s, grp->q, bn_ctx) != 1)
438 fatal("%s: BN_mod_mul (exponent = mypriv2 * s mod p)",
442 * client: tmp = g^(x1 + x3 + x4) mod p
443 * server: tmp = g^(x1 + x2 + x3) mod p
445 if (BN_mod_mul(tmp, mypub1, theirpub1, grp->p, bn_ctx) != 1)
446 fatal("%s: BN_mod_mul (tmp = mypub1 * theirpub1 mod p)",
448 if (BN_mod_mul(tmp, tmp, theirpub2, grp->p, bn_ctx) != 1)
449 fatal("%s: BN_mod_mul (tmp = tmp * theirpub2 mod p)", __func__);
452 * client: a = tmp^exponent = g^((x1+x3+x4) * x2 * s) mod p
453 * server: b = tmp^exponent = g^((x1+x2+x3) * x4 * s) mod p
455 if (BN_mod_exp(*newpub, tmp, exponent, grp->p, bn_ctx) != 1)
456 fatal("%s: BN_mod_mul (newpub = tmp^exponent mod p)", __func__);
458 JPAKE_DEBUG_BN((tmp, "%s: tmp = ", __func__));
459 JPAKE_DEBUG_BN((exponent, "%s: exponent = ", __func__));
461 /* Note the generator here is 'tmp', not g */
462 if (schnorr_sign(grp->p, grp->q, tmp, exponent, *newpub,
464 newpub_exponent_proof, newpub_exponent_proof_len) != 0)
465 fatal("%s: schnorr_sign newpub", __func__);
467 BN_clear_free(tmp); /* XXX stash for later use? */
468 BN_clear_free(exponent); /* XXX stash for later use? (yes, in conf) */
473 /* Confirmation hash calculation */
475 jpake_confirm_hash(const BIGNUM *k,
476 const u_char *endpoint_id, u_int endpoint_id_len,
477 const u_char *sess_id, u_int sess_id_len,
478 u_char **confirm_hash, u_int *confirm_hash_len)
483 * Calculate confirmation proof:
484 * client: H(k || client_id || session_id)
485 * server: H(k || server_id || session_id)
488 buffer_put_bignum2(&b, k);
489 buffer_put_string(&b, endpoint_id, endpoint_id_len);
490 buffer_put_string(&b, sess_id, sess_id_len);
491 if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(),
492 confirm_hash, confirm_hash_len) != 0)
493 fatal("%s: hash_buffer", __func__);
497 /* Shared parts of key derivation and confirmation calculation */
499 jpake_key_confirm(struct jpake_group *grp, BIGNUM *s, BIGNUM *step2_val,
500 BIGNUM *mypriv2, BIGNUM *mypub1, BIGNUM *mypub2,
501 BIGNUM *theirpub1, BIGNUM *theirpub2,
502 const u_char *my_id, u_int my_id_len,
503 const u_char *their_id, u_int their_id_len,
504 const u_char *sess_id, u_int sess_id_len,
505 const u_char *theirpriv2_s_proof, u_int theirpriv2_s_proof_len,
507 u_char **confirm_hash, u_int *confirm_hash_len)
512 if ((bn_ctx = BN_CTX_new()) == NULL)
513 fatal("%s: BN_CTX_new", __func__);
514 if ((tmp = BN_new()) == NULL ||
515 (*k = BN_new()) == NULL)
516 fatal("%s: BN_new", __func__);
518 /* Validate step 2 values */
519 if (BN_cmp(step2_val, BN_value_one()) <= 0)
520 fatal("%s: step2_val <= 1", __func__);
523 * theirpriv2_s_proof is calculated with a different generator:
524 * tmp = g^(mypriv1+mypriv2+theirpub1) = g^mypub1*g^mypub2*g^theirpub1
525 * Calculate it here so we can check the signature.
527 if (BN_mod_mul(tmp, mypub1, mypub2, grp->p, bn_ctx) != 1)
528 fatal("%s: BN_mod_mul (tmp = mypub1 * mypub2 mod p)", __func__);
529 if (BN_mod_mul(tmp, tmp, theirpub1, grp->p, bn_ctx) != 1)
530 fatal("%s: BN_mod_mul (tmp = tmp * theirpub1 mod p)", __func__);
532 JPAKE_DEBUG_BN((tmp, "%s: tmp = ", __func__));
534 if (schnorr_verify(grp->p, grp->q, tmp, step2_val,
535 their_id, their_id_len,
536 theirpriv2_s_proof, theirpriv2_s_proof_len) != 1)
537 fatal("%s: schnorr_verify theirpriv2_s_proof failed", __func__);
541 * client: k = (b / g^(x2*x4*s))^x2 = g^((x1+x3)*x2*x4*s)
542 * server: k = (a / g^(x2*x4*s))^x4 = g^((x1+x3)*x2*x4*s)
545 * client: k = (g_x4^(q - (x2 * s)) * b)^x2 mod p
546 * server: k = (g_x2^(q - (x4 * s)) * b)^x4 mod p
548 if (BN_mul(tmp, mypriv2, s, bn_ctx) != 1)
549 fatal("%s: BN_mul (tmp = mypriv2 * s)", __func__);
550 if (BN_mod_sub(tmp, grp->q, tmp, grp->q, bn_ctx) != 1)
551 fatal("%s: BN_mod_sub (tmp = q - tmp mod q)", __func__);
552 if (BN_mod_exp(tmp, theirpub2, tmp, grp->p, bn_ctx) != 1)
553 fatal("%s: BN_mod_exp (tmp = theirpub2^tmp) mod p", __func__);
554 if (BN_mod_mul(tmp, tmp, step2_val, grp->p, bn_ctx) != 1)
555 fatal("%s: BN_mod_mul (tmp = tmp * step2_val) mod p", __func__);
556 if (BN_mod_exp(*k, tmp, mypriv2, grp->p, bn_ctx) != 1)
557 fatal("%s: BN_mod_exp (k = tmp^mypriv2) mod p", __func__);
562 jpake_confirm_hash(*k, my_id, my_id_len, sess_id, sess_id_len,
563 confirm_hash, confirm_hash_len);
567 * Calculate and check confirmation hash from peer. Returns 1 on success
568 * 0 on failure/mismatch.
571 jpake_check_confirm(const BIGNUM *k,
572 const u_char *peer_id, u_int peer_id_len,
573 const u_char *sess_id, u_int sess_id_len,
574 const u_char *peer_confirm_hash, u_int peer_confirm_hash_len)
576 u_char *expected_confirm_hash;
577 u_int expected_confirm_hash_len;
580 /* Calculate and verify expected confirmation hash */
581 jpake_confirm_hash(k, peer_id, peer_id_len, sess_id, sess_id_len,
582 &expected_confirm_hash, &expected_confirm_hash_len);
584 JPAKE_DEBUG_BUF((expected_confirm_hash, expected_confirm_hash_len,
585 "%s: expected confirm hash", __func__));
586 JPAKE_DEBUG_BUF((peer_confirm_hash, peer_confirm_hash_len,
587 "%s: received confirm hash", __func__));
589 if (peer_confirm_hash_len != expected_confirm_hash_len)
590 error("%s: confirmation length mismatch (my %u them %u)",
591 __func__, expected_confirm_hash_len, peer_confirm_hash_len);
592 else if (memcmp(peer_confirm_hash, expected_confirm_hash,
593 expected_confirm_hash_len) == 0)
595 bzero(expected_confirm_hash, expected_confirm_hash_len);
596 xfree(expected_confirm_hash);
597 debug3("%s: success = %d", __func__, success);
601 /* XXX main() function with tests */