sw/stm32 - Cryptech HSM on STM-32 ARM processor

diff options

author	Fredrik Thulin <fredrik@thulin.net>	2017-03-23 19:45:35 +0100
committer	Fredrik Thulin <fredrik@thulin.net>	2017-03-23 19:45:35 +0100
commit	4344fa71c11453bb316ea990b270fb019e9bfa36 (patch)
tree	e5c0abeb1826eb2d29999a600916b2207614175d /Makefile
parent	700ba6a4add565a95ef37530ac90f6dbd8117037 (diff)

Check CRC32 of data received from host.ft-crc32

Diffstat (limited to 'Makefile')

0 files changed, 0 insertions, 0 deletions

rt out the redeclaration of HAL_OK with Rob's help.' href='/sw/libhal/commit/ks_flash.c?h=auto_zeroise&id=ee89d2e18511332b3a75b370f26d40733a02f7a3'>ee89d2e

6
7

40
41

42
43

45
46

47
48

50
51

58
59
60

61
62

67
68

103
104

142
143
144

152
153

167
168

169
170

192
193
194

195
196
197

199
200

208
209

210
211

218
219
220

228
229
230

260
261
262

264
265

275
276
277

289
290

293
294
295

311
312

316
317

324
325

326
327

332
333

336
337
338

345
346

373
374
375

391
392

394
395
396

397
398

404
405

413
414

417
418

419
420

423
424
425

427
428
429

434
435

445
446

450
451
452

453
454
455

467
468
469

481
482
483

498
499

554
555

566
567
568

570
571

572
573
574

582
583

584
585
586

602
603

604
605

619
620

622
623

637
638

647
648
649

650
651
652

653
654

666
667

745
746
747

749
750

752
753
754

757
758

779
780

783
784

843
844

850
851
852

853
854

879
880
881

884
885
886

889
890

929
930
931

933
934

937
938

941
942

974
975

1022
1023

1024
1025

1057
1058
1059

1073
1074

1078
1079

1082
1083

1084
1085

1086
1087

1088
1089

1090
1091

1117
1118

1119
1120
1121

1146
1147

1179
1180

1182
1183

1214
1215

1526
1527
1528

1529
1530
1531

1657
1658

1660
1661
1662

1663
1664

1673
1674

1682
1683

1686
1687

1690
1691

1694
1695

1696
1697

1716
1717
1718

1722
1723
1724

1733
1734

1743
1744

1745
1746
1747

1749
1750

1752
1753

1762
1763

1765
1766

1769
1770

1773
1774
1775

1792
1793
1794

1796
1797

1799
1800
1801

1802
1803
1804

1806
1807

1811
1812

1813
1814

1825
1826

1828
1829

1849
1850

1851
1852

/*
 * ks_flash.c
 * ----------
 * Keystore implementation in flash memory.
 *
 * Authors: Rob Austein, Fredrik Thulin
 * Copyright (c) 2015-2016, NORDUnet A/S All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * - Neither the name of the NORDUnet nor the names of its contributors may
 *   be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stddef.h>
#include <string.h>
#include <assert.h>

#include "hal.h"
#include "hal_internal.h"

#include "last_gasp_pin_internal.h"

#define HAL_OK CMIS_HAL_OK
#include "stm-keystore.h"
#undef HAL_OK

/*
 * Known block states.
 *
 * C does not guarantee any particular representation for enums, so
 * including enums directly in the block header isn't safe.  Instead,
 * we use an access method which casts when reading from the header.
 * Writing to the header isn't a problem, because C does guarantee
 * that enum is compatible with *some* integer type, it just doesn't
 * specify which one.
 */

typedef enum {
  BLOCK_TYPE_ERASED  = 0xFF, /* Pristine erased block (candidate for reuse) */
  BLOCK_TYPE_ZEROED  = 0x00, /* Zeroed block (recently used) */
  BLOCK_TYPE_KEY     = 0x55, /* Block contains key material */
  BLOCK_TYPE_ATTR    = 0x66, /* Block contains key attributes (overflow from key block) */
  BLOCK_TYPE_PIN     = 0xAA, /* Block contains PINs */
  BLOCK_TYPE_UNKNOWN = -1,   /* Internal code for "I have no clue what this is" */
} flash_block_type_t;

/*
 * Block status.
 */

typedef enum {
  BLOCK_STATUS_LIVE      = 0x66, /* This is a live flash block */
  BLOCK_STATUS_TOMBSTONE = 0x44, /* This is a tombstone left behind during an update  */
  BLOCK_STATUS_UNKNOWN   = -1,   /* Internal code for "I have no clue what this is" */
} flash_block_status_t;

/*
 * Common header for all flash block types.
 * A few of these fields are deliberately omitted from the CRC.
 */

typedef struct {
  uint8_t               block_type;
  uint8_t               block_status;
  uint8_t               total_chunks;
  uint8_t               this_chunk;
  hal_crc32_t           crc;
} flash_block_header_t;

/*
 * Key block.  Tail end of "der" field (after der_len) used for attributes.
 */

typedef struct {
  flash_block_header_t  header;
  hal_uuid_t            name;
  hal_key_type_t        type;
  hal_curve_name_t      curve;
  hal_key_flags_t       flags;
  size_t                der_len;
  unsigned              attributes_len;
  uint8_t               der[];  /* Must be last field -- C99 "flexible array member" */
} flash_key_block_t;

#define SIZEOF_FLASH_KEY_BLOCK_DER \
  (KEYSTORE_SUBSECTOR_SIZE - offsetof(flash_key_block_t, der))

/*
 * Key attribute overflow block (attributes which don't fit in der field of key block).
 */

typedef struct {
  flash_block_header_t  header;
  hal_uuid_t            name;
  unsigned              attributes_len;
  uint8_t               attributes[]; /* Must be last field -- C99 "flexible array member" */
} flash_attributes_block_t;

#define SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES \
  (KEYSTORE_SUBSECTOR_SIZE - offsetof(flash_attributes_block_t, attributes))

/*
 * PIN block.  Also includes space for backing up the KEK when
 * HAL_MKM_FLASH_BACKUP_KLUDGE is enabled.
 */

typedef struct {
  flash_block_header_t  header;
  hal_ks_pin_t          wheel_pin;
  hal_ks_pin_t          so_pin;
  hal_ks_pin_t          user_pin;
#if HAL_MKM_FLASH_BACKUP_KLUDGE
  uint32_t              kek_set;
  uint8_t               kek[KEK_LENGTH];
#endif
} flash_pin_block_t;

#define FLASH_KEK_SET   0x33333333

/*
 * One flash block.
 */

typedef union {
  uint8_t                       bytes[KEYSTORE_SUBSECTOR_SIZE];
  flash_block_header_t          header;
  flash_key_block_t             key;
  flash_attributes_block_t      attr;
  flash_pin_block_t             pin;
} flash_block_t;

/*
 * In-memory cache.
 */

typedef struct {
  unsigned            blockno;
  uint32_t            lru;
  flash_block_t       block;
} cache_block_t;

/*
 * In-memory database.
 *
 * The top-level structure is a static variable; the arrays are allocated at runtime
 * using hal_allocate_static_memory() because they can get kind of large.
 */

#ifndef KS_FLASH_CACHE_SIZE
#define KS_FLASH_CACHE_SIZE 4
#endif

#define NUM_FLASH_BLOCKS        KEYSTORE_NUM_SUBSECTORS

typedef struct {
  hal_ks_t              ks;                  /* Must be first (C "subclassing") */
  hal_ks_index_t        ksi;
  hal_ks_pin_t          wheel_pin;
  hal_ks_pin_t          so_pin;
  hal_ks_pin_t          user_pin;
  uint32_t              cache_lru;
  cache_block_t         *cache;
} db_t;

/*
 * PIN block gets the all-zeros UUID, which will never be returned by
 * the UUID generation code (by definition -- it's not a version 4 UUID).
 */

const static hal_uuid_t pin_uuid = {{0}};

/*
 * The in-memory database structure itself is small, but the arrays it
 * points to are large enough that they come from SDRAM allocated at
 * startup.
 */

static db_t db;

/*
 * Type safe casts.
 */

static inline flash_block_type_t block_get_type(const flash_block_t * const block)
{
  assert(block != NULL);
  return (flash_block_type_t) block->header.block_type;
}

static inline flash_block_status_t block_get_status(const flash_block_t * const block)
{
  assert(block != NULL);
  return (flash_block_status_t) block->header.block_status;
}

/*
 * Pick unused or least-recently-used slot in our in-memory cache.
 *
 * Updating lru values is caller's problem: if caller is using a cache
 * slot as a temporary buffer and there's no point in caching the
 * result, leave the lru values alone and the right thing will happen.
 */

static inline flash_block_t *cache_pick_lru(void)
{
  uint32_t best_delta = 0;
  int      best_index = 0;

  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++) {

    if (db.cache[i].blockno == ~0)
      return &db.cache[i].block;

    const uint32_t delta = db.cache_lru - db.cache[i].lru;
    if (delta > best_delta) {
      best_delta = delta;
      best_index = i;
    }

  }

  db.cache[best_index].blockno = ~0;
  return &db.cache[best_index].block;
}

/*
 * Find a block in our in-memory cache; return block or NULL if not present.
 */

static inline flash_block_t *cache_find_block(const unsigned blockno)
{
  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++)
    if (db.cache[i].blockno == blockno)
      return &db.cache[i].block;
  return NULL;
}

/*
 * Mark a block in our in-memory cache as being in current use.
 */

static inline void cache_mark_used(const flash_block_t * const block, const unsigned blockno)
{
  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++) {
    if (&db.cache[i].block == block) {
      db.cache[i].blockno = blockno;
      db.cache[i].lru = ++db.cache_lru;
      return;
    }
  }
}

/*
 * Release a block from the in-memory cache.
 */

static inline void cache_release(const flash_block_t * const block)
{
  if (block != NULL)
    cache_mark_used(block, ~0);
}

/*
 * Generate CRC-32 for a block.
 *
 * This function needs to understand the structure of
 * flash_block_header_t, so that it can skip over fields that
 * shouldn't be included in the CRC.
 */

static hal_crc32_t calculate_block_crc(const flash_block_t * const block)
{
  assert(block != NULL);

  hal_crc32_t crc = hal_crc32_init();

  crc = hal_crc32_update(crc, &block->header.block_type,
                         sizeof(block->header.block_type));

  crc = hal_crc32_update(crc, &block->header.total_chunks,
                         sizeof(block->header.total_chunks));

  crc = hal_crc32_update(crc, &block->header.this_chunk,
                         sizeof(block->header.this_chunk));

  crc = hal_crc32_update(crc, block->bytes + sizeof(flash_block_header_t),
                         sizeof(*block) - sizeof(flash_block_header_t));

  return hal_crc32_finalize(crc);
}

/*
 * Calculate block offset.
 */

static inline uint32_t block_offset(const unsigned blockno)
{
  return blockno * KEYSTORE_SUBSECTOR_SIZE;
}

/*
 * Read a flash block.
 *
 * Flash read on the Alpha is slow enough that it pays to check the
 * first page before reading the rest of the block.
 */

static hal_error_t block_read(const unsigned blockno, flash_block_t *block)
{
  if (block == NULL || blockno >= NUM_FLASH_BLOCKS || sizeof(*block) != KEYSTORE_SUBSECTOR_SIZE)
    return HAL_ERROR_IMPOSSIBLE;

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(block_offset(blockno),
                         block->bytes,
                         KEYSTORE_PAGE_SIZE) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  switch (block_get_type(block)) {
  case BLOCK_TYPE_ERASED:
  case BLOCK_TYPE_ZEROED:
    return HAL_OK;
  case BLOCK_TYPE_KEY:
  case BLOCK_TYPE_PIN:
  case BLOCK_TYPE_ATTR:
    break;
  default:
    return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
  }

  switch (block_get_status(block)) {
  case BLOCK_STATUS_LIVE:
  case BLOCK_STATUS_TOMBSTONE:
    break;
  default:
    return HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE;
  }

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(block_offset(blockno) + KEYSTORE_PAGE_SIZE,
                         block->bytes + KEYSTORE_PAGE_SIZE,
                         sizeof(*block) - KEYSTORE_PAGE_SIZE) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  if (calculate_block_crc(block) != block->header.crc)
    return HAL_ERROR_KEYSTORE_BAD_CRC;

  return HAL_OK;
}

/*
 * Read a block using the cache.  Marking the block as used is left
 * for the caller, so we can avoid blowing out the cache when we
 * perform a ks_match() operation.
 */

static hal_error_t block_read_cached(const unsigned blockno, flash_block_t **block)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if ((*block = cache_find_block(blockno)) != NULL)
    return HAL_OK;

  if ((*block = cache_pick_lru()) == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  return block_read(blockno, *block);
}

/*
 * Convert a live block into a tombstone.  Caller is responsible for
 * making sure that the block being converted is valid; since we don't
 * need to update the CRC for this, we just modify the first page.
 */

static hal_error_t block_deprecate(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t page[KEYSTORE_PAGE_SIZE];
  flash_block_header_t *header = (void *) page;
  uint32_t offset = block_offset(blockno);

  /* Sigh, magic numeric return codes */
  if (keystore_read_data(offset, page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  header->block_status = BLOCK_STATUS_TOMBSTONE;

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(offset, page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Zero (not erase) a flash block.  Just need to zero the first page.
 */

static hal_error_t block_zero(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t page[KEYSTORE_PAGE_SIZE] = {0};

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(block_offset(blockno), page, sizeof(page)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Erase a flash block.  Also see block_erase_maybe(), below.
 */

static hal_error_t block_erase(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  /* Sigh, magic numeric return codes */
  if (keystore_erase_subsectors(blockno, blockno) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Erase a flash block if it hasn't already been erased.
 * May not be necessary, trying to avoid unnecessary wear.
 *
 * Unclear whether there's any sane reason why this needs to be
 * constant time, given how slow erasure is.  But side channel attacks
 * can be tricky things, and it's theoretically possible that we could
 * leak information about, eg, key length, so we do constant time.
 */

static hal_error_t block_erase_maybe(const unsigned blockno)
{
  if (blockno >= NUM_FLASH_BLOCKS)
    return HAL_ERROR_IMPOSSIBLE;

  uint8_t mask = 0xFF;

  for (uint32_t a = block_offset(blockno); a < block_offset(blockno + 1); a += KEYSTORE_PAGE_SIZE) {
    uint8_t page[KEYSTORE_PAGE_SIZE];
    if (keystore_read_data(a, page, sizeof(page)) != 1)
      return HAL_ERROR_KEYSTORE_ACCESS;
    for (int i = 0; i < KEYSTORE_PAGE_SIZE; i++)
      mask &= page[i];
  }

  return mask == 0xFF ? HAL_OK : block_erase(blockno);
}

/*
 * Write a flash block, calculating CRC when appropriate.
 */

static hal_error_t block_write(const unsigned blockno, flash_block_t *block)
{
  if (block == NULL || blockno >= NUM_FLASH_BLOCKS || sizeof(*block) != KEYSTORE_SUBSECTOR_SIZE)
    return HAL_ERROR_IMPOSSIBLE;

  hal_error_t err = block_erase_maybe(blockno);

  if (err != HAL_OK)
    return err;

  switch (block_get_type(block)) {
  case BLOCK_TYPE_KEY:
  case BLOCK_TYPE_PIN:
  case BLOCK_TYPE_ATTR:
    block->header.crc = calculate_block_crc(block);
    break;
  default:
    break;
  }

  /* Sigh, magic numeric return codes */
  if (keystore_write_data(block_offset(blockno), block->bytes, sizeof(*block)) != 1)
    return HAL_ERROR_KEYSTORE_ACCESS;

  return HAL_OK;
}

/*
 * Update one flash block, including zombie jamboree.
 */

static hal_error_t block_update(const unsigned b1, flash_block_t *block,
                                const hal_uuid_t * const uuid, const unsigned chunk, int *hint)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if (db.ksi.used == db.ksi.size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  cache_release(block);

  hal_error_t err;
  unsigned b2;

  if ((err = block_deprecate(b1))                                       != HAL_OK ||
      (err = hal_ks_index_replace(&db.ksi, uuid, chunk, &b2, hint))     != HAL_OK ||
      (err = block_write(b2, block))                                    != HAL_OK ||
      (err = block_zero(b1))                                            != HAL_OK)
    return err;

  cache_mark_used(block, b2);

  return block_erase_maybe(db.ksi.index[db.ksi.used]);
}

/*
 * Forward reference.
 */

static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block);

/*
 * Initialize keystore.  This includes various tricky bits, some of
 * which attempt to preserve the free list ordering across reboots, to
 * improve our simplistic attempt at wear leveling, others attempt to
 * recover from unclean shutdown.
 */

static inline void *gnaw(uint8_t **mem, size_t *len, const size_t size)
{
  if (mem == NULL || *mem == NULL || len == NULL || size > *len)
    return NULL;
  void *ret = *mem;
  *mem += size;
  *len -= size;
  return ret;
}

static hal_error_t ks_init(const hal_ks_driver_t * const driver)
{
  /*
   * Initialize the in-memory database.
   */

  size_t len = (sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS +
                sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS +
                sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);

  uint8_t *mem = hal_allocate_static_memory(len);

  if (mem == NULL)
    return HAL_ERROR_ALLOCATION_FAILURE;

  memset(&db, 0, sizeof(db));
  memset(mem, 0, len);

  db.ksi.index = gnaw(&mem, &len, sizeof(*db.ksi.index) * NUM_FLASH_BLOCKS);
  db.ksi.names = gnaw(&mem, &len, sizeof(*db.ksi.names) * NUM_FLASH_BLOCKS);
  db.cache     = gnaw(&mem, &len, sizeof(*db.cache)     * KS_FLASH_CACHE_SIZE);
  db.ksi.size  = NUM_FLASH_BLOCKS;
  db.ksi.used  = 0;

  if (db.ksi.index == NULL || db.ksi.names == NULL || db.cache == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++)
    db.cache[i].blockno = ~0;

  /*
   * Scan existing content of flash to figure out what we've got.
   * This gets a bit involved due to the need to recover from things
   * like power failures at inconvenient times.
   */

  flash_block_type_t   block_types[NUM_FLASH_BLOCKS];
  flash_block_status_t block_status[NUM_FLASH_BLOCKS];
  flash_block_t *block = cache_pick_lru();
  int first_erased = -1;
  hal_error_t err;
  uint16_t n = 0;

  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  for (int i = 0; i < NUM_FLASH_BLOCKS; i++) {

    /*
     * Read one block.  If the CRC is bad or the block type is
     * unknown, it's old data we don't understand, something we were
     * writing when we crashed, or bad flash; in any of these cases,
     * we want the block to ends up near the end of the free list.
     */

    err = block_read(i, block);

    if (err == HAL_ERROR_KEYSTORE_BAD_CRC || err == HAL_ERROR_KEYSTORE_BAD_BLOCK_TYPE)
      block_types[i] = BLOCK_TYPE_UNKNOWN;

    else if (err == HAL_OK)
      block_types[i] = block_get_type(block);

    else
      return err;

    switch (block_types[i]) {
    case BLOCK_TYPE_KEY:
    case BLOCK_TYPE_PIN:
    case BLOCK_TYPE_ATTR:
      block_status[i] = block_get_status(block);
      break;
    default:
      block_status[i] = BLOCK_STATUS_UNKNOWN;
    }

    /*
     * First erased block we see is head of the free list.
     */

    if (block_types[i] == BLOCK_TYPE_ERASED && first_erased < 0)
      first_erased = i;

    /*
     * If it's a valid data block, include it in the index.  We remove
     * tombstones (if any) below, for now it's easiest to include them
     * in the index, so we can look them up by name if we must.
     */

    const hal_uuid_t *uuid = NULL;

    switch (block_types[i]) {
    case BLOCK_TYPE_KEY:        uuid = &block->key.name;        break;
    case BLOCK_TYPE_ATTR:       uuid = &block->attr.name;       break;
    case BLOCK_TYPE_PIN:        uuid = &pin_uuid;               break;
    default:                    /* Keep GCC happy */            break;
    }

    if (uuid != NULL) {
      db.ksi.names[i].name = *uuid;
      db.ksi.names[i].chunk = block->header.this_chunk;
      db.ksi.index[n++] = i;
    }
  }

  db.ksi.used = n;

  assert(db.ksi.used <= db.ksi.size);

  /*
   * At this point we've built the (unsorted) index from all the valid
   * blocks.  Now we need to insert free and unrecognized blocks into
   * the free list in our preferred order.  It's possible that there's
   * a better way to do this than linear scan, but this is just
   * integer comparisons in a fairly small data set, so it's probably
   * not worth trying to optimize.
   */

  if (n < db.ksi.size)
    for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_ERASED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = first_erased; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_ZEROED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = 0; i < first_erased; i++)
      if (block_types[i] == BLOCK_TYPE_ZEROED)
        db.ksi.index[n++] = i;

  if (n < db.ksi.size)
    for (int i = 0; i < NUM_FLASH_BLOCKS; i++)
      if (block_types[i] == BLOCK_TYPE_UNKNOWN)
        db.ksi.index[n++] = i;

  assert(n == db.ksi.size);

  /*
   * Initialize the index.
   */

  if ((err = hal_ks_index_setup(&db.ksi)) != HAL_OK)
    return err;

  /*
   * We might want to call hal_ks_index_fsck() here, if we can figure
   * out some safe set of recovery actions we can take.
   */

  /*
   * Deal with tombstones.  These are blocks left behind when
   * something bad (like a power failure) happened while we updating.
   * The sequence of operations while updating is designed so that,
   * barring a bug or a hardware failure, we should never lose data.
   *
   * For any tombstone we find, we start by looking for all the blocks
   * with a matching UUID, then see what valid sequences we can
   * construct from what we found.
   *
   * If we can construct a valid sequence of live blocks, the complete
   * update was written out, and we just need to zero the tombstones.
   *
   * Otherwise, if we can construct a complete sequence of tombstone
   * blocks, the update failed before it was completely written, so we
   * have to zero the incomplete sequence of live blocks then restore
   * from the tombstones.
   *
   * Otherwise, if the live and tombstone blocks taken together form a
   * valid sequence, the update failed while deprecating the old live
   * blocks, and the update itself was not written, so we need to
   * restore the tombstones and leave the live blocks alone.
   *
   * If none of the above applies, we don't understand what happened,
   * which is a symptom of either a bug or a hardware failure more
   * serious than simple loss of power or reboot at an inconvenient
   * time, so we error out to avoid accidental loss of data.
   */

  for (int i = 0; i < NUM_FLASH_BLOCKS; i++) {

    if (block_status[i] != BLOCK_STATUS_TOMBSTONE)
      continue;

    hal_uuid_t name = db.ksi.names[i].name;
    unsigned n_blocks;
    int where = -1;

    if ((err = hal_ks_index_find_range(&db.ksi, &name, 0, &n_blocks, NULL, &where, 0)) != HAL_OK)
      return err;

    while (where > 0 && !hal_uuid_cmp(&name, &db.ksi.names[db.ksi.index[where - 1]].name)) {
      where--;
      n_blocks++;
    }

    int live_ok = 1, tomb_ok = 1, join_ok = 1;
    unsigned n_live = 0, n_tomb = 0;
    unsigned i_live = 0, i_tomb = 0;

    for (int j = 0; j < n_blocks; j++) {
      unsigned b = db.ksi.index[where + j];
      switch (block_status[b]) {
      case BLOCK_STATUS_LIVE:           n_live++;       break;
      case BLOCK_STATUS_TOMBSTONE:      n_tomb++;       break;
      default:                          return HAL_ERROR_IMPOSSIBLE;
      }
    }

    uint16_t live_blocks[n_live], tomb_blocks[n_tomb];

    for (int j = 0; j < n_blocks; j++) {
      unsigned b = db.ksi.index[where + j];

      if ((err = block_read(b, block)) != HAL_OK)
        return err;

      join_ok &= block->header.this_chunk == j && block->header.total_chunks == n_blocks;

      switch (block_status[b]) {
      case BLOCK_STATUS_LIVE:
        live_blocks[i_live] = b;
        live_ok &= block->header.this_chunk == i_live++ && block->header.total_chunks == n_live;
        break;
      case BLOCK_STATUS_TOMBSTONE:
        tomb_blocks[i_tomb] = b;
        tomb_ok &= block->header.this_chunk == i_tomb++ && block->header.total_chunks == n_tomb;
        break;
      default:
        return HAL_ERROR_IMPOSSIBLE;
      }
    }

    if (!live_ok && !tomb_ok && !join_ok)
      return HAL_ERROR_KEYSTORE_LOST_DATA;

    if (live_ok) {
      for (int j = 0; j < n_tomb; j++) {
        const unsigned b = tomb_blocks[j];
        if ((err = block_zero(b)) != HAL_OK)
          return err;
        block_types[b]  = BLOCK_TYPE_ZEROED;
        block_status[b] = BLOCK_STATUS_UNKNOWN;
      }
    }

    else if (tomb_ok) {
      for (int j = 0; j < n_live; j++) {
        const unsigned b = live_blocks[j];
        if ((err = block_zero(b)) != HAL_OK)
          return err;
        block_types[b]  = BLOCK_TYPE_ZEROED;
        block_status[b] = BLOCK_STATUS_UNKNOWN;
      }
    }

    if (live_ok) {
      memcpy(&db.ksi.index[where], live_blocks, n_live * sizeof(*db.ksi.index));
      memmove(&db.ksi.index[where + n_live], &db.ksi.index[where + n_blocks],
              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
      memcpy(&db.ksi.index[db.ksi.size - n_tomb], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
      db.ksi.used -= n_tomb;
      n_blocks = n_live;
    }

    else if (tomb_ok) {
      memcpy(&db.ksi.index[where], tomb_blocks, n_tomb * sizeof(*db.ksi.index));
      memmove(&db.ksi.index[where + n_tomb], &db.ksi.index[where + n_blocks],
              (db.ksi.size - where - n_blocks) * sizeof(*db.ksi.index));
      memcpy(&db.ksi.index[db.ksi.size - n_live], live_blocks, n_live * sizeof(*db.ksi.index));
      db.ksi.used -= n_live;
      n_blocks = n_tomb;
    }

    for (int j = 0; j < n_blocks; j++) {
      int hint = where + j;
      unsigned b1 = db.ksi.index[hint], b2;
      if (block_status[b1] != BLOCK_STATUS_TOMBSTONE)
        continue;
      if ((err = block_read(b1, block)) != HAL_OK)
        return err;
      block->header.block_status = BLOCK_STATUS_LIVE;
      if ((err = hal_ks_index_replace(&db.ksi, &name, j, &b2, &hint)) != HAL_OK ||
          (err = block_write(b2, block)) != HAL_OK)
        return err;
      block_types[b1]  = BLOCK_TYPE_ZEROED;
      block_status[b1] = BLOCK_STATUS_UNKNOWN;
      block_status[b2] = BLOCK_STATUS_LIVE;
    }
  }

  err = fetch_pin_block(NULL, &block);

  if (err == HAL_OK) {
    db.wheel_pin = block->pin.wheel_pin;
    db.so_pin    = block->pin.so_pin;
    db.user_pin  = block->pin.user_pin;
  }

  else if (err != HAL_ERROR_KEY_NOT_FOUND)
    return err;

  else {
    /*
     * We found no PIN block, so create one, with the user and so PINs
     * cleared and the wheel PIN set to the last-gasp value.  The
     * last-gasp WHEEL PIN is a terrible answer, but we need some kind
     * of bootstrapping mechanism when all else fails.  If you have a
     * better suggestion, we'd love to hear it.
     */

    unsigned b;

    memset(block, 0xFF, sizeof(*block));

    block->header.block_type   = BLOCK_TYPE_PIN;
    block->header.block_status = BLOCK_STATUS_LIVE;
    block->header.total_chunks = 1;
    block->header.this_chunk   = 0;

    block->pin.wheel_pin = db.wheel_pin = hal_last_gasp_pin;
    block->pin.so_pin    = db.so_pin;
    block->pin.user_pin  = db.user_pin;

    if ((err = hal_ks_index_add(&db.ksi, &pin_uuid, 0, &b, NULL)) != HAL_OK)
      return err;

    cache_mark_used(block, b);

    err = block_write(b, block);

    cache_release(block);

    if (err != HAL_OK)
      return err;
  }

  /*
   * Erase first block on free list if it's not already erased.
   */

  if (db.ksi.used < db.ksi.size &&
      (err = block_erase_maybe(db.ksi.index[db.ksi.used])) != HAL_OK)
    return err;

  /*
   * And we're finally done.
   */

  db.ks.driver = driver;

  return HAL_OK;
}

static hal_error_t ks_shutdown(const hal_ks_driver_t * const driver)
{
  if (db.ks.driver != driver)
    return HAL_ERROR_KEYSTORE_ACCESS;
  return HAL_OK;
}

static hal_error_t ks_open(const hal_ks_driver_t * const driver,
                                    hal_ks_t **ks)
{
  if (driver != hal_ks_token_driver || ks == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  *ks = &db.ks;
  return HAL_OK;
}

static hal_error_t ks_close(hal_ks_t *ks)
{
  if (ks != NULL && ks != &db.ks)
    return HAL_ERROR_BAD_ARGUMENTS;

  return HAL_OK;
}

static inline int acceptable_key_type(const hal_key_type_t type)
{
  switch (type) {
  case HAL_KEY_TYPE_RSA_PRIVATE:
  case HAL_KEY_TYPE_EC_PRIVATE:
  case HAL_KEY_TYPE_RSA_PUBLIC:
  case HAL_KEY_TYPE_EC_PUBLIC:
    return 1;
  default:
    return 0;
  }
}

static hal_error_t ks_store(hal_ks_t *ks,
                            hal_pkey_slot_t *slot,
                            const uint8_t * const der, const size_t der_len)
{
  if (ks != &db.ks || slot == NULL || der == NULL || der_len == 0 || !acceptable_key_type(slot->type))
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block = cache_pick_lru();
  flash_key_block_t *k = &block->key;
  uint8_t kek[KEK_LENGTH];
  size_t kek_len;
  hal_error_t err;
  unsigned b;

  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if ((err = hal_ks_index_add(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK)
    return err;

  cache_mark_used(block, b);

  memset(block, 0xFF, sizeof(*block));

  block->header.block_type   = BLOCK_TYPE_KEY;
  block->header.block_status = BLOCK_STATUS_LIVE;
  block->header.total_chunks = 1;
  block->header.this_chunk   = 0;

  k->name    = slot->name;
  k->type    = slot->type;
  k->curve   = slot->curve;
  k->flags   = slot->flags;
  k->der_len = SIZEOF_FLASH_KEY_BLOCK_DER;
  k->attributes_len = 0;

  if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
    err = hal_aes_keywrap(NULL, kek, kek_len, der, der_len, k->der, &k->der_len);

  memset(kek, 0, sizeof(kek));

  if (err == HAL_OK &&
      (err = block_write(b, block)) == HAL_OK)
    return HAL_OK;

  memset(block, 0, sizeof(*block));
  cache_release(block);
  (void) hal_ks_index_delete(&db.ksi, &slot->name, 0, NULL, &slot->hint);
  return err;
}

static hal_error_t ks_fetch(hal_ks_t *ks,
                            hal_pkey_slot_t *slot,
                            uint8_t *der, size_t *der_len, const size_t der_max)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = hal_ks_index_find(&db.ksi, &slot->name, 0, &b, &slot->hint)) != HAL_OK ||
      (err = block_read_cached(b, &block))                                != HAL_OK)
    return err;

  if (block_get_type(block) != BLOCK_TYPE_KEY)
    return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */

  cache_mark_used(block, b);

  flash_key_block_t *k = &block->key;

  slot->type  = k->type;
  slot->curve = k->curve;
  slot->flags = k->flags;

  if (der == NULL && der_len != NULL)
    *der_len = k->der_len;

  if (der != NULL) {

    uint8_t kek[KEK_LENGTH];
    size_t kek_len, der_len_;
    hal_error_t err;

    if (der_len == NULL)
      der_len = &der_len_;

    *der_len = der_max;

    if ((err = hal_mkm_get_kek(kek, &kek_len, sizeof(kek))) == HAL_OK)
      err = hal_aes_keyunwrap(NULL, kek, kek_len, k->der, k->der_len, der, der_len);

    memset(kek, 0, sizeof(kek));

    if (err != HAL_OK)
      return err;
  }

  return HAL_OK;
}

static hal_error_t ks_delete(hal_ks_t *ks,
                             hal_pkey_slot_t *slot)
{
  if (ks != &db.ks || slot == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  hal_error_t err;
  unsigned n;

  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, 0, &n, NULL, &slot->hint)) != HAL_OK)
    return err;

  unsigned b[n];

  if ((err = hal_ks_index_delete_range(&db.ksi, &slot->name, n, NULL, b, &slot->hint)) != HAL_OK)
    return err;

  for (int i = 0; i < n; i++)
    cache_release(cache_find_block(b[i]));

  for (int i = 0; i < n; i++)
    if ((err = block_zero(b[i])) != HAL_OK)
      return err;

  return block_erase_maybe(db.ksi.index[db.ksi.used]);
}

static inline hal_error_t locate_attributes(flash_block_t *block, const unsigned chunk,
                                            uint8_t **bytes, size_t *bytes_len,
                                            unsigned **attrs_len)
{
  if (block == NULL || bytes == NULL || bytes_len == NULL || attrs_len == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  if (chunk == 0) {
    if (block_get_type(block) != BLOCK_TYPE_KEY)
      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
    *attrs_len = &block->key.attributes_len;
    *bytes = block->key.der + block->key.der_len;
    *bytes_len = SIZEOF_FLASH_KEY_BLOCK_DER - block->key.der_len;
  }

  else {
    if (block_get_type(block) != BLOCK_TYPE_ATTR)
      return HAL_ERROR_KEYSTORE_WRONG_BLOCK_TYPE; /* HAL_ERROR_KEY_NOT_FOUND */
    *attrs_len = &block->attr.attributes_len;
    *bytes = block->attr.attributes;
    *bytes_len = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
  }

  return HAL_OK;
}

static hal_error_t ks_match(hal_ks_t *ks,
                            const hal_client_handle_t client,
                            const hal_session_handle_t session,
                            const hal_key_type_t type,
                            const hal_curve_name_t curve,
                            const hal_key_flags_t flags,
                            const hal_rpc_pkey_attribute_t *attributes,
                            const unsigned attributes_len,
                            hal_uuid_t *result,
                            unsigned *result_len,
                            const unsigned result_max,
                            const hal_uuid_t * const previous_uuid)
{
  if (ks == NULL || (attributes == NULL && attributes_len > 0) ||
      result == NULL || result_len == NULL || previous_uuid == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  uint8_t need_attr[attributes_len > 0 ? attributes_len : 1];
  flash_block_t *block;
  int possible = 0;
  hal_error_t err;
  int i = -1;

  *result_len = 0;

  err = hal_ks_index_find(&db.ksi, previous_uuid, 0, NULL, &i);

  if (err == HAL_ERROR_KEY_NOT_FOUND)
    i--;
  else if (err != HAL_OK)
    return err;

  while (*result_len < result_max && ++i < db.ksi.used) {

    unsigned b = db.ksi.index[i];

    if (db.ksi.names[b].chunk == 0)
      possible = 1;

    if (!possible)
      continue;

    if ((err = block_read_cached(b, &block)) != HAL_OK)
      return err;

    if (db.ksi.names[b].chunk == 0) {
      memset(need_attr, 1, sizeof(need_attr));
      possible = ((type == HAL_KEY_TYPE_NONE || type  == block->key.type) &&
                  (curve == HAL_CURVE_NONE   || curve == block->key.curve));
    }

    if (!possible)
      continue;

    if (attributes_len > 0) {
      uint8_t *bytes = NULL;
      size_t bytes_len = 0;
      unsigned *attrs_len;

      if ((err = locate_attributes(block, db.ksi.names[b].chunk,
                                   &bytes, &bytes_len, &attrs_len)) != HAL_OK)
        return err;

      if (*attrs_len > 0) {
        hal_rpc_pkey_attribute_t attrs[*attrs_len];

        if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
          return err;

        for (int j = 0; possible && j < attributes_len; j++) {

          if (!need_attr[j])
            continue;

          for (hal_rpc_pkey_attribute_t *a = attrs; a < attrs + *attrs_len; a++) {
            if (a->type != attributes[j].type)
              continue;
            need_attr[j] = 0;
            possible = (a->length == attributes[j].length &&
                        !memcmp(a->value, attributes[j].value, a->length));
            break;
          }
        }
      }
    }

    if (!possible)
      continue;

    if (attributes_len > 0 && memchr(need_attr, 1, sizeof(need_attr)) != NULL)
      continue;

    result[*result_len] = db.ksi.names[b].name;
    ++*result_len;
    possible = 0;
  }

  return HAL_OK;
}

static  hal_error_t ks_set_attributes(hal_ks_t *ks,
                                      hal_pkey_slot_t *slot,
                                      const hal_rpc_pkey_attribute_t *attributes,
                                      const unsigned attributes_len)
{
#warning This function is much too long
  // Probably needs to be broken up into multiple sub-functions, or at least
  // into discrete blocks to scope most of the variables, but let's finish
  // writing the icky version before polishing the chrome.

  if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0)
    return HAL_ERROR_BAD_ARGUMENTS;

  /*
   * Try to add new attribute as a single-block update.
   */

  unsigned updated_attributes_len = attributes_len;
  flash_block_t *block;
  unsigned chunk = 0;
  hal_error_t err;
  unsigned b;

  do {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    cache_mark_used(block, b);

    if (chunk == 0)
      slot->hint = hint;

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    updated_attributes_len += *attrs_len;

    hal_rpc_pkey_attribute_t attrs[*attrs_len + attributes_len];
    size_t total;

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
      return err;

    for (int i = 0; err == HAL_OK && i < attributes_len; i++) {
      if (attributes[i].length == 0)
        err = hal_ks_attribute_delete(bytes, bytes_len, attrs, attrs_len, &total,
                                      attributes[i].type);
      else
        err = hal_ks_attribute_insert(bytes, bytes_len, attrs, attrs_len, &total,
                                      attributes[i].type,
                                      attributes[i].value,
                                      attributes[i].length);
      if (err != HAL_OK)
        cache_release(block);
    }

    if (err == HAL_ERROR_RESULT_TOO_LONG)
      continue;

    if (err != HAL_OK)
      return err;

    return block_update(b, block, &slot->name, chunk, &hint);

  } while (++chunk < block->header.total_chunks);

  /*
   * If we get here, we have to add a new block, which requires
   * rewriting all the others to bump the total_blocks count.  We need
   * to keep track of all the old chunks so we can zero them at the
   * end, and because we can't zero them until we've written out the
   * new chunks, we need enough free blocks for the entire new object.
   *
   * Calculating all of this is extremely tedious, but flash writes
   * are so much more expensive than anything else we do here that
   * it's almost certainly worth it.
   *
   * We don't need the attribute values to compute the sizes, just the
   * attribute sizes, so we scan all the existing blocks, build up a
   * structure with the current attribute types and sizes, modify that
   * according to our arguments, and compute the needed size.  Once we
   * have that, we can start rewriting existing blocks.  We put all
   * the new stuff at the end, which simplifies this slightly.
   *
   * In theory, this process never requires us to have more than two
   * blocks in memory at the same time (source and destination when
   * copying across chunk boundaries), but having enough cache buffers
   * to keep the whole set in memory will almost certainly make this
   * run faster.
   */

  hal_rpc_pkey_attribute_t updated_attributes[updated_attributes_len];
  const unsigned total_chunks_old = block->header.total_chunks;
  size_t bytes_available = 0;

  updated_attributes_len = 0;

  for (chunk = 0; chunk < total_chunks_old; chunk++) {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    cache_mark_used(block, b);

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];
    size_t total;

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, &total)) != HAL_OK)
      return err;

    if (chunk == 0)
      bytes_available = bytes_len;

    for (int i = 0; i < *attrs_len; i++) {
      if (updated_attributes_len >= sizeof(updated_attributes)/sizeof(*updated_attributes))
        return HAL_ERROR_IMPOSSIBLE;
      updated_attributes[updated_attributes_len].type = attrs[i].type;
      updated_attributes[updated_attributes_len].length = attrs[i].length;
      updated_attributes[updated_attributes_len].value = NULL;
      updated_attributes_len++;
    }
  }

  for (int i = 0; i < attributes_len; i++) {

    for (int j = 0; j < updated_attributes_len; j++)
      if (updated_attributes[j].type == attributes[i].type)
        updated_attributes[j].length = 0;

    if (updated_attributes_len >= sizeof(updated_attributes)/sizeof(*updated_attributes))
      return HAL_ERROR_IMPOSSIBLE;
    updated_attributes[updated_attributes_len].type   = attributes[i].type;
    updated_attributes[updated_attributes_len].length = attributes[i].length;
    updated_attributes[updated_attributes_len].value  = attributes[i].value;
    updated_attributes_len++;
  }

  chunk = 0;

  for (int i = 0; i < updated_attributes_len; i++) {

    if (updated_attributes[i].length == 0) {
      memmove(&updated_attributes[i], &updated_attributes[i + 1], updated_attributes_len - i - 1);
      updated_attributes_len--;
      i--;
      continue;
    }

    const size_t needed = hal_ks_attribute_header_size + updated_attributes[i].length;

    if (needed > bytes_available) {
      bytes_available = SIZEOF_FLASH_ATTRIBUTE_BLOCK_ATTRIBUTES;
      chunk++;
    }

    if (needed > bytes_available)
      return HAL_ERROR_RESULT_TOO_LONG;

    bytes_available -= needed;
  }

  const unsigned total_chunks_new = chunk + 1;

  if (db.ksi.used + total_chunks_new > db.ksi.size)
    return HAL_ERROR_NO_KEY_INDEX_SLOTS;

  /*
   * Phase 1: Deprecate all the old chunks, remember where they were.
   */

  unsigned old_blocks[total_chunks_old];

  for (chunk = 0; chunk < total_chunks_old; chunk++) {
    int hint = slot->hint + chunk;
    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_deprecate(b))                                        != HAL_OK)
      return err;
    old_blocks[chunk] = b;
  }

  /*
   * Phase 2: Write new chunks, copying attributes from old chunks and attributes[]
   * as needed.  This is tedious.
   */

  {
    hal_rpc_pkey_attribute_t old_attrs[updated_attributes_len], new_attrs[updated_attributes_len];
    unsigned                *old_attrs_len = NULL,             *new_attrs_len = NULL;
    flash_block_t           *old_block     = NULL,             *new_block     = NULL;
    uint8_t                 *old_bytes     = NULL,             *new_bytes     = NULL;
    size_t                   old_bytes_len = 0,                 new_bytes_len = 0;
    unsigned                 old_chunk     = 0,                 new_chunk     = 0;
    size_t                   old_total     = 0,                 new_total     = 0;

    int updated_attributes_i = 0, old_attrs_i = 0;

    uint32_t       new_attr_type;
    size_t         new_attr_length;
    const uint8_t *new_attr_value;

    while (updated_attributes_i < updated_attributes_len) {

      if (old_chunk >= total_chunks_old || new_chunk >= total_chunks_new)
        return HAL_ERROR_IMPOSSIBLE;

      if (updated_attributes[updated_attributes_i].value != NULL) {
        new_attr_type   = updated_attributes[updated_attributes_i].type;
        new_attr_length = updated_attributes[updated_attributes_i].length;
        new_attr_value  = updated_attributes[updated_attributes_i].value;
      }

      else {

        if (old_block == NULL) {

          if ((err = block_read_cached(old_blocks[old_chunk], &old_block)) != HAL_OK)
            return err;

          if (old_block->header.this_chunk != old_chunk)
            return HAL_ERROR_IMPOSSIBLE;

          if ((err = locate_attributes(old_block, old_chunk,
                                       &old_bytes, &old_bytes_len, &old_attrs_len)) != HAL_OK ||
              (err = hal_ks_attribute_scan(old_bytes, old_bytes_len,
                                           old_attrs, *old_attrs_len, &old_total))  != HAL_OK)
            return err;

          old_attrs_i = 0;
        }

        while (old_attrs_i < *old_attrs_len &&
               old_attrs[old_attrs_i].type != updated_attributes[updated_attributes_i].type)
          old_attrs_i++;

        if (old_attrs_i >= *old_attrs_len) {
          old_chunk++;
          old_block = NULL;
          continue;
        }

        new_attr_type   = old_attrs[old_attrs_i].type;
        new_attr_length = old_attrs[old_attrs_i].length;
        new_attr_value  = old_attrs[old_attrs_i].value;
      }

      if (new_block == NULL) {

        new_block = cache_pick_lru();
        memset(new_block, 0xFF, sizeof(*new_block));

        if (new_chunk == 0) {
          flash_block_t *tmp_block;
          if ((err = block_read_cached(old_blocks[0], &tmp_block)) != HAL_OK)
            return err;
          if (tmp_block->header.this_chunk != 0)
            return HAL_ERROR_IMPOSSIBLE;
          new_block->header.block_type   = BLOCK_TYPE_KEY;
          new_block->key.name            = slot->name;
          new_block->key.type            = tmp_block->key.type;
          new_block->key.curve           = tmp_block->key.curve;
          new_block->key.flags           = tmp_block->key.flags;
          new_block->key.der_len         = tmp_block->key.der_len;
          new_block->key.attributes_len  = 0;
          memcpy(new_block->key.der, tmp_block->key.der, tmp_block->key.der_len);
        }
        else {
          new_block->header.block_type   = BLOCK_TYPE_ATTR;
          new_block->attr.name           = slot->name;
          new_block->attr.attributes_len = 0;
        }

        new_block->header.block_status = BLOCK_STATUS_LIVE;
        new_block->header.total_chunks = total_chunks_new;
        new_block->header.this_chunk   = new_chunk;

        if ((err = locate_attributes(new_block, new_chunk,
                                     &new_bytes, &new_bytes_len, &new_attrs_len)) != HAL_OK)
          return err;

        new_total = 0;
      }

      err = hal_ks_attribute_insert(new_bytes, new_bytes_len, new_attrs, new_attrs_len, &new_total,
                                    new_attr_type, new_attr_value, new_attr_length);

      switch (err) {
      case HAL_OK:
        if (++updated_attributes_i < updated_attributes_len)
          continue;
        break;
      case HAL_ERROR_RESULT_TOO_LONG:
        if (new_chunk > 0 && new_attrs_len == 0)
          return err;
        break;
      default:
        return err;
      }

      int hint = slot->hint + new_chunk;

      if (new_chunk < total_chunks_old)
        err = hal_ks_index_replace(&db.ksi, &slot->name, new_chunk, &b, &hint);
      else
        err = hal_ks_index_add(    &db.ksi, &slot->name, new_chunk, &b, &hint);

      if (err != HAL_OK || (err = block_write(b, new_block)) != HAL_OK)
        return err;

      cache_mark_used(new_block, b);

      new_block = NULL;
      new_chunk++;
    }
  }

  /*
   * Phase 3: Zero the old chunks we deprecated in phase 1.
   */

  for (chunk = 0; chunk < total_chunks_old; chunk++)
    if ((err = block_zero(old_blocks[chunk])) != HAL_OK)
      return err;

  return HAL_OK;
}

static  hal_error_t ks_get_attributes(hal_ks_t *ks,
                                      hal_pkey_slot_t *slot,
                                      hal_rpc_pkey_attribute_t *attributes,
                                      const unsigned attributes_len,
                                      uint8_t *attributes_buffer,
                                      const size_t attributes_buffer_len)
{
  if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0 ||
      attributes_buffer == NULL || attributes_buffer_len == 0)
    return HAL_ERROR_BAD_ARGUMENTS;

  for (int i = 0; i < attributes_len; i++) {
    attributes[i].length = 0;
    attributes[i].value  = NULL;
  }

  uint8_t *abuf = attributes_buffer;
  flash_block_t *block = NULL;
  unsigned chunk = 0;
  unsigned found = 0;
  hal_error_t err;
  unsigned b;

  do {
    int hint = slot->hint + chunk;

    if ((err = hal_ks_index_find(&db.ksi, &slot->name, chunk, &b, &hint)) != HAL_OK ||
        (err = block_read_cached(b, &block))                              != HAL_OK)
      return err;

    if (block->header.this_chunk != chunk)
      return HAL_ERROR_IMPOSSIBLE;

    if (chunk == 0)
      slot->hint = hint;

    cache_mark_used(block, b);

    uint8_t *bytes = NULL;
    size_t bytes_len = 0;
    unsigned *attrs_len;

    if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK)
      return err;

    if (*attrs_len == 0)
      continue;

    hal_rpc_pkey_attribute_t attrs[*attrs_len];

    if ((err = hal_ks_attribute_scan(bytes, bytes_len, attrs, *attrs_len, NULL)) != HAL_OK)
      return err;

    for (int i = 0; i < attributes_len; i++) {

      if (attributes[i].value != NULL)
        continue;

      int j = 0;
      while (j < *attrs_len && attrs[j].type != attributes[i].type)
        j++;
      if (j >= *attrs_len)
        continue;

      if (attrs[j].length > attributes_buffer + attributes_buffer_len - abuf)
        return HAL_ERROR_RESULT_TOO_LONG;

      memcpy(abuf, attrs[j].value, attrs[j].length);
      attributes[i].value  = abuf;
      attributes[i].length = attrs[j].length;
      abuf += attrs[j].length;
      found++;
    }

  } while (found < attributes_len && ++chunk < block->header.total_chunks);

  if (found < attributes_len)
    return HAL_ERROR_ATTRIBUTE_NOT_FOUND;

  return HAL_OK;
}

const hal_ks_driver_t hal_ks_token_driver[1] = {{
  .init                 = ks_init,
  .shutdown             = ks_shutdown,
  .open                 = ks_open,
  .close                = ks_close,
  .store                = ks_store,
  .fetch                = ks_fetch,
  .delete               = ks_delete,
  .match                = ks_match,
  .set_attributes       = ks_set_attributes,
  .get_attributes       = ks_get_attributes
}};

/*
 * The remaining functions aren't really part of the keystore API per se,
 * but they all involve non-key data which we keep in the keystore
 * because it's the flash we've got.
 */

/*
 * Fetch PIN.  This is always cached, so just returned cached value.
 */

hal_error_t hal_get_pin(const hal_user_t user,
                        const hal_ks_pin_t **pin)
{
  if (pin == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  switch (user) {
  case HAL_USER_WHEEL:  *pin = &db.wheel_pin;  break;
  case HAL_USER_SO:     *pin = &db.so_pin;     break;
  case HAL_USER_NORMAL: *pin = &db.user_pin;   break;
  default:              return HAL_ERROR_BAD_ARGUMENTS;
  }

  return HAL_OK;
}

/*
 * Fetch PIN block.  hint = 0 because we know that the all-zeros UUID
 * should always sort to first slot in the index.
 */

static hal_error_t fetch_pin_block(unsigned *b, flash_block_t **block)
{
  if (block == NULL)
    return HAL_ERROR_IMPOSSIBLE;

  hal_error_t err;
  int hint = 0;
  unsigned b_;

  if (b == NULL)
    b = &b_;

  if ((err = hal_ks_index_find(&db.ksi, &pin_uuid, 0, b, &hint)) != HAL_OK ||
      (err = block_read_cached(*b, block))                       != HAL_OK)
    return err;

  cache_mark_used(*block, *b);

  if (block_get_type(*block) != BLOCK_TYPE_PIN)
    return HAL_ERROR_IMPOSSIBLE;

  return HAL_OK;
}

/*
 * Update the PIN block.  This block should always be present, but we
 * have to do the zombie jamboree to make sure we write the new PIN
 * block before destroying the old one.  hint = 0 because we know that
 * the all-zeros UUID should always sort to first slot in the index.
 */

static hal_error_t update_pin_block(const unsigned b,
                                    flash_block_t *block,
                                    const flash_pin_block_t * const new_data)
{
  if (block == NULL || new_data == NULL || block_get_type(block) != BLOCK_TYPE_PIN)
    return HAL_ERROR_IMPOSSIBLE;

  int hint = 0;

  block->pin = *new_data;

  return block_update(b, block, &pin_uuid, 0, &hint);
}

/*
 * Change a PIN.
 */

hal_error_t hal_set_pin(const hal_user_t user,
                        const hal_ks_pin_t * const pin)
{
  if (pin == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;
  hal_ks_pin_t *dp, *bp;

  switch (user) {
  case HAL_USER_WHEEL:  bp = &new_data.wheel_pin; dp = &db.wheel_pin; break;
  case HAL_USER_SO:     bp = &new_data.so_pin;    dp = &db.so_pin;    break;
  case HAL_USER_NORMAL: bp = &new_data.user_pin;  dp = &db.user_pin;  break;
  default:              return HAL_ERROR_BAD_ARGUMENTS;
  }

  const hal_ks_pin_t old_pin = *dp;
  *dp = *bp = *pin;

  if ((err = update_pin_block(b, block, &new_data)) != HAL_OK)
    *dp = old_pin;

  return err;
}

#if HAL_MKM_FLASH_BACKUP_KLUDGE

/*
 * Horrible insecure kludge in lieu of a battery for the MKM.
 *
 * API here is a little strange: all calls pass a length parameter,
 * but any length other than the compiled in constant just returns an
 * immediate error, there's no notion of buffer max length vs buffer
 * used length, querying for the size of buffer really needed, or
 * anything like that.
 *
 * We might want to rewrite this some day, if we don't replace it with
 * a battery first.  For now we just preserve the API as we found it
 * while re-implementing it on top of the new keystore.
 */

hal_error_t hal_mkm_flash_read(uint8_t *buf, const size_t len)
{
  if (buf != NULL && len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  if (block->pin.kek_set != FLASH_KEK_SET)
    return HAL_ERROR_MASTERKEY_NOT_SET;

  if (buf != NULL)
    memcpy(buf, block->pin.kek, len);

  return HAL_OK;
}

hal_error_t hal_mkm_flash_write(const uint8_t * const buf, const size_t len)
{
  if (buf == NULL)
    return HAL_ERROR_BAD_ARGUMENTS;

  if (len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;

  new_data.kek_set = FLASH_KEK_SET;
  memcpy(new_data.kek, buf, len);

  return update_pin_block(b, block, &new_data);
}

hal_error_t hal_mkm_flash_erase(const size_t len)
{
  if (len != KEK_LENGTH)
    return HAL_ERROR_MASTERKEY_BAD_LENGTH;

  flash_block_t *block;
  hal_error_t err;
  unsigned b;

  if ((err = fetch_pin_block(&b, &block)) != HAL_OK)
    return err;

  flash_pin_block_t new_data = block->pin;

  new_data.kek_set = FLASH_KEK_SET;
  memset(new_data.kek, 0, len);

  return update_pin_block(b, block, &new_data);
}

#endif /* HAL_MKM_FLASH_BACKUP_KLUDGE */


/*
 * Local variables:
 * indent-tabs-mode: nil
 * End:
 */


context:
space:
mode: