dtls: imported Fridolin's DTLS sliding window implementation

This simplifies the current code, and reduces the memory needed.

8 files changed, 122 insertions, 176 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index 0b50082797..ec549e848c 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -77,7 +77,7 @@ COBJECTS = range.c record.c compress.c debug.c cipher.c			\
 	system_override.c crypto-backend.c verify-tofu.c pin.c tpm.c fips.c	\
 	safe-memfuncs.c inet_pton.c atfork.c atfork.h randomart.c \
 	system-keys.h urls.c urls.h prf.c auto-verify.c dh-session.c \
-	cert-session.c handshake-checks.c dtls-window.c
+	cert-session.c handshake-checks.c dtls-sw.c
 
 if WINDOWS
 COBJECTS += system-keys-win.c
diff --git a/lib/constate.c b/lib/constate.c
index 16ca0ae791..f4f28c2e62 100644
--- a/lib/constate.c
+++ b/lib/constate.c
@@ -34,6 +34,7 @@
 #include <state.h>
 #include <extensions.h>
 #include <buffers.h>
+#include "dtls.h"
 
 static int
 _gnutls_set_kx(gnutls_session_t session, gnutls_kx_algorithm_t algo);
@@ -378,7 +379,7 @@ int _gnutls_epoch_set_keys(gnutls_session_t session, uint16_t epoch)
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
-	params->record_sw_size = 0;
+	_dtls_reset_window(params);
 
 	_gnutls_record_log("REC[%p]: Epoch #%u ready\n", session,
 			   params->epoch);
diff --git a/lib/dtls-sw.c b/lib/dtls-sw.c
new file mode 100644
index 0000000000..616bd5a868
--- /dev/null
+++ b/lib/dtls-sw.c
@@ -0,0 +1,105 @@
+/*
+ * Copyright (C) 2016 Red Hat, Inc.
+ *
+ * Authors: Fridolin Pokorny
+ *          Nikos Mavrogiannopoulos
+ *
+ * This file is part of GNUTLS.
+ *
+ * The GNUTLS library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+/* Functions that relate to DTLS sliding window handling.
+ */
+
+#ifndef DTLS_SW_NO_INCLUDES
+#include "gnutls_int.h"
+#include "errors.h"
+#include "debug.h"
+#include "dtls.h"
+#include "record.h"
+#endif
+
+/*
+ * DTLS sliding window handling
+ */
+#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_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)))
+
+#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)))
+
+#define DTLS_WINDOW_UPDATE(W)		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);
+}
+
+/* Checks if a sequence number is not replayed. If a replayed
+ * packet is detected it returns a negative value (but no sensible error code).
+ * Otherwise zero.
+ */
+int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq)
+{
+	uint64_t seq_num = 0;
+	unsigned i;
+
+	LOAD_UINT64(seq_num, _seq->i);
+
+	if ((seq_num >> DTLS_EPOCH_SHIFT) != rp->epoch) {
+		return gnutls_assert_val(-1);
+	}
+
+	if (!DTLS_WINDOW_HAVE_RECV_PACKET(rp)) {
+		DTLS_WINDOW_INIT_AT(rp, seq_num);
+		rp->dtls_sw_have_recv = 1;
+		return 0;
+	}
+
+	/* are we inside sliding window? */
+	if (!DTLS_WINDOW_INSIDE(rp, seq_num)) {
+		return gnutls_assert_val(-2);
+	}
+
+	/* already received? */
+	if (DTLS_WINDOW_RECEIVED(rp, seq_num)) {
+		return gnutls_assert_val(-3);
+	}
+
+	DTLS_WINDOW_MARK(rp, seq_num);
+	DTLS_WINDOW_UPDATE(rp);
+
+	return 0;
+}
diff --git a/lib/dtls-window.c b/lib/dtls-window.c
deleted file mode 100644
index dd0be5d5ae..0000000000
--- a/lib/dtls-window.c
+++ /dev/null
@@ -1,159 +0,0 @@
-/*
- * Copyright (C) 2009-2016 Free Software Foundation, Inc.
- * Copyright (C) 2013-2016 Nikos Mavrogiannopoulos
- *
- * Authors: Jonathan Bastien-Filiatrault
- *          Nikos Mavrogiannopoulos
- *
- * This file is part of GNUTLS.
- *
- * The GNUTLS library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * as published by the Free Software Foundation; either version 2.1 of
- * the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>
- *
- */
-
-/* Functions that relate to DTLS window handling.
- */
-
-#include "gnutls_int.h"
-#include "errors.h"
-#include "debug.h"
-#include "dtls.h"
-#include "record.h"
-#include <mbuffers.h>
-#include <buffers.h>
-#include <constate.h>
-#include <state.h>
-#include <gnutls/dtls.h>
-
-#define window_table rp->record_sw
-#define window_size rp->record_sw_size
-#define window_head_idx rp->record_sw_head_idx
-
-#define LOAD_UINT48(out, ubytes) \
-	for (i = 2; i < 8; i++) { \
-		out <<= 8; \
-		out |= ubytes[i] & 0xff; \
-	}
-
-void _dtls_reset_window(gnutls_session_t session, uint8_t _seq[8])
-{
-	record_parameters_st *rp;
-	int ret;
-	unsigned i;
-	uint64_t seq = 0;
-
-	ret =
-	    _gnutls_epoch_get(session, EPOCH_READ_CURRENT, &rp);
-	if (ret < 0)
-		return;
-
-	LOAD_UINT48(seq, _seq);
-
-	if (seq == 0) {
-		window_size = 0;
-		window_head_idx = 0;
-		return;
-	}
-
-	window_size = 1;
-	window_head_idx = 0;
-	window_table[window_head_idx] = seq - 1;
-}
-
-static void slide_window(struct record_parameters_st *rp,
-			 unsigned int places)
-{
-	unsigned int old_head = window_head_idx;
-
-	if (places < window_size) {
-		window_head_idx += places;
-		window_head_idx %= DTLS_RECORD_WINDOW_SIZE;
-
-		window_table[window_head_idx] =
-		    window_table[old_head] + places;
-	} else {
-		unsigned int last_idx =
-		    (window_head_idx + window_size - 1) % window_size;
-		window_table[window_head_idx] = window_table[last_idx];
-	}
-}
-
-/* Checks if a sequence number is not replayed. If replayed
- * returns a negative error code, otherwise zero.
- */
-int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq)
-{
-	uint64_t seq = 0, diff;
-	unsigned int i, offset = 0;
-	unsigned int last_idx;
-
-	LOAD_UINT48(seq, _seq->i);
-
-	/* only two values allowed in window_size */
-	if (window_size == 0) {
-		window_size = 1;
-		window_head_idx = 0;
-		last_idx = window_size - 1;
-		window_table[last_idx] = window_table[window_head_idx] =
-		    seq;
-		return 0;
-	}
-
-	last_idx = (window_head_idx + window_size - 1) % window_size;
-
-	if (seq <= window_table[window_head_idx]) {
-		return -1;
-	}
-
-	if (seq <= window_table[last_idx]) {
-		/* is between first and last */
-		diff = window_table[last_idx] - seq;
-
-		if (diff >= window_size) {
-			return -1;
-		}
-
-		if (diff > last_idx) {
-			diff = diff - last_idx;
-			offset = window_size - 1 - diff;
-		} else
-			offset = last_idx - diff;
-
-		if (window_table[offset] == seq) {
-			return -1;
-		} else
-			window_table[offset] = seq;
-	} else {		/* seq > last */
-
-		diff = seq - window_table[last_idx];
-
-		if (window_size + diff <= DTLS_RECORD_WINDOW_SIZE) {
-			window_size += diff;
-		} else {
-			if (window_size < DTLS_RECORD_WINDOW_SIZE) {
-				offset =
-				    DTLS_RECORD_WINDOW_SIZE - window_size;
-				window_size = DTLS_RECORD_WINDOW_SIZE;
-				diff -= offset;
-			}
-
-			/* diff > 0 */
-			slide_window(rp, diff);
-		}
-
-		offset = (window_head_idx + window_size - 1) % window_size;
-		window_table[offset] = seq;
-	}
-	return 0;
-}
diff --git a/lib/dtls.h b/lib/dtls.h
index d5c8e1df88..e49a8a1344 100644
--- a/lib/dtls.h
+++ b/lib/dtls.h
@@ -32,7 +32,7 @@
 int _dtls_transmit(gnutls_session_t session);
 int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq);
 void _dtls_reset_hsk_state(gnutls_session_t session);
-void _dtls_reset_window(gnutls_session_t session, uint8_t sequence[8]);
+void _dtls_reset_window(struct record_parameters_st *rp);
 
 #define MAX_DTLS_TIMEOUT 60000
 
diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h
index 744261ffc2..bb3739c04e 100644
--- a/lib/gnutls_int.h
+++ b/lib/gnutls_int.h
@@ -1,6 +1,6 @@
 /*
- * Copyright (C) 2000-2015 Free Software Foundation, Inc.
- * Copyright (C) 2015 Red Hat, Inc.
+ * Copyright (C) 2000-2016 Free Software Foundation, Inc.
+ * Copyright (C) 2015-2016 Red Hat, Inc.
  *
  * Author: Nikos Mavrogiannopoulos
  *
@@ -123,7 +123,6 @@ typedef struct {
 #define GNUTLS_RANDOM_SIZE 32
 
 /* DTLS */
-#define DTLS_RECORD_WINDOW_SIZE 64
 #define DTLS_RETRANS_TIMEOUT 1000
 
 /* TLS Extensions */
@@ -620,10 +619,10 @@ struct record_parameters_st {
 	bool etm;
 	const mac_entry_st *mac;
 
-	/* for DTLS */
-	uint64_t record_sw[DTLS_RECORD_WINDOW_SIZE];
-	unsigned int record_sw_head_idx;
-	unsigned int record_sw_size;
+	/* for DTLS sliding window */
+	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;
 	record_state_st write;
diff --git a/lib/record.c b/lib/record.c
index ad60967662..4e462b9eac 100644
--- a/lib/record.c
+++ b/lib/record.c
@@ -1,6 +1,6 @@
 /*
- * Copyright (C) 2000-2013 Free Software Foundation, Inc.
- * Copyright (C) 2012,2013 Nikos Mavrogiannopoulos
+ * Copyright (C) 2000-2016 Free Software Foundation, Inc.
+ * Copyright (C) 2012-2016 Nikos Mavrogiannopoulos
  *
  * Author: Nikos Mavrogiannopoulos
  *
@@ -1194,6 +1194,7 @@ _gnutls_recv_in_buffers(gnutls_session_t session, content_type_t type,
 	if (bufel == NULL)
 		return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
 
+
 	/* We allocate the maximum possible to allow few compressed bytes to expand to a
 	 * full record. Moreover we add space for any pad and the MAC (in case
 	 * they are encrypted).
@@ -1229,11 +1230,10 @@ _gnutls_recv_in_buffers(gnutls_session_t session, content_type_t type,
 		goto sanity_check_error;
 	}
 
-	/* check for duplicates. We check after the message
-	 * is processed and authenticated to avoid someone
-	 * messing with our windows.
-	 */
 	if (IS_DTLS(session)) {
+		/* check for duplicates. We check after the message
+		 * is processed and authenticated to avoid someone
+		 * messing with our windows. */
 		if (likely(!(session->internals.flags & GNUTLS_NO_REPLAY_PROTECTION))) {
 			ret = _dtls_record_check(record_params, packet_sequence);
 			if (ret < 0) {
diff --git a/lib/state.c b/lib/state.c
index f96f43319b..b45237680f 100644
--- a/lib/state.c
+++ b/lib/state.c
@@ -1313,7 +1313,7 @@ gnutls_record_set_state(gnutls_session_t session,
 	memcpy(UINT64DATA(record_state->sequence_number), seq_number, 8);
 
 	if (IS_DTLS(session)) {
-		_dtls_reset_window(session, seq_number);
+		_dtls_reset_window(record_params);
 	}
 
 	return 0;