On Wed, Jul 12, 2017 at 02:00:34PM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@xxxxxxxxxx>
>
> Now that we have a key_hash field which securely identifies a master key
> payload, introduce a cache of the HMAC transforms for the master keys
> currently in use for inodes using v2+ encryption policies. The entries
> in this cache are called 'struct fscrypt_master_key' and are identified
> by key_hash. The cache is per-superblock. (It could be global, but
> making it per-superblock should reduce the lock contention a bit, and we
> may need to keep track of keys on a per-superblock basis for other
> reasons later, e.g. to implement an ioctl for evicting keys.)
>
> This results in a large efficiency gain: we now only have to allocate
> and key an "hmac(sha512)" transformation, execute HKDF-Extract, and
> compute key_hash once per master key rather than once per inode. Note
> that this optimization can't easily be applied to the original AES-based
> KDF because that uses a different AES key for each KDF execution. In
> practice, this difference makes the HKDF per-inode encryption key
> derivation performance comparable to or even faster than the old KDF,
> which typically spends more time allocating an "ecb(aes)" transformation
> from the crypto API than doing actual crypto work.
>
> Note that it would have been possible to make the mapping be from
> raw_key => fscrypt_master_key (where raw_key denotes the actual bytes of
> the master key) rather than from key_hash => fscrypt_master_key.
> However, an advantage of doing lookups by key_hash is that it replaces
> the keyring lookup in most cases, which opens up the future
> possibilities of not even having the master key in memory following an
> initial provisioning step (if the HMAC-SHA512 implementation is
> hardware-backed), or of introducing an ioctl to provision a key to the
> filesystem directly, avoiding keyrings and their visibility problems
> entirely. Also, because key_hash is public information while raw_key is
> secret information, it would have been very difficult to use raw_key as
> a map key in a way that would prevent timing attacks while still being
> scalable to a large number of entries.
>
> Signed-off-by: Eric Biggers <ebiggers@xxxxxxxxxx>
Reviewed-by: Michael Halcrow <mhalcrow@xxxxxxxxxx>
> ---
> fs/crypto/fscrypt_private.h | 11 ++++
> fs/crypto/keyinfo.c | 134 +++++++++++++++++++++++++++++++++++++++++++-
> fs/crypto/policy.c | 5 +-
> fs/super.c | 4 ++
> include/linux/fs.h | 5 ++
> 5 files changed, 152 insertions(+), 7 deletions(-)
>
> diff --git a/fs/crypto/fscrypt_private.h b/fs/crypto/fscrypt_private.h
> index a7baeac92575..4b158717a8c3 100644
> --- a/fs/crypto/fscrypt_private.h
> +++ b/fs/crypto/fscrypt_private.h
> @@ -88,11 +88,22 @@ fscrypt_valid_context_format(const struct fscrypt_context *ctx, int size)
>
> /*
> * fscrypt_master_key - an in-use master key
> + *
> + * This is referenced from each in-core inode that has been "unlocked" using a
> + * particular master key. It's primarily used to cache the HMAC transform so
> + * that the per-inode encryption keys can be derived efficiently with HKDF. It
> + * is securely erased once all inodes referencing it have been evicted.
> + *
> + * If the same master key is used on different filesystems (unusual, but
> + * possible), we'll create one of these structs for each filesystem.
> */
> struct fscrypt_master_key {
> struct crypto_shash *mk_hmac;
> unsigned int mk_size;
> u8 mk_hash[FSCRYPT_KEY_HASH_SIZE];
> + refcount_t mk_refcount;
> + struct rb_node mk_node;
> + struct super_block *mk_sb;
> };
>
> /*
> diff --git a/fs/crypto/keyinfo.c b/fs/crypto/keyinfo.c
> index 12a60eacf819..bf60e76f9599 100644
> --- a/fs/crypto/keyinfo.c
> +++ b/fs/crypto/keyinfo.c
> @@ -176,6 +176,14 @@ static void put_master_key(struct fscrypt_master_key *k)
> if (!k)
> return;
>
> + if (refcount_read(&k->mk_refcount) != 0) { /* in ->s_master_keys? */
> + if (!refcount_dec_and_lock(&k->mk_refcount,
> + &k->mk_sb->s_master_keys_lock))
> + return;
> + rb_erase(&k->mk_node, &k->mk_sb->s_master_keys);
> + spin_unlock(&k->mk_sb->s_master_keys_lock);
> + }
> +
> crypto_free_shash(k->mk_hmac);
> kzfree(k);
> }
> @@ -231,6 +239,87 @@ alloc_master_key(const struct fscrypt_key *payload)
> goto out;
> }
>
> +/*
> + * ->s_master_keys is a map of master keys currently in use by in-core inodes on
> + * a given filesystem, identified by key_hash which is a cryptographically
> + * secure identifier for an actual key payload.
> + *
> + * Note that master_key_descriptor cannot be used to identify the keys because
> + * master_key_descriptor only identifies the "location" of a key in the keyring,
> + * not the actual key payload --- i.e., buggy or malicious userspace may provide
> + * different keys with the same master_key_descriptor.
> + */
> +
> +/*
> + * Search ->s_master_keys for the fscrypt_master_key having the specified hash.
> + * If found return it with a reference taken, otherwise return NULL.
> + */
> +static struct fscrypt_master_key *
> +get_cached_master_key(struct super_block *sb,
> + const u8 hash[FSCRYPT_KEY_HASH_SIZE])
> +{
> + struct rb_node *node;
> + struct fscrypt_master_key *k;
> + int res;
> +
> + spin_lock(&sb->s_master_keys_lock);
> + node = sb->s_master_keys.rb_node;
> + while (node) {
> + k = rb_entry(node, struct fscrypt_master_key, mk_node);
> + res = memcmp(hash, k->mk_hash, FSCRYPT_KEY_HASH_SIZE);
> + if (res < 0)
> + node = node->rb_left;
> + else if (res > 0)
> + node = node->rb_right;
> + else {
> + refcount_inc(&k->mk_refcount);
> + goto out;
> + }
> + }
> + k = NULL;
> +out:
> + spin_unlock(&sb->s_master_keys_lock);
> + return k;
> +}
> +
> +/*
> + * Try to insert the specified fscrypt_master_key into ->s_master_keys. If it
> + * already exists, then drop the key being inserted and take a reference to the
> + * existing one instead.
> + */
> +static struct fscrypt_master_key *
> +insert_master_key(struct super_block *sb, struct fscrypt_master_key *new)
> +{
> + struct fscrypt_master_key *k;
> + struct rb_node *parent = NULL, **p;
> + int res;
> +
> + spin_lock(&sb->s_master_keys_lock);
> + p = &sb->s_master_keys.rb_node;
> + while (*p) {
> + parent = *p;
> + k = rb_entry(parent, struct fscrypt_master_key, mk_node);
> + res = memcmp(new->mk_hash, k->mk_hash, FSCRYPT_KEY_HASH_SIZE);
> + if (res < 0)
> + p = &parent->rb_left;
> + else if (res > 0)
> + p = &parent->rb_right;
> + else {
> + refcount_inc(&k->mk_refcount);
> + spin_unlock(&sb->s_master_keys_lock);
> + put_master_key(new);
> + return k;
> + }
> + }
> +
> + rb_link_node(&new->mk_node, parent, p);
> + rb_insert_color(&new->mk_node, &sb->s_master_keys);
> + refcount_set(&new->mk_refcount, 1);
> + new->mk_sb = sb;
> + spin_unlock(&sb->s_master_keys_lock);
> + return new;
> +}
> +
> static void release_keyring_key(struct key *keyring_key)
> {
> up_read(&keyring_key->sem);
> @@ -321,6 +410,47 @@ load_master_key_from_keyring(const struct inode *inode,
> return master_key;
> }
>
> +/*
> + * Get the fscrypt_master_key identified by the specified v2+ encryption
> + * context, or create it if not found.
> + *
> + * Returns the fscrypt_master_key with a reference taken, or an ERR_PTR().
> + */
> +static struct fscrypt_master_key *
> +find_or_create_master_key(const struct inode *inode,
> + const struct fscrypt_context *ctx,
> + unsigned int min_keysize)
> +{
> + struct fscrypt_master_key *master_key;
> +
> + if (WARN_ON(ctx->version < FSCRYPT_CONTEXT_V2))
> + return ERR_PTR(-EINVAL);
Isn't this a programming error? If so, consider either BUG_ON() or
omit the check.
> +
> + /*
> + * First try looking up the master key by its cryptographically secure
> + * key_hash. If it's already in memory, there's no need to do a keyring
> + * search. (Note that we don't enforce access control based on which
> + * processes "have the key" and which don't, as encryption is meant to
> + * be orthogonal to operating-system level access control. Hence, it's
> + * sufficient for anyone on the system to have added the needed key.)
> + */
> + master_key = get_cached_master_key(inode->i_sb, ctx->key_hash);
> + if (master_key)
> + return master_key;
> +
> + /*
> + * The needed master key isn't in memory yet. Load it from the keyring.
> + */
> + master_key = load_master_key_from_keyring(inode,
> + ctx->master_key_descriptor,
> + min_keysize);
> + if (IS_ERR(master_key))
> + return master_key;
> +
> + /* Cache the key for later */
> + return insert_master_key(inode->i_sb, master_key);
> +}
> +
> static void derive_crypt_complete(struct crypto_async_request *req, int rc)
> {
> struct fscrypt_completion_result *ecr = req->data;
> @@ -638,9 +768,7 @@ int fscrypt_get_encryption_info(struct inode *inode)
> derived_keysize);
> } else {
> crypt_info->ci_master_key =
> - load_master_key_from_keyring(inode,
> - ctx.master_key_descriptor,
> - derived_keysize);
> + find_or_create_master_key(inode, &ctx, derived_keysize);
> if (IS_ERR(crypt_info->ci_master_key)) {
> res = PTR_ERR(crypt_info->ci_master_key);
> crypt_info->ci_master_key = NULL;
> diff --git a/fs/crypto/policy.c b/fs/crypto/policy.c
> index 2934bc2bff4b..7661c66a3533 100644
> --- a/fs/crypto/policy.c
> +++ b/fs/crypto/policy.c
> @@ -259,10 +259,7 @@ int fscrypt_has_permitted_context(struct inode *parent, struct inode *child)
> (parent_ci->ci_filename_mode ==
> child_ci->ci_filename_mode) &&
> (parent_ci->ci_flags == child_ci->ci_flags) &&
> - (parent_ci->ci_context_version == FSCRYPT_CONTEXT_V1 ||
> - (memcmp(parent_ci->ci_master_key->mk_hash,
> - child_ci->ci_master_key->mk_hash,
> - FSCRYPT_KEY_HASH_SIZE) == 0));
> + (parent_ci->ci_master_key == child_ci->ci_master_key);
> }
>
> res = cops->get_context(parent, &parent_ctx, sizeof(parent_ctx));
> diff --git a/fs/super.c b/fs/super.c
> index adb0c0de428c..90bd61ea139c 100644
> --- a/fs/super.c
> +++ b/fs/super.c
> @@ -215,6 +215,10 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags,
> spin_lock_init(&s->s_inode_list_lock);
> INIT_LIST_HEAD(&s->s_inodes_wb);
> spin_lock_init(&s->s_inode_wblist_lock);
> +#if IS_ENABLED(CONFIG_FS_ENCRYPTION)
> + s->s_master_keys = RB_ROOT;
> + spin_lock_init(&s->s_master_keys_lock);
> +#endif
>
> if (list_lru_init_memcg(&s->s_dentry_lru))
> goto fail;
> diff --git a/include/linux/fs.h b/include/linux/fs.h
> index 976aaa1af82a..4f47e1bc81bc 100644
> --- a/include/linux/fs.h
> +++ b/include/linux/fs.h
> @@ -1417,6 +1417,11 @@ struct super_block {
>
> spinlock_t s_inode_wblist_lock;
> struct list_head s_inodes_wb; /* writeback inodes */
> +
> +#if IS_ENABLED(CONFIG_FS_ENCRYPTION)
> + spinlock_t s_master_keys_lock;
> + struct rb_root s_master_keys; /* master crypto keys in use */
> +#endif
> };
>
> /* Helper functions so that in most cases filesystems will
> --
> 2.13.2.932.g7449e964c-goog
>
