cryptohome/sign_in_hash_tree.h

// Copyright 2018 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CRYPTOHOME_SIGN_IN_HASH_TREE_H_
#define CRYPTOHOME_SIGN_IN_HASH_TREE_H_

#include <stdint.h>

#include <map>
#include <memory>
#include <string>
#include <vector>

#include <base/files/file_path.h>
#include <base/files/memory_mapped_file.h>
#include <base/files/scoped_file.h>
#include <base/logging.h>
#include <gtest/gtest_prod.h>

#include "cryptohome/persistent_lookup_table.h"

namespace cryptohome {

const char kLeafCacheFileName[] = "leafcache";

// This class represents the hash tree which is used to store and manage the
// various credentials used to access the system. It is used to represent
// not just the leaf nodes of the hash tree, but also hashes of the inner nodes.
//
// A hash tree is used because it offers an efficient way to store a large set
// of credentials and check the integrity of the stored data. This is
// accomplished by having each of the credentials occupy a leaf node. Each
// credential will have an HMAC associated with it, which is calculated on the
// credential metadata. Based on the fan-out, i.e number of children per node of
// the tree, the leaf nodes will be used to calculate the hash of their
// corresponding parent. This process will repeat until we find the hash of the
// root node.
//
// This hash will then be compared to the root hash value stored in a secure
// non-volatile storage ( e.g Cr50 ), and can be used to verify integrity of the
// data we have on disk.
//
// There are two variables which will define the structure of the hash-table:
// - The length of a leaf bit string, leaf_length.
// - The fan-out, i.e number of children for a parent, fan_out.
//
// leaf_length and fan_out are expected to obey the following relation:
//  leaf_length = n * log2(fan_out), where n is any non-negative integer.
//
// The recalculation of the entire hash tree given the leaf nodes can be
// time consuming. To avoid that, this class also maintains a "HashCache".
// Conceptually, the HashCache stores the hashes of each node of the hash
// tree for easy access without the need to recompute them on every operation.
// Practically, it is implemented in two parts:
// - LeafCache: This file will store the MACs of all the leaf nodes of the
//   hash tree. It is expected to persist across reboots, and will be accessible
//   via a memory mapped file descriptor. The LeafCache avoids having to read
//   all the leaves from disk to obtain their hashes, which would be slow.
// - InnerHashArray: This in-memory array will store the hashes of all the inner
//   nodes of the hash tree. It is expected to be regenerated on the first
//   operation after a reboot. When a SignInHashTree object is created, the
//   InnerHashArray will consist of an all-zero array. This can be used to
//   determine whether the InnerHashArray has been initialized or not.
//
// Once the HashCache is generated, we can index into the file or array to find
// the relevant node's hash. NOTE: The HashCache is considered to be completely
// redundant. If there is any detected discrepancy between the root hash on the
// InnerHashArray, and the root hash on the Cr50, we will reconstruct the
// HashCache from scratch.
//
// While calculating the inner nodes' hashes, the LeafCache will be used to
// get the corresponding leaf MAC values.
//
// The SignInHashTree needs a persistent consistent storage on disk, and this
// will be provided by the PersistentLookupTable (referred to as PLT in the
// comments for this class, due to brevity).
//
// For each label, the value stored in the PersistentLookupTable will be in
// the following format
//
// |   HMAC(credential meatadata)   |             credential metadata          |
// |                                |                                          |
//
// Empty or non-existent leaf labels are assumed to have an HMAC of 32 bytes of
// zeroes.
class SignInHashTree {
 public:
  static constexpr size_t kHashSize = 32;

  // Convenience class to help represent the labels of nodes in the
  // SignInHashTree.
  // The high level abstraction is one of a bitstring. This can be
  // realized by using:
  // - a uin64_t |value_| variable, which can represent a bitstring of max
  // length 64.
  // - a |length| variable, which denotes the length of the bitstring
  // stored in the |value_| variable.
  //
  // In addition, we also store the number of bits per level of the
  // hash tree, represented by |bits_per_level_|. This variable
  // helps to both obtain the parent of a label, and to create children
  // for a particular label.
  class Label {
   public:
    Label() = default;
    Label(uint64_t value, uint8_t length, uint8_t bits_per_level)
        : value_(value), length_(length), bits_per_level_(bits_per_level) {
      CHECK_LE(length, 64);
      CHECK_EQ(0, length % bits_per_level);
    }

    uint64_t value() const { return value_; }

    uint8_t length() const { return length_; }

    bool is_root() const { return length_ == 0; }

    // Helper function to map the label to a unique non-negative index. The
    // index is the position of the tree node in pre-order traversal.
    // This can be used to index arrays with each array element
    // corresponding to a specific tree node.
    uint32_t cache_index() const {
      uint8_t height = length_ / bits_per_level_;
      uint8_t fan_out = 1 << bits_per_level_;

      // The the starting index for a height H in the hash tree is computed
      // as follows:
      //   starting_index(H) = starting_index(H-1) + fan_out^(H-1)
      //
      // This is geometric series which can be collapsed into the closed
      // form expression:
      //  starting_index(H) = (starting_index^(H + 1) - 1) / (fan_out - 1)
      //
      // |value_| is added to the starting index to get the cache index.
      uint32_t starting_index =
          ((1 << (bits_per_level_ * height)) - 1) / (fan_out - 1);
      return starting_index + value_;
    }

    // This function returns a Label which denotes the parent of Label
    // itself.
    Label GetParent() const {
      CHECK_GT(length_, 0);
      uint64_t parent_value = value_ >> bits_per_level_;
      uint8_t parent_length = length_ - bits_per_level_;
      return Label(parent_value, parent_length, bits_per_level_);
    }

    // This function helps to generate a child label of the current label,
    // appended with the child label suffix denoted by |child|.
    Label Extend(uint64_t child) const {
      uint8_t child_length = length_ + bits_per_level_;
      CHECK_LE(child_length, 64);
      CHECK_EQ(0, child & ~((1 << bits_per_level_) - 1));
      uint64_t child_value = value_ << bits_per_level_ | child;
      return Label(child_value, child_length, bits_per_level_);
    }

    bool operator!=(const Label& rhs) const {
      return value_ != rhs.value_ || length_ != rhs.length_ ||
             bits_per_level_ != rhs.bits_per_level_;
    }

    // If |bits_per_level_| is zero, the Label is considered invalid.
    bool is_valid() const { return bits_per_level_ != 0; }

   private:
    uint64_t value_ = 0;
    uint8_t length_ = 0;
    uint8_t bits_per_level_ = 0;
  };

  SignInHashTree(uint32_t leaf_length,
                 uint8_t bits_per_level,
                 base::FilePath basedir);

  ~SignInHashTree();

  // Return a vector of labels required to recompute the root node hash,
  // given the leaf node label |key|. This function will return a list
  // of relevant labels on success, and an empty list otherwise.
  //
  // NOTE: The list of auxiliary labels returned will follow a specific
  // order (left-to-right, bottom to top). That way, we can reason about
  // which hashes to use for which specific inner node hash calculation when
  // coupled with knowledge of the credential label in question.
  std::vector<Label> GetAuxiliaryLabels(const Label& leaf_label);

  // Compute all the hashes of the hash tree.
  //
  // This function first calls PopulateLeafCache(), and then calculates all
  // inner hashes and updates the |inner_hash_array_|.
  void GenerateAndStoreHashCache();

  // Compute all the inner hashes of the hash tree (i.e all levels of the hash
  // tree except for the leaf level). This function calls CalculateHash() on the
  // root hash.
  void GenerateInnerHashArray();

  // Store the credential data for label |label| in the Hash Tree.
  // The HMAC and the credential metadata are provided as two parameters,
  // |hmac| and |cred_data| respectively.
  // In case the label is an inner node , |hmac| will represent the hash of the
  // node, and |cred_data| MUST be empty. |metadata_lost| signifies whether
  // there is valid metadata stored for this label(false) or not(true).
  // This function should lead to two things happening(in the prescribed order):
  // - Concat the HMAC and credential metadata blobs together and store it
  //   in the underlying PersistentLookupTable pointed by |plt_|, with the
  //   key |label.value()|.
  // - Store the MAC in the |leaf_cache_| file if it is a leaf label, or update
  //   the |inner_hash_array_| otherwise.
  // - This function will also update the HashCache (i.e all the hashes along
  //   the path to the root hash) as well.
  //
  // NOTE: The SignInHashTree will write over any previous value for a
  // particular label. Ensure that the label is available before invoking this
  // routine. To obtain available labels, use SignInHashTree::GetFreeLabel().
  //
  // TODO(pmalani): Split into CreateLabel() and UpdateLabel() to better
  // clarify the user intention.
  bool StoreLabel(const Label& label,
                  const std::vector<uint8_t>& hmac,
                  const std::vector<uint8_t>& cred_metadata,
                  bool metadata_lost);

  // Get the hash/hmac and, if applicable, the credential metadata associated
  // with a label.
  // If |label| refers to a leaf node, then |cred_data| will be filled to
  // contain the relevant credential metadata, and |hmac| will be filled with
  // the associated HMAC, which will be taken directly from the table.
  // If |label| refers to an inner node, then the |hmac| will be filled with the
  // hash obtained from the |inner_hash_array_|.
  //
  // |hmac| and |cred_data| are expected to be pointers to empty vectors. The
  // function will ensure that the corresponding vectors have sufficient space.
  // |metadata_lost| will return whether the credential metadata in this leaf
  // is lost or not. This flag is set to true when a leaf was re-inserted as
  // part of a log replay operation.
  //
  // Note that the hash returned may be incorrect if the HashCache is stale
  // or erroneous, and a failure will necessitate the regeneration of the
  // HashCache.
  //
  // Note that this function does NOT update the |leaf_cache_|. Therefore, in
  // the event that the |leaf_cache_| is inconsistent with the on-disk table
  // contents, the values retrieved from GetLabelData() and |leaf_cache_| may
  // be different.
  //
  // Returns true on success, false otherwise.
  bool GetLabelData(const Label& label,
                    std::vector<uint8_t>* hmac,
                    std::vector<uint8_t>* cred_metadata,
                    bool* metadata_lost);

  // Remove the credential metadata associated with label |label| from the hash
  // tree. The |label| must refer to a leaf node; if a label for a inner node is
  // provided, or if the underlying PLT has an issue, an error will be returned.
  //
  // The function will update the HashCache after removing the label.
  //
  // Returns true on success, false otherwise.
  bool RemoveLabel(const Label& label);

  // Returns the first available free leaf label for credential metadata.
  // Returns the label on success. If a free label is not available, this
  // function will return an empty Label (i.e value_ = length_ =
  // bits_per_per_level_ = 0);
  Label GetFreeLabel();

  // Fills the current root hash from |inner_hash_array_| into
  // |root_hash|. Before that, it regenerates the entire |inner_hash_array_|.
  void GetRootHash(std::vector<uint8_t>* root_hash);

 private:
  // Recursive function which is used to calculate the hashes for the hash tree,
  // starting node |label|. The resultant hash is returned.
  // This function assumes that the leaf MAC values have already been updated
  // in the |leaf_cache_|.
  //
  // In addition to calculating the hash for |label|, this function will
  // also update the |inner_hash_array_| with the new value.
  std::vector<uint8_t> CalculateHash(const Label& label);

  // Helper function to determine whether a Label corresponds to a leaf
  // node of the hash tree.
  bool IsLeafLabel(const Label& l) { return l.length() == leaf_length_; }

  // Update the HashCache associated with the path for |label|, and in doing
  // so modifies the |inner_hash_array_|.
  // This function is typically called after an update is made to the
  // underlying PLT.
  // This function assumes that the |leaf_cache_| is up to date,
  void UpdateHashCacheLabelPath(const Label& label);

  // Update the |inner_hash_array_| with the provided value.
  // This function does NOT update the entire HashCache label path to the root
  // for this index.
  void UpdateInnerHashArray(uint32_t index, const uint8_t* data, size_t size);

  // Update the |leaf_cache_| with the provided value.
  // This function does NOT update the entire HashCache label path to the root
  // for this index.
  void UpdateLeafCache(uint32_t index, const uint8_t* data, size_t size);

  // Populate the |leaf_cache_| with the MAC values of all leaf labels.
  void PopulateLeafCache();

  // Length of the leaf node label.
  uint32_t leaf_length_;
  // Fan out of the hash tree, i.e number of children of each inner node.
  uint32_t fan_out_;
  // Number of bits per level of the hash tree.
  uint8_t bits_per_level_;
  // Memory mapped file pointing to the LeafCache file on disk.
  base::MemoryMappedFile leaf_cache_;
  // Pointer to the |leaf_cache_| file data.
  // Each element is a 32-byte hash.
  uint8_t (*leaf_cache_array_)[kHashSize];
  // In-memory array used to store inner node hash values.
  std::vector<uint8_t> inner_hash_vector_;
  // Pointer to the |inner_hash_vector_| data.
  uint8_t (*inner_hash_array_)[kHashSize];

  // This is used to actually store and retrieve data from the backing disk
  // storage.
  std::unique_ptr<Platform> p_;
  PersistentLookupTable plt_;
};

}  // namespace cryptohome

#endif  // CRYPTOHOME_SIGN_IN_HASH_TREE_H_