aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorJason A. Donenfeld <Jason@zx2c4.com>2016-06-20 02:02:47 +0200
committerJason A. Donenfeld <Jason@zx2c4.com>2016-06-25 16:48:39 +0200
commitcec43eced713e32c28c1b557e3c7f066570f81d3 (patch)
treee2ebdf289c8a9d2755acf4b7572d8097e4bfd80d
parentInitial commit (diff)
downloadwireguard-monolithic-historical-cec43eced713e32c28c1b557e3c7f066570f81d3.tar.xz
wireguard-monolithic-historical-cec43eced713e32c28c1b557e3c7f066570f81d3.zip
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.
Diffstat (limited to '')
-rw-r--r--src/data.c144
-rw-r--r--src/noise.c2
-rw-r--r--src/noise.h10
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 <linux/bitmap.h>
#include <linux/scatterlist.h>
-/* 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;