TLS 1.3: implement anti-replay measure using ClientHello recording

This implements ClientHello recording outlined in section 8.2 of RFC
8446.

Signed-off-by: Daiki Ueno <dueno@redhat.com>

16 files changed, 595 insertions, 16 deletions

diff --git a/.gitignore b/.gitignore
index d4a06fe3f7..c8b8ff40a3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -760,6 +760,7 @@ tests/tls12-resume-psk
 tests/tls12-resume-x509
 tests/tls12-rollback-detection
 tests/tls12-server-kx-neg
+tests/tls13/anti_replay
 tests/tls13-cert-key-exchange
 tests/tls13/change_cipher_spec
 tests/tls13-cipher-neg
diff --git a/doc/Makefile.am b/doc/Makefile.am
index 64095e9b60..6d6865fce9 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -673,6 +673,14 @@ FUNCS += functions/gnutls_anon_set_server_known_dh_params
 FUNCS += functions/gnutls_anon_set_server_known_dh_params.short
 FUNCS += functions/gnutls_anon_set_server_params_function
 FUNCS += functions/gnutls_anon_set_server_params_function.short
+FUNCS += functions/gnutls_anti_replay_deinit
+FUNCS += functions/gnutls_anti_replay_deinit.short
+FUNCS += functions/gnutls_anti_replay_enable
+FUNCS += functions/gnutls_anti_replay_enable.short
+FUNCS += functions/gnutls_anti_replay_init
+FUNCS += functions/gnutls_anti_replay_init.short
+FUNCS += functions/gnutls_anti_replay_set_window
+FUNCS += functions/gnutls_anti_replay_set_window.short
 FUNCS += functions/gnutls_auth_client_get_type
 FUNCS += functions/gnutls_auth_client_get_type.short
 FUNCS += functions/gnutls_auth_get_type
diff --git a/doc/manpages/Makefile.am b/doc/manpages/Makefile.am
index 7edbc45400..75c3aa7793 100644
--- a/doc/manpages/Makefile.am
+++ b/doc/manpages/Makefile.am
@@ -138,6 +138,10 @@ APIMANS += gnutls_anon_set_params_function.3
 APIMANS += gnutls_anon_set_server_dh_params.3
 APIMANS += gnutls_anon_set_server_known_dh_params.3
 APIMANS += gnutls_anon_set_server_params_function.3
+APIMANS += gnutls_anti_replay_deinit.3
+APIMANS += gnutls_anti_replay_enable.3
+APIMANS += gnutls_anti_replay_init.3
+APIMANS += gnutls_anti_replay_set_window.3
 APIMANS += gnutls_auth_client_get_type.3
 APIMANS += gnutls_auth_get_type.3
 APIMANS += gnutls_auth_server_get_type.3
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 6167c4e861..32a8511b33 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -99,7 +99,8 @@ COBJECTS += tls13/encrypted_extensions.c tls13/encrypted_extensions.h \
 	tls13/certificate.c tls13/certificate.h \
 	tls13/early_data.c tls13/early_data.h \
 	tls13/post_handshake.c \
-	tls13/psk_ext_parser.c tls13/psk_ext_parser.h
+	tls13/psk_ext_parser.c tls13/psk_ext_parser.h \
+	tls13/anti_replay.c tls13/anti_replay.h
 
 if ENABLE_PKCS11
 COBJECTS += pkcs11.c pkcs11x.c pkcs11_privkey.c pkcs11_write.c pkcs11_secret.c \
diff --git a/lib/errors.c b/lib/errors.c
index a83a49eeab..acdaf65bca 100644
--- a/lib/errors.c
+++ b/lib/errors.c
@@ -431,6 +431,8 @@ static const gnutls_error_entry error_entries[] = {
 		    GNUTLS_E_INSUFFICIENT_SECURITY),
 	ERROR_ENTRY(N_("No common key share with peer."),
 		    GNUTLS_E_NO_COMMON_KEY_SHARE),
+	ERROR_ENTRY(N_("The early data were rejected."),
+		    GNUTLS_E_EARLY_DATA_REJECTED),
 	{NULL, NULL, 0}
 };
 
diff --git a/lib/ext/early_data.c b/lib/ext/early_data.c
index 729a528bd7..a58e473ae1 100644
--- a/lib/ext/early_data.c
+++ b/lib/ext/early_data.c
@@ -59,10 +59,13 @@ early_data_recv_params(gnutls_session_t session,
 		return gnutls_assert_val(0);
 
 	if (session->security_parameters.entity == GNUTLS_SERVER) {
+		/* The flag may be cleared by pre_shared_key
+		 * extension, when replay is detected. */
 		if ((session->internals.flags & GNUTLS_ENABLE_EARLY_DATA) &&
 		    /* Refuse early data when this is a second CH after HRR */
 		    !(session->internals.hsk_flags & HSK_HRR_SENT))
 			session->internals.hsk_flags |= HSK_EARLY_DATA_ACCEPTED;
+
 		session->internals.hsk_flags |= HSK_EARLY_DATA_IN_FLIGHT;
 	} else {
 		if (_gnutls_ext_get_msg(session) == GNUTLS_EXT_FLAG_EE)
diff --git a/lib/ext/pre_shared_key.c b/lib/ext/pre_shared_key.c
index 7e4374042b..bc7fc8aa95 100644
--- a/lib/ext/pre_shared_key.c
+++ b/lib/ext/pre_shared_key.c
@@ -25,6 +25,7 @@
 #include "auth/psk.h"
 #include "handshake.h"
 #include "secrets.h"
+#include "tls13/anti_replay.h"
 #include "tls13/psk_ext_parser.h"
 #include "tls13/finished.h"
 #include "tls13/session_ticket.h"
@@ -482,7 +483,9 @@ static int server_recv_params(gnutls_session_t session,
 	struct psk_st psk;
 	psk_auth_info_t info;
 	tls13_ticket_st ticket_data;
-	uint32_t ticket_age;
+	/* These values should be set properly when session ticket is accepted. */
+	uint32_t ticket_age = UINT32_MAX;
+	struct timespec ticket_creation_time = { 0, 0 };
 	bool resuming;
 
 	ret = _gnutls13_psk_ext_parser_init(&psk_parser, data, len);
@@ -526,6 +529,10 @@ static int server_recv_params(gnutls_session_t session,
 				continue;
 			}
 
+			memcpy(&ticket_creation_time,
+			       &ticket_data.creation_time,
+			       sizeof(struct timespec));
+
 			tls13_ticket_deinit(&ticket_data);
 
 			resuming = 1;
@@ -612,6 +619,24 @@ static int server_recv_params(gnutls_session_t session,
 		info->username[psk.identity.size] = 0;
 		_gnutls_handshake_log("EXT[%p]: selected PSK identity: %s (%d)\n", session, info->username, psk_index);
 	} else {
+		if (session->internals.hsk_flags & HSK_EARLY_DATA_ACCEPTED) {
+			if (session->internals.anti_replay) {
+				ret = _gnutls_anti_replay_check(session,
+								ticket_age,
+								&ticket_creation_time,
+								&binder_recvd);
+				if (ret < 0) {
+					session->internals.hsk_flags &= ~HSK_EARLY_DATA_ACCEPTED;
+					_gnutls_handshake_log("EXT[%p]: replay detected; rejecting early data\n",
+						      session);
+				}
+			} else {
+				_gnutls_handshake_log("EXT[%p]: anti-replay is not enabled; rejecting early data\n",
+						      session);
+				session->internals.hsk_flags &= ~HSK_EARLY_DATA_ACCEPTED;
+			}
+		}
+
 		session->internals.resumed = RESUME_TRUE;
 		_gnutls_handshake_log("EXT[%p]: selected resumption PSK identity (%d)\n", session, psk_index);
 	}
diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h
index 42d68d4398..e34bea85b8 100644
--- a/lib/gnutls_int.h
+++ b/lib/gnutls_int.h
@@ -1460,6 +1460,9 @@ typedef struct {
 	/* the amount of early data received so far */
 	uint32_t early_data_received;
 
+	/* anti-replay measure for 0-RTT mode */
+	gnutls_anti_replay_t anti_replay;
+
 	/* If you add anything here, check _gnutls_handshake_internal_state_clear().
 	 */
 } internals_st;
diff --git a/lib/includes/gnutls/gnutls.h.in b/lib/includes/gnutls/gnutls.h.in
index 3a4d01d442..2af09bb24a 100644
--- a/lib/includes/gnutls/gnutls.h.in
+++ b/lib/includes/gnutls/gnutls.h.in
@@ -2991,6 +2991,17 @@ void gnutls_supplemental_recv(gnutls_session_t session, unsigned do_recv_supplem
 
 void gnutls_supplemental_send(gnutls_session_t session, unsigned do_send_supplemental);
 
+/* Anti-replay related functions */
+
+typedef struct gnutls_anti_replay_st *gnutls_anti_replay_t;
+
+int gnutls_anti_replay_init(gnutls_anti_replay_t *anti_replay);
+void gnutls_anti_replay_deinit(gnutls_anti_replay_t anti_replay);
+void gnutls_anti_replay_set_window(gnutls_anti_replay_t anti_replay,
+				   unsigned int window);
+void gnutls_anti_replay_enable(gnutls_session_t session,
+			       gnutls_anti_replay_t anti_replay);
+
 /* FIPS140-2 related functions */
 unsigned gnutls_fips140_mode_enabled(void);
 
@@ -3270,6 +3281,7 @@ void gnutls_fips140_set_mode(gnutls_fips_mode_t mode, unsigned flags);
 #define GNUTLS_E_CRL_VERIFICATION_ERROR -426
 #define GNUTLS_E_MISSING_EXTENSION -427
 #define GNUTLS_E_DB_ENTRY_EXISTS -428
+#define GNUTLS_E_EARLY_DATA_REJECTED -429
 
 #define GNUTLS_E_UNIMPLEMENTED_FEATURE -1250
 
diff --git a/lib/libgnutls.map b/lib/libgnutls.map
index a4aaf11ca1..3cfc0c450b 100644
--- a/lib/libgnutls.map
+++ b/lib/libgnutls.map
@@ -1256,6 +1256,10 @@ GNUTLS_3_6_5
 	gnutls_record_recv_early_data;
 	gnutls_db_check_entry_expire_time;
 	gnutls_db_set_add_function;
+	gnutls_anti_replay_init;
+	gnutls_anti_replay_deinit;
+	gnutls_anti_replay_set_window;
+	gnutls_anti_replay_enable;
 } GNUTLS_3_6_4;
 
 GNUTLS_FIPS140_3_4 {
@@ -1338,4 +1342,6 @@ GNUTLS_PRIVATE_3_4 {
 	_gnutls_set_session_ticket_key_rotation_callback;
 	# Internal symbols needed by tests/virt-time.h
 	_gnutls_global_set_gettime_function;
+	# Internal symbols needed by tests/tls13/anti_replay.c
+	_gnutls_anti_replay_check;
 } GNUTLS_3_4;
diff --git a/lib/tls13/anti_replay.c b/lib/tls13/anti_replay.c
new file mode 100644
index 0000000000..5ae9926afd
--- /dev/null
+++ b/lib/tls13/anti_replay.c
@@ -0,0 +1,221 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GnuTLS.
+ *
+ * The GnuTLS 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/>
+ *
+ */
+
+#include "gnutls_int.h"
+#include "db.h"
+#include "system.h"
+#include "tls13/anti_replay.h"
+
+/* The default time window in milliseconds; RFC8446 suggests the order
+ * of ten seconds is sufficient for the clients on the Internet. */
+#define DEFAULT_WINDOW_MS 10000
+
+struct gnutls_anti_replay_st {
+	uint32_t window;
+	struct timespec start_time;
+};
+
+/**
+ * gnutls_anti_replay_init:
+ * @anti_replay: is a pointer to #gnutls_anti_replay_t type
+ *
+ * This function will allocate and initialize the @anti_replay context
+ * to be usable for detect replay attacks. The context can then be
+ * attached to a @gnutls_session_t with
+ * gnutls_anti_replay_enable().
+ *
+ * Returns: Zero or a negative error code on error.
+ *
+ * Since: 3.6.5
+ **/
+int
+gnutls_anti_replay_init(gnutls_anti_replay_t *anti_replay)
+{
+	*anti_replay = gnutls_calloc(1, sizeof(struct gnutls_anti_replay_st));
+	if (!*anti_replay)
+		return gnutls_assert_val(GNUTLS_E_MEMORY_ERROR);
+
+	(*anti_replay)->window = DEFAULT_WINDOW_MS;
+
+	gnutls_gettime(&(*anti_replay)->start_time);
+
+	return 0;
+}
+
+/**
+ * gnutls_anti_replay_set_window:
+ * @anti_replay: is a #gnutls_anti_replay_t type.
+ * @window: is the time window recording ClientHello, in milliseconds
+ *
+ * Sets the time window used for ClientHello recording.  In order to
+ * protect against replay attacks, the server records ClientHello
+ * messages within this time period from the last update, and
+ * considers it a replay when a ClientHello outside of the period; if
+ * a ClientHello arrives within this period, the server checks the
+ * database and detects duplicates.
+ *
+ * For the details of the algorithm, see RFC 8446, section 8.2.
+ *
+ * Since: 3.6.5
+ */
+void
+gnutls_anti_replay_set_window(gnutls_anti_replay_t anti_replay,
+			      unsigned int window)
+{
+	anti_replay->window = window;
+}
+
+/**
+ * gnutls_anti_replay_deinit:
+ * @anti_replay: is a #gnutls_anti_replay type
+ *
+ * This function will deinitialize all resources occupied by the given
+ * anti-replay context.
+ *
+ * Since: 3.6.5
+ **/
+void
+gnutls_anti_replay_deinit(gnutls_anti_replay_t anti_replay)
+{
+	gnutls_free(anti_replay);
+}
+
+/**
+ * gnutls_anti_replay_enable:
+ * @session: is a #gnutls_session_t type.
+ * @anti_replay: is a #gnutls_anti_replay_t type.
+ *
+ * Request that the server should use anti-replay mechanism.
+ *
+ * Since: 3.6.5
+ **/
+void
+gnutls_anti_replay_enable(gnutls_session_t session,
+			  gnutls_anti_replay_t anti_replay)
+{
+	if (unlikely(session->security_parameters.entity != GNUTLS_SERVER)) {
+		gnutls_assert();
+		return;
+	}
+
+	session->internals.anti_replay = anti_replay;
+}
+
+int
+_gnutls_anti_replay_check(gnutls_session_t session,
+			  uint32_t client_ticket_age,
+			  struct timespec *ticket_creation_time,
+			  gnutls_datum_t *id)
+{
+	gnutls_anti_replay_t anti_replay = session->internals.anti_replay;
+	struct timespec now;
+	uint32_t server_ticket_age, diff;
+	gnutls_datum_t key = { NULL, 0 };
+	gnutls_datum_t entry = { NULL, 0 };
+	unsigned char key_buffer[MAX_HASH_SIZE + 12];
+	unsigned char entry_buffer[12]; /* magic + timestamp + expire_time */
+	unsigned char *p;
+	int ret;
+
+	if (unlikely(id->size > MAX_HASH_SIZE))
+		return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
+
+	gnutls_gettime(&now);
+	server_ticket_age = timespec_sub_ms(&now, ticket_creation_time);
+
+	/* It shouldn't be possible that the server's view of ticket
+	 * age is smaller than the client's view.
+	 */
+	if (unlikely(server_ticket_age < client_ticket_age))
+		return gnutls_assert_val(GNUTLS_E_ILLEGAL_PARAMETER);
+
+	/* If ticket is created before recording has started, discard
+	 * reject early data.
+	 */
+	if (_gnutls_timespec_cmp(ticket_creation_time,
+				 &anti_replay->start_time) < 0) {
+		_gnutls_handshake_log("anti_replay: ticket is created before recording has started\n");
+		return gnutls_assert_val(GNUTLS_E_EARLY_DATA_REJECTED);
+	}
+
+	/* If certain amount of time (window) has elapsed, rollover
+	 * the recording.
+	 */
+	diff = timespec_sub_ms(&now, &anti_replay->start_time);
+	if (diff > anti_replay->window)
+		gnutls_gettime(&anti_replay->start_time);
+
+	/* If expected_arrival_time is out of window, reject early
+	 * data.
+	 */
+	if (server_ticket_age - client_ticket_age > anti_replay->window) {
+		_gnutls_handshake_log("anti_replay: server ticket age: %u, client ticket age: %u\n",
+				      server_ticket_age,
+				      client_ticket_age);
+		return gnutls_assert_val(GNUTLS_E_EARLY_DATA_REJECTED);
+	}
+
+	/* Check if the ClientHello is stored in the database.
+	 */
+	if (!session->internals.db_add_func)
+		return gnutls_assert_val(GNUTLS_E_EARLY_DATA_REJECTED);
+
+	/* Create a key for database lookup, prefixing window start
+	 * time to ID.  Note that this shouldn't clash with session ID
+	 * used in TLS 1.2, because such IDs are 32 octets, while here
+	 * the key becomes 44+ octets.
+	 */
+	p = key_buffer;
+	_gnutls_write_uint32((uint64_t) anti_replay->start_time.tv_sec >> 32, p);
+	p += 4;
+	_gnutls_write_uint32(anti_replay->start_time.tv_sec & 0xFFFFFFFF, p);
+	p += 4;
+	_gnutls_write_uint32(anti_replay->start_time.tv_nsec, p);
+	p += 4;
+	memcpy(p, id->data, id->size);
+	p += id->size;
+	key.data = key_buffer;
+	key.size = p - key_buffer;
+
+	/* Create an entry to be stored on database if the lookup
+	 * failed.  This is formatted so that
+	 * gnutls_db_entry_is_expired() work.
+	 */
+	p = entry_buffer;
+	_gnutls_write_uint32(PACKED_SESSION_MAGIC, p);
+	p += 4;
+	_gnutls_write_uint32(now.tv_sec, p);
+	p += 4;
+	_gnutls_write_uint32(anti_replay->window / 1000, p);
+	p += 4;
+	entry.data = entry_buffer;
+	entry.size = p - entry_buffer;
+
+	ret = session->internals.db_add_func(session->internals.db_ptr,
+					     key, entry);
+	if (ret < 0) {
+		_gnutls_handshake_log("anti_replay: duplicate ClientHello found\n");
+		return gnutls_assert_val(GNUTLS_E_EARLY_DATA_REJECTED);
+	}
+
+	return 0;
+}
diff --git a/lib/tls13/anti_replay.h b/lib/tls13/anti_replay.h
new file mode 100644
index 0000000000..e44186c910
--- /dev/null
+++ b/lib/tls13/anti_replay.h
@@ -0,0 +1,26 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc.
+ *
+ * Author: Daiki Ueno
+ *
+ * This file is part of GnuTLS.
+ *
+ * The GnuTLS 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/>
+ *
+ */
+
+int _gnutls_anti_replay_check(gnutls_session_t session,
+			      uint32_t client_ticket_age,
+			      struct timespec *ticket_creation_time,
+			      gnutls_datum_t *id);
diff --git a/symbols.last b/symbols.last
index 1cb4050933..878c5c30b7 100644
--- a/symbols.last
+++ b/symbols.last
@@ -25,6 +25,10 @@ gnutls_anon_set_params_function@GNUTLS_3_4
 gnutls_anon_set_server_dh_params@GNUTLS_3_4
 gnutls_anon_set_server_known_dh_params@GNUTLS_3_4
 gnutls_anon_set_server_params_function@GNUTLS_3_4
+gnutls_anti_replay_deinit@GNUTLS_3_6_5
+gnutls_anti_replay_enable@GNUTLS_3_6_5
+gnutls_anti_replay_init@GNUTLS_3_6_5
+gnutls_anti_replay_set_window@GNUTLS_3_6_5
 gnutls_auth_client_get_type@GNUTLS_3_4
 gnutls_auth_get_type@GNUTLS_3_4
 gnutls_auth_server_get_type@GNUTLS_3_4
diff --git a/tests/Makefile.am b/tests/Makefile.am
index b3fee01e00..1ccba11028 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -109,7 +109,8 @@ ctests = tls13/supported_versions tls13/tls12-no-tls13-exts \
 	tls13/cookie tls13/key_share tls13/prf tls13/post-handshake-with-cert-ticket \
 	tls12-rollback-detection tls11-rollback-detection \
 	tls12-check-rollback-val tls11-check-rollback-val tls13/hello_random_value \
-	tls13/post-handshake-with-psk tls13/post-handshake-with-cert-auto
+	tls13/post-handshake-with-psk tls13/post-handshake-with-cert-auto \
+	tls13/anti_replay
 
 ctests += tls13/hello_retry_request
 
@@ -425,6 +426,16 @@ name_constraints_merge_CPPFLAGS = $(AM_CPPFLAGS) \
 	-I$(top_builddir)/gl	\
 	$(NETTLE_CFLAGS)
 
+murmur3_CPPFLAGS = $(AM_CPPFLAGS) \
+	-I$(top_srcdir)/gl	\
+	-I$(top_builddir)/gl	\
+	$(NETTLE_CFLAGS)
+
+tls13_anti_replay_CPPFLAGS = $(AM_CPPFLAGS) \
+	-I$(top_srcdir)/gl	\
+	-I$(top_builddir)/gl	\
+	$(NETTLE_CFLAGS)
+
 dist_check_SCRIPTS = rfc2253-escape-test rsa-md5-collision/rsa-md5-collision.sh systemkey.sh
 
 if !WINDOWS
diff --git a/tests/tls13-early-data.c b/tests/tls13-early-data.c
index 1189eb10c1..f23aec77fa 100644
--- a/tests/tls13-early-data.c
+++ b/tests/tls13-early-data.c
@@ -43,12 +43,14 @@ int main(void)
 #include <arpa/inet.h>
 #include <unistd.h>
 #include <gnutls/gnutls.h>
+#include <gnutls/crypto.h>
 #include <gnutls/dtls.h>
 #include <signal.h>
 #include <assert.h>
 
 #include "cert-common.h"
 #include "utils.h"
+#include "virt-time.h"
 
 /* This program tests the robustness of record sending with padding.
  */
@@ -73,6 +75,25 @@ static void client_log_func(int level, const char *str)
 #define EARLY_MSG "Hello TLS, it's early"
 #define PRIORITY "NORMAL:-VERS-ALL:+VERS-TLS1.3"
 
+static const
+gnutls_datum_t hrnd = {(void*)"\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00", 32};
+
+static int gnutls_rnd_works;
+
+int __attribute__ ((visibility ("protected")))
+gnutls_rnd(gnutls_rnd_level_t level, void *data, size_t len)
+{
+	gnutls_rnd_works = 1;
+
+	memset(data, 0xff, len);
+
+	/* Flip the first byte to avoid infinite loop in the RSA
+	 * blinding code of Nettle */
+	if (len > 0)
+		memset(data, 0x0, 1);
+	return 0;
+}
+
 static void client(int sds[])
 {
 	int ret;
@@ -87,6 +108,11 @@ static void client(int sds[])
 		gnutls_global_set_log_level(7);
 	}
 
+	/* Generate the same ob_ticket_age value, which affects the
+	 * binder calculation.
+	 */
+	virt_time_init();
+
 	gnutls_certificate_allocate_credentials(&x509_cred);
 
 	for (t = 0; t < SESSIONS; t++) {
@@ -102,6 +128,7 @@ static void client(int sds[])
 		if (t > 0) {
 			assert(gnutls_session_set_data(session, session_data.data, session_data.size) >= 0);
 			assert(gnutls_record_send_early_data(session, EARLY_MSG, sizeof(EARLY_MSG)) >= 0);
+			assert(gnutls_handshake_set_random(session, &hrnd) >= 0);
 		}
 
 		/* Perform the TLS handshake
@@ -130,7 +157,7 @@ static void client(int sds[])
 				fail("client: Getting resume data failed\n");
 		}
 
-		if (t == 1) {
+		if (t > 0) {
 			if (!gnutls_session_is_resumed(session)) {
 				fail("client: session_is_resumed error (%d)\n", t);
 			}
@@ -166,6 +193,55 @@ static void client(int sds[])
 
 static pid_t child;
 
+#define MAX_CLIENT_HELLO_RECORDED 10
+
+struct storage_st {
+	gnutls_datum_t entries[MAX_CLIENT_HELLO_RECORDED];
+	size_t num_entries;
+};
+
+static int
+storage_add(void *ptr, gnutls_datum_t key, gnutls_datum_t value)
+{
+	struct storage_st *storage = ptr;
+	gnutls_datum_t *datum;
+	size_t i;
+
+	for (i = 0; i < storage->num_entries; i++) {
+		if (key.size == storage->entries[i].size &&
+		    memcmp(storage->entries[i].data, key.data, key.size) == 0) {
+			return GNUTLS_E_DB_ENTRY_EXISTS;
+		}
+	}
+
+	/* If the maximum number of ClientHello exceeded, reject early
+	 * data until next time.
+	 */
+	if (storage->num_entries == MAX_CLIENT_HELLO_RECORDED)
+		return GNUTLS_E_DB_ERROR;
+
+	datum = &storage->entries[storage->num_entries];
+	datum->data = gnutls_malloc(key.size);
+	if (!datum->data)
+		return GNUTLS_E_MEMORY_ERROR;
+	memcpy(datum->data, key.data, key.size);
+	datum->size = key.size;
+
+	storage->num_entries++;
+
+	return 0;
+}
+
+static void
+storage_clear(struct storage_st *storage)
+{
+	size_t i;
+
+	for (i = 0; i < storage->num_entries; i++)
+		gnutls_free(storage->entries[i].data);
+	storage->num_entries = 0;
+}
+
 static void server(int sds[])
 {
 	int ret;
@@ -173,12 +249,15 @@ static void server(int sds[])
 	gnutls_session_t session;
 	gnutls_certificate_credentials_t x509_cred;
 	gnutls_datum_t session_ticket_key = { NULL, 0 };
+	struct storage_st storage;
+	gnutls_anti_replay_t anti_replay;
 	int t;
 
 	/* this must be called once in the program
 	 */
 	global_init();
 	memset(buffer, 0, sizeof(buffer));
+	memset(&storage, 0, sizeof(storage));
 
 	if (debug) {
 		gnutls_global_set_log_function(server_log_func);
@@ -192,6 +271,10 @@ static void server(int sds[])
 
 	gnutls_session_ticket_key_generate(&session_ticket_key);
 
+	ret = gnutls_anti_replay_init(&anti_replay);
+	if (ret < 0)
+		fail("server: failed to initialize anti-replay\n");
+
 	for (t = 0; t < SESSIONS; t++) {
 		int sd = sds[t];
 
@@ -204,6 +287,10 @@ static void server(int sds[])
 		gnutls_session_ticket_enable_server(session,
 						    &session_ticket_key);
 
+		gnutls_db_set_add_function(session, storage_add);
+		gnutls_db_set_ptr(session, &storage);
+		gnutls_anti_replay_enable(session, anti_replay);
+
 		gnutls_transport_set_int(session, sd);
 
 		do {
@@ -220,23 +307,39 @@ static void server(int sds[])
 		if (debug)
 			success("server: Handshake was completed\n");
 
-		if (t == 1) {
+		if (t > 0) {
 			if (!gnutls_session_is_resumed(session)) {
 				fail("server: session_is_resumed error (%d)\n", t);
 			}
 
-			if (!(gnutls_session_get_flags(session) & GNUTLS_SFLAGS_EARLY_DATA)) {
-				fail("server: early data is not received (%d)\n", t);
-			}
-
-			ret = gnutls_record_recv_early_data(session, buffer, sizeof(buffer));
-			if (ret < 0) {
-				fail("server: failed to retrieve early data: %s\n",
-				     gnutls_strerror(ret));
+			/* as we reuse the same ticket twice, expect
+			 * early data only on the first resumption */
+			if (t == 1) {
+				if (gnutls_rnd_works) {
+					if (!(gnutls_session_get_flags(session) & GNUTLS_SFLAGS_EARLY_DATA)) {
+						fail("server: early data is not received (%d)\n", t);
+					}
+				} else {
+					success("server: gnutls_rnd() could not be overridden, skip checking replay (%d)\n", t);
+				}
+
+				ret = gnutls_record_recv_early_data(session, buffer, sizeof(buffer));
+				if (ret < 0) {
+					fail("server: failed to retrieve early data: %s\n",
+					     gnutls_strerror(ret));
+				}
+
+				if (ret != sizeof(EARLY_MSG) || memcmp(buffer, EARLY_MSG, ret))
+					fail("server: early data mismatch\n");
+			} else {
+				if (gnutls_rnd_works) {
+					if (gnutls_session_get_flags(session) & GNUTLS_SFLAGS_EARLY_DATA) {
+						fail("server: early data is not rejected (%d)\n", t);
+					}
+				} else {
+					success("server: gnutls_rnd() could not be overridden, skip checking replay (%d)\n", t);
+				}
 			}
-
-			if (ret != sizeof(EARLY_MSG) || memcmp(buffer, EARLY_MSG, ret))
-				fail("server: early data mismatch\n");
 		}
 
 		/* see the Getting peer's information example */
@@ -271,6 +374,10 @@ static void server(int sds[])
 		gnutls_deinit(session);
 	}
 
+	gnutls_anti_replay_deinit(anti_replay);
+
+	storage_clear(&storage);
+
 	gnutls_free(session_ticket_key.data);
 
 	gnutls_certificate_free_credentials(x509_cred);
diff --git a/tests/tls13/anti_replay.c b/tests/tls13/anti_replay.c
new file mode 100644
index 0000000000..090dcabbdb
--- /dev/null
+++ b/tests/tls13/anti_replay.c
@@ -0,0 +1,145 @@
+/*
+ * Copyright (C) 2015-2018 Red Hat, Inc.
+ *
+ * This file is part of GnuTLS.
+ *
+ * GnuTLS is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuTLS 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
+ * 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/>
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <assert.h>
+#include <stdint.h>
+
+#include "utils.h"
+#include "virt-time.h"
+#include "../../lib/tls13/anti_replay.h"
+#include "../../lib/system.h"
+
+#define MAX_CLIENT_HELLO_RECORDED 10
+
+struct storage_st {
+	gnutls_datum_t entries[MAX_CLIENT_HELLO_RECORDED];
+	size_t num_entries;
+};
+
+static int
+storage_add(void *ptr, gnutls_datum_t key, gnutls_datum_t value)
+{
+	struct storage_st *storage = ptr;
+	gnutls_datum_t *datum;
+	size_t i;
+
+	for (i = 0; i < storage->num_entries; i++) {
+		if (key.size == storage->entries[i].size &&
+		    memcmp(storage->entries[i].data, key.data, key.size) == 0) {
+			return GNUTLS_E_DB_ENTRY_EXISTS;
+		}
+	}
+
+	/* If the maximum number of ClientHello exceeded, reject early
+	 * data until next time.
+	 */
+	if (storage->num_entries == MAX_CLIENT_HELLO_RECORDED)
+		return GNUTLS_E_DB_ERROR;
+
+	datum = &storage->entries[storage->num_entries];
+	datum->data = gnutls_malloc(key.size);
+	if (!datum->data)
+		return GNUTLS_E_MEMORY_ERROR;
+	memcpy(datum->data, key.data, key.size);
+	datum->size = key.size;
+
+	storage->num_entries++;
+
+	return 0;
+}
+
+static void
+storage_clear(struct storage_st *storage)
+{
+	size_t i;
+
+	for (i = 0; i < storage->num_entries; i++)
+		gnutls_free(storage->entries[i].data);
+	storage->num_entries = 0;
+}
+
+void doit(void)
+{
+	gnutls_anti_replay_t anti_replay;
+	gnutls_datum_t key = { (unsigned char *) "\xFF\xFF\xFF\xFF", 4 };
+	struct timespec creation_time;
+	struct storage_st storage;
+	gnutls_session_t session;
+	int ret;
+
+	virt_time_init();
+	memset(&storage, 0, sizeof(storage));
+
+	/* server_ticket_age < client_ticket_age */
+	ret = gnutls_anti_replay_init(&anti_replay);
+	assert(ret == 0);
+	gnutls_anti_replay_set_window(anti_replay, 10000);
+	gnutls_init(&session, GNUTLS_SERVER);
+	gnutls_db_set_add_function(session, storage_add);
+	gnutls_db_set_ptr(session, &storage);
+	gnutls_anti_replay_enable(session, anti_replay);
+	mygettime(&creation_time);
+	ret = _gnutls_anti_replay_check(session, 10000, &creation_time, &key);
+	if (ret != GNUTLS_E_ILLEGAL_PARAMETER)
+		fail("error is not returned, while server_ticket_age < client_ticket_age\n");
+	gnutls_deinit(session);
+	gnutls_anti_replay_deinit(anti_replay);
+	storage_clear(&storage);
+
+	/* server_ticket_age - client_ticket_age > window */
+	ret = gnutls_anti_replay_init(&anti_replay);
+	assert(ret == 0);
+	gnutls_anti_replay_set_window(anti_replay, 10000);
+	gnutls_init(&session, GNUTLS_SERVER);
+	gnutls_db_set_add_function(session, storage_add);
+	gnutls_db_set_ptr(session, &storage);
+	gnutls_anti_replay_enable(session, anti_replay);
+	mygettime(&creation_time);
+	virt_sec_sleep(30);
+	ret = _gnutls_anti_replay_check(session, 10000, &creation_time, &key);
+	if (ret != GNUTLS_E_EARLY_DATA_REJECTED)
+		fail("early data is NOT rejected, while freshness check fails\n");
+	gnutls_deinit(session);
+	gnutls_anti_replay_deinit(anti_replay);
+	storage_clear(&storage);
+
+	/* server_ticket_age - client_ticket_age < window */
+	ret = gnutls_anti_replay_init(&anti_replay);
+	assert(ret == 0);
+	gnutls_anti_replay_set_window(anti_replay, 10000);
+	gnutls_init(&session, GNUTLS_SERVER);
+	gnutls_db_set_add_function(session, storage_add);
+	gnutls_db_set_ptr(session, &storage);
+	gnutls_anti_replay_enable(session, anti_replay);
+	mygettime(&creation_time);
+	virt_sec_sleep(15);
+	ret = _gnutls_anti_replay_check(session, 10000, &creation_time, &key);
+	if (ret != 0)
+		fail("early data is rejected, while freshness check succeeds\n");
+	ret = _gnutls_anti_replay_check(session, 10000, &creation_time, &key);
+	if (ret != GNUTLS_E_EARLY_DATA_REJECTED)
+		fail("early data is NOT rejected for a duplicate key\n");
+	gnutls_deinit(session);
+	gnutls_anti_replay_deinit(anti_replay);
+	storage_clear(&storage);
+}