diff options
Diffstat (limited to 'ks_flash.c')
| -rw-r--r-- | ks_flash.c | 2042 |
1 files changed, 1836 insertions, 206 deletions
@@ -33,315 +33,1945 @@ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#define HAL_OK LIBHAL_OK +#include <stddef.h> +#include <string.h> +#include <assert.h> + #include "hal.h" #include "hal_internal.h" -#undef HAL_OK + +#include "last_gasp_pin_internal.h" #define HAL_OK CMIS_HAL_OK #include "stm-keystore.h" -#include "masterkey.h" #undef HAL_OK -#include <string.h> +/* + * 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; -#define PAGE_SIZE_MASK (KEYSTORE_PAGE_SIZE - 1) +/* + * 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; /* - * Use a one-element array here so that references can be pointer-based - * as in the other implementations, to ease re-merge at some later date. + * 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). */ -static hal_ks_keydb_t db[1]; +const static hal_uuid_t pin_uuid = {{0}}; -#define FLASH_SECTOR_1_OFFSET (0 * KEYSTORE_SECTOR_SIZE) -#define FLASH_SECTOR_2_OFFSET (1 * KEYSTORE_SECTOR_SIZE) +/* + * 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. + */ -uint32_t _active_sector_offset() +static db_t db; + +/* + * Type safe casts. + */ + +static inline flash_block_type_t block_get_type(const flash_block_t * const block) { - /* XXX Load status bytes from both sectors and decide which is current. */ - #warning Have not implemented two flash sectors yet - return FLASH_SECTOR_1_OFFSET; + assert(block != NULL); + return (flash_block_type_t) block->header.block_type; } -uint32_t _get_key_offset(uint32_t num) +static inline flash_block_status_t block_get_status(const flash_block_t * const block) { - /* Reserve first two pages for flash sector state, PINs and future additions. - * The three PINs alone currently occupy 3 * (64 + 16 + 4) bytes (252). - */ - uint32_t offset = KEYSTORE_PAGE_SIZE * 2; - uint32_t key_size = sizeof(*db->keys); - uint32_t bytes_per_key = KEYSTORE_PAGE_SIZE * ((key_size / KEYSTORE_PAGE_SIZE) + 1); - offset += num * bytes_per_key; - return offset; + assert(block != NULL); + return (flash_block_status_t) block->header.block_status; } -const hal_ks_keydb_t *hal_ks_get_keydb(void) +/* + * 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 offset, i, idx = 0, active_sector_offset; - hal_ks_key_t *key; - uint8_t page_buf[KEYSTORE_PAGE_SIZE]; + uint32_t best_delta = 0; + int best_index = 0; - memset(db, 0, sizeof(*db)); + for (int i = 0; i < KS_FLASH_CACHE_SIZE; i++) { - if (keystore_check_id() != 1) return NULL; + if (db.cache[i].blockno == ~0) + return &db.cache[i].block; - active_sector_offset = _active_sector_offset(); + const uint32_t delta = db.cache_lru - db.cache[i].lru; + if (delta > best_delta) { + best_delta = delta; + best_index = i; + } - /* The PINs are in the second page of the sector. */ - offset = active_sector_offset + KEYSTORE_PAGE_SIZE; - if (keystore_read_data(offset, page_buf, sizeof(page_buf)) != 1) return NULL; - offset = 0; - memcpy(&db->wheel_pin, page_buf + offset, sizeof(db->wheel_pin)); - offset += sizeof(db->wheel_pin); - memcpy(&db->so_pin, page_buf + offset, sizeof(db->so_pin)); - offset += sizeof(db->so_pin); - memcpy(&db->user_pin, page_buf + offset, sizeof(db->user_pin)); + } - for (i = 0; i < sizeof(db->keys) / sizeof(*db->keys); i++) { - offset = _get_key_offset(i); - if (offset > KEYSTORE_SECTOR_SIZE) { - idx++; - continue; - } + db.cache[best_index].blockno = ~0; + return &db.cache[best_index].block; +} - offset += active_sector_offset; +/* + * Find a block in our in-memory cache; return block or NULL if not present. + */ - if (keystore_read_data(offset, page_buf, sizeof(page_buf)) != 1) return NULL; +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; +} - key = (hal_ks_key_t *) page_buf; - if (key->in_use == 0xff) { - /* unprogrammed data */ - idx++; - continue; - } +/* + * Mark a block in our in-memory cache as being in current use. + */ - if (key->in_use == 1) { - uint8_t *dst = (uint8_t *) &db->keys[idx]; - uint32_t to_read = sizeof(*db->keys); - - /* We already have the first page in page_buf. Put it into place. */ - memcpy(dst, page_buf, sizeof(page_buf)); - to_read -= sizeof(page_buf); - dst += sizeof(page_buf); - - /* Read as many more full pages as possible */ - if (keystore_read_data (offset + KEYSTORE_PAGE_SIZE, dst, to_read & ~PAGE_SIZE_MASK) != 1) return NULL; - dst += to_read & ~PAGE_SIZE_MASK; - to_read &= PAGE_SIZE_MASK; - - if (to_read) { - /* Partial last page. We can only read full pages so load it into page_buf. */ - if (keystore_read_data(offset + sizeof(*db->keys) - to_read, page_buf, sizeof(page_buf)) != 1) return NULL; - memcpy(dst, page_buf, to_read); - } - } - idx++; +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; } + } +} - return db; +/* + * 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); } -hal_error_t _write_data_to_flash(const uint32_t offset, const uint8_t *data, const size_t len) +/* + * 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) { - uint8_t page_buf[KEYSTORE_PAGE_SIZE]; - uint32_t to_write = len; + assert(block != NULL); - if (keystore_write_data(offset, data, to_write & ~PAGE_SIZE_MASK) != 1) { - return HAL_ERROR_KEYSTORE_ACCESS; - } - to_write &= PAGE_SIZE_MASK; - if (to_write) { - /* Use page_buf to write the remaining bytes, since we must write a full page each time. */ - memset(page_buf, 0xff, sizeof(page_buf)); - memcpy(page_buf, data + len - to_write, to_write); - if (keystore_write_data((offset + len) & ~PAGE_SIZE_MASK, page_buf, sizeof(page_buf)) != 1) { - return HAL_ERROR_KEYSTORE_ACCESS; - } - } + 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); - return LIBHAL_OK; + 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]); } /* - * Write the full DB to flash, PINs and all. + * Forward reference. */ -hal_error_t _write_db_to_flash(const uint32_t sector_offset) + +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, const int alloc) { - hal_error_t status; - uint8_t page_buf[KEYSTORE_PAGE_SIZE]; - uint32_t i, offset; + /* + * Initialize the in-memory database. + */ + + if (alloc) { + + 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; + } + + else { + memset(&db.wheel_pin, 0, sizeof(db.wheel_pin)); + memset(&db.so_pin, 0, sizeof(db.so_pin)); + memset(&db.user_pin, 0, sizeof(db.user_pin)); + } + + 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; - if (sizeof(db->wheel_pin) + sizeof(db->so_pin) + sizeof(db->user_pin) > sizeof(page_buf)) { - return HAL_ERROR_BAD_ARGUMENTS; + 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; } - /* Put the three PINs into page_buf */ - offset = 0; - memcpy(page_buf + offset, &db->wheel_pin, sizeof(db->wheel_pin)); - offset += sizeof(db->wheel_pin); - memcpy(page_buf + offset, &db->so_pin, sizeof(db->so_pin)); - offset += sizeof(db->so_pin); - memcpy(page_buf + offset, &db->user_pin, sizeof(db->user_pin)); - - /* Write PINs into the second of the two reserved pages at the start of the sector. */ - offset = sector_offset + KEYSTORE_PAGE_SIZE; - if ((status = _write_data_to_flash(offset, page_buf, sizeof(page_buf))) != LIBHAL_OK) { - return status; + /* + * 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; } - for (i = 0; i < sizeof(db->keys) / sizeof(*db->keys); i++) { - offset = _get_key_offset(i); - if (offset > KEYSTORE_SECTOR_SIZE) { - return HAL_ERROR_BAD_ARGUMENTS; - } + 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]; - offset += sector_offset; + if ((err = block_read(b, block)) != HAL_OK) + return err; - if ((status =_write_data_to_flash(offset, (uint8_t *) &db->keys[i], sizeof(*db->keys))) != LIBHAL_OK) { - return status; + 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_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_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_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; + } } + } } - return LIBHAL_OK; + 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; } -hal_error_t hal_ks_set_keydb(const hal_ks_key_t * const key, - const int loc, - const int updating) +/* + * This controls whether we include a separate code path for the + * common case where we can handle attribute setting via a single + * block update. It's a lot simpler when it works, but it's yet + * another code path, and enabling it leaves the slower full-blown + * algorithm less tested. + */ + +#ifndef KS_SET_ATTRIBUTES_SINGLE_BLOCK_UPDATE_FAST_PATH +#define KS_SET_ATTRIBUTES_SINGLE_BLOCK_UPDATE_FAST_PATH 0 +#endif + +/* + * ks_set_attributes() is much too long. Probably needs to be broken + * up into a collection of inline functions, even if most of them end + * up being called exactly once. + */ + +static hal_error_t ks_set_attributes(hal_ks_t *ks, + hal_pkey_slot_t *slot, + const hal_pkey_attribute_t *attributes, + const unsigned attributes_len) { - hal_error_t status; - uint32_t offset, active_sector_offset; - hal_ks_key_t *tmp_key; - uint8_t page_buf[KEYSTORE_PAGE_SIZE]; + if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0) + return HAL_ERROR_BAD_ARGUMENTS; - if (key == NULL || loc < 0 || loc >= sizeof(db->keys)/sizeof(*db->keys) || (!key->in_use != !updating)) - return HAL_ERROR_BAD_ARGUMENTS; + /* + * Perform initial scan of the object to figure out the total + * attribute count and a few other parameters. + * + * If enabled, try to do everything as as a single-block update. If + * single block update fails, we MUST clear the modified block from + * the cache before doing anything else. + */ - offset = _get_key_offset(loc); - if (offset > KEYSTORE_SECTOR_SIZE) return HAL_ERROR_BAD_ARGUMENTS; + 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; + +#if KS_SET_ATTRIBUTES_SINGLE_BLOCK_UPDATE_FAST_PATH + + hal_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 == HAL_PKEY_ATTRIBUTE_NIL) + 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); + +#endif /* KS_SET_ATTRIBUTES_SINGLE_BLOCK_UPDATE_FAST_PATH */ + + } while (++chunk < block->header.total_chunks); + + /* + * If we get here, we're on the slow path, which requires rewriting + * all the chunks in this object but which can also add or remove + * chunks from this object. 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 to hold all the new chunks. + * + * 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_pkey_attribute_t updated_attributes[updated_attributes_len]; + const unsigned total_chunks_old = block->header.total_chunks; + size_t bytes_available = 0; - active_sector_offset = _active_sector_offset(); + updated_attributes_len = 0; - offset += active_sector_offset; + /* + * Phase 0.1: Walk the old chunks to populate updated_attributes[]. + * This also initializes bytes_available, since we can only get that + * by reading old chunk zero. + */ - if (keystore_check_id() != 1) return HAL_ERROR_KEYSTORE_ACCESS; + for (chunk = 0; chunk < total_chunks_old; chunk++) { + int hint = slot->hint + chunk; - /* Check if there is a key occupying this slot in the flash already. - * Don't trust the in-memory representation since it would mean data - * corruption in flash if it had been altered. - */ - if (keystore_read_data(offset, page_buf, sizeof(page_buf)) != 1) { - return HAL_ERROR_KEYSTORE_ACCESS; + 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_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++; } - tmp_key = (hal_ks_key_t *) page_buf; + } + + /* + * Phase 0.2: Merge new attributes into updated_attributes[]. + */ + + 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 = HAL_PKEY_ATTRIBUTE_NIL; + + 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++; + } + + /* + * Phase 0.3: Prune trailing deletion actions: we don't need them to + * maintain synchronization with existing attributes, and doing so + * simplifies logic for updating the final new chunk. + */ + + while (updated_attributes_len > 0 && + updated_attributes[updated_attributes_len - 1].length == HAL_PKEY_ATTRIBUTE_NIL) + --updated_attributes_len; + + /* + * Phase 0.4: Figure out how many chunks all this will occupy. + */ + + chunk = 0; + + for (int i = 0; i < updated_attributes_len; i++) { - db->keys[loc] = *key; - db->keys[loc].in_use = 1; + if (updated_attributes[i].length == HAL_PKEY_ATTRIBUTE_NIL) + continue; - if (tmp_key->in_use == 0xff) { - /* Key slot was unused in flash. Write the new key there. */ - if ((status = _write_data_to_flash(offset, (uint8_t *) key, sizeof(*db->keys))) != LIBHAL_OK) { - return status; + 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 there aren't enough free blocks, give up now, before changing anything. + */ + + 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 or + * from attributes[], as needed. + */ + + { + hal_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 we've gotten as far as new data that comes from + * attributes[], we have it in hand and can just copy it. + */ + + if (updated_attributes_len - updated_attributes_i <= attributes_len) { + 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; + } + + /* + * Otherwise, we have to read it from an old block, which may in + * turn require reading in the next old block. + */ + + 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; + } + + if (old_attrs_i >= *old_attrs_len) { + old_chunk++; + old_block = NULL; + continue; } - } else { - /* TODO: Erase and write the database to the inactive sector, and then toggle active sector. */ - if (keystore_erase_sectors(active_sector_offset / KEYSTORE_SECTOR_SIZE, - active_sector_offset / KEYSTORE_SECTOR_SIZE) != 1) { - return HAL_ERROR_KEYSTORE_ACCESS; + + 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_attr_type != updated_attributes[updated_attributes_i].type) + return HAL_ERROR_IMPOSSIBLE; + + old_attrs_i++; + } + + /* + * Unless this is a deletion, we should have something to write. + */ + + if (new_attr_length != HAL_PKEY_ATTRIBUTE_NIL && new_attr_value == NULL) + return HAL_ERROR_IMPOSSIBLE; + + /* + * Initialize the new block if necessary. If it's the new chunk + * zero, we need to copy all the non-attribute data from the old + * chunk zero; otherwise, it's a new empty attribute block. + */ + + 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); } - if ((status =_write_db_to_flash(active_sector_offset)) != LIBHAL_OK) { - return status; + 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; + } + + /* + * After all that setup, we finally get to write the frelling attribute. + */ + + if (new_attr_length != HAL_PKEY_ATTRIBUTE_NIL) + 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); + + /* + * Figure out what to do next: immediately loop for next + * attribute, write current block, or bail out. + */ + + 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; + } + + /* + * If we get here, either the current new block is full or we + * finished the last block, so we need to write it out. + */ + + 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++; } - return LIBHAL_OK; + /* + * If number of blocks shrank, we need to clear trailing entries from the index. + */ + + for (old_chunk = total_chunks_new; old_chunk < total_chunks_old; old_chunk++) { + int hint = slot->hint + old_chunk; + + err = hal_ks_index_delete(&db.ksi, &slot->name, old_chunk, NULL, &hint); + + if (err != HAL_OK) + return err; + } + + } + + /* + * 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; + +#warning What happens if something goes wrong partway through this awful mess? + // We're left in a state with all the old blocks deprecated and + // (maybe) some of the new blocks current, need to clean that up. + // Would be nice if we could just reuse the keystore initialization + // code, but don't quite see how (yet?). } -hal_error_t hal_ks_del_keydb(const int loc) +static hal_error_t ks_get_attributes(hal_ks_t *ks, + hal_pkey_slot_t *slot, + hal_pkey_attribute_t *attributes, + const unsigned attributes_len, + uint8_t *attributes_buffer, + const size_t attributes_buffer_len) { - uint32_t offset; - - if (loc < 0 || loc >= sizeof(db->keys)/sizeof(*db->keys)) + if (ks != &db.ks || slot == NULL || attributes == NULL || attributes_len == 0 || + attributes_buffer == NULL) return HAL_ERROR_BAD_ARGUMENTS; - offset = _get_key_offset(loc); - if (offset > KEYSTORE_SECTOR_SIZE) { - return HAL_ERROR_BAD_ARGUMENTS; + for (int i = 0; i < attributes_len; i++) { + attributes[i].length = 0; + attributes[i].value = NULL; } - offset += _active_sector_offset(); + 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); - memset(&db->keys[loc], 0, sizeof(*db->keys)); + uint8_t *bytes = NULL; + size_t bytes_len = 0; + unsigned *attrs_len; - /* Setting bits to 0 never requires erasing flash. Just write it. */ - return _write_data_to_flash(offset, (uint8_t *) &db->keys[loc], sizeof(*db->keys)); + if ((err = locate_attributes(block, chunk, &bytes, &bytes_len, &attrs_len)) != HAL_OK) + return err; + + if (*attrs_len == 0) + continue; + + hal_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].length > 0) + continue; + + int j = 0; + while (j < *attrs_len && attrs[j].type != attributes[i].type) + j++; + if (j >= *attrs_len) + continue; + found++; + + attributes[i].length = attrs[j].length; + + if (attributes_buffer_len == 0) + 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; + abuf += attrs[j].length; + } + + } while (found < attributes_len && ++chunk < block->header.total_chunks); + + if (found < attributes_len && attributes_buffer_len > 0) + return HAL_ERROR_ATTRIBUTE_NOT_FOUND; + + return HAL_OK; } -hal_error_t hal_ks_set_pin(const hal_user_t user, - const hal_ks_pin_t * const pin) -{ - uint32_t active_sector_offset; +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; - hal_ks_pin_t *p = NULL; - switch (user) { - case HAL_USER_WHEEL: p = &db->wheel_pin; break; - case HAL_USER_SO: p = &db->so_pin; break; - case HAL_USER_NORMAL: p = &db->user_pin; break; - default: return HAL_ERROR_BAD_ARGUMENTS; + 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; } - memcpy(p, pin, sizeof(*p)); + 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; - active_sector_offset = _active_sector_offset(); + hal_error_t err; + int hint = 0; + unsigned b_; - /* TODO: Could check if the PIN is currently all 0xff, in which case we wouldn't have to - * erase and re-write the whole DB. - */ + if (b == NULL) + b = &b_; - /* TODO: Erase and write the database to the inactive sector, and then toggle active sector. */ - if (keystore_erase_sectors(active_sector_offset / KEYSTORE_SECTOR_SIZE, - active_sector_offset / KEYSTORE_SECTOR_SIZE) != 1) { - return HAL_ERROR_KEYSTORE_ACCESS; - } - return _write_db_to_flash(active_sector_offset); + 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. + */ -hal_error_t hal_ks_get_kek(uint8_t *kek, - size_t *kek_len, - const size_t kek_max) +static hal_error_t update_pin_block(const unsigned b, + flash_block_t *block, + const flash_pin_block_t * const new_data) { - if (kek == NULL || kek_len == NULL || kek_max < bitsToBytes(128)) + 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; - const size_t len = ((kek_max < bitsToBytes(192)) ? bitsToBytes(128) : - (kek_max < bitsToBytes(256)) ? bitsToBytes(192) : - bitsToBytes(256)); + flash_block_t *block; + hal_error_t err; + unsigned b; - hal_error_t err = masterkey_volatile_read(kek, len); - if (err == LIBHAL_OK) { - *kek_len = len; - return LIBHAL_OK; - } - if (masterkey_flash_read(kek, len) == LIBHAL_OK) { - *kek_len = len; - return LIBHAL_OK; + 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; } - /* Both keystores returned an error, probably HAL_ERROR_MASTERKEY_NOT_SET. - * I could try to be clever and compare the errors, but really the volatile - * keystore is the important one (you shouldn't store the master key in - * flash), so return that error. - */ + 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 */ /* |