From: Mark Wooding Date: Tue, 18 Sep 2012 02:30:28 +0000 (+0100) Subject: Merge branch 'mdw/backoff' X-Git-Tag: 1.0.0pre11~2 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/commitdiff_plain/9cda68ab3974b1f2c08a5896929890bf4a973e9a?hp=d245350adb5c3c687159409dcecc24fd1e7098d0 Merge branch 'mdw/backoff' * mdw/backoff: server/tests.at: Test key exchange and retransmit with a flaky network. server/tests.at: Add a retry loop in `COMMS_EPING'. proxy: Add a `drop' filter to randomly discard packets. server/keyexch.c: Randomized exponential retransmit backoff. server/keyexch.c: Use high-resolution `struct timeval' timers. server/{keyexch.c,keyset.c}: Eliminate `ks_tregen'. server/{keyexch.c,keyset.c}: Move timing parameters to tripe.h. Conflicts: server/tests.at --- diff --git a/proxy/tripe-mitm.8.in b/proxy/tripe-mitm.8.in index 38062a0d..f9cea379 100644 --- a/proxy/tripe-mitm.8.in +++ b/proxy/tripe-mitm.8.in @@ -201,6 +201,11 @@ the queue) then it has a 1 in .I p-replay probability (default 1 in 20) of being left in the queue. .TP +.BI drop\fR[\fP: p-drop\fR] +Randomly drop messages. Each message has a 1 in +.I p-drop +probability (default 1 in 5) of being discarded. +.TP .BI corrupt\fR[\fP: p-corrupt\fR] Randomly corrupt messages. Each message has a 1 in .I p-corrupt diff --git a/proxy/tripe-mitm.c b/proxy/tripe-mitm.c index 4b0e4470..eb1c7fd2 100644 --- a/proxy/tripe-mitm.c +++ b/proxy/tripe-mitm.c @@ -257,7 +257,7 @@ static void addcorrupt(filter *f, unsigned ac, char **av) { corrupt *c; if (ac > 1) - die(1, "syntax: filt:corrupt[:PCORRUPT]"); + die(1, "syntax: filt:corrupt[:P-CORRUPT]"); c = CREATE(corrupt); if (ac > 0) c->p_corrupt = atoi(av[0]); @@ -267,6 +267,36 @@ static void addcorrupt(filter *f, unsigned ac, char **av) f->func = docorrupt; } +/*----- Drop filter -------------------------------------------------------*/ + +typedef struct drop { + unsigned p_drop; +} drop; + +static void dodrop(filter *f, const octet *buf, size_t sz) +{ + drop *d = f->state; + + if (!RND(d->p_drop)) + puts("drop packet"); + else + PASS(f->next, buf, sz); +} + +static void adddrop(filter *f, unsigned ac, char **av) +{ + drop *d; + if (ac > 1) + die(1, "syntax: filt:drop[:P-DROP]"); + d = CREATE(drop); + if (ac > 0) + d->p_drop = atoi(av[0]); + else + d->p_drop = 5; + f->state = d; + f->func = dodrop; +} + /*----- Delay filter ------------------------------------------------------*/ typedef struct delaynode { @@ -379,7 +409,7 @@ static void adddelay(filter *f, unsigned ac, char **av) unsigned i; if (ac < 1 || ac > 3) - die(1, "syntax: filt:delay:QLEN[:MILLIS:PREPLAY]"); + die(1, "syntax: filt:delay:QLEN[:MILLIS:P-REPLAY]"); d = CREATE(delay); d->max = atoi(av[0]); if (ac > 1) @@ -426,6 +456,7 @@ const struct filtab { { "send", addsend }, { "fork", addfork }, { "delay", adddelay }, + { "drop", adddrop }, { "corrupt", addcorrupt }, { 0, 0 } }; @@ -633,6 +664,7 @@ Filters:\n\ send\n\ fork:TAG\n\ delay:QLEN[:MILLIS:P-REPLAY]\n\ + drop[:P-DROP]\n\ corrupt[:P-CORRUPT]\n", fp); } diff --git a/server/keyexch.c b/server/keyexch.c index 8eaf1e88..b1f23d73 100644 --- a/server/keyexch.c +++ b/server/keyexch.c @@ -75,13 +75,6 @@ * Switch received. Committed; send data; move to @KXS_SWITCH@. */ -/*----- Tunable parameters ------------------------------------------------*/ - -#define T_VALID SEC(20) /* Challenge validity period */ -#define T_RETRY SEC(10) /* Challenge retransmit interval */ - -#define VALIDP(kx, now) ((now) < (kx)->t_valid) - /*----- Static tables -----------------------------------------------------*/ static const char *const pkname[] = { @@ -90,6 +83,17 @@ static const char *const pkname[] = { /*----- Various utilities -------------------------------------------------*/ +/* --- @VALIDP@ --- * + * + * Arguments: @const keyexch *kx@ = key exchange state + * @time_t now@ = current time in seconds + * + * Returns: Whether the challenge in the key-exchange state is still + * valid or should be regenerated. + */ + +#define VALIDP(kx, now) ((now) < (kx)->t_valid) + /* --- @hashge@ --- * * * Arguments: @ghash *h@ = pointer to hash context @@ -261,24 +265,102 @@ static void timer(struct timeval *tv, void *v) /* --- @settimer@ --- * * * Arguments: @keyexch *kx@ = pointer to key exchange context - * @time_t t@ = when to set the timer for + * @struct timeval *tv@ = when to set the timer for * * Returns: --- * * Use: Sets the timer for the next key exchange attempt. */ -static void settimer(keyexch *kx, time_t t) +static void settimer(keyexch *kx, struct timeval *tv) { - struct timeval tv; - if (kx->f & KXF_TIMER) - sel_rmtimer(&kx->t); - tv.tv_sec = t; - tv.tv_usec = 0; - sel_addtimer(&sel, &kx->t, &tv, timer, kx); + if (kx->f & KXF_TIMER) sel_rmtimer(&kx->t); + sel_addtimer(&sel, &kx->t, tv, timer, kx); kx->f |= KXF_TIMER; } +/* --- @f2tv@ --- * + * + * Arguments: @struct timeval *tv@ = where to write the timeval + * @double t@ = a time as a floating point number + * + * Returns: --- + * + * Use: Converts a floating-point time into a timeval. + */ + +static void f2tv(struct timeval *tv, double t) +{ + tv->tv_sec = t; + tv->tv_usec = (t - tv->tv_sec)*MILLION; +} + +/* --- @wobble@ --- * + * + * Arguments: @double t@ = a time interval + * + * Returns: The same time interval, with a random error applied. + */ + +static double wobble(double t) +{ + uint32 r = rand_global.ops->word(&rand_global); + double w = (r/F_2P32) - 0.5; + return (t + t*w*T_WOBBLE); +} + +/* --- @rs_time@ --- * + * + * Arguments: @retry *rs@ = current retry state + * @struct timeval *tv@ = where to write the result + * @const struct timeval *now@ = current time, or null + * + * Returns: --- + * + * Use: Computes a time at which to retry sending a key-exchange + * packet. This algorithm is subject to change, but it's + * currently a capped exponential backoff, slightly randomized + * to try to keep clients from hammering a server that's only + * just woken up. + * + * If @now@ is null then the function works out the time for + * itself. + */ + +static void rs_time(retry *rs, struct timeval *tv, const struct timeval *now) +{ + double t; + struct timeval rtv; + + if (!rs->t) + t = SEC(2); + else { + t = (rs->t * 5)/4; + if (t > MIN(5)) t = MIN(5); + } + rs->t = t; + + if (!now) { + now = tv; + gettimeofday(tv, 0); + } + f2tv(&rtv, wobble(t)); + TV_ADD(tv, now, &rtv); +} + +/* --- @retry_reset@ --- * + * + * Arguments: @retry *rs@ = retry state + * + * Returns: -- + * + * Use: Resets a retry state to indicate that progress has been + * made. Also useful for initializing the state in the first + * place. + */ + +static void rs_reset(retry *rs) { rs->t = 0; } + /*----- Challenge management ----------------------------------------------*/ /* --- Notes on challenge management --- * @@ -363,6 +445,7 @@ static kxchal *kxc_new(keyexch *kx) kxc->kx = kx; kxc->f = 0; kx->r[i] = kxc; + rs_reset(&kxc->rs); return (kxc); } @@ -457,7 +540,7 @@ static void kxc_answer(keyexch *kx, kxchal *kxc) if (kxc->f & KXF_TIMER) sel_rmtimer(&kxc->t); gettimeofday(&tv, 0); - tv.tv_sec += T_RETRY; + rs_time(&kxc->rs, &tv, &tv); sel_addtimer(&sel, &kxc->t, &tv, kxc_timer, kxc); kxc->f |= KXF_TIMER; } @@ -724,6 +807,7 @@ static void resend(keyexch *kx) kxchal *kxc; buf bb; stats *st = p_stats(kx->p); + struct timeval tv; buf *b; switch (kx->s) { @@ -766,8 +850,10 @@ static void resend(keyexch *kx) p_txend(kx->p); } - if (kx->s < KXS_SWITCH) - settimer(kx, time(0) + T_RETRY); + if (kx->s < KXS_SWITCH) { + rs_time(&kx->rs, &tv, 0); + settimer(kx, &tv); + } } /* --- @decryptrest@ --- * @@ -908,8 +994,13 @@ bad: static void kxfinish(keyexch *kx) { kxchal *kxc = kx->r[0]; + struct timeval now, tv; + ks_activate(kxc->ks); - settimer(kx, ks_tregen(kxc->ks)); + gettimeofday(&now, 0); + f2tv(&tv, wobble(T_REGEN)); + TV_ADD(&tv, &now, &tv); + settimer(kx, &tv); kx->s = KXS_SWITCH; a_notify("KXDONE", "?PEER", kx->p, A_END); p_stats(kx->p)->t_kx = time(0); @@ -1156,23 +1247,26 @@ void kx_start(keyexch *kx, int forcep) void kx_message(keyexch *kx, unsigned msg, buf *b) { - time_t now = time(0); + struct timeval now, tv; stats *st = p_stats(kx->p); size_t sz = BSZ(b); int rc; + gettimeofday(&now, 0); + rs_reset(&kx->rs); if (kx->f & KXF_CORK) { - start(kx, now); - settimer(kx, now + T_RETRY); + start(kx, now.tv_sec); + rs_time(&kx->rs, &tv, &now); + settimer(kx, &tv); a_notify("KXSTART", A_END); } if (checkpub(kx)) return; - if (!VALIDP(kx, now)) { + if (!VALIDP(kx, now.tv_sec)) { stop(kx); - start(kx, now); + start(kx, now.tv_sec); } T( trace(T_KEYEXCH, "keyexch: processing %s packet from `%s'", msg < KX_NMSG ? pkname[msg] : "unknown", p_name(kx->p)); ) @@ -1272,6 +1366,7 @@ int kx_init(keyexch *kx, peer *p, keyset **ks, unsigned f) return (-1); } kx->f = KXF_DEAD | KXF_PUBKEY | f; + rs_reset(&kx->rs); if (!(kx->f & KXF_CORK)) { start(kx, time(0)); resend(kx); diff --git a/server/keyset.c b/server/keyset.c index 1f580ff7..f21a59a9 100644 --- a/server/keyset.c +++ b/server/keyset.c @@ -28,11 +28,6 @@ #include "tripe.h" -/*----- Tunable parameters ------------------------------------------------*/ - -#define T_EXP MIN(60) /* Expiry time for a key */ -#define T_REGEN MIN(45) /* Regeneration time for a key */ - /*----- Handy macros ------------------------------------------------------*/ #define KEYOK(ks, now) ((ks)->sz_exp > 0 && (ks)->t_exp > now) @@ -358,15 +353,6 @@ keyset *ks_gen(const void *k, size_t x, size_t y, size_t z, peer *p) return (ks); } -/* --- @ks_tregen@ --- * - * - * Arguments: @keyset *ks@ = pointer to a keyset - * - * Returns: The time at which moves ought to be made to replace this key. - */ - -time_t ks_tregen(keyset *ks) { return (ks->t_exp - T_EXP + T_REGEN); } - /* --- @ks_activate@ --- * * * Arguments: @keyset *ks@ = pointer to a keyset diff --git a/server/tests.at b/server/tests.at index ab64c538..e0eaa05b 100644 --- a/server/tests.at +++ b/server/tests.at @@ -40,6 +40,7 @@ m4_define([TRIPECTL], [$abs_top_builddir/client/tripectl -d. -aadmin]) m4_define([USLIP], [$abs_top_builddir/uslip/tripe-uslip]) m4_define([PKSTREAM], [$abs_top_builddir/pkstream/pkstream -b127.0.0.1 -p127.0.0.1]) +m4_define([MITM], [$abs_top_builddir/proxy/tripe-mitm]) ## Sequences. (These are used for testing the replay protection machinery.) m4_define([R32], [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dnl @@ -181,10 +182,24 @@ m4_define([WITH_3TRIPES], [WITH_TRIPEX([$3], [$4 $7], [$8])])])]) -## COMMS_EPING(adir, aname, bdir, bname) +## RETRY(n, body) +m4_define([RETRY], [ + n=0 rc=1 + while test $n -lt $1; do + if $2 + then rc=0; break + fi + n=$(( $n + 1 )) + done + exit $rc +]) + +## COMMS_EPING(adir, aname, bdir, bname, [n]) m4_define([COMMS_EPING], [ - AT_CHECK([TRIPECTL -d$1 EPING $4],, [ignore]) - AT_CHECK([TRIPECTL -d$3 EPING $2],, [ignore]) + AT_CHECK([RETRY([m4_default([$5], [1])], + [TRIPECTL -d$1 EPING $4])],, [ignore]) + AT_CHECK([RETRY([m4_default([$5], [1])], + [TRIPECTL -d$3 EPING $2])],, [ignore]) ]) ## COMMS_SLIP(adir, aname, bdir, bname) @@ -423,6 +438,44 @@ WITH_3TRIPES([alice], [bob], [carol], [-nslip], AT_CLEANUP +###-------------------------------------------------------------------------- +### Adverse communication. + +AT_SETUP([server retry]) +AT_KEYWORDS([backoff]) +export TRIPE_SLIPIF=USLIP + +for i in alice bob; do (mkdir $i; cd $i; SETUPDIR([beta])); done + +WITH_2TRIPES([alice], [bob], [-nslip], [-talice], [-tbob], [ + + ## Set up the evil proxy. + alicemitm=24516 bobmitm=14016 + MITM -kalice/keyring.pub >mitm.out 2>mitm.err \ + peer:alice:$alicemitm:127.0.0.1:$(cat alice/port) \ + peer:bob:$bobmitm:127.0.0.1:$(cat bob/port) \ + filt:drop:5 filt:send& mitmpid=$! + strace -omitm.trace -p$mitmpid& mitmtrace=$! + trap 'kill $mitmpid $mitmtrace; exit 127' EXIT INT QUIT TERM HUP + + ## Try to establish keys anyway. + AWAIT_KXDONE([alice], [alice], [bob], [bob], [ + AT_CHECK([TRIPECTL -dalice ADD -cork bob INET 127.0.0.1 $alicemitm]) + AT_CHECK([TRIPECTL -dbob ADD alice INET 127.0.0.1 $bobmitm]) + ]) + + ## Check pinging. + COMMS_EPING([alice], [alice], [bob], [bob], [10]) + COMMS_EPING([bob], [bob], [alice], [alice], [10]) + + ## Tear down the MITM proxy. + kill $mitmpid + wait $mitmpid + wait $mitmtrace +]) + +AT_CLEANUP + ###-------------------------------------------------------------------------- ### Services. diff --git a/server/tripe.h b/server/tripe.h index 8a0be518..ad20daa7 100644 --- a/server/tripe.h +++ b/server/tripe.h @@ -134,8 +134,21 @@ #define SEC(n) (n##u) #define MIN(n) (n##u * 60u) +#define F_2P32 (65536.0*65536.0) #define MEG(n) (n##ul * 1024ul * 1024ul) +/* --- Timing parameters --- */ + +#define T_EXP MIN(60) /* Expiry time for a key */ +#define T_REGEN MIN(40) /* Regeneration time for a key */ + +#define T_VALID SEC(20) /* Challenge validity period */ +#define T_RETRYMIN SEC(2) /* Minimum retry interval */ +#define T_RETRYMAX MIN(5) /* Maximum retry interval */ +#define T_RETRYGROW (5.0/4.0) /* Retry interval growth factor */ + +#define T_WOBBLE (1.0/3.0) /* Relative timer randomness */ + /* --- Other things --- */ #define PKBUFSZ 65536 @@ -238,6 +251,10 @@ typedef struct keyset { * Clive Jones. */ +typedef struct retry { + double t; /* Current retry time */ +} retry; + #define KX_NCHAL 16u typedef struct kxchal { @@ -247,6 +264,7 @@ typedef struct kxchal { keyset *ks; /* Pointer to temporary keyset */ unsigned f; /* Various useful flags */ sel_timer t; /* Response timer for challenge */ + retry rs; /* Retry state */ octet hc[MAXHASHSZ]; /* Hash of his challenge */ octet ck[MAXHASHSZ]; /* His magical check value */ octet hswrq_in[MAXHASHSZ]; /* Inbound switch request message */ @@ -261,6 +279,7 @@ typedef struct keyexch { unsigned f; /* Various useful flags */ unsigned s; /* Current state in exchange */ sel_timer t; /* Timer for next exchange */ + retry rs; /* Retry state */ ge *kpub; /* Peer's public key */ time_t texp_kpub; /* Expiry time for public key */ mp *alpha; /* My temporary secret */ @@ -670,15 +689,6 @@ extern keyset *ks_gen(const void */*k*/, size_t /*x*/, size_t /*y*/, size_t /*z*/, peer */*p*/); -/* --- @ks_tregen@ --- * - * - * Arguments: @keyset *ks@ = pointer to a keyset - * - * Returns: The time at which moves ought to be made to replace this key. - */ - -extern time_t ks_tregen(keyset */*ks*/); - /* --- @ks_activate@ --- * * * Arguments: @keyset *ks@ = pointer to a keyset