Cr50: Added Pinweaver base implementation.

This adds some of the ground work for hardware backed brute force
resistance on Cr50. The feature is called Pinweaver. It will
initially be used to enable PIN authentication on CrOS devices
without reducing the security of the platform. A Merkle tree is
used to validate encrypted metadata used to track login attempts.

The metadata tracks counts of failed attempts, a timestamp of the
last failed attempt, the secrets, and any associated parameters.
Instead of storing the metadata on Cr50 an AES-CTR is used with an
HMAC to encrypt the data so it can be stored off-chip and loaded
when needed.

The Merkle tree is used to track the current state of all the
metadata to prevent replay attacks of previously exported copies.
It is a tree of hashes whose root hash is stored on Cr50, and whose
leaves are the HMACs of the encrypted metadata.

BRANCH=none
BUG=chromium:809730, chromium:809741, chromium:809743, chromium:809747
TEST=cd ~/src/platform/ec && V=1 make run-pinweaver -j

Change-Id: Id10bb49d8ebc5a487dd90c6093bc0f51dadbd124
Signed-off-by: Allen Webb <allenwebb@google.com>
Reviewed-on: https://chromium-review.googlesource.com/895395
Reviewed-by: Vadim Bendebury <vbendeb@chromium.org>

2 files changed, 895 insertions, 0 deletions

diff --git a/common/build.mk b/common/build.mk
index 37e8a322c1..a48880bafc 100644
--- a/common/build.mk
+++ b/common/build.mk
@@ -81,6 +81,7 @@ common-$(CONFIG_MAG_CALIBRATE)+= mag_cal.o math_util.o vec3.o mat33.o mat44.o
 common-$(CONFIG_MKBP_EVENT)+=mkbp_event.o
 common-$(CONFIG_ONEWIRE)+=onewire.o
 common-$(CONFIG_PHYSICAL_PRESENCE)+=physical_presence.o
+common-$(CONFIG_PINWEAVER)+=pinweaver.o
 common-$(CONFIG_POWER_BUTTON)+=power_button.o
 common-$(CONFIG_POWER_BUTTON_X86)+=power_button_x86.o
 common-$(CONFIG_PSTORE)+=pstore_commands.o
diff --git a/common/pinweaver.c b/common/pinweaver.c
new file mode 100644
index 0000000000..63e1a4522e
--- /dev/null
+++ b/common/pinweaver.c
@@ -0,0 +1,894 @@
+/* Copyright 2018 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include <common.h>
+#include <console.h>
+#include <dcrypto.h>
+#include <pinweaver.h>
+#include <pinweaver_tpm_imports.h>
+#include <pinweaver_types.h>
+#include <timer.h>
+#include <trng.h>
+#include <tpm_registers.h>
+#include <util.h>
+
+/* Compile time sanity checks. */
+/* Make sure the hash size is consistent with dcrypto. */
+BUILD_ASSERT(PW_HASH_SIZE >= SHA256_DIGEST_SIZE);
+
+/* sizeof(struct leaf_data_t) % 16 should be zero */
+BUILD_ASSERT(sizeof(struct leaf_sensitive_data_t) % PW_WRAP_BLOCK_SIZE == 0);
+
+BUILD_ASSERT(sizeof(((struct merkle_tree_t *)0)->wrap_key) ==
+	     AES256_BLOCK_CIPHER_KEY_SIZE);
+
+/* Verify that the request structs will fit into the message. */
+BUILD_ASSERT(PW_MAX_MESSAGE_SIZE >=
+	     sizeof(struct pw_request_header_t) +
+	     sizeof(union {struct pw_request_insert_leaf_t insert_leaf;
+		     struct pw_request_remove_leaf_t remove_leaf;
+		     struct pw_request_try_auth_t try_auth;
+		     struct pw_request_reset_auth_t reset_auth; }) +
+	     sizeof(struct leaf_public_data_t) +
+	     sizeof(struct leaf_sensitive_data_t) +
+	     PW_MAX_PATH_SIZE);
+
+/* Verify that the request structs will fit into the message. */
+BUILD_ASSERT(PW_MAX_MESSAGE_SIZE >=
+	     sizeof(struct pw_response_header_t) +
+	     sizeof(union {struct pw_response_insert_leaf_t insert_leaf;
+		     struct pw_response_try_auth_t try_auth;
+		     struct pw_response_reset_auth_t reset_auth; }) +
+	     PW_LEAF_PAYLOAD_SIZE);
+/* Make sure the largest possible message would fit in
+ * (struct tpm_register_file).data_fifo.
+ */
+BUILD_ASSERT(PW_MAX_MESSAGE_SIZE + sizeof(struct tpm_cmd_header) <= 2048);
+
+/* PW_MAX_PATH_SIZE should not change unless PW_LEAF_MAJOR_VERSION changes too.
+ * Update these statements whenever these constants are changed to remind future
+ * maintainers about this requirement.
+ *
+ * This requirement helps guarantee that forward compatibility across the same
+ * PW_LEAF_MAJOR_VERSION doesn't break because of a path length becoming too
+ * long after new fields are added to struct wrapped_leaf_data_t or its sub
+ * fields.
+ */
+BUILD_ASSERT(PW_LEAF_MAJOR_VERSION == 0);
+BUILD_ASSERT(PW_MAX_PATH_SIZE == 1536);
+
+/* If fields are appended to struct leaf_sensitive_data_t, an encryption
+ * operation should be performed on them reusing the same IV since the prefix
+ * won't change.
+ *
+ * If any data in the original struct leaf_sensitive_data_t changes, a new IV
+ * should be generated and stored as part of the log for a replay to be
+ * possible.
+ */
+BUILD_ASSERT(sizeof(struct leaf_sensitive_data_t) == 3 * PW_SECRET_SIZE);
+
+/******************************************************************************/
+/* Struct helper functions.
+ */
+
+void import_leaf(const struct unimported_leaf_data_t *unimported,
+		 struct imported_leaf_data_t *imported)
+{
+	imported->head = &unimported->head;
+	imported->hmac = unimported->hmac;
+	imported->iv = unimported->iv;
+	imported->pub = (const struct leaf_public_data_t *)unimported->payload;
+	imported->cipher_text = unimported->payload + unimported->head.pub_len;
+	imported->hashes = (const uint8_t (*)[PW_HASH_SIZE])(
+			imported->cipher_text + unimported->head.sec_len);
+}
+
+/******************************************************************************/
+/* Basic operations required by the Merkle tree.
+ */
+
+static int derive_keys(struct merkle_tree_t *merkle_tree)
+{
+	struct APPKEY_CTX ctx;
+	int ret = EC_SUCCESS;
+	const uint32_t KEY_TYPE_AES = 0x0;
+	const uint32_t KEY_TYPE_HMAC = 0xffffffff;
+	union {
+		uint32_t v[8];
+		uint8_t bytes[sizeof(uint32_t) * 8];
+	} input;
+	uint32_t type_field;
+	size_t seed_size = sizeof(input);
+	size_t x;
+
+	get_storage_seed(input.v, &seed_size);
+	for (x = 0; x < ARRAY_SIZE(input.bytes) &&
+		    x < ARRAY_SIZE(merkle_tree->key_derivation_nonce); ++x)
+		input.bytes[x] ^= merkle_tree->key_derivation_nonce[x];
+	type_field = input.v[6];
+
+	if (!DCRYPTO_appkey_init(PINWEAVER, &ctx))
+		return PW_ERR_CRYPTO_FAILURE;
+
+	input.v[6] = type_field ^ KEY_TYPE_AES;
+	if (!DCRYPTO_appkey_derive(PINWEAVER, input.v,
+				  (uint32_t *)merkle_tree->wrap_key)) {
+		ret = PW_ERR_CRYPTO_FAILURE;
+		goto cleanup;
+	}
+
+	input.v[6] = type_field ^ KEY_TYPE_HMAC;
+	if (!DCRYPTO_appkey_derive(PINWEAVER, input.v,
+				  (uint32_t *)merkle_tree->hmac_key)) {
+		ret = PW_ERR_CRYPTO_FAILURE;
+	}
+cleanup:
+	DCRYPTO_appkey_finish(&ctx);
+	return ret;
+}
+
+/* Creates an empty merkle_tree with the given parameters. */
+static int create_merkle_tree(struct bits_per_level_t bits_per_level,
+			      struct height_t height,
+			      struct merkle_tree_t *merkle_tree)
+{
+	uint16_t fan_out = 1 << bits_per_level.v;
+	uint8_t temp_hash[PW_HASH_SIZE] = {};
+	uint8_t hx;
+	uint16_t kx;
+	LITE_SHA256_CTX ctx;
+
+	merkle_tree->bits_per_level = bits_per_level;
+	merkle_tree->height = height;
+
+	/* Initialize the root hash. */
+	for (hx = 0; hx < height.v; ++hx) {
+		DCRYPTO_SHA256_init(&ctx, 0);
+		for (kx = 0; kx < fan_out; ++kx)
+			HASH_update(&ctx, temp_hash, PW_HASH_SIZE);
+		memcpy(temp_hash, HASH_final(&ctx), PW_HASH_SIZE);
+	}
+	memcpy(merkle_tree->root, temp_hash, PW_HASH_SIZE);
+
+	rand_bytes(merkle_tree->key_derivation_nonce,
+		   sizeof(merkle_tree->key_derivation_nonce));
+	return derive_keys(merkle_tree);
+}
+
+/* Computes the HMAC for an encrypted leaf using the key in the merkle_tree. */
+static void compute_hmac(
+		const struct merkle_tree_t *merkle_tree,
+		const struct imported_leaf_data_t *imported_leaf_data,
+		uint8_t result[PW_HASH_SIZE])
+{
+	LITE_HMAC_CTX hmac;
+
+	DCRYPTO_HMAC_SHA256_init(&hmac, merkle_tree->hmac_key,
+				 sizeof(merkle_tree->hmac_key));
+	HASH_update(&hmac.hash, imported_leaf_data->head,
+		    sizeof(*imported_leaf_data->head));
+	HASH_update(&hmac.hash, imported_leaf_data->iv,
+		    sizeof(PW_WRAP_BLOCK_SIZE));
+	HASH_update(&hmac.hash, imported_leaf_data->pub,
+		    imported_leaf_data->head->pub_len);
+	HASH_update(&hmac.hash, imported_leaf_data->cipher_text,
+		    imported_leaf_data->head->sec_len);
+	memcpy(result, DCRYPTO_HMAC_final(&hmac), PW_HASH_SIZE);
+}
+
+/* Computes the root hash for the specified path and child hash. */
+static void compute_root_hash(const struct merkle_tree_t *merkle_tree,
+			      struct label_t path,
+			      const uint8_t hashes[][PW_HASH_SIZE],
+			      const uint8_t child_hash[PW_HASH_SIZE],
+			      uint8_t new_root[PW_HASH_SIZE])
+{
+	/* This is one less than the fan out, the number of sibling hashes. */
+	const uint16_t num_aux = (1 << merkle_tree->bits_per_level.v) - 1;
+	const uint16_t path_suffix_mask = num_aux;
+	uint8_t temp_hash[PW_HASH_SIZE];
+	uint8_t hx = 0;
+	uint64_t index = path.v;
+
+	compute_hash(hashes, num_aux,
+		     (struct index_t){index & path_suffix_mask},
+		     child_hash, temp_hash);
+	for (hx = 1; hx < merkle_tree->height.v; ++hx) {
+		hashes += num_aux;
+		index = index >> merkle_tree->bits_per_level.v;
+		compute_hash(hashes, num_aux,
+			     (struct index_t){index & path_suffix_mask},
+			     temp_hash, temp_hash);
+	}
+	memcpy(new_root, temp_hash, sizeof(temp_hash));
+}
+
+/* Checks to see the specified path is valid. The length of the path should be
+ * validated prior to calling this function.
+ *
+ * Returns 0 on success or an error code otherwise.
+ */
+static int authenticate_path(const struct merkle_tree_t *merkle_tree,
+			     struct label_t path,
+			     const uint8_t hashes[][PW_HASH_SIZE],
+			     const uint8_t child_hash[PW_HASH_SIZE])
+{
+	uint8_t parent[PW_HASH_SIZE];
+
+	compute_root_hash(merkle_tree, path, hashes, child_hash, parent);
+	if (memcmp(parent, merkle_tree->root, sizeof(parent)) != 0)
+		return PW_ERR_PATH_AUTH_FAILED;
+	return EC_SUCCESS;
+}
+
+static void init_wrapped_leaf_data(
+		struct wrapped_leaf_data_t *wrapped_leaf_data)
+{
+	wrapped_leaf_data->head.leaf_version.major = PW_LEAF_MAJOR_VERSION;
+	wrapped_leaf_data->head.leaf_version.minor = PW_LEAF_MINOR_VERSION;
+	wrapped_leaf_data->head.pub_len = sizeof(wrapped_leaf_data->pub);
+	wrapped_leaf_data->head.sec_len =
+			sizeof(wrapped_leaf_data->cipher_text);
+}
+
+/* Encrypts the leaf meta data. */
+static int encrypt_leaf_data(const struct merkle_tree_t *merkle_tree,
+			     const struct leaf_data_t *leaf_data,
+			     struct wrapped_leaf_data_t *wrapped_leaf_data)
+{
+	/* Generate a random IV.
+	 *
+	 * If fields are appended to struct leaf_sensitive_data_t, an encryption
+	 * operation should be performed on them reusing the same IV since the
+	 * prefix won't change.
+	 *
+	 * If any data of in the original struct leaf_sensitive_data_t changes,
+	 * a new IV should be generated and stored as part of the log for a
+	 * replay to be possible.
+	 */
+	rand_bytes(wrapped_leaf_data->iv, sizeof(wrapped_leaf_data->iv));
+	memcpy(&wrapped_leaf_data->pub, &leaf_data->pub,
+	       sizeof(leaf_data->pub));
+	if (!DCRYPTO_aes_ctr(wrapped_leaf_data->cipher_text,
+			    merkle_tree->wrap_key,
+			    sizeof(merkle_tree->wrap_key) << 3,
+			    wrapped_leaf_data->iv, (uint8_t *)&leaf_data->sec,
+			    sizeof(leaf_data->sec))) {
+		return PW_ERR_CRYPTO_FAILURE;
+	}
+	return EC_SUCCESS;
+}
+
+/* Decrypts the leaf meta data. */
+static int decrypt_leaf_data(
+		const struct merkle_tree_t *merkle_tree,
+		const struct imported_leaf_data_t *imported_leaf_data,
+		struct leaf_data_t *leaf_data)
+{
+	memcpy(&leaf_data->pub, imported_leaf_data->pub,
+	       sizeof(leaf_data->pub));
+	if (!DCRYPTO_aes_ctr((uint8_t *)&leaf_data->sec, merkle_tree->wrap_key,
+			    sizeof(merkle_tree->wrap_key) << 3,
+			    imported_leaf_data->iv,
+			    imported_leaf_data->cipher_text,
+			    sizeof(leaf_data->sec))) {
+		return PW_ERR_CRYPTO_FAILURE;
+	}
+	return EC_SUCCESS;
+}
+
+static int handle_leaf_update(
+		const struct merkle_tree_t *merkle_tree,
+		const struct leaf_data_t *leaf_data,
+		const uint8_t hashes[][PW_HASH_SIZE],
+		struct wrapped_leaf_data_t *wrapped_leaf_data,
+		uint8_t new_root[PW_HASH_SIZE],
+		const struct imported_leaf_data_t *optional_old_wrapped_data)
+{
+	int ret;
+	struct imported_leaf_data_t ptrs;
+
+	init_wrapped_leaf_data(wrapped_leaf_data);
+	if (optional_old_wrapped_data == NULL) {
+		ret = encrypt_leaf_data(merkle_tree, leaf_data,
+					wrapped_leaf_data);
+		if (ret != EC_SUCCESS)
+			return ret;
+	} else {
+		memcpy(wrapped_leaf_data->iv, optional_old_wrapped_data->iv,
+		       sizeof(wrapped_leaf_data->iv));
+		memcpy(&wrapped_leaf_data->pub, &leaf_data->pub,
+		       sizeof(leaf_data->pub));
+		memcpy(wrapped_leaf_data->cipher_text,
+		       optional_old_wrapped_data->cipher_text,
+		       sizeof(wrapped_leaf_data->cipher_text));
+	}
+
+	import_leaf((const struct unimported_leaf_data_t *)wrapped_leaf_data,
+		    &ptrs);
+	compute_hmac(merkle_tree, &ptrs, wrapped_leaf_data->hmac);
+
+	compute_root_hash(merkle_tree, leaf_data->pub.label,
+			  hashes, wrapped_leaf_data->hmac,
+			  new_root);
+
+	return EC_SUCCESS;
+}
+
+/******************************************************************************/
+/* Parameter and state validation functions.
+ */
+
+static int validate_tree_parameters(struct bits_per_level_t bits_per_level,
+				    struct height_t height)
+{
+	uint8_t fan_out = 1 << bits_per_level.v;
+
+	if (bits_per_level.v < BITS_PER_LEVEL_MIN ||
+	    bits_per_level.v > BITS_PER_LEVEL_MAX)
+		return PW_ERR_BITS_PER_LEVEL_INVALID;
+
+	if (height.v < HEIGHT_MIN ||
+	    height.v > HEIGHT_MAX(bits_per_level.v) ||
+	    ((fan_out - 1) * height.v) * PW_HASH_SIZE > PW_MAX_PATH_SIZE)
+		return PW_ERR_HEIGHT_INVALID;
+
+	return EC_SUCCESS;
+}
+
+/* Verifies that merkle_tree has been initialized. */
+static int validate_tree(const struct merkle_tree_t *merkle_tree)
+{
+	if (validate_tree_parameters(merkle_tree->bits_per_level,
+				     merkle_tree->height) != EC_SUCCESS)
+		return PW_ERR_TREE_INVALID;
+	return EC_SUCCESS;
+}
+
+/* Checks the following conditions:
+ * Extra index fields should be all zero.
+ */
+static int validate_label(const struct merkle_tree_t *merkle_tree,
+			  struct label_t path)
+{
+	uint8_t shift_by = merkle_tree->bits_per_level.v *
+			   merkle_tree->height.v;
+
+	if ((path.v >> shift_by) == 0)
+		return EC_SUCCESS;
+	return PW_ERR_LABEL_INVALID;
+}
+
+/* Checks the following conditions:
+ * Columns should be strictly increasing.
+ * Zeroes for filler at the end of the delay_schedule are permitted.
+ */
+static int validate_delay_schedule(const struct delay_schedule_entry_t
+				   delay_schedule[PW_SCHED_COUNT])
+{
+	size_t x;
+
+	/* The first entry should not be useless. */
+	if (delay_schedule[0].time_diff.v == 0)
+		return PW_ERR_DELAY_SCHEDULE_INVALID;
+
+	for (x = PW_SCHED_COUNT - 1; x > 0; --x) {
+		if (delay_schedule[x].attempt_count.v == 0) {
+			if (delay_schedule[x].time_diff.v != 0)
+				return PW_ERR_DELAY_SCHEDULE_INVALID;
+		} else if (delay_schedule[x].attempt_count.v <=
+				delay_schedule[x - 1].attempt_count.v ||
+				delay_schedule[x].time_diff.v <=
+				delay_schedule[x - 1].time_diff.v) {
+			return PW_ERR_DELAY_SCHEDULE_INVALID;
+		}
+	}
+	return EC_SUCCESS;
+}
+
+static int validate_leaf_header(const struct leaf_header_t *head,
+				uint16_t payload_len, uint16_t aux_hash_len)
+{
+	uint32_t leaf_payload_len = head->pub_len + head->sec_len;
+
+	if (head->leaf_version.major != PW_LEAF_MAJOR_VERSION)
+		return PW_ERR_LEAF_VERSION_MISMATCH;
+
+	if (head->leaf_version.minor == PW_LEAF_MINOR_VERSION) {
+		if (leaf_payload_len != PW_LEAF_PAYLOAD_SIZE)
+			return PW_ERR_LENGTH_INVALID;
+	} else if (leaf_payload_len < PW_LEAF_PAYLOAD_SIZE)
+		return PW_ERR_LENGTH_INVALID;
+
+	if (payload_len != leaf_payload_len + aux_hash_len * PW_HASH_SIZE)
+		return PW_ERR_LENGTH_INVALID;
+
+	return EC_SUCCESS;
+}
+
+/* Common validation for requests that include a path to authenticate. */
+static int validate_request_with_path(const struct merkle_tree_t *merkle_tree,
+				      struct label_t path,
+				      const uint8_t hashes[][PW_HASH_SIZE],
+				      const uint8_t hmac[PW_HASH_SIZE])
+{
+	int ret;
+
+	ret = validate_tree(merkle_tree);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	ret = validate_label(merkle_tree, path);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	return authenticate_path(merkle_tree, path, hashes, hmac);
+}
+
+/* Common validation for requests that import a leaf. */
+static int validate_request_with_wrapped_leaf(
+		const struct merkle_tree_t *merkle_tree,
+		uint16_t payload_len,
+		const struct unimported_leaf_data_t *unimported_leaf_data,
+		struct imported_leaf_data_t *imported_leaf_data,
+		struct leaf_data_t *leaf_data)
+{
+	int ret;
+	uint8_t hmac[PW_HASH_SIZE];
+
+	ret = validate_leaf_header(&unimported_leaf_data->head, payload_len,
+				   get_path_auxiliary_hash_count(merkle_tree));
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	import_leaf(unimported_leaf_data, imported_leaf_data);
+	ret = validate_request_with_path(merkle_tree,
+					 imported_leaf_data->pub->label,
+					 imported_leaf_data->hashes,
+					 imported_leaf_data->hmac);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	compute_hmac(merkle_tree, imported_leaf_data, hmac);
+	/* Safe memcmp is used here to prevent an attacker from being able to
+	 * brute force a valid HMAC for a crafted wrapped_leaf_data.
+	 * memcmp provides an attacker a timing side-channel they can use to
+	 * determine how much of a prefix is correct.
+	 */
+	if (safe_memcmp(hmac, unimported_leaf_data->hmac, sizeof(hmac)))
+		return PW_ERR_HMAC_AUTH_FAILED;
+
+	return decrypt_leaf_data(merkle_tree, imported_leaf_data, leaf_data);
+}
+
+/* Sets the value of ts to the current notion of time. */
+static void update_timestamp(struct pw_timestamp_t *ts)
+{
+	ts->timer_value = get_time().val / SECOND;
+	ts->boot_count = get_restart_count();
+}
+
+/* Checks if an auth attempt can be made or not based on the delay schedule.
+ * EC_SUCCESS is returned when a new attempt can be made otherwise
+ * seconds_to_wait will be updated with the remaining wait time required.
+ */
+static int test_rate_limit(struct leaf_data_t *leaf_data,
+			   struct time_diff_t *seconds_to_wait)
+{
+	uint64_t ready_time;
+	uint8_t x;
+	struct pw_timestamp_t current_time;
+	struct time_diff_t delay = {0};
+
+	/* This loop ends when x is one greater than the index that applies. */
+	for (x = 0; x < ARRAY_SIZE(leaf_data->pub.delay_schedule); ++x) {
+		/* Stop if a null entry is reached. The first part of the delay
+		 * schedule has a list of increasing (attempt_count, time_diff)
+		 * pairs with any unused entries zeroed out at the end.
+		 */
+		if (leaf_data->pub.delay_schedule[x].attempt_count.v == 0)
+			break;
+
+		/* Stop once a delay schedule entry is reached whose
+		 * threshold is greater than the current number of
+		 * attempts.
+		 */
+		if (leaf_data->pub.attempt_count.v <
+		    leaf_data->pub.delay_schedule[x].attempt_count.v)
+			break;
+	}
+
+	/* If the first threshold was greater than the current number of
+	 * attempts, there is no delay. Otherwise, grab the delay from the
+	 * entry prior to the one that was too big.
+	 */
+	if (x > 0)
+		delay = leaf_data->pub.delay_schedule[x - 1].time_diff;
+
+	if (delay.v == 0)
+		return EC_SUCCESS;
+
+	if (delay.v == PW_BLOCK_ATTEMPTS) {
+		seconds_to_wait->v = PW_BLOCK_ATTEMPTS;
+		return PW_ERR_RATE_LIMIT_REACHED;
+	}
+
+	update_timestamp(&current_time);
+
+	if (leaf_data->pub.timestamp.boot_count == current_time.boot_count)
+		ready_time = delay.v + leaf_data->pub.timestamp.timer_value;
+	else
+		ready_time = delay.v;
+
+	if (current_time.timer_value >= ready_time)
+		return EC_SUCCESS;
+
+	seconds_to_wait->v = ready_time - current_time.timer_value;
+	return PW_ERR_RATE_LIMIT_REACHED;
+}
+
+/******************************************************************************/
+/* Per-request-type handler implementations.
+ */
+
+static int pw_handle_reset_tree(struct merkle_tree_t *merkle_tree,
+				const struct pw_request_reset_tree_t *request,
+				uint16_t req_size)
+{
+	struct merkle_tree_t new_tree = {};
+	int ret;
+
+	if (req_size != sizeof(*request))
+		return PW_ERR_LENGTH_INVALID;
+
+	ret = validate_tree_parameters(request->bits_per_level,
+				       request->height);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	ret = create_merkle_tree(request->bits_per_level, request->height,
+				 &new_tree);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	memcpy(merkle_tree, &new_tree, sizeof(new_tree));
+	return EC_SUCCESS;
+}
+
+static int pw_handle_insert_leaf(struct merkle_tree_t *merkle_tree,
+				 const struct pw_request_insert_leaf_t *request,
+				 uint16_t req_size,
+				 struct pw_response_insert_leaf_t *response,
+				 uint16_t *response_size)
+{
+	int ret = EC_SUCCESS;
+	struct leaf_data_t leaf_data = {};
+	struct wrapped_leaf_data_t wrapped_leaf_data;
+	const uint8_t empty_hash[PW_HASH_SIZE] = {};
+	uint8_t new_root[PW_HASH_SIZE];
+
+	if (req_size != sizeof(*request) +
+			get_path_auxiliary_hash_count(merkle_tree) *
+			PW_HASH_SIZE)
+		return PW_ERR_LENGTH_INVALID;
+
+	ret = validate_request_with_path(merkle_tree, request->label,
+					 request->path_hashes, empty_hash);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	ret = validate_delay_schedule(request->delay_schedule);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	memset(&leaf_data, 0, sizeof(leaf_data));
+	leaf_data.pub.label.v = request->label.v;
+	memcpy(&leaf_data.pub.delay_schedule, &request->delay_schedule,
+	       sizeof(request->delay_schedule));
+	memcpy(&leaf_data.sec.low_entropy_secret, &request->low_entropy_secret,
+	       sizeof(request->low_entropy_secret));
+	memcpy(&leaf_data.sec.high_entropy_secret,
+	       &request->high_entropy_secret,
+	       sizeof(request->high_entropy_secret));
+	memcpy(&leaf_data.sec.reset_secret, &request->reset_secret,
+	       sizeof(request->reset_secret));
+
+	ret = handle_leaf_update(merkle_tree, &leaf_data, request->path_hashes,
+				 &wrapped_leaf_data, new_root, NULL);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	memcpy(merkle_tree->root, new_root, sizeof(new_root));
+
+	memcpy(&response->unimported_leaf_data, &wrapped_leaf_data,
+	       sizeof(wrapped_leaf_data));
+
+	*response_size = sizeof(*response) + PW_LEAF_PAYLOAD_SIZE;
+
+	return ret;
+}
+
+static int pw_handle_remove_leaf(struct merkle_tree_t *merkle_tree,
+				 const struct pw_request_remove_leaf_t *request,
+				 uint16_t req_size)
+{
+	int ret = EC_SUCCESS;
+	const uint8_t empty_hash[PW_HASH_SIZE] = {};
+	uint8_t new_root[PW_HASH_SIZE];
+
+	if (req_size != sizeof(*request) +
+			get_path_auxiliary_hash_count(merkle_tree) *
+			PW_HASH_SIZE)
+		return PW_ERR_LENGTH_INVALID;
+
+	ret = validate_request_with_path(merkle_tree, request->leaf_location,
+					 request->path_hashes,
+					 request->leaf_hmac);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	compute_root_hash(merkle_tree, request->leaf_location,
+			  request->path_hashes, empty_hash, new_root);
+
+	memcpy(merkle_tree->root, new_root, sizeof(new_root));
+
+	return ret;
+}
+
+/* Processes a try_auth request.
+ *
+ * The valid fields in response based on return code are:
+ *   EC_SUCCESS                 ->  unimported_leaf_data and high_entropy_secret
+ *   PW_ERR_RATE_LIMIT_REACHED  ->  seconds_to_wait
+ *   PW_ERR_LOWENT_AUTH_FAILED  ->  unimported_leaf_data
+ */
+static int pw_handle_try_auth(struct merkle_tree_t *merkle_tree,
+			      const struct pw_request_try_auth_t *request,
+			      uint16_t req_size,
+			      struct pw_response_try_auth_t *response,
+			      uint16_t *data_length)
+{
+	int ret = EC_SUCCESS;
+	struct leaf_data_t leaf_data = {};
+	struct imported_leaf_data_t imported_leaf_data;
+	struct wrapped_leaf_data_t wrapped_leaf_data;
+	struct time_diff_t seconds_to_wait;
+	uint8_t zeros[PW_SECRET_SIZE] = {};
+	uint8_t new_root[PW_HASH_SIZE];
+
+	/* These variables help eliminate the possibility of a timing side
+	 * channel that would allow an attacker to prevent the log write.
+	 */
+	volatile int auth_result;
+
+	volatile struct {
+		uint32_t attempts;
+		int ret;
+		uint8_t *secret;
+	} results_table[2] = {
+			{ 0, PW_ERR_LOWENT_AUTH_FAILED, zeros },
+			{ 0, EC_SUCCESS, leaf_data.sec.high_entropy_secret },
+	};
+
+	if (req_size < sizeof(*request))
+		return PW_ERR_LENGTH_INVALID;
+
+	ret = validate_request_with_wrapped_leaf(
+			merkle_tree, req_size - sizeof(*request),
+			&request->unimported_leaf_data, &imported_leaf_data,
+			&leaf_data);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	ret = test_rate_limit(&leaf_data, &seconds_to_wait);
+	if (ret != EC_SUCCESS) {
+		*data_length = sizeof(*response) + PW_LEAF_PAYLOAD_SIZE;
+		memset(response, 0, *data_length);
+		memcpy(&response->seconds_to_wait, &seconds_to_wait,
+		       sizeof(seconds_to_wait));
+		return ret;
+	}
+
+	update_timestamp(&leaf_data.pub.timestamp);
+
+	/* Precompute the failed attempts. */
+	results_table[0].attempts = leaf_data.pub.attempt_count.v;
+	if (results_table[0].attempts != UINT32_MAX)
+		++results_table[0].attempts;
+
+	/**********************************************************************/
+	/* After this:
+	 * 1) results_table should not be changed;
+	 * 2) the runtime of the code paths for failed and successful
+	 *    authentication attempts should not diverge.
+	 */
+	auth_result = safe_memcmp(request->low_entropy_secret,
+				  leaf_data.sec.low_entropy_secret,
+				  sizeof(request->low_entropy_secret)) == 0;
+	leaf_data.pub.attempt_count.v = results_table[auth_result].attempts;
+
+	/* This has a non-constant time path, but it doesn't convey information
+	 * about whether a PW_ERR_LOWENT_AUTH_FAILED happened or not.
+	 */
+	ret = handle_leaf_update(merkle_tree, &leaf_data,
+				 imported_leaf_data.hashes, &wrapped_leaf_data,
+				 new_root, &imported_leaf_data);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	memcpy(merkle_tree->root, new_root, sizeof(new_root));
+
+	*data_length = sizeof(*response) + PW_LEAF_PAYLOAD_SIZE;
+	memset(response, 0, *data_length);
+
+	memcpy(&response->unimported_leaf_data, &wrapped_leaf_data,
+	       sizeof(wrapped_leaf_data));
+
+	memcpy(&response->high_entropy_secret,
+	       results_table[auth_result].secret,
+	       sizeof(response->high_entropy_secret));
+
+	return results_table[auth_result].ret;
+}
+
+static int pw_handle_reset_auth(struct merkle_tree_t *merkle_tree,
+				const struct pw_request_reset_auth_t *request,
+				uint16_t req_size,
+				struct pw_response_reset_auth_t *response,
+				uint16_t *response_size)
+{
+	int ret = EC_SUCCESS;
+	struct leaf_data_t leaf_data = {};
+	struct imported_leaf_data_t imported_leaf_data;
+	struct wrapped_leaf_data_t wrapped_leaf_data;
+	uint8_t new_root[PW_HASH_SIZE];
+
+	if (req_size < sizeof(*request))
+		return PW_ERR_LENGTH_INVALID;
+
+	ret = validate_request_with_wrapped_leaf(
+			merkle_tree, req_size - sizeof(*request),
+			&request->unimported_leaf_data, &imported_leaf_data,
+			&leaf_data);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	/* Safe memcmp is used here to prevent an attacker from being able to
+	 * brute force the reset secret and use it to unlock the leaf.
+	 * memcmp provides an attacker a timing side-channel they can use to
+	 * determine how much of a prefix is correct.
+	 */
+	if (safe_memcmp(request->reset_secret,
+			leaf_data.sec.reset_secret,
+			sizeof(request->reset_secret)) != 0)
+		return PW_ERR_RESET_AUTH_FAILED;
+
+	leaf_data.pub.attempt_count.v = 0;
+
+	ret = handle_leaf_update(merkle_tree, &leaf_data,
+				 imported_leaf_data.hashes, &wrapped_leaf_data,
+				 new_root, &imported_leaf_data);
+	if (ret != EC_SUCCESS)
+		return ret;
+
+	memcpy(merkle_tree->root, new_root, sizeof(new_root));
+
+	memcpy(&response->unimported_leaf_data, &wrapped_leaf_data,
+	       sizeof(wrapped_leaf_data));
+
+	memcpy(response->high_entropy_secret,
+	       leaf_data.sec.high_entropy_secret,
+	       sizeof(response->high_entropy_secret));
+
+	*response_size = sizeof(*response) + PW_LEAF_PAYLOAD_SIZE;
+
+	return ret;
+}
+
+/******************************************************************************/
+/* Non-static functions.
+ */
+
+int get_path_auxiliary_hash_count(const struct merkle_tree_t *merkle_tree)
+{
+	return ((1 << merkle_tree->bits_per_level.v) - 1) *
+			merkle_tree->height.v;
+}
+
+/* Computes the SHA256 parent hash of a set of child hashes given num_hashes
+ * sibling hashes in hashes[] and the index of child_hash.
+ *
+ * Assumptions:
+ * num_hashes == fan_out - 1
+ * ARRAY_SIZE(hashes) == num_hashes
+ * 0 <= location <= num_hashes
+ */
+void compute_hash(const uint8_t hashes[][PW_HASH_SIZE], uint16_t num_hashes,
+		  struct index_t location,
+		  const uint8_t child_hash[PW_HASH_SIZE],
+		  uint8_t result[PW_HASH_SIZE])
+{
+	LITE_SHA256_CTX ctx;
+
+	DCRYPTO_SHA256_init(&ctx, 0);
+	if (location.v > 0)
+		HASH_update(&ctx, hashes[0], PW_HASH_SIZE * location.v);
+	HASH_update(&ctx, child_hash, PW_HASH_SIZE);
+	if (location.v < num_hashes)
+		HASH_update(&ctx, hashes[location.v],
+			    PW_HASH_SIZE * (num_hashes - location.v));
+	memcpy(result, HASH_final(&ctx), PW_HASH_SIZE);
+}
+
+/* Handles the message in request using the context in merkle_tree and writes
+ * the results to response. The return value captures any error conditions that
+ * occurred or EC_SUCCESS if there were no errors.
+ *
+ * This implementation is written to handle the case where request and response
+ * exist at the same memory location---are backed by the same buffer. This means
+ * the implementation requires that no reads are made to request after response
+ * has been written to.
+ */
+int pw_handle_request(struct merkle_tree_t *merkle_tree,
+		      const struct pw_request_t *request,
+		      struct pw_response_t *response)
+{
+	int32_t ret;
+	uint16_t resp_length;
+	/* Store the message type of the request since it may be overwritten
+	 * inside the switch whenever response and request overlap in memory.
+	 */
+	struct pw_message_type_t type = request->header.type;
+
+	resp_length = 0;
+
+	if (request->header.version != PW_PROTOCOL_VERSION) {
+		ret = PW_ERR_VERSION_MISMATCH;
+		goto cleanup;
+	}
+
+	switch (type.v) {
+	case PW_RESET_TREE:
+		ret = pw_handle_reset_tree(merkle_tree,
+					   &request->data.reset_tree,
+					   request->header.data_length);
+		break;
+	case PW_INSERT_LEAF:
+		ret = pw_handle_insert_leaf(merkle_tree,
+					    &request->data.insert_leaf,
+					    request->header.data_length,
+					    &response->data.insert_leaf,
+					    &resp_length);
+		break;
+	case PW_REMOVE_LEAF:
+		ret = pw_handle_remove_leaf(merkle_tree,
+					    &request->data.remove_leaf,
+					    request->header.data_length);
+		break;
+	case PW_TRY_AUTH:
+		ret = pw_handle_try_auth(merkle_tree, &request->data.try_auth,
+					 request->header.data_length,
+					 &response->data.try_auth,
+					 &resp_length);
+		break;
+	case PW_RESET_AUTH:
+		ret = pw_handle_reset_auth(merkle_tree,
+					   &request->data.reset_auth,
+					   request->header.data_length,
+					   &response->data.reset_auth,
+					   &resp_length);
+		break;
+	default:
+		ret = PW_ERR_TYPE_INVALID;
+		break;
+	}
+cleanup:
+	response->header.version = PW_PROTOCOL_VERSION;
+	response->header.data_length = resp_length;
+	response->header.result_code = ret;
+	memcpy(&response->header.root, merkle_tree->root,
+	       sizeof(merkle_tree->root));
+	return ret;
+};