/* -*-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
*
/*----- 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.
*
#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)
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
sel_rmtimer(&kxc->t);
mp_drop(kxc->c);
mp_drop(kxc->r);
+ mp_drop(kxc->ck);
ks_drop(kxc->ks);
DESTROY(kxc);
}
{
if (kxc->f & KXF_TIMER)
sel_rmtimer(&kxc->t);
+ kxc->f &= ~KXF_TIMER;
}
/* --- @kxc_new@ --- *
kxc = CREATE(kxchal);
kxc->c = 0;
kxc->r = 0;
+ kxc->ck = 0;
kxc->ks = 0;
kxc->kx = kx;
kxc->f = 0;
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 --- */
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 --- */
*
* 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");
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@ --- *
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 --- */
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;
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 --- *
* 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;
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 --- */
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);
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;
}
tidy:
mp_drop(c);
+ mp_drop(ck);
return (0);
bad:
mp_drop(c);
+ mp_drop(ck);
return (-1);
}
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'",
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();
/* --- @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.
* 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;
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));
/* --- 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;
/* --- 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;
}
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) {
}
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));
return (0);
bad:
+ mp_drop(ck);
return (-1);
}
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));
}
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;
}
~mdw / tripe / blobdiff