From cec43eced713e32c28c1b557e3c7f066570f81d3 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Mon, 20 Jun 2016 02:02:47 +0200 Subject: nonce: switch to RFC6479 to better support packet reordering With packets hitting multiple cores, a 64bit backtrack was too small. This algorithm increases our backtrack to 1984bits. --- src/data.c | 144 ++++++++++++++++++++++++++++++++++++------------------------ src/noise.c | 2 +- src/noise.h | 10 ++++- 3 files changed, 95 insertions(+), 61 deletions(-) diff --git a/src/data.c b/src/data.c index 5b3c781..205020c 100644 --- a/src/data.c +++ b/src/data.c @@ -12,11 +12,11 @@ #include #include -/* This is appendix C of RFC 2401 - a sliding window bitmap. */ +/* This is RFC6479, a replay detection bitmap algorithm that avoids bitshifts */ static inline bool counter_validate(union noise_counter *counter, u64 their_counter) { bool ret = false; - u64 difference; + unsigned long index, index_current, top, i; spin_lock_bh(&counter->receive.lock); if (unlikely(counter->receive.counter >= REJECT_AFTER_MESSAGES + 1 || their_counter >= REJECT_AFTER_MESSAGES)) @@ -24,22 +24,21 @@ static inline bool counter_validate(union noise_counter *counter, u64 their_coun ++their_counter; + if (unlikely((COUNTER_WINDOW_SIZE + their_counter) < counter->receive.counter)) + goto out; + + index = their_counter >> ilog2(COUNTER_REDUNDANT_BITS); + if (likely(their_counter > counter->receive.counter)) { - difference = their_counter - counter->receive.counter; - if (likely(difference < BITS_PER_LONG)) { - counter->receive.backtrack <<= difference; - counter->receive.backtrack |= 1; - } else - counter->receive.backtrack = 1; + index_current = counter->receive.counter >> ilog2(COUNTER_REDUNDANT_BITS); + top = min_t(unsigned long, index - index_current, COUNTER_BITS_TOTAL / BITS_PER_LONG); + for (i = 1; i <= top; ++i) + counter->receive.backtrack[(i + index_current) & ((COUNTER_BITS_TOTAL / BITS_PER_LONG) - 1)] = 0; counter->receive.counter = their_counter; - ret = true; - goto out; } - difference = counter->receive.counter - their_counter; - if (unlikely(difference >= BITS_PER_LONG)) - goto out; - ret = !test_and_set_bit(difference, &counter->receive.backtrack); + index &= (COUNTER_BITS_TOTAL / BITS_PER_LONG) - 1; + ret = !test_and_set_bit(their_counter & (COUNTER_REDUNDANT_BITS - 1), &counter->receive.backtrack[index]); out: spin_unlock_bh(&counter->receive.lock); @@ -50,46 +49,83 @@ out: void packet_counter_selftest(void) { bool success = true; - unsigned int i = 0; - union noise_counter counter = { { 0 } }; - spin_lock_init(&counter.receive.lock); - -#define T(n, v) do { ++i; if (counter_validate(&counter, n) != v) { pr_info("nonce counter self-test %u: FAIL\n", i); success = false; } } while (0) + unsigned int test_num = 0, i; + union noise_counter counter; + +#define T_INIT do { memset(&counter, 0, sizeof(union noise_counter)); spin_lock_init(&counter.receive.lock); } while (0) +#define T_LIM (COUNTER_WINDOW_SIZE + 1) +#define T(n, v) do { ++test_num; if (counter_validate(&counter, n) != v) { pr_info("nonce counter self-test %u: FAIL\n", test_num); success = false; } } while (0) + T_INIT; + /* 1 */ T(0, true); + /* 2 */ T(1, true); + /* 3 */ T(1, false); + /* 4 */ T(9, true); + /* 5 */ T(8, true); + /* 6 */ T(7, true); + /* 7 */ T(7, false); + /* 8 */ T(T_LIM, true); + /* 9 */ T(T_LIM - 1, true); + /* 10 */ T(T_LIM - 1, false); + /* 11 */ T(T_LIM - 2, true); + /* 12 */ T(2, true); + /* 13 */ T(2, false); + /* 14 */ T(T_LIM + 16, true); + /* 15 */ T(3, false); + /* 16 */ T(T_LIM + 16, false); + /* 17 */ T(T_LIM * 4, true); + /* 18 */ T(T_LIM * 4 - (T_LIM - 1), true); + /* 19 */ T(10, false); + /* 20 */ T(T_LIM * 4 - T_LIM, false); + /* 21 */ T(T_LIM * 4 - (T_LIM + 1), false); + /* 22 */ T(T_LIM * 4 - (T_LIM - 2), true); + /* 23 */ T(T_LIM * 4 + 1 - T_LIM, false); + /* 24 */ T(0, false); + /* 25 */ T(REJECT_AFTER_MESSAGES, false); + /* 26 */ T(REJECT_AFTER_MESSAGES - 1, true); + /* 27 */ T(REJECT_AFTER_MESSAGES, false); + /* 28 */ T(REJECT_AFTER_MESSAGES - 1, false); + /* 29 */ T(REJECT_AFTER_MESSAGES - 2, true); + /* 30 */ T(REJECT_AFTER_MESSAGES + 1, false); + /* 31 */ T(REJECT_AFTER_MESSAGES + 2, false); + /* 32 */ T(REJECT_AFTER_MESSAGES - 2, false); + /* 33 */ T(REJECT_AFTER_MESSAGES - 3, true); + /* 34 */ T(0, false); + + T_INIT; + for (i = 1; i <= COUNTER_WINDOW_SIZE; ++i) + T(i, true); T(0, true); + T(0, false); + + T_INIT; + for (i = 2; i <= COUNTER_WINDOW_SIZE + 1; ++i) + T(i, true); T(1, true); - T(1, false); - T(9, true); - T(8, true); - T(7, true); - T(7, false); - T(BITS_PER_LONG, true); - T(BITS_PER_LONG - 1, true); - T(BITS_PER_LONG - 1, false); - T(BITS_PER_LONG - 2, true); - T(2, true); - T(2, false); - T(BITS_PER_LONG + 16, true); - T(3, false); - T(BITS_PER_LONG + 16, false); - T(BITS_PER_LONG * 4, true); - T(BITS_PER_LONG * 4 - (BITS_PER_LONG - 1), true); - T(10, false); - T(BITS_PER_LONG * 4 - BITS_PER_LONG, false); - T(BITS_PER_LONG * 4 - (BITS_PER_LONG + 1), false); - T(BITS_PER_LONG * 4 - (BITS_PER_LONG - 2), true); - T(BITS_PER_LONG * 4 + 1 - BITS_PER_LONG, false); T(0, false); - T(REJECT_AFTER_MESSAGES, false); - T(REJECT_AFTER_MESSAGES - 1, true); - T(REJECT_AFTER_MESSAGES, false); - T(REJECT_AFTER_MESSAGES - 1, false); - T(REJECT_AFTER_MESSAGES - 2, true); - T(REJECT_AFTER_MESSAGES + 1, false); - T(REJECT_AFTER_MESSAGES + 2, false); - T(REJECT_AFTER_MESSAGES - 2, false); - T(REJECT_AFTER_MESSAGES - 3, true); + + T_INIT; + for (i = COUNTER_WINDOW_SIZE + 1; i-- > 0 ;) + T(i, true); + + T_INIT; + for (i = COUNTER_WINDOW_SIZE + 2; i-- > 1 ;) + T(i, true); T(0, false); + + T_INIT; + for (i = COUNTER_WINDOW_SIZE + 1; i-- > 1 ;) + T(i, true); + T(COUNTER_WINDOW_SIZE + 1, true); + T(0, false); + + T_INIT; + for (i = COUNTER_WINDOW_SIZE + 1; i-- > 1 ;) + T(i, true); + T(0, true); + T(COUNTER_WINDOW_SIZE + 1, true); #undef T +#undef T_LIM +#undef T_INIT if (success) pr_info("nonce counter self-tests: pass\n"); @@ -343,15 +379,7 @@ static void finish_decrypt_packet(struct packet_data_decryption_ctx *ctx) if (likely(!ret)) used_new_key = noise_received_with_keypair(&ctx->keypair->entry.peer->keypairs, ctx->keypair); else { - /* TODO: currently either the nonce window is not big enough, or we're sending things in - * the wrong order. Try uncommenting the below code to see for yourself. This is a problem - * that needs to be solved. - * - * Debug with: - * #define XSTR(s) STR(s) - * #define STR(s) #s - * net_dbg_ratelimited("Packet has invalid nonce %Lu (max %Lu, backtrack %" XSTR(BITS_PER_LONG) "pbl)\n", ctx->nonce, ctx->keypair->receiving.counter.receive.counter, &ctx->keypair->receiving.counter.receive.backtrack); - */ + net_dbg_ratelimited("Packet has invalid nonce %Lu (max %Lu)\n", ctx->nonce, ctx->keypair->receiving.counter.receive.counter); peer_put(ctx->keypair->entry.peer); goto err; } diff --git a/src/noise.c b/src/noise.c index 053d946..3762e2d 100644 --- a/src/noise.c +++ b/src/noise.c @@ -218,7 +218,7 @@ static void symmetric_key_init(struct noise_symmetric_key *key) { spin_lock_init(&key->counter.receive.lock); atomic64_set(&key->counter.counter, 0); - key->counter.receive.backtrack = 0; + memset(key->counter.receive.backtrack, 0, sizeof(key->counter.receive.backtrack)); key->birthdate = get_jiffies_64(); key->is_valid = true; } diff --git a/src/noise.h b/src/noise.h index 65ca9d8..289f60b 100644 --- a/src/noise.h +++ b/src/noise.h @@ -37,9 +37,15 @@ enum noise_lengths { NOISE_HASH_LEN = BLAKE2S_OUTBYTES }; +enum counter_values { + COUNTER_BITS_TOTAL = 2048, + COUNTER_REDUNDANT_BITS = BITS_PER_LONG, + COUNTER_WINDOW_SIZE = COUNTER_BITS_TOTAL - COUNTER_REDUNDANT_BITS +}; + enum wireguard_limits { REKEY_AFTER_MESSAGES = U64_MAX - 0xffff, - REJECT_AFTER_MESSAGES = U64_MAX - 0xf, /* It's important that this value is always at *least* one less than U64_MAX. */ + REJECT_AFTER_MESSAGES = U64_MAX - COUNTER_WINDOW_SIZE - 1, REKEY_TIMEOUT = 5 * HZ, REKEY_AFTER_TIME = 120 * HZ, REJECT_AFTER_TIME = 180 * HZ, @@ -50,7 +56,7 @@ enum wireguard_limits { union noise_counter { struct { u64 counter; - unsigned long backtrack; + unsigned long backtrack[COUNTER_BITS_TOTAL / BITS_PER_LONG]; spinlock_t lock; } receive; atomic64_t counter; -- cgit v1.2.3-59-g8ed1b