Add a regression test that builds up the handshake state table

from graph information and cross-checks it against the state
table in tls13_handshake.c.

with help from jsing

2 files changed, 399 insertions, 1 deletions

diff --git a/regress/lib/libssl/handshake/Makefile b/regress/lib/libssl/handshake/Makefile
index 151496fcbc4..8d42038a270 100644
--- a/regress/lib/libssl/handshake/Makefile
+++ b/regress/lib/libssl/handshake/Makefile
@@ -1,5 +1,6 @@
-#	$OpenBSD: Makefile,v 1.1 2019/01/20 06:47:38 tb Exp $
+#	$OpenBSD: Makefile,v 1.2 2019/01/23 04:50:24 tb Exp $
 
+PROGS += handshake_table
 PROGS += valid_handshakes_terminate
 
 .for p in ${PROGS}
@@ -11,6 +12,9 @@ DPADD =		${LIBCRYPTO} ${LIBSSL}
 WARNINGS =	Yes
 CFLAGS +=	-DLIBRESSL_INTERNAL -Wundef -Werror -I$(BSDSRCDIR)/lib/libssl
 
+print:	handshake_table
+	./handshake_table -C
+
 .for p in ${PROGS}
 run-$p: $p
 	@echo '\n======== $@ ========'
diff --git a/regress/lib/libssl/handshake/handshake_table.c b/regress/lib/libssl/handshake/handshake_table.c
new file mode 100644
index 00000000000..5a94d5806a5
--- /dev/null
+++ b/regress/lib/libssl/handshake/handshake_table.c
@@ -0,0 +1,394 @@
+/*	$OpenBSD: handshake_table.c,v 1.1 2019/01/23 04:50:24 tb Exp $	*/
+/*
+ * Copyright (c) 2019 Theo Buehler <tb@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <err.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "tls13_handshake.h"
+
+/*
+ * From RFC 8446:
+ *
+ * Appendix A.  State Machine
+ *
+ *    This appendix provides a summary of the legal state transitions for
+ *    the client and server handshakes.  State names (in all capitals,
+ *    e.g., START) have no formal meaning but are provided for ease of
+ *    comprehension.  Actions which are taken only in certain circumstances
+ *    are indicated in [].  The notation "K_{send,recv} = foo" means "set
+ *    the send/recv key to the given key".
+ *
+ * A.1.  Client
+ *
+ *                               START <----+
+ *                Send ClientHello |        | Recv HelloRetryRequest
+ *           [K_send = early data] |        |
+ *                                 v        |
+ *            /                 WAIT_SH ----+
+ *            |                    | Recv ServerHello
+ *            |                    | K_recv = handshake
+ *        Can |                    V
+ *       send |                 WAIT_EE
+ *      early |                    | Recv EncryptedExtensions
+ *       data |           +--------+--------+
+ *            |     Using |                 | Using certificate
+ *            |       PSK |                 v
+ *            |           |            WAIT_CERT_CR
+ *            |           |        Recv |       | Recv CertificateRequest
+ *            |           | Certificate |       v
+ *            |           |             |    WAIT_CERT
+ *            |           |             |       | Recv Certificate
+ *            |           |             v       v
+ *            |           |              WAIT_CV
+ *            |           |                 | Recv CertificateVerify
+ *            |           +> WAIT_FINISHED <+
+ *            |                  | Recv Finished
+ *            \                  | [Send EndOfEarlyData]
+ *                               | K_send = handshake
+ *                               | [Send Certificate [+ CertificateVerify]]
+ *     Can send                  | Send Finished
+ *     app data   -->            | K_send = K_recv = application
+ *     after here                v
+ *                           CONNECTED
+ *
+ *    Note that with the transitions as shown above, clients may send
+ *    alerts that derive from post-ServerHello messages in the clear or
+ *    with the early data keys.  If clients need to send such alerts, they
+ *    SHOULD first rekey to the handshake keys if possible.
+ *
+ */
+
+extern enum tls13_message_type handshakes[][TLS13_NUM_MESSAGE_TYPES];
+
+struct child {
+	enum tls13_message_type	mt;
+	uint8_t			flag;
+	uint8_t			forced;
+	uint8_t			illegal;
+};
+
+#define DEFAULT			0x00
+
+static struct child stateinfo[][TLS13_NUM_MESSAGE_TYPES] = {
+	[CLIENT_HELLO] = {
+		{ SERVER_HELLO, NEGOTIATED, 0, 0 },
+	},
+	[SERVER_HELLO] = {
+		{ SERVER_ENCRYPTED_EXTENSIONS, DEFAULT, 0, 0 },
+		{ CLIENT_HELLO_RETRY, WITH_HRR, 0, 0 },
+	},
+	[CLIENT_HELLO_RETRY] = {
+		{ SERVER_ENCRYPTED_EXTENSIONS, DEFAULT, 0, 0},
+	},
+	[SERVER_ENCRYPTED_EXTENSIONS] = {
+		{ SERVER_CERTIFICATE_REQUEST, DEFAULT, 0, 0},
+		{ SERVER_CERTIFICATE, WITHOUT_CR, 0, 0},
+		{ SERVER_FINISHED, WITH_PSK, 0, 0},
+	},
+	[SERVER_CERTIFICATE_REQUEST] = {
+		{ SERVER_CERTIFICATE, DEFAULT, 0, 0},
+	},
+	[SERVER_CERTIFICATE] = {
+		{ SERVER_CERTIFICATE_VERIFY, DEFAULT, 0, 0},
+	},
+	[SERVER_CERTIFICATE_VERIFY] = {
+		{ SERVER_FINISHED, DEFAULT, 0, 0},
+	},
+	[SERVER_FINISHED] = {
+		{ CLIENT_FINISHED, DEFAULT, WITHOUT_CR | WITH_PSK, 0 },
+		{ CLIENT_CERTIFICATE, DEFAULT, 0, WITHOUT_CR | WITH_PSK },
+		/* { CLIENT_END_OF_EARLY_DATA, WITH_0RTT, 0, 0}, */
+	},
+	[CLIENT_CERTIFICATE] = {
+		{ CLIENT_FINISHED, DEFAULT, 0, 0},
+		{ CLIENT_CERTIFICATE_VERIFY, WITH_CCV, 0, 0},
+	},
+	[CLIENT_CERTIFICATE_VERIFY] = {
+		{ CLIENT_FINISHED, DEFAULT, 0, 0},
+	},
+	[CLIENT_FINISHED] = {
+		{ APPLICATION_DATA, DEFAULT, 0, 0},
+	},
+	[APPLICATION_DATA] = {
+		{ 0, DEFAULT, 0, 0},
+	},
+};
+
+const char *flag2str(uint8_t flag);
+void print_flags(uint8_t flags);
+const char *mt2str(enum tls13_message_type mt);
+void build_table(enum tls13_message_type
+    table[UINT8_MAX][TLS13_NUM_MESSAGE_TYPES], struct child current,
+    struct child end, struct child path[], uint8_t flags, unsigned int depth);
+void print_entry(enum tls13_message_type path[TLS13_NUM_MESSAGE_TYPES],
+    uint8_t flags);
+__dead void usage(void);
+int verify_table(enum tls13_message_type
+    table[UINT8_MAX][TLS13_NUM_MESSAGE_TYPES], int print);
+
+const char *
+flag2str(uint8_t flag)
+{
+	const char *ret;
+
+	if (flag & (flag - 1))
+		errx(1, "more than one bit is set");
+
+	switch (flag) {
+	case DEFAULT:
+		ret = "";
+		break;
+	case NEGOTIATED:
+		ret = "NEGOTIATED";
+		break;
+	case WITHOUT_CR:
+		ret = "WITHOUT_CR";
+		break;
+	case WITH_HRR:
+		ret = "WITH_HRR";
+		break;
+	case WITH_PSK:
+		ret = "WITH_PSK";
+		break;
+	case WITH_CCV:
+		ret = "WITH_CCV";
+		break;
+	case WITH_0RTT:
+		ret = "WITH_0RTT";
+		break;
+	default:
+		ret = "UNKNOWN";
+	}
+
+	return ret;
+}
+
+const char *
+mt2str(enum tls13_message_type mt)
+{
+	const char *ret;
+
+	switch (mt) {
+	case INVALID:
+		ret = "INVALID";
+		break;
+	case CLIENT_HELLO:
+		ret = "CLIENT_HELLO";
+		break;
+	case CLIENT_HELLO_RETRY:
+		ret = "CLIENT_HELLO_RETRY";
+		break;
+	case CLIENT_END_OF_EARLY_DATA:
+		ret = "CLIENT_END_OF_EARLY_DATA";
+		break;
+	case CLIENT_CERTIFICATE:
+		ret = "CLIENT_CERTIFICATE";
+		break;
+	case CLIENT_CERTIFICATE_VERIFY:
+		ret = "CLIENT_CERTIFICATE_VERIFY";
+		break;
+	case CLIENT_FINISHED:
+		ret = "CLIENT_FINISHED";
+		break;
+	case CLIENT_KEY_UPDATE:
+		ret = "CLIENT_KEY_UPDATE";
+		break;
+	case SERVER_HELLO:
+		ret = "SERVER_HELLO";
+		break;
+	case SERVER_NEW_SESSION_TICKET:
+		ret = "SERVER_NEW_SESSION_TICKET";
+		break;
+	case SERVER_ENCRYPTED_EXTENSIONS:
+		ret = "SERVER_ENCRYPTED_EXTENSIONS";
+		break;
+	case SERVER_CERTIFICATE:
+		ret = "SERVER_CERTIFICATE";
+		break;
+	case SERVER_CERTIFICATE_VERIFY:
+		ret = "SERVER_CERTIFICATE_VERIFY";
+		break;
+	case SERVER_CERTIFICATE_REQUEST:
+		ret = "SERVER_CERTIFICATE_REQUEST";
+		break;
+	case SERVER_FINISHED:
+		ret = "SERVER_FINISHED";
+		break;
+	case APPLICATION_DATA:
+		ret = "APPLICATION_DATA";
+		break;
+	case TLS13_NUM_MESSAGE_TYPES:
+		ret = "TLS13_NUM_MESSAGE_TYPES";
+		break;
+	default:
+		ret = "UNKNOWN";
+		break;
+	}
+
+	return ret;
+}
+
+void
+print_flags(uint8_t flags)
+{
+	int first = 1, i;
+
+	for (i = 0; i < 8; i++) {
+		uint8_t set = flags & (1U << i);
+
+		if (set) {
+			printf("%s%s", first ? "" : " | ", flag2str(set));
+			first = 0;
+		}
+	}
+}
+
+void
+print_entry(enum tls13_message_type path[TLS13_NUM_MESSAGE_TYPES],
+    uint8_t flags)
+{
+	int i;
+
+	printf("\t[");
+	print_flags(flags);
+	printf("] = {\n");
+
+	for (i = 0; i < TLS13_NUM_MESSAGE_TYPES; i++) {
+		if (path[i] == 0)
+			break;
+		printf("\t\t%s,\n", mt2str(path[i]));
+	}
+	printf("\t},\n");
+}
+
+void
+build_table(enum tls13_message_type table[UINT8_MAX][TLS13_NUM_MESSAGE_TYPES],
+    struct child current, struct child end, struct child path[], uint8_t flags,
+    unsigned int depth)
+{
+	unsigned int i;
+
+	if (depth >= TLS13_NUM_MESSAGE_TYPES - 1)
+		errx(1, "recursed too deeply");
+
+	/* Record current node. */
+	path[depth++] = current;
+	flags |= current.flag;
+
+	/* If we haven't reached the end, recurse over the children. */
+	if (current.mt != end.mt) {
+		for (i = 0; stateinfo[current.mt][i].mt != 0; i++) {
+			struct child child = stateinfo[current.mt][i];
+			int forced = stateinfo[current.mt][i].forced;
+			int illegal = stateinfo[current.mt][i].illegal;
+
+			if ((forced == 0 || (forced & flags)) &&
+			    (illegal == 0 || !(illegal & flags)))
+				build_table(table, child, end, path, flags,
+				    depth);
+		}
+		return;
+	}
+
+	if (flags == 0)
+		errx(1, "path does not set flags");
+
+	if (table[flags][0] != 0)
+		errx(1, "path traversed twice");
+
+	for (i = 0; i < depth; i++)
+		table[flags][i] = path[i].mt;
+}
+
+int
+verify_table(enum tls13_message_type table[UINT8_MAX][TLS13_NUM_MESSAGE_TYPES],
+    int print)
+{
+	int	success = 1, i;
+	uint8_t	flags = 0;
+
+	do {
+		flags++;
+		if (table[flags][0] == 0)
+			continue;
+
+		for (i = 0; i < TLS13_NUM_MESSAGE_TYPES; i++) {
+			if (table[flags][i] != handshakes[flags][i]) {
+				printf("incorrrect entry %d of handshake ", i);
+				print_flags(flags);
+				printf("\n");
+				success = 0;
+			}
+		}
+
+		if (print)
+			print_entry(table[flags], flags);
+	} while(flags != UINT8_MAX);
+
+	return success;
+}
+
+__dead void
+usage(void)
+{
+	fprintf(stderr, "usage: handshake_table [-C]\n");
+	exit(1);
+}
+
+int
+main(int argc, char *argv[])
+{
+	static enum tls13_message_type
+	    hs_table[UINT8_MAX][TLS13_NUM_MESSAGE_TYPES];
+	struct child	start = {
+		CLIENT_HELLO, NEGOTIATED, 0, 0,
+	};
+	struct child	end = {
+		APPLICATION_DATA, DEFAULT, 0, 0,
+	};
+	struct child	path[TLS13_NUM_MESSAGE_TYPES] = {{ 0 }};
+	uint8_t		flags = 0;
+	unsigned int	depth = 0;
+	int		ch, print = 0;
+
+	while ((ch = getopt(argc, argv, "C")) != -1) {
+		switch (ch) {
+		case 'C':
+			print = 1;
+			break;
+		default:
+			usage();
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	if (argc != 0)
+		usage();
+
+	build_table(hs_table, start, end, path, flags, depth);
+	if (!verify_table(hs_table, print))
+		return 1;
+
+	if (!print)
+		printf("SUCCESS\n");
+
+	return 0;
+}