futility: the show command can traverse all file types

It doesn't yet handle block devices, but it can display normal files
containing a entire BIOS image, a GBB, a VBLOCK, a .vbpubk, a .vblock,
and a firmware preamble (VbFirmwarePreambleHeader).

The command-line options are not well-documented.

BUG=chromium:224734
BRANCH=ToT
TEST=make runtests

Change-Id: I181f6331ae23599302bbaee3f270e8af9586cf06
Reviewed-on: https://chromium-review.googlesource.com/216032
Commit-Queue: Bill Richardson <wfrichar@chromium.org>
Tested-by: Bill Richardson <wfrichar@chromium.org>
Reviewed-by: Randall Spangler <rspangler@chromium.org>

10 files changed, 989 insertions, 50 deletions

diff --git a/Makefile b/Makefile
index ec551b38..ace39ebe 100644
--- a/Makefile
+++ b/Makefile
@@ -534,7 +534,8 @@ FUTIL_BUILTIN = \
 FUTIL_STATIC_SRCS = \
 	futility/futility.c \
 	futility/cmd_dump_fmap.c \
-	futility/cmd_gbb_utility.c
+	futility/cmd_gbb_utility.c \
+	futility/misc.c
 
 FUTIL_SRCS = \
 	$(FUTIL_STATIC_SRCS) \
@@ -544,7 +545,9 @@ FUTIL_SRCS = \
 	futility/cmd_vbutil_kernel.c \
 	futility/cmd_vbutil_key.c \
 	futility/cmd_vbutil_keyblock.c \
-	futility/cmd_verify_kernel.c
+	futility/cmd_verify_kernel.c \
+	futility/cmd_show.c \
+	futility/traversal.c
 
 ifneq (${VBOOT2},)
 FUTIL_SRCS += \
diff --git a/futility/cmd_gbb_utility.c b/futility/cmd_gbb_utility.c
index 9810058d..428f05b2 100644
--- a/futility/cmd_gbb_utility.c
+++ b/futility/cmd_gbb_utility.c
@@ -74,48 +74,6 @@ static char *short_opts = ":gsc:o:k:b:R:r:h:i:L:f:";
 
 static int errorcnt;
 
-static int ValidGBB(GoogleBinaryBlockHeader * gbb, size_t maxlen)
-{
-	uint32_t i;
-	char *s;
-
-	if (gbb->major_version != GBB_MAJOR_VER)
-		goto bad;
-	if (gbb->header_size != GBB_HEADER_SIZE || gbb->header_size > maxlen)
-		goto bad;
-	if (gbb->hwid_offset < GBB_HEADER_SIZE)
-		goto bad;
-	if (gbb->hwid_offset + gbb->hwid_size > maxlen)
-		goto bad;
-	if (gbb->hwid_size) {
-		/* Make sure the HWID is null-terminated (ASCII, not unicode) */
-		s = (char *)((char *)gbb + gbb->hwid_offset);
-		for (i = 0; i < gbb->hwid_size; i++)
-			if (*s++ == '\0')
-				break;
-		if (i >= gbb->hwid_size)
-			goto bad;
-	}
-	if (gbb->rootkey_offset < GBB_HEADER_SIZE)
-		goto bad;
-	if (gbb->rootkey_offset + gbb->rootkey_size > maxlen)
-		goto bad;
-	if (gbb->bmpfv_offset < GBB_HEADER_SIZE)
-		goto bad;
-	if (gbb->bmpfv_offset + gbb->bmpfv_size > maxlen)
-		goto bad;
-	if (gbb->recovery_key_offset < GBB_HEADER_SIZE)
-		goto bad;
-	if (gbb->recovery_key_offset + gbb->recovery_key_size > maxlen)
-		goto bad;
-
-	return 1;
-
-bad:
-	errorcnt++;
-	return 0;
-}
-
 #define GBB_SEARCH_STRIDE 4
 GoogleBinaryBlockHeader *FindGbbHeader(uint8_t * ptr, size_t size)
 {
@@ -129,7 +87,7 @@ GoogleBinaryBlockHeader *FindGbbHeader(uint8_t * ptr, size_t size)
 
 		/* Found something. See if it's any good. */
 		tmp = (GoogleBinaryBlockHeader *) (ptr + i);
-		if (ValidGBB(tmp, size - i))
+		if (futil_valid_gbb_header(tmp, size - i, NULL))
 			if (!count++)
 				gbb_header = tmp;
 	}
diff --git a/futility/cmd_show.c b/futility/cmd_show.c
new file mode 100644
index 00000000..24d41fde
--- /dev/null
+++ b/futility/cmd_show.c
@@ -0,0 +1,481 @@
+/*
+ * Copyright 2014 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 <errno.h>
+#include <fcntl.h>
+#include <getopt.h>
+#include <inttypes.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "bmpblk_header.h"
+#include "fmap.h"
+#include "futility.h"
+#include "gbb_header.h"
+#include "host_common.h"
+#include "traversal.h"
+#include "util_misc.h"
+#include "vboot_common.h"
+
+/* Local values for cb_area_s._flags */
+enum callback_flags {
+	AREA_IS_VALID =     0x00000001,
+};
+
+/* Local structure for args, etc. */
+static struct local_data_s {
+	VbPublicKey *k;
+	uint8_t *f;
+	uint64_t f_size;
+} option;
+
+static void show_key(VbPublicKey *pubkey, const char *sp)
+{
+	printf("%sAlgorithm:           %" PRIu64 " %s\n", sp,pubkey->algorithm,
+	       (pubkey->algorithm < kNumAlgorithms ?
+		algo_strings[pubkey->algorithm] : "(invalid)"));
+	printf("%sKey Version:         %" PRIu64 "\n", sp, pubkey->key_version);
+	printf("%sKey sha1sum:         ", sp);
+	PrintPubKeySha1Sum(pubkey);
+	printf("\n");
+}
+
+static void show_keyblock(VbKeyBlockHeader *key_block, const char *name,
+			  int sign_key, int good_sig)
+{
+	printf("Key block:               %s\n", name);
+	printf("  Size:                  %" PRIu64 "\n",
+	       key_block->key_block_size);
+	printf("  Signature              %s\n",
+	       sign_key ? (good_sig ? "valid" : "invalid" ) : "ignored");
+	printf("  Flags:                 %" PRIu64 " ",
+	       key_block->key_block_flags);
+	if (key_block->key_block_flags & KEY_BLOCK_FLAG_DEVELOPER_0)
+		printf(" !DEV");
+	if (key_block->key_block_flags & KEY_BLOCK_FLAG_DEVELOPER_1)
+		printf(" DEV");
+	if (key_block->key_block_flags & KEY_BLOCK_FLAG_RECOVERY_0)
+		printf(" !REC");
+	if (key_block->key_block_flags & KEY_BLOCK_FLAG_RECOVERY_1)
+		printf(" REC");
+	printf("\n");
+
+	VbPublicKey *data_key = &key_block->data_key;
+	printf("  Data key algorithm:    %" PRIu64 " %s\n", data_key->algorithm,
+	       (data_key->algorithm < kNumAlgorithms
+		? algo_strings[data_key->algorithm]
+		: "(invalid)"));
+	printf("  Data key version:      %" PRIu64 "\n", data_key->key_version);
+	printf("  Data key sha1sum:      ");
+	PrintPubKeySha1Sum(data_key);
+	printf("\n");
+}
+
+int futil_cb_show_key(struct futil_traverse_state_s *state)
+{
+	VbPublicKey *pubkey = (VbPublicKey *)state->my_area->buf;
+
+	if (!PublicKeyLooksOkay(pubkey, state->my_area->len)) {
+		printf("%s looks bogus\n", state->name);
+		return 1;
+	}
+
+	printf("Public Key file:       %s\n", state->in_filename);
+	show_key(pubkey, "  ");
+
+	state->my_area->_flags |= AREA_IS_VALID;
+	return 0;
+}
+
+int futil_cb_show_gbb(struct futil_traverse_state_s *state)
+{
+	uint8_t *buf = state->my_area->buf;
+	uint32_t len = state->my_area->len;
+	GoogleBinaryBlockHeader *gbb = (GoogleBinaryBlockHeader *)buf;
+	VbPublicKey *pubkey;
+	BmpBlockHeader *bmp;
+	int retval = 0;
+	uint32_t maxlen = 0;
+
+	/* It looks like a GBB or we wouldn't be called. */
+	if (!futil_valid_gbb_header(gbb, len, &maxlen))
+		retval = 1;
+
+	printf("GBB header:              %s\n",
+	       state->component == CB_GBB ? state->in_filename : state->name);
+	printf("  Version:               %d.%d\n",
+	       gbb->major_version, gbb->minor_version);
+	printf("  Flags:                 0x08%x\n", gbb->flags);
+	printf("  Regions:                 offset       size\n");
+	printf("    hwid                 0x%08x   0x%08x\n",
+	       gbb->hwid_offset, gbb->hwid_size);
+	printf("    bmpvf                0x%08x   0x%08x\n",
+	       gbb->bmpfv_offset, gbb->bmpfv_size);
+	printf("    rootkey              0x%08x   0x%08x\n",
+	       gbb->rootkey_offset, gbb->rootkey_size);
+	printf("    recovery_key         0x%08x   0x%08x\n",
+	       gbb->recovery_key_offset, gbb->recovery_key_size);
+
+	printf("  Size:                  0x%08x / 0x%08x%s\n",
+	       maxlen, len, maxlen > len ? "  (not enough)" : "");
+
+	if (retval) {
+		printf("GBB header is invalid, ignoring content\n");
+		return 1;
+	}
+
+	printf("GBB content:\n");
+	printf("  HWID:                  %s\n",
+	       (const char *)(buf + gbb->hwid_offset));
+
+	pubkey = (VbPublicKey *)(buf + gbb->rootkey_offset);
+	if (PublicKeyLooksOkay(pubkey, gbb->rootkey_size)) {
+		state->rootkey.offset = state->my_area->offset +
+			gbb->rootkey_offset;
+		state->rootkey.buf = buf + gbb->rootkey_offset;
+		state->rootkey.len = gbb->rootkey_size;
+		state->rootkey._flags |= AREA_IS_VALID;
+		printf("  Root Key:\n");
+		show_key(pubkey, "    ");
+	} else {
+		retval = 1;
+		printf("  Root Key:              <invalid>\n");
+	}
+
+	pubkey = (VbPublicKey *)(buf + gbb->recovery_key_offset);
+	if (PublicKeyLooksOkay(pubkey, gbb->recovery_key_size)) {
+		state->recovery_key.offset = state->my_area->offset +
+			gbb->recovery_key_offset;
+		state->recovery_key.buf = buf + gbb->recovery_key_offset;
+		state->recovery_key.len = gbb->recovery_key_size;
+		state->recovery_key._flags |= AREA_IS_VALID;
+		printf("  Recovery Key:\n");
+		show_key(pubkey, "    ");
+	} else {
+		retval = 1;
+		printf("  Recovery Key:          <invalid>\n");
+	}
+
+	bmp = (BmpBlockHeader *)(buf + gbb->bmpfv_offset);
+	if (0 != memcmp(bmp, BMPBLOCK_SIGNATURE, BMPBLOCK_SIGNATURE_SIZE)) {
+		retval = 1;
+		printf("  BmpBlock:              <invalid>\n");
+	} else {
+		printf("  BmpBlock:\n");
+		printf("    Version:             %d.%d\n",
+		       bmp->major_version, bmp->minor_version);
+		printf("    Localizations:       %d\n",
+		       bmp->number_of_localizations);
+		printf("    Screen layouts:      %d\n",
+		       bmp->number_of_screenlayouts);
+		printf("    Image infos:         %d\n",
+		       bmp->number_of_imageinfos);
+	}
+
+	if (!retval)
+		state->my_area->_flags |= AREA_IS_VALID;
+
+	return retval;
+}
+
+int futil_cb_show_keyblock(struct futil_traverse_state_s *state)
+{
+	VbKeyBlockHeader *block = (VbKeyBlockHeader *)state->my_area->buf;
+	VbPublicKey *sign_key = option.k;
+	int good_sig = 0;
+
+	/* Check the hash only first */
+	if (0 != KeyBlockVerify(block, state->my_area->len, NULL, 1)) {
+		printf("%s is invalid\n", state->name);
+		return 1;
+	}
+
+	/* Check the signature if we have one */
+	if (sign_key && VBOOT_SUCCESS ==
+	    KeyBlockVerify(block, state->my_area->len, sign_key, 0))
+		good_sig = 1;
+
+	show_keyblock(block, state->in_filename, !!sign_key, good_sig);
+
+	state->my_area->_flags |= AREA_IS_VALID;
+
+	return 0;
+}
+
+/*
+ * This handles FW_MAIN_A and FW_MAIN_B while processing a BIOS image.
+ *
+ * The data in state->my_area is just the RW firmware blob, so there's nothing
+ * useful to show about it. We'll just mark it as present so when we encounter
+ * corresponding VBLOCK area, we'll have this to verify.
+ */
+int futil_cb_show_fw_main(struct futil_traverse_state_s *state)
+{
+	printf("Firmware body:           %s\n", state->name);
+	printf("  Offset:                0x%08x\n", state->my_area->offset);
+	printf("  Size:                  0x%08x\n", state->my_area->len);
+
+	state->my_area->_flags |= AREA_IS_VALID;
+
+	return 0;
+}
+
+int futil_cb_show_fw_preamble(struct futil_traverse_state_s *state)
+{
+	VbKeyBlockHeader *key_block = (VbKeyBlockHeader *)state->my_area->buf;
+	uint32_t len = state->my_area->len;
+	VbPublicKey *sign_key = 0;
+	uint8_t *fv_data = 0;
+	uint64_t fv_size = 0;
+	struct cb_area_s *fw_body_area = 0;
+	int good_sig = 0;
+
+	/* Check the hash... */
+	if (VBOOT_SUCCESS != KeyBlockVerify(key_block, len, NULL, 1)) {
+		printf("%s keyblock component is invalid\n", state->name);
+		return 1;
+	}
+
+	switch (state->component) {
+	case CB_FMAP_VBLOCK_A:
+		/* BIOS should have a rootkey in the GBB */
+		if (state->rootkey._flags & AREA_IS_VALID)
+			sign_key = (VbPublicKey *)state->rootkey.buf;
+		/* And we should have already seen the firmware body */
+		fw_body_area = &state->cb_area[CB_FMAP_FW_MAIN_A];
+		break;
+	case CB_FMAP_VBLOCK_B:
+		/* BIOS should have a rootkey in the GBB */
+		if (state->rootkey._flags & AREA_IS_VALID)
+			sign_key = (VbPublicKey *)state->rootkey.buf;
+		/* And we should have already seen the firmware body */
+		fw_body_area = &state->cb_area[CB_FMAP_FW_MAIN_B];
+		break;
+	case CB_FW_PREAMBLE:
+		/* We'll have to get a signature and body from elsewhere */
+		sign_key = option.k;
+		fv_data = option.f;
+		fv_size = option.f_size;
+		break;
+	default:
+		DIE;
+	}
+
+	/* If we have a key, check the signature too */
+	if (sign_key && VBOOT_SUCCESS ==
+	    KeyBlockVerify(key_block, len, sign_key, 0))
+		good_sig = 1;
+
+	show_keyblock(key_block,
+		      state->component == CB_FW_PREAMBLE
+		      ? state->in_filename : state->name,
+		      !!sign_key, good_sig);
+
+	RSAPublicKey *rsa = PublicKeyToRSA(&key_block->data_key);
+	if (!rsa) {
+		VbExError("Error parsing data key in %s\n", state->name);
+		return 1;
+	}
+	uint32_t more = key_block->key_block_size;
+	VbFirmwarePreambleHeader *preamble =
+		(VbFirmwarePreambleHeader *)(state->my_area->buf + more);
+
+	if (VBOOT_SUCCESS != VerifyFirmwarePreamble(preamble,
+						    len - more, rsa)) {
+		printf("%s is invalid\n", state->name);
+		return 1;
+	}
+
+	uint32_t flags = VbGetFirmwarePreambleFlags(preamble);
+	printf("Preamble:\n");
+	printf("  Size:                  %" PRIu64 "\n",
+	       preamble->preamble_size);
+	printf("  Header version:        %" PRIu32 ".%" PRIu32 "\n",
+	       preamble->header_version_major, preamble->header_version_minor);
+	printf("  Firmware version:      %" PRIu64 "\n",
+	       preamble->firmware_version);
+	VbPublicKey *kernel_subkey = &preamble->kernel_subkey;
+	printf("  Kernel key algorithm:  %" PRIu64 " %s\n",
+	       kernel_subkey->algorithm,
+	       (kernel_subkey->algorithm < kNumAlgorithms ?
+		algo_strings[kernel_subkey->algorithm] : "(invalid)"));
+	printf("  Kernel key version:    %" PRIu64 "\n",
+	       kernel_subkey->key_version);
+	printf("  Kernel key sha1sum:    ");
+	PrintPubKeySha1Sum(kernel_subkey);
+	printf("\n");
+	printf("  Firmware body size:    %" PRIu64 "\n",
+	       preamble->body_signature.data_size);
+	printf("  Preamble flags:        %" PRIu32 "\n", flags);
+
+
+	if (flags & VB_FIRMWARE_PREAMBLE_USE_RO_NORMAL) {
+		printf ("Preamble requests USE_RO_NORMAL;"
+			" skipping body verification.\n");
+		goto done;
+	}
+
+	/* We'll need to get the firmware body from somewhere... */
+	if (fw_body_area && (fw_body_area->_flags & AREA_IS_VALID))
+	{
+		fv_data = fw_body_area->buf;
+		fv_size = fw_body_area->len;
+	}
+
+	if (!fv_data) {
+		printf("No firmware body available to verify.\n");
+		return 1;
+	}
+
+	if (VBOOT_SUCCESS !=
+	    VerifyData(fv_data, fv_size, &preamble->body_signature, rsa)) {
+		VbExError("Error verifying firmware body.\n");
+		return 1;
+	}
+
+done:
+	/* Can't trust the BIOS unless everything is signed,
+	 * but standalone files are okay. */
+	if ((state->component == CB_FW_PREAMBLE) ||
+	    (sign_key && good_sig)) {
+		if (!(flags & VB_FIRMWARE_PREAMBLE_USE_RO_NORMAL))
+			printf("Body verification succeeded.\n");
+		state->my_area->_flags |= AREA_IS_VALID;
+	} else {
+		printf("Body seems legit, but the signature is unverified.\n");
+	}
+
+	return 0;
+}
+
+int futil_cb_show_begin(struct futil_traverse_state_s *state)
+{
+	switch (state->in_type) {
+	case FILE_TYPE_UNKNOWN:
+		fprintf(stderr, "Unable to determine type of %s\n",
+			state->in_filename);
+		return 1;
+
+	case FILE_TYPE_BIOS_IMAGE:
+	case FILE_TYPE_OLD_BIOS_IMAGE:
+		printf("BIOS:                    %s\n", state->in_filename);
+		break;
+
+	default:
+		break;
+	}
+	return 0;
+}
+
+static void help_and_quit(const char *prog)
+{
+	fprintf(stderr, "\n"
+		"Usage:  " MYNAME " %s [OPTIONS] FILE\n"
+		"\n"
+		"Display the contents of the given FILE\n"
+		"\n"
+		"Options:\n"
+		"  -k|--publickey FILE    Use this public key for validation\n"
+		"  -f|--fv FILE           Use this firmware blob where needed\n"
+		"\n", prog);
+	exit(1);
+}
+
+static const struct option long_opts[] = {
+	/* name    hasarg *flag val */
+	{"publickey", 1, 0, 'k'},
+	{"fv", 1, 0, 'f'},
+	{NULL, 0, NULL, 0},
+};
+static char *short_opts = ":f:k:";
+
+static int do_show(int argc, char *argv[])
+{
+	char *infile = 0;
+	int ifd, i;
+	int errorcnt = 0;
+	struct futil_traverse_state_s state;
+
+	opterr = 0;		/* quiet, you */
+	while ((i = getopt_long(argc, argv, short_opts, long_opts, 0)) != -1) {
+		switch (i) {
+		case 'f':
+			option.f = ReadFile(optarg, &option.f_size);
+			if (!option.f) {
+				fprintf(stderr, "Error reading %s\n", optarg);
+				errorcnt++;
+			}
+			break;
+		case 'k':
+			option.k = PublicKeyRead(optarg);
+			if (!option.k) {
+				fprintf(stderr, "Error reading %s\n", optarg);
+				errorcnt++;
+			}
+			break;
+
+		case '?':
+			if (optopt)
+				fprintf(stderr, "Unrecognized option: -%c\n",
+					optopt);
+			else
+				fprintf(stderr, "Unrecognized option\n");
+			errorcnt++;
+			break;
+		case ':':
+			fprintf(stderr, "Missing argument to -%c\n", optopt);
+			errorcnt++;
+			break;
+		default:
+			DIE;
+		}
+	}
+
+	if (errorcnt)
+		help_and_quit(argv[0]);
+
+	if (argc - optind < 1) {
+		fprintf(stderr, "ERROR: missing input filename\n");
+		help_and_quit(argv[0]);
+	}
+
+	for (i = optind; i < argc; i++) {
+		infile = argv[i];
+		ifd = open(infile, O_RDONLY);
+		if (ifd < 0) {
+			errorcnt++;
+			fprintf(stderr, "Can't open %s: %s\n",
+				infile, strerror(errno));
+			return 1;
+		}
+
+		memset(&state, 0, sizeof(state));
+		state.in_filename = infile ? infile : "<none>";
+		state.op = FUTIL_OP_SHOW;
+
+		errorcnt += futil_traverse(ifd, &state);
+
+		if (close(ifd)) {
+			errorcnt++;
+			fprintf(stderr, "Error when closing %s: %s\n",
+				infile, strerror(errno));
+		}
+	}
+
+	if (option.k)
+		free(option.k);
+	if (option.f)
+		free(option.f);
+
+	return !!errorcnt;
+}
+
+DECLARE_FUTIL_COMMAND(show, do_show, "Display what we know about a file");
diff --git a/futility/futility.c b/futility/futility.c
index 3496cdc2..f18edb50 100644
--- a/futility/futility.c
+++ b/futility/futility.c
@@ -16,7 +16,6 @@
 
 #include "futility.h"
 
-#define MYNAME "futility"
 #define MYNAME_S MYNAME "_s"
 
 /* File to use for logging, if present */
diff --git a/futility/futility.h b/futility/futility.h
index dfccf6f9..8c2b809b 100644
--- a/futility/futility.h
+++ b/futility/futility.h
@@ -3,10 +3,15 @@
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
-#include <stdint.h>
-
 #ifndef VBOOT_REFERENCE_FUTILITY_H_
 #define VBOOT_REFERENCE_FUTILITY_H_
+#include <stdint.h>
+
+#include "vboot_common.h"
+#include "gbb_header.h"
+
+/* This program */
+#define MYNAME "futility"
 
 /* Here's a structure to define the commands that futility implements. */
 struct futil_cmd_t {
@@ -46,4 +51,24 @@ extern const struct futil_cmd_t *const futil_cmds[];
 #define BUILD_ASSERT(cond) _BA0_(cond, __LINE__)
 #endif
 
+/* Fatal internal stupidness */
+#ifndef DIE
+#define DIE do {							\
+		fprintf(stderr, MYNAME ": internal error at %s:%d\n",	\
+			__FILE__, __LINE__);				\
+		exit(1);						\
+	} while (0)
+#endif
+
+
+/* Returns true if this looks enough like a GBB header to proceed. */
+int futil_looks_like_gbb(GoogleBinaryBlockHeader *gbb, uint32_t len);
+
+/*
+ * Returns true if the gbb header is valid (and optionally updates *maxlen).
+ * This doesn't verify the contents, though.
+ */
+int futil_valid_gbb_header(GoogleBinaryBlockHeader *gbb, uint32_t len,
+			   uint32_t *maxlen);
+
 #endif /* VBOOT_REFERENCE_FUTILITY_H_ */
diff --git a/futility/misc.c b/futility/misc.c
new file mode 100644
index 00000000..91962cbd
--- /dev/null
+++ b/futility/misc.c
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2014 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 <stdint.h>
+#include <string.h>
+
+#include "gbb_header.h"
+
+static int is_null_terminated(const char *s, int len)
+{
+	len--;
+	s += len;
+	while (len-- >= 0)
+		if (!*s--)
+			return 1;
+	return 0;
+}
+
+static inline uint32_t max(uint32_t a, uint32_t b)
+{
+	return a > b ? a : b;
+}
+
+int futil_looks_like_gbb(GoogleBinaryBlockHeader *gbb, uint32_t len)
+{
+	if (memcmp(gbb->signature, GBB_SIGNATURE, GBB_SIGNATURE_SIZE))
+		return 0;
+	if (gbb->major_version > GBB_MAJOR_VER)
+		return 0;
+	if (sizeof(GoogleBinaryBlockHeader) > len)
+		return 0;
+
+	/* close enough */
+	return 1;
+}
+
+int futil_valid_gbb_header(GoogleBinaryBlockHeader *gbb, uint32_t len,
+			   uint32_t *maxlen_ptr)
+{
+	if (memcmp(gbb->signature, GBB_SIGNATURE, GBB_SIGNATURE_SIZE))
+		return 0;
+	if (gbb->major_version != GBB_MAJOR_VER)
+		return 0;
+
+	/* Check limits first, to help identify problems */
+	if (maxlen_ptr) {
+		uint32_t maxlen = gbb->header_size;
+		maxlen = max(maxlen,
+			     gbb->hwid_offset + gbb->hwid_size);
+		maxlen = max(maxlen,
+			     gbb->rootkey_offset + gbb->rootkey_size);
+		maxlen = max(maxlen,
+			     gbb->bmpfv_offset + gbb->bmpfv_size);
+		maxlen = max(maxlen,
+			     gbb->recovery_key_offset + gbb->recovery_key_size);
+		*maxlen_ptr = maxlen;
+	}
+
+	if (gbb->header_size != GBB_HEADER_SIZE || gbb->header_size > len)
+		return 0;
+	if (gbb->hwid_offset < GBB_HEADER_SIZE)
+		return 0;
+	if (gbb->hwid_offset + gbb->hwid_size > len)
+		return 0;
+	if (gbb->hwid_size) {
+		const char *s = (const char *)
+			((uint8_t *)gbb + gbb->hwid_offset);
+		if (!is_null_terminated(s, gbb->hwid_size))
+			return 0;
+	}
+	if (gbb->rootkey_offset < GBB_HEADER_SIZE)
+		return 0;
+	if (gbb->rootkey_offset + gbb->rootkey_size > len)
+		return 0;
+
+	if (gbb->bmpfv_offset < GBB_HEADER_SIZE)
+		return 0;
+	if (gbb->bmpfv_offset + gbb->bmpfv_size > len)
+		return 0;
+	if (gbb->recovery_key_offset < GBB_HEADER_SIZE)
+		return 0;
+	if (gbb->recovery_key_offset + gbb->recovery_key_size > len)
+		return 0;
+
+	/* Seems legit... */
+	return 1;
+}
diff --git a/futility/traversal.c b/futility/traversal.c
new file mode 100644
index 00000000..81303d9d
--- /dev/null
+++ b/futility/traversal.c
@@ -0,0 +1,291 @@
+/*
+ * Copyright 2014 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 <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "fmap.h"
+#include "futility.h"
+#include "gbb_header.h"
+#include "host_key.h"
+#include "traversal.h"
+
+/* What functions do we invoke for a particular operation and component? */
+
+/* FUTIL_OP_SHOW */
+static int (* const cb_show_funcs[])(struct futil_traverse_state_s *state) =
+{
+	futil_cb_show_begin,		/* CB_BEGIN_TRAVERSAL */
+	NULL,				/* CB_END_TRAVERSAL */
+	futil_cb_show_gbb,		/* CB_FMAP_GBB */
+	futil_cb_show_fw_preamble,	/* CB_FMAP_VBLOCK_A */
+	futil_cb_show_fw_preamble,	/* CB_FMAP_VBLOCK_B */
+	futil_cb_show_fw_main,     	/* CB_FMAP_FW_MAIN_A */
+	futil_cb_show_fw_main,     	/* CB_FMAP_FW_MAIN_B */
+	futil_cb_show_key,      	/* CB_PUBKEY */
+	futil_cb_show_keyblock,      	/* CB_KEYBLOCK */
+	futil_cb_show_gbb,		/* CB_GBB */
+	futil_cb_show_fw_preamble,	/* CB_FW_PREAMBLE */
+};
+BUILD_ASSERT(ARRAY_SIZE(cb_show_funcs) == NUM_CB_COMPONENTS);
+
+static int (* const * const cb_func[])(struct futil_traverse_state_s *state) =
+{
+	cb_show_funcs,
+};
+BUILD_ASSERT(ARRAY_SIZE(cb_func) == NUM_FUTIL_OPS);
+
+
+static int invoke_callback(struct futil_traverse_state_s *state,
+			   enum futil_cb_component c, const char *name,
+			   uint32_t offset, uint8_t *buf, uint32_t len)
+{
+	if (c < 0 || c >= NUM_CB_COMPONENTS) {
+		fprintf(stderr, "Invalid component %d\n", c);
+		return 1;
+	}
+
+	state->component = c;
+	state->name = name;
+	state->cb_area[c].offset = offset;
+	state->cb_area[c].buf = buf;
+	state->cb_area[c].len = len;
+	state->my_area = &state->cb_area[c];
+
+	if (cb_func[state->op][c])
+		return cb_func[state->op][c](state);
+
+	return 0;
+}
+
+/*
+ * File types that don't need iterating can use a lookup table to determine the
+ * callback component and name. The index is the file type.
+ */
+static const struct {
+	enum futil_cb_component component;
+	const char * const name;
+} direct_callback[] = {
+	{0,                NULL},		/* FILE_TYPE_UNKNOWN */
+	{CB_PUBKEY,        "VbPublicKey"},	/* FILE_TYPE_PUBKEY */
+	{CB_KEYBLOCK,      "VbKeyBlock"},	/* FILE_TYPE_KEYBLOCK */
+	{CB_FW_PREAMBLE,   "FW Preamble"},	/* FILE_TYPE_FIRMWARE */
+	{CB_GBB,           "GBB"},		/* FILE_TYPE_GBB */
+	{0,                NULL},		/* FILE_TYPE_BIOS_IMAGE */
+	{0,                NULL},		/* FILE_TYPE_OLD_BIOS_IMAGE */
+};
+BUILD_ASSERT(ARRAY_SIZE(direct_callback) == NUM_FILE_TYPES);
+
+/*
+ * The Chrome OS BIOS must contain specific FMAP areas, and we generally want
+ * to look at each one in a certain order.
+ */
+struct bios_area_s {
+	const char * const name;
+	enum futil_cb_component component;
+};
+
+/* This are the expected areas, in order of traversal. */
+static const struct bios_area_s bios_area[] = {
+	{"GBB",       CB_FMAP_GBB},
+	{"FW_MAIN_A", CB_FMAP_FW_MAIN_A},
+	{"FW_MAIN_B", CB_FMAP_FW_MAIN_B},
+	{"VBLOCK_A",  CB_FMAP_VBLOCK_A},
+	{"VBLOCK_B",  CB_FMAP_VBLOCK_B},
+	{0, 0}
+};
+
+/* Really old BIOS images had different names, but worked the same. */
+static const struct bios_area_s old_bios_area[] = {
+	{"GBB Area",        CB_FMAP_GBB},
+	{"Firmware A Data", CB_FMAP_FW_MAIN_A},
+	{"Firmware B Data", CB_FMAP_FW_MAIN_B},
+	{"Firmware A Key",  CB_FMAP_VBLOCK_A},
+	{"Firmware B Key",  CB_FMAP_VBLOCK_B},
+	{0, 0}
+};
+
+static int has_all_areas(uint8_t *buf, uint32_t len, FmapHeader *fmap,
+			 const struct bios_area_s *area)
+{
+	// We must have all the expected areas
+	for ( ; area->name; area++)
+		if (!fmap_find_by_name(buf, len, fmap, area->name, 0))
+			return 0;
+
+	/* Found 'em all */
+	return 1;
+}
+
+static enum futil_file_type what_is_this(uint8_t *buf, uint32_t len)
+{
+	VbPublicKey *pubkey = (VbPublicKey *)buf;
+	VbKeyBlockHeader *key_block = (VbKeyBlockHeader *)buf;
+	GoogleBinaryBlockHeader *gbb = (GoogleBinaryBlockHeader *)buf;
+	VbFirmwarePreambleHeader *fw_preamble;
+	RSAPublicKey *rsa;
+	FmapHeader *fmap;
+
+	/*
+	 * Complex structs may begin with simpler structs first, so try them
+	 * in reverse order.
+	 */
+
+	fmap = fmap_find(buf, len);
+	if (fmap) {
+		if (has_all_areas(buf, len, fmap, bios_area))
+			return FILE_TYPE_BIOS_IMAGE;
+		if (has_all_areas(buf, len, fmap, old_bios_area))
+			return FILE_TYPE_OLD_BIOS_IMAGE;
+	}
+
+	if (futil_looks_like_gbb(gbb, len))
+		return FILE_TYPE_GBB;
+
+	if (VBOOT_SUCCESS == KeyBlockVerify(key_block, len, NULL, 1)) {
+		/* and firmware preamble too? */
+		fw_preamble = (VbFirmwarePreambleHeader *)
+			(buf + key_block->key_block_size);
+		uint32_t more = key_block->key_block_size;
+		rsa = PublicKeyToRSA(&key_block->data_key);
+		if (VBOOT_SUCCESS ==
+		    VerifyFirmwarePreamble(fw_preamble, len - more, rsa))
+			return FILE_TYPE_FIRMWARE;
+
+		/* no, just keyblock */
+		return FILE_TYPE_KEYBLOCK;
+	}
+
+	if (PublicKeyLooksOkay(pubkey, len)) {
+		return FILE_TYPE_PUBKEY;
+	}
+
+	return FILE_TYPE_UNKNOWN;
+}
+
+static int traverse_buffer(uint8_t *buf, uint32_t len,
+			   struct futil_traverse_state_s *state)
+{
+	FmapHeader *fmap;
+	FmapAreaHeader *ah = 0;
+	const struct bios_area_s *area;
+	enum futil_file_type type;
+	int retval = 0;
+
+	type = what_is_this(buf, len);
+	state->in_type = type;
+
+	state->errors = retval;
+	retval |= invoke_callback(state, CB_BEGIN_TRAVERSAL, "<begin>",
+				  0, buf, len);
+	state->errors = retval;
+
+	switch (type) {
+	case FILE_TYPE_PUBKEY:
+	case FILE_TYPE_KEYBLOCK:
+	case FILE_TYPE_FIRMWARE:
+	case FILE_TYPE_GBB:
+		retval |= invoke_callback(state,
+					  direct_callback[type].component,
+					  direct_callback[type].name,
+					  0, buf, len);
+		state->errors = retval;
+		break;
+
+	case FILE_TYPE_BIOS_IMAGE:
+		/* We've already checked, so we know this will work. */
+		fmap = fmap_find(buf, len);
+		for (area = bios_area; area->name; area++) {
+			/* We know this will work, too */
+			fmap_find_by_name(buf, len, fmap, area->name, &ah);
+			retval |= invoke_callback(state,
+						  area->component,
+						  area->name,
+						  ah->area_offset,
+						  buf + ah->area_offset,
+						  ah->area_size);
+			state->errors = retval;
+		}
+		break;
+
+	case FILE_TYPE_OLD_BIOS_IMAGE:
+		/* We've already checked, so we know this will work. */
+		fmap = fmap_find(buf, len);
+		for (area = old_bios_area; area->name; area++) {
+			/* We know this will work, too */
+			fmap_find_by_name(buf, len, fmap, area->name, &ah);
+			retval |= invoke_callback(state,
+						  area->component,
+						  area->name,
+						  ah->area_offset,
+						  buf + ah->area_offset,
+						  ah->area_size);
+			state->errors = retval;
+		}
+		break;
+
+	default:
+		retval = 1;
+	}
+
+	retval |= invoke_callback(state, CB_END_TRAVERSAL, "<end>",
+				  0, buf, len);
+	return retval;
+}
+
+int futil_traverse(int ifd, struct futil_traverse_state_s *state)
+{
+	struct stat sb;
+	void *mmap_ptr;
+	uint32_t reasonable_len;
+	int errorcnt = 0;
+
+	if (state->op < 0 || state->op >= NUM_FUTIL_OPS) {
+		fprintf(stderr, "Invalid op %d\n", state->op);
+		return 1;
+	}
+
+	if (0 != fstat(ifd, &sb)) {
+		fprintf(stderr, "Can't stat input file: %s\n",
+			strerror(errno));
+		return 1;
+	}
+
+	if (!S_ISREG(sb.st_mode)) {
+		fprintf(stderr, "Block devices are not yet supported\n");
+		return 1;
+	}
+
+	/* If the image is larger than 2^32 bytes, it's wrong. */
+	if (sb.st_size < 0 || sb.st_size > UINT32_MAX) {
+		fprintf(stderr, "Image size is unreasonable\n");
+		return 1;
+	}
+	reasonable_len = (uint32_t)sb.st_size;
+
+	mmap_ptr = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, ifd, 0);
+	if (mmap_ptr == (void *)-1) {
+		fprintf(stderr, "Can't mmap input file: %s\n",
+			strerror(errno));
+		return 1;
+	}
+
+	errorcnt += traverse_buffer(mmap_ptr, reasonable_len, state);
+
+	if (0 != munmap(mmap_ptr, sb.st_size)) {
+		fprintf(stderr, "Can't munmap pointer: %s\n",
+			strerror(errno));
+		errorcnt++;
+	}
+
+	return errorcnt;
+}
diff --git a/futility/traversal.h b/futility/traversal.h
new file mode 100644
index 00000000..ca31978a
--- /dev/null
+++ b/futility/traversal.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2013 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.
+ */
+#ifndef VBOOT_REFERENCE_FUTILITY_TRAVERSAL_H_
+#define VBOOT_REFERENCE_FUTILITY_TRAVERSAL_H_
+#include <stdint.h>
+
+
+/* What type of things do I know how to handle? */
+enum futil_file_type {
+	FILE_TYPE_UNKNOWN = 0,
+	FILE_TYPE_PUBKEY,			/* 1 VbPublicKey */
+	FILE_TYPE_KEYBLOCK,			/* 2 VbKeyBlockHeader */
+	FILE_TYPE_FIRMWARE,			/* 3 VbFirmwarePreambleHeader */
+	FILE_TYPE_GBB,				/* 4 GoogleBinaryBlockHeader */
+	FILE_TYPE_BIOS_IMAGE,			/* 5 Chrome OS BIOS image */
+	FILE_TYPE_OLD_BIOS_IMAGE,		/* 6 Old Chrome OS BIOS image */
+
+	NUM_FILE_TYPES
+};
+
+/* What are we trying to accomplish? */
+enum futil_op_type {
+	FUTIL_OP_SHOW,
+
+	NUM_FUTIL_OPS
+};
+
+/* What component are we currently handling in the callback routine? */
+enum futil_cb_component {
+	/* entire input buffer */
+	CB_BEGIN_TRAVERSAL,
+	CB_END_TRAVERSAL,
+	/* fmap areas within a bios image */
+	CB_FMAP_GBB,
+	CB_FMAP_VBLOCK_A,
+	CB_FMAP_VBLOCK_B,
+	CB_FMAP_FW_MAIN_A,
+	CB_FMAP_FW_MAIN_B,
+	/* individual files (extracted from a bios, for example) */
+	CB_PUBKEY,
+	CB_KEYBLOCK,
+	CB_GBB,
+	CB_FW_PREAMBLE,
+
+	NUM_CB_COMPONENTS
+};
+
+/* Where is the component we're poking at? */
+struct cb_area_s {
+	uint32_t offset;			/* to avoid pointer math */
+	uint8_t *buf;
+	uint32_t len;
+	uint32_t _flags;			/* for callback use */
+};
+
+/* What do we know at this point in time? */
+struct futil_traverse_state_s {
+	/* These two should be initialized by the caller */
+	const char *in_filename;
+	enum futil_op_type op;
+	/* Current activity during traversal */
+	enum futil_cb_component component;
+	struct cb_area_s *my_area;
+	const char *name;
+	/* Other activites, possibly before or after the current one */
+	struct cb_area_s cb_area[NUM_CB_COMPONENTS];
+	struct cb_area_s recovery_key;
+	struct cb_area_s rootkey;
+	enum futil_file_type in_type;
+	int errors;
+};
+
+/*
+ * Traverse the input file using the provided state
+ * Return nonzero (but no details) if there were any errors.
+ */
+int futil_traverse(int ifd, struct futil_traverse_state_s *state);
+
+/* These are invoked by the traversal. They also return nonzero on error. */
+int futil_cb_show_begin(struct futil_traverse_state_s *state);
+int futil_cb_show_key(struct futil_traverse_state_s *state);
+int futil_cb_show_gbb(struct futil_traverse_state_s *state);
+int futil_cb_show_keyblock(struct futil_traverse_state_s *state);
+int futil_cb_show_fw_main(struct futil_traverse_state_s *state);
+int futil_cb_show_fw_preamble(struct futil_traverse_state_s *state);
+
+#endif /* VBOOT_REFERENCE_FUTILITY_TRAVERSAL_H_ */
diff --git a/host/lib/fmap.c b/host/lib/fmap.c
index f9b0e5ed..76fa9f1d 100644
--- a/host/lib/fmap.c
+++ b/host/lib/fmap.c
@@ -14,7 +14,10 @@ FmapHeader *fmap_find(uint8_t *ptr, size_t size)
 {
 	size_t i;
 	FmapHeader *fmap_header;
-	for (i=0; i<size; i += FMAP_SEARCH_STRIDE, ptr += FMAP_SEARCH_STRIDE) {
+	size_t lim = size - sizeof(FmapHeader);
+	for (i = 0;
+	     i <= lim;
+	     i += FMAP_SEARCH_STRIDE, ptr += FMAP_SEARCH_STRIDE) {
 		if (0 != memcmp(ptr, FMAP_SIGNATURE, FMAP_SIGNATURE_SIZE))
 			continue;
 		fmap_header = (FmapHeader *)ptr;
diff --git a/host/lib/include/host_key.h b/host/lib/include/host_key.h
index 85aef244..9f98ccc3 100644
--- a/host/lib/include/host_key.h
+++ b/host/lib/include/host_key.h
@@ -9,7 +9,6 @@
 #define VBOOT_REFERENCE_HOST_KEY_H_
 
 #include "cryptolib.h"
-#include "utility.h"
 #include "vboot_struct.h"