X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/blobdiff_plain/00e64b67d321bf53224d546dcba58c52834a7b79..38c3bc8753411a533e2a36af1e9efee69dcba3f3:/keyexch.c diff --git a/keyexch.c b/keyexch.c index c17f4009..f4125da2 100644 --- a/keyexch.c +++ b/keyexch.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: keyexch.c,v 1.4 2001/06/22 19:40:36 mdw Exp $ + * $Id: keyexch.c,v 1.9 2003/07/13 11:53:14 mdw Exp $ * * Key exchange protocol * @@ -29,6 +29,24 @@ /*----- Revision history --------------------------------------------------* * * $Log: keyexch.c,v $ + * Revision 1.9 2003/07/13 11:53:14 mdw + * Add protocol commentary. + * + * Revision 1.8 2003/07/13 11:19:49 mdw + * Incopatible protocol fix! Include message type code under MAC tag to prevent + * cut-and-paste from key-exchange messages to general packet transport. + * + * Revision 1.7 2003/05/17 11:01:28 mdw + * Handle flags on challenge timers correctly to prevent confusing the event + * list. + * + * Revision 1.6 2003/04/06 10:26:35 mdw + * Report peer name on decrypt errors. + * + * Revision 1.5 2002/01/13 14:54:40 mdw + * Patch up zero-knowledge property by passing an encrypted log with a + * challenge, so that the prover can verify that the challenge is good. + * * Revision 1.4 2001/06/22 19:40:36 mdw * Support expiry of other peers' public keys. * @@ -47,10 +65,60 @@ #include "tripe.h" +/*----- Brief protocol overview -------------------------------------------* + * + * Let %$G$% be a cyclic group; let %$g$% be a generator of %$G$%, and let + * %$q$% be the order of %$G$%; for a key %$K$%, let %$E_K(\cdot)$% denote + * application of the symmetric packet protocol to a message; let + * %$H(\cdot)$% be the random oracle. Let $\alpha \inr \{0,\ldots,q - 1\}$% + * be Alice's private key; let %$a = g^\alpha$% be her public key; let %$b$% + * be Bob's public key. + * + * At the beginning of the session, Alice chooses + * + * %$\rho_A \inr \{0, \ldots q - 1\}$% + * + * We also have: + * + * %$r_A = g^{\rho_A}$% Alice's challenge + * %$c_A = H(\cookie{cookie}, r_A)$% Alice's cookie + * %$v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})$% + * Alice's challenge check value + * %$r_B^\alpha = a^{\rho_B}$% Alice's reply + * %$K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}$% + * Alice and Bob's shared secret key + * %$w_A = H(\cookie{switch-request}, c_A, c_B)$% + * Alice's switch request value + * %$u_A = H(\cookie{switch-confirm}, c_A, c_B)$% + * Alice's switch confirm value + * + * The messages are then: + * + * %$\cookie{kx-pre-challenge}, r_A$% + * Initial greeting. In state @KXS_CHAL@. + * + * %$\cookie{kx-cookie}, r_A, c_B$% + * My table is full but I got your message. + * + * %$\cookie{kx-challenge}, r_A, c_B, v_A$% + * Here's a full challenge for you to answer. + * + * %$\cookie{kx-reply}, c_A, c_B, v_A, E_K(r_B^\alpha))$% + * Challenge accpeted: here's the answer. Commit to my challenge. Move + * to @KXS_COMMIT@. + * + * %$\cookie{kx-switch}, c_A, c_B, E_K(r_B^\alpha, w_A))$% + * Reply received: here's my reply. Committed; send data; move to + * @KXS_SWITCH@. + * + * %$\cookie{kx-switch-ok}, E_K(u_A))$% + * Switch received. Committed; send data; move to @KXS_SWITCH@. + */ + /*----- Tunable parameters ------------------------------------------------*/ -#define T_VALID MIN(2) -#define T_RETRY SEC(10) +#define T_VALID MIN(2) /* Challenge validity period */ +#define T_RETRY SEC(10) /* Challenge retransmit interval */ #define ISVALID(kx, now) ((now) < (kx)->t_valid) @@ -76,6 +144,31 @@ static void hashmp(HASH_CTX *r, mp *m) HASH(r, BBASE(&b), BLEN(&b)); } +/* --- @mpcrypt@ --- * + * + * Arguments: @mp *d@ = the destination integer + * @mp *x@ = the plaintext/ciphertext integer + * @size_t sz@ = the expected size of the plaintext + * @const octet *k@ = pointer to key material + * @size_t ksz@ = size of the key + * + * Returns: The encrypted/decrypted integer. + * + * Use: Encrypts (or decrypts) a multiprecision integer using another + * multiprecision integer as the key. This is a slightly grotty + * way to do this, but it's easier than the alternatives. + */ + +static mp *mpcrypt(mp *d, mp *x, size_t sz, const octet *k, size_t ksz) +{ + MGF_CTX m; + + MGF_INIT(&m, k, ksz, 0); + mp_storeb(x, buf_t, sz); + MGF_CRYPT(&m, buf_t, buf_t, sz); + return (mp_loadb(d, buf_t, sz)); +} + /* --- @timer@ --- * * * Arguments: @struct timeval *tv@ = the current time @@ -145,6 +238,7 @@ static void kxc_destroy(kxchal *kxc) sel_rmtimer(&kxc->t); mp_drop(kxc->c); mp_drop(kxc->r); + mp_drop(kxc->ck); ks_drop(kxc->ks); DESTROY(kxc); } @@ -164,6 +258,7 @@ static void kxc_stoptimer(kxchal *kxc) { if (kxc->f & KXF_TIMER) sel_rmtimer(&kxc->t); + kxc->f &= ~KXF_TIMER; } /* --- @kxc_new@ --- * @@ -194,6 +289,7 @@ static kxchal *kxc_new(keyexch *kx) kxc = CREATE(kxchal); kxc->c = 0; kxc->r = 0; + kxc->ck = 0; kxc->ks = 0; kxc->kx = kx; kxc->f = 0; @@ -277,7 +373,7 @@ static void kxc_answer(keyexch *kx, kxchal *kxc) else buf_put(b, kx->hc, HASHSZ); buf_put(b, kxc->hc, HASHSZ); - buf_put(b, kxc->hrx, HASHSZ); + buf_putmp(b, kxc->ck); /* --- Maybe send an actual reply, if we have one --- */ @@ -289,7 +385,7 @@ static void kxc_answer(keyexch *kx, kxchal *kxc) buf_init(&bb, buf_i, sizeof(buf_i)); buf_putmp(&bb, kxc->r); buf_flip(&bb); - ks_encrypt(kxc->ks, &bb, b); + ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_REPLY, &bb, b); } /* --- Update the statistics --- */ @@ -316,18 +412,20 @@ static void kxc_answer(keyexch *kx, kxchal *kxc) * * Arguments: @keyexch *kx@ = pointer to key exchange context * @mp *c@ = a challenge - * @const octet *hrx@ = the supplied expected-reply hash + * @mp *ck@ = the supplied expected-reply check value * * Returns: A pointer to the reply, or null if the reply-hash was wrong. * * Use: Computes replies to challenges. */ -static mp *getreply(keyexch *kx, mp *c, const octet *hrx) +static mp *getreply(keyexch *kx, mp *c, mp *ck) { mp *r = mpmont_exp(&mg, MP_NEW, c, kpriv.x); + mp *a; HASH_CTX h; - octet buf[HASHSZ]; + octet buf[HASHSZ]; + int ok; HASH_INIT(&h); HASH_STRING(&h, "tripe-expected-reply"); @@ -335,16 +433,24 @@ static mp *getreply(keyexch *kx, mp *c, const octet *hrx) hashmp(&h, kx->c); hashmp(&h, r); HASH_DONE(&h, buf); + + a = mpcrypt(MP_NEW, ck, mp_octets(kpriv.dp.q), buf, sizeof(buf)); IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, { trace(T_CRYPTO, "crypto: computed reply = %s", mpstr(r)); trace_block(T_CRYPTO, "crypto: computed reply hash", buf, HASHSZ); + trace(T_CRYPTO, "crypto: recovered log = %s", mpstr(a)); })) - if (memcmp(buf, hrx, HASHSZ) != 0) { - a_warn("invalid expected-reply hash from `%s'", p_name(kx->p)); + a = mpmont_exp(&mg, a, kpriv.dp.g, a); + ok = mp_eq(a, c); + if (!ok) { + a_warn("invalid expected-reply check from `%s'", p_name(kx->p)); + IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, { + trace(T_CRYPTO, "crypto: computed challenge = %s", mpstr(a)); + })) mp_drop(r); - return (0); } - return (r); + mp_drop(a); + return (ok ? r : 0); } /* --- @dochallenge@ --- * @@ -360,10 +466,11 @@ static mp *getreply(keyexch *kx, mp *c, const octet *hrx) static int dochallenge(keyexch *kx, unsigned msg, buf *b) { - mp *c = 0; - const octet *hc = 0, *hrx = 0; + mp *c = 0, *ck = 0; + const octet *hc = 0; kxchal *kxc; HASH_CTX h; + octet buf[HASHSZ]; /* --- Ensure that we're in a sensible state --- */ @@ -376,7 +483,7 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) if ((c = buf_getmp(b)) == 0 || (msg >= KX_COOKIE && (hc = buf_get(b, HASHSZ)) == 0) || - (msg >= KX_CHAL && (hrx = buf_get(b, HASHSZ)) == 0) || + (msg >= KX_CHAL && (ck = buf_getmp(b)) == 0) || BLEFT(b)) { a_warn("malformed packet from `%s'", p_name(kx->p)); goto bad; @@ -385,7 +492,7 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, { trace(T_CRYPTO, "crypto: challenge = %s", mpstr(c)); if (hc) trace_block(T_CRYPTO, "crypto: cookie", hc, HASHSZ); - if (hrx) trace_block(T_CRYPTO, "crypto: response hash", hrx, HASHSZ); + if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck)); })) /* --- First, handle a bare challenge --- * @@ -428,10 +535,10 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) * it. */ - if (!hrx) + if (!ck) kxc = kxc_new(kx); else { - if ((r = getreply(kx, c, hrx)) == 0) + if ((r = getreply(kx, c, ck)) == 0) goto bad; kxc = kxc_new(kx); kxc->r = r; @@ -452,11 +559,16 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) hashmp(&h, kx->c); hashmp(&h, kxc->c); hashmp(&h, kx->rx); - HASH_DONE(&h, kxc->hrx); + HASH_DONE(&h, buf); + kxc->ck = mpcrypt(MP_NEW, kx->alpha, mp_octets(kpriv.dp.q), + buf, sizeof(buf)); /* --- Work out the shared key --- */ + trace(T_CRYPTO, "debug: c = %s", mpstr(c)); + trace(T_CRYPTO, "debug: alpha = %s", mpstr(kx->alpha)); r = mpmont_exp(&mg, MP_NEW, c, kx->alpha); + trace(T_CRYPTO, "debug: r = %s", mpstr(r)); /* --- Compute the switch messages --- */ @@ -476,7 +588,9 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, { trace_block(T_CRYPTO, "crypto: computed cookie", kxc->hc, HASHSZ); - trace_block(T_CRYPTO, "crypto: my reply hash", kxc->hrx, HASHSZ); + trace_block(T_CRYPTO, "crypto: expected-reply hash", + buf, HASHSZ); + trace(T_CRYPTO, "crypto: my reply check = %s", mpstr(kxc->ck)); trace(T_CRYPTO, "crypto: shared secret = %s", mpstr(r)); trace_block(T_CRYPTO, "crypto: outbound switch request", kxc->hswrq_out, HASHSZ); @@ -496,15 +610,15 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) buf_putmp(b, r); z = BLEN(b); assert(BOK(b)); - kxc->ks = ks_gen(BBASE(b), x, y, z); + kxc->ks = ks_gen(BBASE(b), x, y, z, kx->p); mp_drop(r); } /* --- Answer the challenge if we need to --- */ - if (hrx && !kxc->r) { + if (ck && !kxc->r) { mp *r; - if ((r = getreply(kx, c, hrx)) == 0) + if ((r = getreply(kx, c, ck)) == 0) goto bad; kxc->r = r; } @@ -515,10 +629,12 @@ static int dochallenge(keyexch *kx, unsigned msg, buf *b) tidy: mp_drop(c); + mp_drop(ck); return (0); bad: mp_drop(c); + mp_drop(ck); return (-1); } @@ -556,7 +672,7 @@ static void resend(keyexch *kx) buf_putmp(&bb, kxc->r); buf_put(&bb, kxc->hswrq_out, HASHSZ); buf_flip(&bb); - ks_encrypt(kxc->ks, &bb, b); + ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCH, &bb, b); break; case KXS_SWITCH: T( trace(T_KEYEXCH, "keyexch: sending switch confirmation to `%s'", @@ -566,7 +682,7 @@ static void resend(keyexch *kx) buf_init(&bb, buf_i, sizeof(buf_i)); buf_put(&bb, kxc->hswok_out, HASHSZ); buf_flip(&bb); - ks_encrypt(kxc->ks, &bb, b); + ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, &bb, b); break; default: abort(); @@ -585,9 +701,10 @@ static void resend(keyexch *kx) /* --- @matchreply@ --- * * * Arguments: @keyexch *kx@ = pointer to key exchange context + * @unsigned ty@ = type of incoming message * @const octet *hc_in@ = a hash of his challenge * @const octet *hc_out@ = a hash of my challenge (cookie) - * @const octet *krx@ = his expected-reply hash (optional) + * @mp *ck@ = his expected-reply hash (optional) * @buf *b@ = encrypted remainder of the packet * * Returns: A pointer to the challenge block if OK, or null on failure. @@ -598,8 +715,8 @@ static void resend(keyexch *kx) * challenge is returned. */ -static kxchal *matchreply(keyexch *kx, const octet *hc_in, - const octet *hc_out, const octet *hrx, buf *b) +static kxchal *matchreply(keyexch *kx, unsigned ty, const octet *hc_in, + const octet *hc_out, mp *ck, buf *b) { kxchal *kxc; buf bb; @@ -610,7 +727,7 @@ static kxchal *matchreply(keyexch *kx, const octet *hc_in, IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, { trace_block(T_CRYPTO, "crypto: challenge", hc_in, HASHSZ); trace_block(T_CRYPTO, "crypto: cookie", hc_out, HASHSZ); - if (hrx) trace_block(T_CRYPTO, "crypto: response hash", hrx, HASHSZ); + if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck)); })) if (memcmp(hc_out, kx->hc, HASHSZ) != 0) { a_warn("incorrect cookie from `%s'", p_name(kx->p)); @@ -624,11 +741,11 @@ static kxchal *matchreply(keyexch *kx, const octet *hc_in, /* --- Maybe compute a reply for the challenge --- */ if (!kxc->r) { - if (!hrx) { + if (!ck) { a_warn("unexpected switch request from `%s'", p_name(kx->p)); goto bad; } - if ((r = getreply(kx, kxc->c, hrx)) == 0) + if ((r = getreply(kx, kxc->c, ck)) == 0) goto bad; kxc->r = r; r = 0; @@ -637,7 +754,7 @@ static kxchal *matchreply(keyexch *kx, const octet *hc_in, /* --- Decrypt the rest of the packet --- */ buf_init(&bb, buf_o, sizeof(buf_o)); - if (ks_decrypt(kxc->ks, b, &bb)) { + if (ks_decrypt(kxc->ks, ty, b, &bb)) { a_warn("failed to decrypt reply from `%s'", p_name(kx->p)); goto bad; } @@ -702,7 +819,8 @@ static void commit(keyexch *kx, kxchal *kxc) static int doreply(keyexch *kx, buf *b) { - const octet *hc_in, *hc_out, *hrx; + const octet *hc_in, *hc_out; + mp *ck = 0; kxchal *kxc; if (kx->s != KXS_CHAL && kx->s != KXS_COMMIT) { @@ -711,11 +829,12 @@ static int doreply(keyexch *kx, buf *b) } if ((hc_in = buf_get(b, HASHSZ)) == 0 || (hc_out = buf_get(b, HASHSZ)) == 0 || - (hrx = buf_get(b, HASHSZ)) == 0) { + (ck = buf_getmp(b)) == 0) { a_warn("invalid reply packet from `%s'", p_name(kx->p)); goto bad; } - if ((kxc = matchreply(kx, hc_in, hc_out, hrx, b)) == 0) + if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_REPLY, + hc_in, hc_out, ck, b)) == 0) goto bad; if (BLEFT(b)) { a_warn("invalid reply packet from `%s'", p_name(kx->p)); @@ -729,6 +848,7 @@ static int doreply(keyexch *kx, buf *b) return (0); bad: + mp_drop(ck); return (-1); } @@ -752,7 +872,8 @@ static int doswitch(keyexch *kx, buf *b) a_warn("invalid switch request from `%s'", p_name(kx->p)); goto bad; } - if ((kxc = matchreply(kx, hc_in, hc_out, 0, b)) == 0) + if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_SWITCH, + hc_in, hc_out, 0, b)) == 0) goto bad; if ((hswrq = buf_get(b, HASHSZ)) == 0 || BLEFT(b)) { a_warn("invalid switch request from `%s'", p_name(kx->p)); @@ -803,7 +924,7 @@ static int doswitchok(keyexch *kx, buf *b) } kxc = kx->r[0]; buf_init(&bb, buf_o, sizeof(buf_o)); - if (ks_decrypt(kxc->ks, b, &bb)) { + if (ks_decrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, b, &bb)) { a_warn("failed to decrypt switch confirmation from `%s'", p_name(kx->p)); goto bad; }