lms.cpp

Go to the documentation of this file.

/**
 * LMS - Leighton-Micali Hash-Based Signatures (RFC 8554)
 * (C) 2023 Jack Lloyd
 *     2023 Fabian Albert, Philippe Lieser - Rohde & Schwarz Cybersecurity GmbH
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
#include <botan/internal/lms.h>
 
#include <botan/internal/int_utils.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/tree_hash.h>
 
namespace Botan {
namespace {
 
/**
 * @brief Domain-separation parameter when computing the hash of the leaf of an LMS tree.
 */
constexpr uint16_t D_LEAF = 0x8282;
 
/**
 * @brief Domain-separation parameter when computing the hash of an interior node of an LMS tree.
 */
constexpr uint16_t D_INTR = 0x8383;
 
/// Index of the layer in a tree starting with 0 for the bottom level to the root layer
using LMS_TreeLayerIndex = Strong<uint32_t, struct LMS_TreeLayerIndex_, EnableArithmeticWithPlainNumber>;
 
class TreeAddress final {
   public:
      explicit TreeAddress(uint32_t total_tree_height) : m_h(total_tree_height), m_r(0) {
         BOTAN_ARG_CHECK(total_tree_height > 0 && total_tree_height < 32, "Invalid tree height");
      }
 
      TreeAddress& set_address(LMS_TreeLayerIndex tree_layer, LMS_Tree_Node_Idx tree_index) {
         BOTAN_ARG_CHECK(tree_index.get() < (1 << m_h), "Invalid tree index");
         BOTAN_ARG_CHECK(tree_layer.get() <= m_h, "Invalid tree index");
         m_r = (1 << (m_h - tree_layer)).get() + tree_index.get();
         return *this;
      }
 
      uint32_t r() const { return m_r; }
 
      bool is_leaf() const { return m_r >= (1 << m_h); }
 
      LMS_Tree_Node_Idx q() const {
         BOTAN_STATE_CHECK(is_leaf());
         return LMS_Tree_Node_Idx(m_r - (1 << m_h.get()));
      }
 
   private:
      LMS_TreeLayerIndex m_h;
      uint32_t m_r;
};
 
auto get_hash_pair_func_for_identifier(const LMS_Params& lms_params, LMS_Identifier identifier) {
   return [hash = lms_params.hash(), I = std::move(identifier)](StrongSpan<LMS_Tree_Node> out,
                                                                const TreeAddress& address,
                                                                StrongSpan<const LMS_Tree_Node> left,
                                                                StrongSpan<const LMS_Tree_Node> right) {
      hash->update(I);
      hash->update(store_be(address.r()));
      hash->update(store_be(D_INTR));
      hash->update(left);
      hash->update(right);
      hash->final(out);
   };
}
 
void lms_gen_leaf(StrongSpan<LMS_Tree_Node> out,
                  const LMOTS_Public_Key& lmots_pk,
                  const TreeAddress& tree_address,
                  HashFunction& hash) {
   hash.update(lmots_pk.identifier());
   hash.update(store_be(tree_address.r()));
   hash.update(store_be(D_LEAF));
   hash.update(lmots_pk.K());
   hash.final(out);
}
 
auto lms_gen_leaf_func(const LMS_PrivateKey& lms_sk) {
   return [hash = lms_sk.lms_params().hash(), lms_sk](StrongSpan<LMS_Tree_Node> out, const TreeAddress& tree_address) {
      auto lmots_sk = LMOTS_Private_Key(lms_sk.lmots_params(), lms_sk.identifier(), tree_address.q(), lms_sk.seed());
      auto lmots_pk = LMOTS_Public_Key(lmots_sk);
      lms_gen_leaf(out, lmots_pk, tree_address, *hash);
   };
}
 
void lms_treehash(StrongSpan<LMS_Tree_Node> out_root,
                  std::optional<StrongSpan<LMS_AuthenticationPath>> out_auth_path,
                  std::optional<LMS_Tree_Node_Idx> leaf_idx,
                  const LMS_PrivateKey& lms_sk) {
   auto hash_pair_func = get_hash_pair_func_for_identifier(lms_sk.lms_params(), lms_sk.identifier());
   auto gen_leaf = lms_gen_leaf_func(lms_sk);
   TreeAddress lms_tree_address(lms_sk.lms_params().h());
 
   treehash(out_root,
            out_auth_path,
            leaf_idx,
            lms_sk.lms_params().m(),
            LMS_TreeLayerIndex(lms_sk.lms_params().h()),
            0,
            std::move(hash_pair_func),
            std::move(gen_leaf),
            lms_tree_address);
}
 
}  // namespace
 
LMS_Params LMS_Params::create_or_throw(LMS_Algorithm_Type type) {
   auto [hash_name, height] = [](const LMS_Algorithm_Type& lms_type) -> std::pair<std::string_view, uint8_t> {
      switch(lms_type) {
         case LMS_Algorithm_Type::SHA256_M32_H5:
            return {"SHA-256", 5};
         case LMS_Algorithm_Type::SHA256_M32_H10:
            return {"SHA-256", 10};
         case LMS_Algorithm_Type::SHA256_M32_H15:
            return {"SHA-256", 15};
         case LMS_Algorithm_Type::SHA256_M32_H20:
            return {"SHA-256", 20};
         case LMS_Algorithm_Type::SHA256_M32_H25:
            return {"SHA-256", 25};
         case LMS_Algorithm_Type::SHA256_M24_H5:
            return {"Truncated(SHA-256,192)", 5};
         case LMS_Algorithm_Type::SHA256_M24_H10:
            return {"Truncated(SHA-256,192)", 10};
         case LMS_Algorithm_Type::SHA256_M24_H15:
            return {"Truncated(SHA-256,192)", 15};
         case LMS_Algorithm_Type::SHA256_M24_H20:
            return {"Truncated(SHA-256,192)", 20};
         case LMS_Algorithm_Type::SHA256_M24_H25:
            return {"Truncated(SHA-256,192)", 25};
         case LMS_Algorithm_Type::SHAKE_M32_H5:
            return {"SHAKE-256(256)", 5};
         case LMS_Algorithm_Type::SHAKE_M32_H10:
            return {"SHAKE-256(256)", 10};
         case LMS_Algorithm_Type::SHAKE_M32_H15:
            return {"SHAKE-256(256)", 15};
         case LMS_Algorithm_Type::SHAKE_M32_H20:
            return {"SHAKE-256(256)", 20};
         case LMS_Algorithm_Type::SHAKE_M32_H25:
            return {"SHAKE-256(256)", 25};
         case LMS_Algorithm_Type::SHAKE_M24_H5:
            return {"SHAKE-256(192)", 5};
         case LMS_Algorithm_Type::SHAKE_M24_H10:
            return {"SHAKE-256(192)", 10};
         case LMS_Algorithm_Type::SHAKE_M24_H15:
            return {"SHAKE-256(192)", 15};
         case LMS_Algorithm_Type::SHAKE_M24_H20:
            return {"SHAKE-256(192)", 20};
         case LMS_Algorithm_Type::SHAKE_M24_H25:
            return {"SHAKE-256(192)", 25};
         default:
            throw Decoding_Error("Unsupported LMS algorithm type");
      }
   }(type);
 
   return LMS_Params(type, hash_name, height);
}
 
LMS_Params LMS_Params::create_or_throw(std::string_view hash_name, uint8_t height) {
   LMS_Algorithm_Type type = [](std::string_view hash, uint8_t h) -> LMS_Algorithm_Type {
      if(hash == "SHA-256") {
         switch(h) {
            case 5:
               return LMS_Algorithm_Type::SHA256_M32_H5;
            case 10:
               return LMS_Algorithm_Type::SHA256_M32_H10;
            case 15:
               return LMS_Algorithm_Type::SHA256_M32_H15;
            case 20:
               return LMS_Algorithm_Type::SHA256_M32_H20;
            case 25:
               return LMS_Algorithm_Type::SHA256_M32_H25;
            default:
               throw Decoding_Error("Unsupported height for hash function");
         }
      }
      if(hash == "Truncated(SHA-256,192)") {
         switch(h) {
            case 5:
               return LMS_Algorithm_Type::SHA256_M24_H5;
            case 10:
               return LMS_Algorithm_Type::SHA256_M24_H10;
            case 15:
               return LMS_Algorithm_Type::SHA256_M24_H15;
            case 20:
               return LMS_Algorithm_Type::SHA256_M24_H20;
            case 25:
               return LMS_Algorithm_Type::SHA256_M24_H25;
            default:
               throw Decoding_Error("Unsupported height for hash function");
         }
      }
      if(hash == "SHAKE-256(256)") {
         switch(h) {
            case 5:
               return LMS_Algorithm_Type::SHAKE_M32_H5;
            case 10:
               return LMS_Algorithm_Type::SHAKE_M32_H10;
            case 15:
               return LMS_Algorithm_Type::SHAKE_M32_H15;
            case 20:
               return LMS_Algorithm_Type::SHAKE_M32_H20;
            case 25:
               return LMS_Algorithm_Type::SHAKE_M32_H25;
            default:
               throw Decoding_Error("Unsupported height for hash function");
         }
      }
      if(hash == "SHAKE-256(192)") {
         switch(h) {
            case 5:
               return LMS_Algorithm_Type::SHAKE_M24_H5;
            case 10:
               return LMS_Algorithm_Type::SHAKE_M24_H10;
            case 15:
               return LMS_Algorithm_Type::SHAKE_M24_H15;
            case 20:
               return LMS_Algorithm_Type::SHAKE_M24_H20;
            case 25:
               return LMS_Algorithm_Type::SHAKE_M24_H25;
            default:
               throw Decoding_Error("Unsupported height for hash function");
         }
      }
      throw Decoding_Error("Unsupported hash function");
   }(hash_name, height);
 
   return LMS_Params(type, hash_name, height);
}
 
LMS_Params::LMS_Params(LMS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t h) :
      m_algorithm_type(algorithm_type), m_h(h), m_hash_name(hash_name) {
   const auto hash = HashFunction::create_or_throw(m_hash_name);
   m_m = hash->output_length();
}
 
LMS_PublicKey LMS_PrivateKey::sign_and_get_pk(StrongSpan<LMS_Signature_Bytes> out_sig,
                                              LMS_Tree_Node_Idx q,
                                              const LMS_Message& msg) const {
   // Pre-alloc space for the signature
   BOTAN_ARG_CHECK(out_sig.size() == LMS_Signature::size(lms_params(), lmots_params()), "Invalid output buffer size");
 
   BufferStuffer sig_stuffer(out_sig);
   sig_stuffer.append(store_be(q));
   const LMOTS_Private_Key lmots_sk(lmots_params(), identifier(), q, seed());
   lmots_sk.sign(sig_stuffer.next<LMOTS_Signature_Bytes>(LMOTS_Signature::size(lmots_params())), msg);
   sig_stuffer.append(store_be(lms_params().algorithm_type()));
   const auto auth_path_buffer = sig_stuffer.next<LMS_AuthenticationPath>(lms_params().m() * lms_params().h());
 
   BOTAN_ASSERT_NOMSG(sig_stuffer.full());
 
   TreeAddress lms_tree_address(lms_params().h());
   LMS_Tree_Node pk_buffer(lms_params().m());
   lms_treehash(StrongSpan<LMS_Tree_Node>(pk_buffer.get()), auth_path_buffer, q, *this);
 
   return LMS_PublicKey(lms_params(), lmots_params(), identifier(), std::move(pk_buffer));
}
 
LMS_PublicKey LMS_PublicKey::from_bytes_or_throw(BufferSlicer& slicer) {
   size_t total_remaining_bytes = slicer.remaining();
   // Alg. 6. 1. (4 bytes are sufficient until the next check)
   if(total_remaining_bytes < sizeof(LMS_Algorithm_Type)) {
      throw Decoding_Error("Too few bytes while parsing LMS public key.");
   }
   // Alg. 6. 2.a.
   auto lms_type = load_be<LMS_Algorithm_Type>(slicer.take<sizeof(LMS_Algorithm_Type)>());
   // Alg. 6. 2.c.
   auto lms_params = LMS_Params::create_or_throw(lms_type);
   // Alg. 6. 2.d.
   if(total_remaining_bytes < LMS_PublicKey::size(lms_params)) {
      throw Decoding_Error("Too few bytes while parsing LMS public key.");
   }
   // Alg. 6. 2.b.
   auto lmots_type = load_be<LMOTS_Algorithm_Type>(slicer.take<sizeof(LMOTS_Algorithm_Type)>());
   auto lmots_params = LMOTS_Params::create_or_throw(lmots_type);
 
   if(lms_params.hash_name() != lmots_params.hash_name()) {
      throw Decoding_Error("No support for HSS-LMS instances with multiple hash functions.");
   }
 
   // Alg. 6. 2.e.
   auto I = slicer.copy<LMS_Identifier>(LMS_IDENTIFIER_LEN);
   // Alg. 6. 2.f.
   auto lms_root = slicer.copy<LMS_Tree_Node>(lms_params.m());
 
   return LMS_PublicKey(std::move(lms_params), std::move(lmots_params), std::move(I), std::move(lms_root));
}
 
std::vector<uint8_t> LMS_PublicKey::to_bytes() const {
   // clang-format off
   return concat<std::vector<uint8_t>>(
      store_be(lms_params().algorithm_type()),
      store_be(lmots_params().algorithm_type()),
      identifier(),
      m_lms_root);
   // clang-format on
}
 
LMS_PublicKey::LMS_PublicKey(LMS_Params lms_params,
                             LMOTS_Params lmots_params,
                             LMS_Identifier I,
                             LMS_Tree_Node lms_root) :
      LMS_Instance(std::move(lms_params), std::move(lmots_params), std::move(I)), m_lms_root(std::move(lms_root)) {
   BOTAN_ARG_CHECK(identifier().size() == LMS_IDENTIFIER_LEN, "Invalid LMS identifier");
   BOTAN_ARG_CHECK(m_lms_root.size() == this->lms_params().m(), "Invalid LMS root");
}
 
size_t LMS_PublicKey::size(const LMS_Params& lms_params) {
   return sizeof(LMS_Algorithm_Type) + sizeof(LMOTS_Algorithm_Type) + LMS_IDENTIFIER_LEN + lms_params.m();
}
 
LMS_Signature LMS_Signature::from_bytes_or_throw(BufferSlicer& slicer) {
   size_t total_remaining_bytes = slicer.remaining();
   // Alg. 6a 1. (next 4 bytes are checked in LMOTS_Signature::from_bytes_or_throw)
   if(total_remaining_bytes < sizeof(LMS_Tree_Node_Idx)) {
      throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
   }
   // Alg. 6a 2.a.
   auto q = load_be<LMS_Tree_Node_Idx>(slicer.take<sizeof(LMS_Tree_Node_Idx)>());
 
   // Alg. 6a 2.b.-e.
   auto lmots_sig = LMOTS_Signature::from_bytes_or_throw(slicer);
   LMOTS_Params lmots_params = LMOTS_Params::create_or_throw(lmots_sig.algorithm_type());
 
   if(slicer.remaining() < sizeof(LMS_Algorithm_Type)) {
      throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
   }
   // Alg. 6a 2.f.
   auto lms_type = load_be<LMS_Algorithm_Type>(slicer.take<sizeof(LMS_Algorithm_Type)>());
   // Alg. 6a 2.h.
   LMS_Params lms_params = LMS_Params::create_or_throw(lms_type);
   // Alg. 6a 2.i. (signature is not exactly [...] bytes long)
   if(total_remaining_bytes < size(lms_params, lmots_params)) {
      throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
   }
 
   // Alg. 6a 2.j.
   auto auth_path = slicer.copy<LMS_AuthenticationPath>(lms_params.m() * lms_params.h());
 
   return LMS_Signature(q, std::move(lmots_sig), lms_type, std::move(auth_path));
}
 
LMS_PublicKey::LMS_PublicKey(const LMS_PrivateKey& sk) : LMS_Instance(sk), m_lms_root(sk.lms_params().m()) {
   lms_treehash(StrongSpan<LMS_Tree_Node>(m_lms_root), std::nullopt, std::nullopt, sk);
}
 
bool LMS_PublicKey::verify_signature(const LMS_Message& msg, const LMS_Signature& sig) const {
   if(lms_root().size() != lms_params().m()) {
      // LMS public key (T[1] part) has unexpected length
      return false;
   }
   if(lms_params().algorithm_type() != sig.lms_type()) {
      // LMS algorithm type does not match with the signature's
      return false;
   }
   // Alg. 6a 2.g.
   if(lmots_params().algorithm_type() != sig.lmots_sig().algorithm_type()) {
      // LMOTS algorithm type does not match with the signature's
      return false;
   }
   // Alg. 6a 2.i.
   if(sig.q() >= (1ULL << uint64_t(lms_params().h()))) {
      return false;
   }
   // Alg 6. 3.
   std::optional<LMS_Tree_Node> Tc = lms_compute_root_from_sig(msg, sig);
   if(!Tc.has_value()) {
      return false;
   }
   // Alg 6. 4.
   return Tc.value() == lms_root();
}
 
std::optional<LMS_Tree_Node> LMS_PublicKey::lms_compute_root_from_sig(const LMS_Message& msg,
                                                                      const LMS_Signature& sig) const {
   // Alg. 6a 2.c, 2.g
   if(lms_params().algorithm_type() != sig.lms_type() ||
      lmots_params().algorithm_type() != sig.lmots_sig().algorithm_type()) {
      return std::nullopt;
   }
   try {
      const LMS_Params lms_params = LMS_Params::create_or_throw(sig.lms_type());
      const LMOTS_Signature& lmots_sig = sig.lmots_sig();
      const LMOTS_Params lmots_params = LMOTS_Params::create_or_throw(lmots_sig.algorithm_type());
      const LMOTS_K Kc = lmots_compute_pubkey_from_sig(lmots_sig, msg, identifier(), sig.q());
      const auto hash = lms_params.hash();
 
      auto hash_pair_func = get_hash_pair_func_for_identifier(lms_params, identifier());
 
      auto lms_address = TreeAddress(lms_params.h());
      lms_address.set_address(LMS_TreeLayerIndex(0), LMS_Tree_Node_Idx(sig.q().get()));
 
      LMOTS_Public_Key pk_candidate(lmots_params, identifier(), sig.q(), Kc);
      LMS_Tree_Node tmp(lms_params.m());
      lms_gen_leaf(tmp, pk_candidate, lms_address, *hash);
 
      LMS_Tree_Node root(lms_params.m());
 
      compute_root(StrongSpan<LMS_Tree_Node>(root),
                   sig.auth_path(),
                   sig.q(),
                   StrongSpan<const LMS_Tree_Node>(tmp),
                   lms_params.m(),
                   LMS_TreeLayerIndex(lms_params.h()),
                   0,
                   std::move(hash_pair_func),
                   lms_address);
      return LMS_Tree_Node(root);
   } catch(const Decoding_Error&) {
      return std::nullopt;
   }
}
 
size_t LMS_Signature::size(const LMS_Params& lms_params, const LMOTS_Params& lmots_params) {
   return sizeof(uint32_t) + LMOTS_Signature::size(lmots_params) + sizeof(uint32_t) + lms_params.h() * lms_params.m();
}
 
}  // namespace Botan