Import DTLS sliding window validation from OpenConnect ESP codedtls-window

In this implementation, the end of the sliding window is always advanced
to the latest received packet, and we accept up to 64 packets before
that one. We no longer refuse to accept packets because they are
*too* far ahead of what we've already seen.

Some of the test cases are fixed up accordingly.

This matches the code in OpenConnect esp-seqno.c at commit ab2c4fc.

3 files changed, 112 insertions, 76 deletions

diff --git a/lib/dtls-sw.c b/lib/dtls-sw.c
index 8c334c05af..f13f6dd378 100644
--- a/lib/dtls-sw.c
+++ b/lib/dtls-sw.c
@@ -37,42 +37,26 @@
  */
 #define DTLS_EPOCH_SHIFT		(6*CHAR_BIT)
 #define DTLS_SEQ_NUM_MASK		0x0000FFFFFFFFFFFF
-#define DTLS_WINDOW_HAVE_RECV_PACKET(W) ((W)->dtls_sw_have_recv != 0)
 
-#define DTLS_WINDOW_INIT_AT(W, S)	(W)->dtls_sw_bits = ((W)->dtls_sw_have_recv) = 0; (W)->dtls_sw_start = (S&DTLS_SEQ_NUM_MASK)
-#define DTLS_WINDOW_INIT(W)		DTLS_WINDOW_INIT_AT(W, 0)
+#define DTLS_EMPTY_BITMAP		(0xFFFFFFFFFFFFFFFFULL)
 
-#define DTLS_WINDOW_INSIDE(W, S)	((((S) & DTLS_SEQ_NUM_MASK) > (W)->dtls_sw_start) && \
-						(((S)  & DTLS_SEQ_NUM_MASK) - (W)->dtls_sw_start <= (sizeof((W)->dtls_sw_bits) * CHAR_BIT)))
+/* We expect the compiler to be able to spot that this is a byteswapping
+ * load, and emit instructions like 'movbe' on x86_64 where appropriate.
+*/
+#define LOAD_UINT64(out, ubytes)  \
+	out = (((uint64_t)ubytes[0] << 56) |	\
+	       ((uint64_t)ubytes[1] << 48) |	\
+	       ((uint64_t)ubytes[2] << 40) |	\
+	       ((uint64_t)ubytes[3] << 32) |	\
+	       ((uint64_t)ubytes[4] << 24) |	\
+	       ((uint64_t)ubytes[5] << 16) |	\
+	       ((uint64_t)ubytes[6] << 8) |	\
+	       ((uint64_t)ubytes[7] << 0) )
 
-#define DTLS_WINDOW_OFFSET(W, S)	((((S) & DTLS_SEQ_NUM_MASK) - (W)->dtls_sw_start) - 1)
-
-#define DTLS_WINDOW_RECEIVED(W, S)	(((W)->dtls_sw_bits & ((uint64_t) 1 << DTLS_WINDOW_OFFSET(W, S))) != 0)
-
-#define DTLS_WINDOW_MARK(W, S)		((W)->dtls_sw_bits |= ((uint64_t) 1 << DTLS_WINDOW_OFFSET(W, S)))
-
-/* We forcefully advance the window once we have received more than
- * 8 packets since the first one. That way we ensure that we don't
- * get stuck on connections with many lost packets. */
-#define DTLS_WINDOW_UPDATE(W)		\
-					if (((W)->dtls_sw_bits & 0xffffffffffff0000LL) != 0) { \
-						(W)->dtls_sw_bits = (W)->dtls_sw_bits >> 1; \
-						(W)->dtls_sw_start++; \
-					} \
-					while ((W)->dtls_sw_bits & (uint64_t) 1) { \
-						(W)->dtls_sw_bits = (W)->dtls_sw_bits >> 1; \
-						(W)->dtls_sw_start++; \
-					}
-
-#define LOAD_UINT64(out, ubytes) \
-	for (i = 0; i < 8; i++) { \
-		out <<= 8; \
-		out |= ubytes[i] & 0xff; \
-	}
 
 void _dtls_reset_window(struct record_parameters_st *rp)
 {
-	DTLS_WINDOW_INIT(rp);
+	rp->dtls_sw_have_recv = 0;
 }
 
 /* Checks if a sequence number is not replayed. If a replayed
@@ -82,7 +66,6 @@ void _dtls_reset_window(struct record_parameters_st *rp)
 int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq)
 {
 	uint64_t seq_num = 0;
-	unsigned i;
 
 	LOAD_UINT64(seq_num, _seq->i);
 
@@ -90,24 +73,77 @@ int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq)
 		return gnutls_assert_val(-1);
 	}
 
-	if (!DTLS_WINDOW_HAVE_RECV_PACKET(rp)) {
-		DTLS_WINDOW_INIT_AT(rp, seq_num);
+	seq_num &= DTLS_SEQ_NUM_MASK;
+
+	/*
+	 * rp->dtls_sw_next is the next *expected* packet (N), being
+	 * the sequence number *after* the latest we have received.
+	 *
+	 * By definition, therefore, packet N-1 *has* been received.
+	 * And thus there's no point wasting a bit in the bitmap for it.
+	 *
+	 * So the backlog bitmap covers the 64 packets prior to that,
+	 * with the LSB representing packet (N - 2), and the MSB
+	 * representing (N - 65). A received packet is represented
+	 * by a zero bit, and a missing packet is represented by a one.
+	 *
+	 * Thus we can allow out-of-order reception of packets that are
+	 * within a reasonable interval of the latest packet received.
+	 */
+	if (!rp->dtls_sw_have_recv) {
+		rp->dtls_sw_next = seq_num + 1;
+		rp->dtls_sw_bits = DTLS_EMPTY_BITMAP;
 		rp->dtls_sw_have_recv = 1;
 		return 0;
-	}
+	} else if (seq_num == rp->dtls_sw_next) {
+		/* The common case. This is the packet we expected next. */
 
-	/* are we inside sliding window? */
-	if (!DTLS_WINDOW_INSIDE(rp, seq_num)) {
-		return gnutls_assert_val(-2);
-	}
+		rp->dtls_sw_bits <<= 1;
 
-	/* already received? */
-	if (DTLS_WINDOW_RECEIVED(rp, seq_num)) {
-		return gnutls_assert_val(-3);
-	}
+		/* This might reach a value higher than 48-bit DTLS sequence
+		 * numbers can actually reach. Which is fine. When that
+		 * happens, we'll do the right thing and just not accept
+		 * any newer packets. Someone needs to start a new epoch. */
+		rp->dtls_sw_next++;
+		return 0;
+	} else if (seq_num + 65 < rp->dtls_sw_next) {
+		/* Too old. We can't know if it's a replay */
+		return gnutls_assert_val(-2);
+	} else if (seq_num < rp->dtls_sw_next) {
+		/* Within the sliding window, so we remember whether we've seen it or not */
+		uint64_t mask = 1ULL << (rp->dtls_sw_next - seq_num - 2);
 
-	DTLS_WINDOW_MARK(rp, seq_num);
-	DTLS_WINDOW_UPDATE(rp);
+		if (!(rp->dtls_sw_bits & mask))
+			return gnutls_assert_val(-3);
 
-	return 0;
+		rp->dtls_sw_bits &= ~mask;
+		return 0;
+	} else {
+		/* The packet we were expecting has gone missing; this one is newer. */
+		uint64_t delta = seq_num - rp->dtls_sw_next;
+
+		if (delta >= 64) {
+			/* We jumped a long way into the future. We have not seen
+			 * any of the previous 32 packets so set the backlog bitmap
+			 * to all ones. */
+			rp->dtls_sw_bits = DTLS_EMPTY_BITMAP;
+		} else if (delta == 63) {
+			/* Avoid undefined behaviour that shifting by 64 would incur.
+			 * The (clear) top bit represents the packet which is currently
+			 * esp->seq - 1, which we know was already received. */
+			rp->dtls_sw_bits = DTLS_EMPTY_BITMAP >> 1;
+		} else {
+			/* We have missed (delta) packets. Shift the backlog by that
+			 * amount *plus* the one we would have shifted it anyway if
+			 * we'd received the packet we were expecting. The zero bit
+			 * representing the packet which is currently esp->seq - 1,
+			 * which we know has been received, ends up at bit position
+			 * (1<<delta). Then we set all the bits lower than that, which
+			 * represent the missing packets. */
+			rp->dtls_sw_bits <<= delta + 1;
+			rp->dtls_sw_bits |= (1ULL << delta) - 1;
+		}
+		rp->dtls_sw_next = seq_num + 1;
+		return 0;
+	}
 }
diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h
index a984b49c7f..25d4b3a814 100644
--- a/lib/gnutls_int.h
+++ b/lib/gnutls_int.h
@@ -622,8 +622,8 @@ struct record_parameters_st {
 	const mac_entry_st *mac;
 
 	/* for DTLS sliding window */
+	uint64_t dtls_sw_next; /* The end point (next expected packet) of the sliding window without epoch */
 	uint64_t dtls_sw_bits;
-	uint64_t dtls_sw_start; /* The starting point of the sliding window without epoch */
 	unsigned dtls_sw_have_recv; /* whether at least a packet has been received */
 
 	record_state_st read;
diff --git a/tests/dtls-sliding-window.c b/tests/dtls-sliding-window.c
index 1ad15296cd..c6a5e3d554 100644
--- a/tests/dtls-sliding-window.c
+++ b/tests/dtls-sliding-window.c
@@ -36,7 +36,7 @@
 
 struct record_parameters_st {
 	uint64_t dtls_sw_bits;
-	uint64_t dtls_sw_start;
+	uint64_t dtls_sw_next;
 	unsigned dtls_sw_have_recv;
 	unsigned epoch;
 };
@@ -75,8 +75,8 @@ static void uint64_set(uint64* t, uint64_t v)
 #define RESET_WINDOW \
 	memset(&state, 0, sizeof(state))
 
-#define SET_WINDOW_START(x) \
-	state.dtls_sw_start = ((x)&DTLS_SEQ_NUM_MASK)
+#define SET_WINDOW_NEXT(x) \
+	state.dtls_sw_next = (((x)&DTLS_SEQ_NUM_MASK))
 
 #define SET_WINDOW_LAST_RECV(x) \
 	uint64_set(&t, BSWAP64(x)); \
@@ -88,7 +88,7 @@ static void check_dtls_window_uninit_0(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 
 	uint64_set(&t, 0);
 
@@ -125,7 +125,7 @@ static void check_dtls_window_12(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(1);
 
 	uint64_set(&t, BSWAP64(2));
@@ -139,7 +139,7 @@ static void check_dtls_window_19(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(1);
 
 	uint64_set(&t, BSWAP64(9));
@@ -154,7 +154,7 @@ static void check_dtls_window_skip1(void **glob_state)
 	unsigned i;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(1);
 
 	for (i=2;i<256;i+=2) {
@@ -170,7 +170,7 @@ static void check_dtls_window_skip3(void **glob_state)
 	unsigned i;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(1);
 
 	for (i=5;i<256;i+=2) {
@@ -185,7 +185,7 @@ static void check_dtls_window_21(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(2);
 
 	uint64_set(&t, BSWAP64(1));
@@ -199,7 +199,7 @@ static void check_dtls_window_91(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(9);
 
 	uint64_set(&t, BSWAP64(1));
@@ -213,7 +213,7 @@ static void check_dtls_window_large_21(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT);
+	SET_WINDOW_NEXT(LARGE_INT);
 	SET_WINDOW_LAST_RECV(LARGE_INT+2);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+1));
@@ -227,7 +227,7 @@ static void check_dtls_window_large_12(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT);
+	SET_WINDOW_NEXT(LARGE_INT);
 	SET_WINDOW_LAST_RECV(LARGE_INT+1);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+2));
@@ -241,7 +241,7 @@ static void check_dtls_window_large_91(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT);
+	SET_WINDOW_NEXT(LARGE_INT);
 	SET_WINDOW_LAST_RECV(LARGE_INT+9);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+1));
@@ -255,7 +255,7 @@ static void check_dtls_window_large_19(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT);
+	SET_WINDOW_NEXT(LARGE_INT);
 	SET_WINDOW_LAST_RECV(LARGE_INT+1);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+9));
@@ -269,7 +269,7 @@ static void check_dtls_window_very_large_12(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(INT_OVER_32_BITS);
+	SET_WINDOW_NEXT(INT_OVER_32_BITS);
 	SET_WINDOW_LAST_RECV(INT_OVER_32_BITS+1);
 
 	uint64_set(&t, BSWAP64(INT_OVER_32_BITS+2));
@@ -283,7 +283,7 @@ static void check_dtls_window_very_large_91(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(INT_OVER_32_BITS);
+	SET_WINDOW_NEXT(INT_OVER_32_BITS);
 	SET_WINDOW_LAST_RECV(INT_OVER_32_BITS+9);
 
 	uint64_set(&t, BSWAP64(INT_OVER_32_BITS+1));
@@ -297,7 +297,7 @@ static void check_dtls_window_very_large_19(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(INT_OVER_32_BITS);
+	SET_WINDOW_NEXT(INT_OVER_32_BITS);
 	SET_WINDOW_LAST_RECV(INT_OVER_32_BITS+1);
 
 	uint64_set(&t, BSWAP64(INT_OVER_32_BITS+9));
@@ -311,12 +311,12 @@ static void check_dtls_window_outside(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(0);
+	SET_WINDOW_NEXT(0);
 	SET_WINDOW_LAST_RECV(1);
 
 	uint64_set(&t, BSWAP64(1+64));
 
-	assert_int_equal(_dtls_record_check(&state, &t), -2);
+	assert_int_equal(_dtls_record_check(&state, &t), 0);
 }
 
 static void check_dtls_window_large_outside(void **glob_state)
@@ -325,12 +325,12 @@ static void check_dtls_window_large_outside(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT);
+	SET_WINDOW_NEXT(LARGE_INT);
 	SET_WINDOW_LAST_RECV(LARGE_INT+1);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+1+64));
 
-	assert_int_equal(_dtls_record_check(&state, &t), -2);
+	assert_int_equal(_dtls_record_check(&state, &t), 0);
 }
 
 static void check_dtls_window_very_large_outside(void **glob_state)
@@ -339,12 +339,12 @@ static void check_dtls_window_very_large_outside(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(INT_OVER_32_BITS);
+	SET_WINDOW_NEXT(INT_OVER_32_BITS);
 	SET_WINDOW_LAST_RECV(INT_OVER_32_BITS+1);
 
 	uint64_set(&t, BSWAP64(INT_OVER_32_BITS+1+64));
 
-	assert_int_equal(_dtls_record_check(&state, &t), -2);
+	assert_int_equal(_dtls_record_check(&state, &t), 0);
 }
 
 static void check_dtls_window_dup1(void **glob_state)
@@ -353,7 +353,7 @@ static void check_dtls_window_dup1(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT-1);
+	SET_WINDOW_NEXT(LARGE_INT-1);
 	SET_WINDOW_LAST_RECV(LARGE_INT);
 
 	uint64_set(&t, BSWAP64(LARGE_INT));
@@ -366,7 +366,7 @@ static void check_dtls_window_dup1(void **glob_state)
 	assert_int_equal(_dtls_record_check(&state, &t), 0);
 
 	uint64_set(&t, BSWAP64(LARGE_INT+1));
-	assert_int_equal(_dtls_record_check(&state, &t), -2);
+	assert_int_equal(_dtls_record_check(&state, &t), -3);
 }
 
 static void check_dtls_window_dup2(void **glob_state)
@@ -375,7 +375,7 @@ static void check_dtls_window_dup2(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT-1);
+	SET_WINDOW_NEXT(LARGE_INT-1);
 	SET_WINDOW_LAST_RECV(LARGE_INT);
 
 	uint64_set(&t, BSWAP64(LARGE_INT));
@@ -397,7 +397,7 @@ static void check_dtls_window_dup3(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT-1);
+	SET_WINDOW_NEXT(LARGE_INT-1);
 	SET_WINDOW_LAST_RECV(LARGE_INT);
 
 	uint64_set(&t, BSWAP64(LARGE_INT));
@@ -425,7 +425,7 @@ static void check_dtls_window_out_of_order(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT-1);
+	SET_WINDOW_NEXT(LARGE_INT-1);
 	SET_WINDOW_LAST_RECV(LARGE_INT);
 
 	uint64_set(&t, BSWAP64(LARGE_INT));
@@ -465,7 +465,7 @@ static void check_dtls_window_epoch_higher(void **glob_state)
 	uint64 t;
 
 	RESET_WINDOW;
-	SET_WINDOW_START(LARGE_INT-1);
+	SET_WINDOW_NEXT(LARGE_INT-1);
 	SET_WINDOW_LAST_RECV(LARGE_INT);
 
 	uint64_set(&t, BSWAP64(LARGE_INT));
@@ -484,7 +484,7 @@ static void check_dtls_window_epoch_lower(void **glob_state)
 	uint64_set(&t, BSWAP64(0x1000000000000LL));
 
 	state.epoch = 1;
-	SET_WINDOW_START(0x1000000000000LL);
+	SET_WINDOW_NEXT(0x1000000000000LL);
 	SET_WINDOW_LAST_RECV((0x1000000000000LL) + 1);
 
 	uint64_set(&t, BSWAP64(2 | 0x1000000000000LL));