tls1.3: server returns early on handshake when no cert is provided by client

Under TLS1.3 the server knows the negotiated keys early, if no client
certificate is sent. In that case, the server is not only able to
transmit the session ticket immediately after its finished message,
but is also able to transmit data, similarly to false start.

Resolves #481
Resolves #457

Signed-off-by: Nikos Mavrogiannopoulos <nmav@redhat.com>

13 files changed, 324 insertions, 96 deletions

diff --git a/lib/alert.c b/lib/alert.c
index 6b19507780..5755970ca1 100644
--- a/lib/alert.c
+++ b/lib/alert.c
@@ -209,6 +209,7 @@ int gnutls_error_to_alert(int err, int *level)
 	case GNUTLS_E_UNEXPECTED_PACKET_LENGTH:
 	case GNUTLS_E_UNEXPECTED_EXTENSIONS_LENGTH:
 	case GNUTLS_E_NO_CERTIFICATE_FOUND:
+	case GNUTLS_E_HANDSHAKE_TOO_LARGE:
 		ret = GNUTLS_A_DECODE_ERROR;
 		_level = GNUTLS_AL_FATAL;
 		break;
diff --git a/lib/constate.c b/lib/constate.c
index e43bad811a..3ff6b526da 100644
--- a/lib/constate.c
+++ b/lib/constate.c
@@ -262,34 +262,34 @@ _tls13_update_keys(gnutls_session_t session, hs_stage_t stage,
 		ret = _tls13_expand_secret(session, APPLICATION_TRAFFIC_UPDATE,
 					   sizeof(APPLICATION_TRAFFIC_UPDATE)-1,
 					   NULL, 0,
-					   session->key.proto.tls13.hs_ckey,
+					   session->key.proto.tls13.ap_ckey,
 					   session->security_parameters.prf->output_size,
-					   session->key.proto.tls13.hs_ckey);
+					   session->key.proto.tls13.ap_ckey);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 
-		ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.hs_ckey, key_size, key_block);
+		ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.ap_ckey, key_size, key_block);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 
-		ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.hs_ckey, iv_size, iv_block);
+		ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.ap_ckey, iv_size, iv_block);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 	} else {
 		ret = _tls13_expand_secret(session, APPLICATION_TRAFFIC_UPDATE,
 					   sizeof(APPLICATION_TRAFFIC_UPDATE)-1,
 					   NULL, 0,
-					   session->key.proto.tls13.hs_skey,
+					   session->key.proto.tls13.ap_skey,
 					   session->security_parameters.prf->output_size,
-					   session->key.proto.tls13.hs_skey);
+					   session->key.proto.tls13.ap_skey);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 
-		ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.hs_skey, key_size, key_block);
+		ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.ap_skey, key_size, key_block);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 
-		ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.hs_skey, iv_size, iv_block);
+		ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.ap_skey, iv_size, iv_block);
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 	}
@@ -335,6 +335,7 @@ _tls13_set_keys(gnutls_session_t session, hs_stage_t stage,
 	const char *label;
 	unsigned label_size, hsk_len;
 	const char *keylog_label;
+	void *ckey, *skey;
 	int ret;
 
 	if (stage == STAGE_UPD_OURS || stage == STAGE_UPD_PEERS)
@@ -346,31 +347,33 @@ _tls13_set_keys(gnutls_session_t session, hs_stage_t stage,
 		label_size = sizeof(HANDSHAKE_CLIENT_TRAFFIC_LABEL)-1;
 		hsk_len = session->internals.handshake_hash_buffer.length;
 		keylog_label = "CLIENT_HANDSHAKE_TRAFFIC_SECRET";
+		ckey = session->key.proto.tls13.hs_ckey;
 	} else {
 		label = APPLICATION_CLIENT_TRAFFIC_LABEL;
 		label_size = sizeof(APPLICATION_CLIENT_TRAFFIC_LABEL)-1;
 		hsk_len = session->internals.handshake_hash_buffer_server_finished_len;
 		keylog_label = "CLIENT_TRAFFIC_SECRET_0";
+		ckey = session->key.proto.tls13.ap_ckey;
 	}
 
 	ret = _tls13_derive_secret(session, label, label_size,
 				   session->internals.handshake_hash_buffer.data,
 				   hsk_len,
 				   session->key.proto.tls13.temp_secret,
-				   session->key.proto.tls13.hs_ckey);
+				   ckey);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
 	_gnutls_nss_keylog_write(session, keylog_label,
-				 session->key.proto.tls13.hs_ckey,
+				 ckey,
 				 session->security_parameters.prf->output_size);
 
 	/* client keys */
-	ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.hs_ckey, key_size, ckey_block);
+	ret = _tls13_expand_secret(session, "key", 3, NULL, 0, ckey, key_size, ckey_block);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
-	ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.hs_ckey, iv_size, civ_block);
+	ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, ckey, iv_size, civ_block);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
@@ -379,30 +382,32 @@ _tls13_set_keys(gnutls_session_t session, hs_stage_t stage,
 		label = HANDSHAKE_SERVER_TRAFFIC_LABEL;
 		label_size = sizeof(HANDSHAKE_SERVER_TRAFFIC_LABEL)-1;
 		keylog_label = "SERVER_HANDSHAKE_TRAFFIC_SECRET";
+		skey = session->key.proto.tls13.hs_skey;
 	} else {
 		label = APPLICATION_SERVER_TRAFFIC_LABEL;
 		label_size = sizeof(APPLICATION_SERVER_TRAFFIC_LABEL)-1;
 		keylog_label = "SERVER_TRAFFIC_SECRET_0";
+		skey = session->key.proto.tls13.ap_skey;
 	}
 
 	ret = _tls13_derive_secret(session, label, label_size,
 				   session->internals.handshake_hash_buffer.data,
 				   hsk_len,
 				   session->key.proto.tls13.temp_secret,
-				   session->key.proto.tls13.hs_skey);
+				   skey);
 
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
 	_gnutls_nss_keylog_write(session, keylog_label,
-				 session->key.proto.tls13.hs_skey,
+				 skey,
 				 session->security_parameters.prf->output_size);
 
-	ret = _tls13_expand_secret(session, "key", 3, NULL, 0, session->key.proto.tls13.hs_skey, key_size, skey_block);
+	ret = _tls13_expand_secret(session, "key", 3, NULL, 0, skey, key_size, skey_block);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
-	ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, session->key.proto.tls13.hs_skey, iv_size, siv_block);
+	ret = _tls13_expand_secret(session, "iv", 2, NULL, 0, skey, iv_size, siv_block);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
@@ -1012,6 +1017,44 @@ int _tls13_connection_state_init(gnutls_session_t session, hs_stage_t stage)
 	return 0;
 }
 
+int _tls13_read_connection_state_init(gnutls_session_t session, hs_stage_t stage)
+{
+	const uint16_t epoch_next =
+	    session->security_parameters.epoch_next;
+	int ret;
+
+	ret = _gnutls_epoch_set_keys(session, epoch_next, stage);
+	if (ret < 0)
+		return ret;
+
+	_gnutls_handshake_log("HSK[%p]: TLS 1.3 set read key with cipher suite: %s\n",
+			      session,
+			      session->security_parameters.cs->name);
+
+	session->security_parameters.epoch_read = epoch_next;
+
+	return 0;
+}
+
+int _tls13_write_connection_state_init(gnutls_session_t session, hs_stage_t stage)
+{
+	const uint16_t epoch_next =
+	    session->security_parameters.epoch_next;
+	int ret;
+
+	ret = _gnutls_epoch_set_keys(session, epoch_next, stage);
+	if (ret < 0)
+		return ret;
+
+	_gnutls_handshake_log("HSK[%p]: TLS 1.3 set write key with cipher suite: %s\n",
+			      session,
+			      session->security_parameters.cs->name);
+
+	session->security_parameters.epoch_write = epoch_next;
+
+	return 0;
+}
+
 static int
 _tls13_init_record_state(gnutls_cipher_algorithm_t algo, record_state_st *state)
 {
diff --git a/lib/constate.h b/lib/constate.h
index 8a15400f5f..125a48f8f2 100644
--- a/lib/constate.h
+++ b/lib/constate.h
@@ -46,6 +46,8 @@ void _gnutls_epoch_free(gnutls_session_t session,
 void _gnutls_set_resumed_parameters(gnutls_session_t session);
 
 int _tls13_connection_state_init(gnutls_session_t session, hs_stage_t stage);
+int _tls13_read_connection_state_init(gnutls_session_t session, hs_stage_t stage);
+int _tls13_write_connection_state_init(gnutls_session_t session, hs_stage_t stage);
 
 static inline int _gnutls_epoch_is_valid(gnutls_session_t session,
 					 int epoch)
diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h
index 6525282a69..c19a909225 100644
--- a/lib/gnutls_int.h
+++ b/lib/gnutls_int.h
@@ -269,7 +269,7 @@ typedef enum handshake_state_t { STATE0 = 0, STATE1, STATE2,
 	STATE90=90, STATE91, STATE92, STATE93, STATE94, STATE99=99,
 	STATE100=100, STATE101, STATE102, STATE103, STATE104,
 	STATE105, STATE106, STATE107, STATE108, STATE109, STATE110,
-	STATE111, STATE112,
+	STATE111, STATE112, STATE113, STATE114,
 	STATE150 /* key update */
 } handshake_state_t;
 
@@ -299,9 +299,14 @@ typedef enum heartbeat_state_t {
 typedef enum recv_state_t {
 	RECV_STATE_0 = 0,
 	RECV_STATE_DTLS_RETRANSMIT,
+	/* client-side false start state */
 	RECV_STATE_FALSE_START_HANDLING, /* we are calling gnutls_handshake() within record_recv() */
 	RECV_STATE_FALSE_START, /* gnutls_record_recv() should complete the handshake */
-	RECV_STATE_ASYNC_HANDSHAKE /* an incomplete async handshake message was seen */
+	/* async handshake msg state */
+	RECV_STATE_ASYNC_HANDSHAKE, /* an incomplete async handshake message was seen */
+	/* server-side early start under TLS1.3; enabled when no client cert is received */
+	RECV_STATE_EARLY_START_HANDLING, /* we are calling gnutls_handshake() within record_recv() */
+	RECV_STATE_EARLY_START /* gnutls_record_recv() should complete the handshake */
 } recv_state_t;
 
 #include "str.h"
@@ -504,8 +509,10 @@ struct gnutls_key_st {
 			 * early_secret, client_early_traffic_secret, ... */
 			uint8_t temp_secret[MAX_HASH_SIZE];
 			unsigned temp_secret_size; /* depends on negotiated PRF size */
-			uint8_t hs_ckey[MAX_HASH_SIZE]; /* client_hs_traffic_secret/client_ap_traffic_secret */
-			uint8_t hs_skey[MAX_HASH_SIZE]; /* server_hs_traffic_secret/server_ap_traffic_secret */
+			uint8_t hs_ckey[MAX_HASH_SIZE]; /* client_hs_traffic_secret */
+			uint8_t hs_skey[MAX_HASH_SIZE]; /* server_hs_traffic_secret */
+			uint8_t ap_ckey[MAX_HASH_SIZE]; /* client_ap_traffic_secret */
+			uint8_t ap_skey[MAX_HASH_SIZE]; /* server_ap_traffic_secret */
 			uint8_t ap_expkey[MAX_HASH_SIZE]; /* exporter_master_secret */
 			uint8_t ap_rms[MAX_HASH_SIZE]; /* resumption_master_secret */
 		} tls13; /* tls1.3 */
@@ -1279,6 +1286,7 @@ typedef struct {
 				       * server: a ticket was sent to client.
 				       */
 #define HSK_TICKET_RECEIVED (1<<20) /* client: a session ticket was received */
+#define HSK_EARLY_START_USED (1<<21)
 
 	/* The hsk_flags are for use within the ongoing handshake;
 	 * they are reset to zero prior to handshake start by gnutls_handshake. */
diff --git a/lib/handshake-tls13.c b/lib/handshake-tls13.c
index ffd1b1531d..a8666186c7 100644
--- a/lib/handshake-tls13.c
+++ b/lib/handshake-tls13.c
@@ -56,7 +56,8 @@
 #include "tls13/key_update.h"
 #include "ext/pre_shared_key.h"
 
-static int generate_hs_traffic_keys(gnutls_session_t session);
+static int generate_rms_keys(gnutls_session_t session);
+static int generate_and_set_hs_traffic_keys(gnutls_session_t session);
 static int generate_ap_traffic_keys(gnutls_session_t session);
 
 #define SAVE_TRANSCRIPT \
@@ -90,9 +91,9 @@ int _gnutls13_handshake_client(gnutls_session_t session)
 		/* fall through */
 	case STATE101:
 		ret =
-		    generate_hs_traffic_keys(session);
+		    generate_and_set_hs_traffic_keys(session);
 		STATE = STATE101;
-		IMED_RET("generate session keys", ret, 0);
+		IMED_RET_FATAL("generate session keys", ret, 0);
 		/* fall through */
 	case STATE102:
 		ret = _gnutls13_recv_encrypted_extensions(session);
@@ -141,10 +142,18 @@ int _gnutls13_handshake_client(gnutls_session_t session)
 		IMED_RET("send finished", ret, 0);
 		/* fall through */
 	case STATE111:
+		STATE = STATE111;
+
 		ret =
 		    generate_ap_traffic_keys(session);
-		STATE = STATE111;
-		IMED_RET("generate app keys", ret, 0);
+		IMED_RET_FATAL("generate app keys", ret, 0);
+
+		ret = generate_rms_keys(session);
+		IMED_RET_FATAL("generate rms keys", ret, 0);
+
+		/* set traffic keys */
+		ret = _tls13_connection_state_init(session, STAGE_APP);
+		IMED_RET_FATAL("set app keys", ret, 0);
 
 		STATE = STATE0;
 		break;
@@ -152,6 +161,7 @@ int _gnutls13_handshake_client(gnutls_session_t session)
 		return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
 	}
 
+
 	/* explicitly reset any false start flags */
 	session->internals.recv_state = RECV_STATE_0;
 	session->internals.initial_negotiation_completed = 1;
@@ -164,6 +174,58 @@ int _gnutls13_handshake_client(gnutls_session_t session)
 	return 0;
 }
 
+static int generate_non_auth_rms_keys(gnutls_session_t session)
+{
+	int ret;
+	/* we simulate client finished */
+	uint8_t finished[MAX_HASH_SIZE+TLS_HANDSHAKE_HEADER_SIZE];
+	unsigned spos;
+
+	ret = _gnutls13_compute_finished(session->security_parameters.prf,
+					 session->key.proto.tls13.hs_ckey,
+					 &session->internals.handshake_hash_buffer,
+					 finished+TLS_HANDSHAKE_HEADER_SIZE);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	spos = session->internals.handshake_hash_buffer.length;
+
+	finished[0] = GNUTLS_HANDSHAKE_FINISHED;
+	_gnutls_write_uint24(session->security_parameters.prf->output_size, finished+1);
+
+	ret = _gnutls_buffer_append_data(&session->internals.handshake_hash_buffer, finished,
+					 TLS_HANDSHAKE_HEADER_SIZE+session->security_parameters.prf->output_size);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	ret = _tls13_derive_secret(session, RMS_MASTER_LABEL, sizeof(RMS_MASTER_LABEL)-1,
+				   session->internals.handshake_hash_buffer.data,
+				   session->internals.handshake_hash_buffer.length,
+				   session->key.proto.tls13.temp_secret,
+				   session->key.proto.tls13.ap_rms);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	session->internals.handshake_hash_buffer.length = spos;
+
+	return 0;
+}
+
+static int generate_rms_keys(gnutls_session_t session)
+{
+	int ret;
+
+	ret = _tls13_derive_secret(session, RMS_MASTER_LABEL, sizeof(RMS_MASTER_LABEL)-1,
+				   session->internals.handshake_hash_buffer.data,
+				   session->internals.handshake_hash_buffer_client_finished_len,
+				   session->key.proto.tls13.temp_secret,
+				   session->key.proto.tls13.ap_rms);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	return 0;
+}
+
 static int generate_ap_traffic_keys(gnutls_session_t session)
 {
 	int ret;
@@ -192,27 +254,15 @@ static int generate_ap_traffic_keys(gnutls_session_t session)
 				 session->key.proto.tls13.ap_expkey,
 				 session->security_parameters.prf->output_size);
 
-	ret = _tls13_derive_secret(session, RMS_MASTER_LABEL, sizeof(RMS_MASTER_LABEL)-1,
-				   session->internals.handshake_hash_buffer.data,
-				   session->internals.handshake_hash_buffer_client_finished_len,
-				   session->key.proto.tls13.temp_secret,
-				   session->key.proto.tls13.ap_rms);
-	if (ret < 0)
-		return gnutls_assert_val(ret);
-
 	_gnutls_epoch_bump(session);
 	ret = _gnutls_epoch_dup(session);
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
-	ret = _tls13_connection_state_init(session, STAGE_APP);
-	if (ret < 0)
-		return gnutls_assert_val(ret);
-
 	return 0;
 }
 
-static int generate_hs_traffic_keys(gnutls_session_t session)
+static int generate_and_set_hs_traffic_keys(gnutls_session_t session)
 {
 	int ret;
 	unsigned null_key = 0;
@@ -268,6 +318,8 @@ static int generate_hs_traffic_keys(gnutls_session_t session)
 	return 0;
 }
 
+#define TICKETS_TO_SEND 1
+
 /*
  * _gnutls13_handshake_server
  * This function does the server stuff of the handshake protocol.
@@ -280,7 +332,7 @@ int _gnutls13_handshake_server(gnutls_session_t session)
 	case STATE90:
 		ret = _gnutls13_handshake_hash_buffers_synth(session, session->security_parameters.prf, 0);
 		STATE = STATE90;
-		IMED_RET("reset handshake buffers", ret, 0);
+		IMED_RET_FATAL("reset handshake buffers", ret, 0);
 		/* fall through */
 	case STATE91:
 		ret = _gnutls13_send_hello_retry_request(session, AGAIN(STATE91));
@@ -329,9 +381,9 @@ int _gnutls13_handshake_server(gnutls_session_t session)
 		/* fall through */
 	case STATE101:
 		ret =
-		    generate_hs_traffic_keys(session);
+		    generate_and_set_hs_traffic_keys(session);
 		STATE = STATE101;
-		IMED_RET("generate session keys", ret, 0);
+		IMED_RET_FATAL("generate session keys", ret, 0);
 		/* fall through */
 	case STATE102:
 		ret = _gnutls13_send_encrypted_extensions(session, AGAIN(STATE102));
@@ -359,40 +411,96 @@ int _gnutls13_handshake_server(gnutls_session_t session)
 		IMED_RET("send finished", ret, 0);
 		/* fall through */
 	case STATE107:
+		/* At this point our sending keys should be the app keys
+		 * see 4.4.4 at draft-ietf-tls-tls13-28 */
+		ret =
+		    generate_ap_traffic_keys(session);
+		IMED_RET_FATAL("generate app keys", ret, 0);
+
+		/* If the session is unauthenticated, try to optimize the handshake by
+		 * sending the session ticket early. */
+		if (!(session->internals.hsk_flags & (HSK_CRT_REQ_SENT|HSK_PSK_SELECTED))) {
+			STATE = STATE107;
+
+			ret = generate_non_auth_rms_keys(session);
+			IMED_RET_FATAL("generate rms keys", ret, 0);
+
+			session->internals.hsk_flags |= HSK_EARLY_START_USED;
+			_gnutls_handshake_log("HSK[%p]: unauthenticated session eligible for early start\n", session);
+		}
+
+		ret = _tls13_write_connection_state_init(session, STAGE_APP);
+		IMED_RET_FATAL("set write app keys", ret, 0);
+
+		_gnutls_handshake_log("HSK[%p]: switching early to application traffic keys\n", session);
+
+		/* fall through */
+	case STATE108:
+		if (session->internals.resumed != RESUME_FALSE)
+			_gnutls_set_resumed_parameters(session);
+
+		if (session->internals.hsk_flags & HSK_EARLY_START_USED) {
+			ret = _gnutls13_send_session_ticket(session, TICKETS_TO_SEND,
+							    AGAIN(STATE108));
+
+			STATE = STATE108;
+			IMED_RET("send session ticket", ret, 0);
+
+			/* complete this phase of the handshake. We
+			 * should be called again by gnutls_record_recv()
+			 */
+
+			if (session->internals.flags & GNUTLS_ENABLE_EARLY_START) {
+				STATE = STATE112; /* finished */
+				gnutls_assert();
+
+				session->internals.recv_state = RECV_STATE_EARLY_START;
+				return 0;
+			}
+		}
+		/* fall through */
+	case STATE109:
 		ret = _gnutls13_recv_certificate(session);
-		STATE = STATE107;
+		STATE = STATE109;
 		IMED_RET("recv certificate", ret, 0);
 		/* fall through */
-	case STATE108:
+	case STATE110:
 		ret = _gnutls13_recv_certificate_verify(session);
-		STATE = STATE108;
+		STATE = STATE110;
 		IMED_RET("recv certificate verify", ret, 0);
 		/* fall through */
-	case STATE109:
+	case STATE111:
 		ret = _gnutls_run_verify_callback(session, GNUTLS_CLIENT);
-		STATE = STATE109;
+		STATE = STATE111;
 		if (ret < 0)
 			return gnutls_assert_val(ret);
 		/* fall through */
-	case STATE110:
+	case STATE112: /* can enter from STATE108 */
 		ret = _gnutls13_recv_finished(session);
-		STATE = STATE110;
+		STATE = STATE112;
 		IMED_RET("recv finished", ret, 0);
 		/* fall through */
-	case STATE111:
-		ret =
-		    generate_ap_traffic_keys(session);
-		STATE = STATE111;
-		IMED_RET("generate app keys", ret, 0);
+	case STATE113:
+		/* If we did request a client certificate, then we can
+		 * only send the tickets here */
+		STATE = STATE113;
+
+		if (!(session->internals.hsk_flags & HSK_EARLY_START_USED)) {
+			ret = generate_rms_keys(session);
+			IMED_RET_FATAL("generate rms keys", ret, 0);
+		}
 
-		if (session->internals.resumed != RESUME_FALSE)
-			_gnutls_set_resumed_parameters(session);
-		/* fall through */
-	case STATE112:
+		ret = _tls13_read_connection_state_init(session, STAGE_APP);
+		IMED_RET_FATAL("set read app keys", ret, 0);
 
-		ret = _gnutls13_send_session_ticket(session, 1, AGAIN(STATE112));
-		STATE = STATE112;
-		IMED_RET("send session ticket", ret, 0);
+		/* fall through */
+	case STATE114:
+		if (!(session->internals.hsk_flags & (HSK_TLS13_TICKET_SENT|HSK_EARLY_START_USED))) {
+			ret = _gnutls13_send_session_ticket(session, TICKETS_TO_SEND,
+							    AGAIN(STATE114));
+			STATE = STATE114;
+			IMED_RET("send session ticket", ret, 0);
+		}
 
 		STATE = STATE0;
 		break;
diff --git a/lib/handshake.c b/lib/handshake.c
index d0c0f9dc97..ba3911d160 100644
--- a/lib/handshake.c
+++ b/lib/handshake.c
@@ -2462,8 +2462,9 @@ int gnutls_rehandshake(gnutls_session_t session)
 	if (session->security_parameters.entity == GNUTLS_CLIENT)
 		return GNUTLS_E_INVALID_REQUEST;
 
-	if (vers->tls13_sem)
+	if (vers->tls13_sem) {
 		return gnutls_session_key_update(session, GNUTLS_KU_PEER);
+	}
 
 	_dtls_async_timer_delete(session);
 
@@ -2652,9 +2653,8 @@ int gnutls_handshake(gnutls_session_t session)
 	}
 
 	/* clear handshake buffer */
-	if (session->security_parameters.entity != GNUTLS_CLIENT ||
-	    !(session->internals.flags & GNUTLS_ENABLE_FALSE_START) ||
-	    session->internals.recv_state != RECV_STATE_FALSE_START) {
+	if (session->internals.recv_state != RECV_STATE_FALSE_START &&
+	    session->internals.recv_state != RECV_STATE_EARLY_START) {
 
 		_gnutls_handshake_hash_buffers_clear(session);
 
@@ -2839,7 +2839,7 @@ static int handshake_client(gnutls_session_t session)
 
 		ret = _gnutls_ext_sr_verify(session);
 		STATE = STATE4;
-		IMED_RET("recv hello", ret, 0);
+		IMED_RET_FATAL("recv hello", ret, 0);
 		/* fall through */
 	case STATE5:
 		if (session->security_parameters.do_recv_supplemental) {
@@ -3257,7 +3257,7 @@ static int handshake_server(gnutls_session_t session)
 
 		ret = _gnutls_ext_sr_verify(session);
 		STATE = STATE2;
-		IMED_RET("recv hello", ret, 0);
+		IMED_RET_FATAL("recv hello", ret, 0);
 		/* fall through */
 	case STATE3:
 		ret = _gnutls_send_server_hello(session, AGAIN(STATE3));
diff --git a/lib/handshake.h b/lib/handshake.h
index 248d6a1896..e32de894f2 100644
--- a/lib/handshake.h
+++ b/lib/handshake.h
@@ -28,6 +28,11 @@
 #include "record.h"
 #include <assert.h>
 
+/* The following two macros are used in the handshake state machines; the first
+ * (IMED_RET) accounts for non-fatal errors and re-entry to current state, while
+ * the latter invalidates the handshake on any error (to be used by functions
+ * that are not expected to return non-fatal errors).
+ */
 #define IMED_RET( str, ret, allow_alert) do { \
 	if (ret < 0) { \
 		/* EAGAIN and INTERRUPTED are always non-fatal */ \
@@ -54,6 +59,16 @@
 		return ret; \
 	} } while (0)
 
+#define IMED_RET_FATAL( str, ret, allow_alert) do { \
+	if (ret < 0) { \
+		gnutls_assert(); \
+		if (gnutls_error_is_fatal(ret) == 0) \
+			ret = gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR); \
+		session_invalidate(session); \
+		_gnutls_handshake_hash_buffers_clear(session); \
+		return ret; \
+	} } while (0)
+
 int _gnutls_send_handshake(gnutls_session_t session, mbuffer_st * bufel,
 			   gnutls_handshake_description_t type);
 int _gnutls_recv_hello_request(gnutls_session_t session, void *data,
diff --git a/lib/includes/gnutls/gnutls.h.in b/lib/includes/gnutls/gnutls.h.in
index 6baebc295c..2252be0224 100644
--- a/lib/includes/gnutls/gnutls.h.in
+++ b/lib/includes/gnutls/gnutls.h.in
@@ -381,6 +381,10 @@ typedef enum {
  * @GNUTLS_NO_REPLAY_PROTECTION: Disable any replay protection in DTLS. This must only be used if  replay protection is achieved using other means. Since 3.2.2.
  * @GNUTLS_ALLOW_ID_CHANGE: Allow the peer to replace its certificate, or change its ID during a rehandshake. This change is often used in attacks and thus prohibited by default. Since 3.5.0.
  * @GNUTLS_ENABLE_FALSE_START: Enable the TLS false start on client side if the negotiated ciphersuites allow it. This will enable sending data prior to the handshake being complete, and may introduce a risk of crypto failure when combined with certain key exchanged; for that GnuTLS may not enable that option in ciphersuites that are known to be not safe for false start. Since 3.5.0.
+ * @GNUTLS_ENABLE_EARLY_START: Under TLS1.3 allow the server to return earlier than the full handshake
+ *   finish; similarly to false start the handshake will be completed once data are received by the
+ *   client, while the server is able to transmit sooner. This is not enabled by default as it could
+ *   break certain existing server assumptions and use-cases. Since 3.6.4.
  * @GNUTLS_FORCE_CLIENT_CERT: When in client side and only a single cert is specified, send that certificate irrespective of the issuers expected by the server. Since 3.5.0.
  * @GNUTLS_NO_TICKETS: Flag to indicate that the session should not use resumption with session tickets.
  * @GNUTLS_KEY_SHARE_TOP3: Generate key shares for the top-3 different groups which are enabled.
@@ -428,7 +432,8 @@ typedef enum {
 	GNUTLS_KEY_SHARE_TOP3 = (1<<13),
 	GNUTLS_POST_HANDSHAKE_AUTH = (1<<14),
 	GNUTLS_NO_AUTO_REKEY = (1<<15),
-	GNUTLS_SAFE_PADDING_CHECK = (1<<16)
+	GNUTLS_SAFE_PADDING_CHECK = (1<<16),
+	GNUTLS_ENABLE_EARLY_START = (1<<17)
 } gnutls_init_flags_t;
 
 /* compatibility defines (previous versions of gnutls
@@ -1441,9 +1446,10 @@ unsigned gnutls_session_etm_status(gnutls_session_t session);
  * @GNUTLS_SFLAGS_RFC7919: The RFC7919 Diffie-Hellman parameters were negotiated
  * @GNUTLS_SFLAGS_HB_LOCAL_SEND: The heartbeat negotiation allows the local side to send heartbeat messages
  * @GNUTLS_SFLAGS_HB_PEER_SEND: The heartbeat negotiation allows the peer to send heartbeat messages
- * @GNUTLS_SFLAGS_FALSE_START: The appdata set with gnutls_handshake_set_appdata() were sent during handshake (false start)
+ * @GNUTLS_SFLAGS_FALSE_START: False start was used in this client session.
  * @GNUTLS_SFLAGS_SESSION_TICKET: A session ticket has been received by the server.
  * @GNUTLS_SFLAGS_POST_HANDSHAKE_AUTH: Indicates client capability for post-handshake auth; set only on server side.
+ * @GNUTLS_SFLAGS_EARLY_START: The TLS1.3 server session returned early.
  *
  * Enumeration of different session parameters.
  */
@@ -1456,7 +1462,8 @@ typedef enum {
 	GNUTLS_SFLAGS_FALSE_START = 1<<5,
 	GNUTLS_SFLAGS_RFC7919 = 1<<6,
 	GNUTLS_SFLAGS_SESSION_TICKET = 1<<7,
-	GNUTLS_SFLAGS_POST_HANDSHAKE_AUTH = 1<<8
+	GNUTLS_SFLAGS_POST_HANDSHAKE_AUTH = 1<<8,
+	GNUTLS_SFLAGS_EARLY_START = 1<<9
 } gnutls_session_flags_t;
 
 unsigned gnutls_session_get_flags(gnutls_session_t session);
diff --git a/lib/record.c b/lib/record.c
index 9b485fd293..1cc328cb93 100644
--- a/lib/record.c
+++ b/lib/record.c
@@ -1521,30 +1521,48 @@ check_session_status(gnutls_session_t session, unsigned ms)
 			return gnutls_assert_val(ret);
 
 		return GNUTLS_E_AGAIN;
+	case RECV_STATE_EARLY_START_HANDLING:
 	case RECV_STATE_FALSE_START_HANDLING:
 		return 1;
 	case RECV_STATE_FALSE_START:
 		/* if false start is not complete we always expect for handshake packets
 		 * prior to anything else. */
-		if (session->security_parameters.entity == GNUTLS_CLIENT &&
-		    (session->internals.flags & GNUTLS_ENABLE_FALSE_START)) {
-			/* Attempt to complete handshake */
+		if (session->security_parameters.entity != GNUTLS_CLIENT ||
+		    !(session->internals.flags & GNUTLS_ENABLE_FALSE_START))
+			return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
 
-			session->internals.recv_state = RECV_STATE_FALSE_START_HANDLING;
-			ret = gnutls_handshake(session);
-			if (ret < 0) {
-				/* a temp or fatal error, make sure we reset the state
-				 * so we can resume or temp errors */
-				session->internals.recv_state = RECV_STATE_FALSE_START;
-				gnutls_assert();
-				return ret;
-			}
+		/* Attempt to complete handshake */
 
-			session->internals.recv_state = RECV_STATE_0;
-			return 1;
-		} else {
+		session->internals.recv_state = RECV_STATE_FALSE_START_HANDLING;
+		ret = gnutls_handshake(session);
+		if (ret < 0) {
+			/* a temp or fatal error, make sure we reset the state
+			 * so we can resume on temp errors */
+			session->internals.recv_state = RECV_STATE_FALSE_START;
+			return gnutls_assert_val(ret);
+		}
+
+		session->internals.recv_state = RECV_STATE_0;
+		return 1;
+	case RECV_STATE_EARLY_START:
+		/* if early start is not complete we always expect for handshake packets
+		 * prior to anything else. */
+		if (session->security_parameters.entity != GNUTLS_SERVER ||
+		    !(session->internals.flags & GNUTLS_ENABLE_EARLY_START))
 			return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR);
+
+		/* Attempt to complete handshake */
+		session->internals.recv_state = RECV_STATE_EARLY_START_HANDLING;
+		ret = gnutls_handshake(session);
+		if (ret < 0) {
+			/* a temp or fatal error, make sure we reset the state
+			 * so we can resume on temp errors */
+			session->internals.recv_state = RECV_STATE_EARLY_START;
+			return gnutls_assert_val(ret);
 		}
+
+		session->internals.recv_state = RECV_STATE_0;
+		return 1;
 	case RECV_STATE_DTLS_RETRANSMIT:
 		ret = _dtls_retransmit(session);
 		if (ret < 0)
@@ -1809,7 +1827,8 @@ gnutls_record_send2(gnutls_session_t session, const void *data,
 		/* this is to protect buggy applications from sending unencrypted
 		 * data. We allow sending however, if we are in false start handshake
 		 * state. */
-		if (session->internals.recv_state != RECV_STATE_FALSE_START)
+		if (session->internals.recv_state != RECV_STATE_FALSE_START &&
+		    session->internals.recv_state != RECV_STATE_EARLY_START)
 			return gnutls_assert_val(GNUTLS_E_UNAVAILABLE_DURING_HANDSHAKE);
 	}
 
@@ -1984,7 +2003,8 @@ gnutls_record_recv(gnutls_session_t session, void *data, size_t data_size)
 		/* this is to protect buggy applications from sending unencrypted
 		 * data. We allow sending however, if we are in false start handshake
 		 * state. */
-		if (session->internals.recv_state != RECV_STATE_FALSE_START)
+		if (session->internals.recv_state != RECV_STATE_FALSE_START &&
+		    session->internals.recv_state != RECV_STATE_EARLY_START)
 			return gnutls_assert_val(GNUTLS_E_UNAVAILABLE_DURING_HANDSHAKE);
 	}
 
diff --git a/lib/session_pack.c b/lib/session_pack.c
index 615eb6c2a5..2ed04a8eeb 100644
--- a/lib/session_pack.c
+++ b/lib/session_pack.c
@@ -860,7 +860,8 @@ pack_security_parameters(gnutls_session_t session, gnutls_buffer_st * ps)
 	size_t cur_size;
 
 	if (session->security_parameters.epoch_read
-	    != session->security_parameters.epoch_write) {
+	    != session->security_parameters.epoch_write &&
+	    !(session->internals.hsk_flags & HSK_EARLY_START_USED)) {
 		gnutls_assert();
 		return GNUTLS_E_UNAVAILABLE_DURING_HANDSHAKE;
 	}
diff --git a/lib/state.c b/lib/state.c
index d01475c84a..8469339c7a 100644
--- a/lib/state.c
+++ b/lib/state.c
@@ -1351,6 +1351,9 @@ unsigned gnutls_session_get_flags(gnutls_session_t session)
 		flags |= GNUTLS_SFLAGS_HB_PEER_SEND;
 	if (session->internals.hsk_flags & HSK_FALSE_START_USED)
 		flags |= GNUTLS_SFLAGS_FALSE_START;
+	if ((session->internals.hsk_flags & HSK_EARLY_START_USED) &&
+	    (session->internals.flags & GNUTLS_ENABLE_EARLY_START))
+		flags |= GNUTLS_SFLAGS_EARLY_START;
 	if (session->internals.hsk_flags & HSK_USED_FFDHE)
 		flags |= GNUTLS_SFLAGS_RFC7919;
 	if (session->internals.hsk_flags & HSK_TICKET_RECEIVED)
diff --git a/lib/tls13/finished.c b/lib/tls13/finished.c
index cb768b9739..6d88e8feed 100644
--- a/lib/tls13/finished.c
+++ b/lib/tls13/finished.c
@@ -75,10 +75,17 @@ int _gnutls13_recv_finished(gnutls_session_t session)
 
 	hash_size = session->security_parameters.prf->output_size;
 
-	if (session->security_parameters.entity == GNUTLS_CLIENT)
-		base_key = session->key.proto.tls13.hs_skey;
-	else
-		base_key = session->key.proto.tls13.hs_ckey;
+	if (!session->internals.initial_negotiation_completed) {
+		if (session->security_parameters.entity == GNUTLS_CLIENT)
+			base_key = session->key.proto.tls13.hs_skey;
+		else
+			base_key = session->key.proto.tls13.hs_ckey;
+	} else {
+		if (session->security_parameters.entity == GNUTLS_CLIENT)
+			base_key = session->key.proto.tls13.ap_skey;
+		else
+			base_key = session->key.proto.tls13.ap_ckey;
+	}
 
 	ret = _gnutls13_compute_finished(session->security_parameters.prf,
 			base_key,
@@ -133,10 +140,17 @@ int _gnutls13_send_finished(gnutls_session_t session, unsigned again)
 
 		hash_size = session->security_parameters.prf->output_size;
 
-		if (session->security_parameters.entity == GNUTLS_CLIENT)
-			base_key = session->key.proto.tls13.hs_ckey;
-		else
-			base_key = session->key.proto.tls13.hs_skey;
+		if (!session->internals.initial_negotiation_completed) {
+			if (session->security_parameters.entity == GNUTLS_CLIENT)
+				base_key = session->key.proto.tls13.hs_ckey;
+			else
+				base_key = session->key.proto.tls13.hs_skey;
+		} else {
+			if (session->security_parameters.entity == GNUTLS_CLIENT)
+				base_key = session->key.proto.tls13.ap_ckey;
+			else
+				base_key = session->key.proto.tls13.ap_skey;
+		}
 
 		ret = _gnutls13_compute_finished(session->security_parameters.prf,
 				base_key,
diff --git a/lib/tls13/key_update.c b/lib/tls13/key_update.c
index 9bbfca15e3..d9c495efdc 100644
--- a/lib/tls13/key_update.c
+++ b/lib/tls13/key_update.c
@@ -44,7 +44,13 @@ static int update_keys(gnutls_session_t session, hs_stage_t stage)
 	if (ret < 0)
 		return gnutls_assert_val(ret);
 
-	ret = _tls13_connection_state_init(session, stage);
+	/* If we send a key update during early start, only update our
+	 * write keys */
+	if (session->internals.recv_state == RECV_STATE_EARLY_START) {
+		ret = _tls13_write_connection_state_init(session, stage);
+	} else {
+		ret = _tls13_connection_state_init(session, stage);
+	}
 	if (ret < 0)
 		return gnutls_assert_val(ret);