HSS-LMS Signature Algorithm Implementation#3716
Conversation
c19b7a4 to
9516b5c
Compare
|
This PR is now ready! Any review is welcome ❤️ |
reneme
left a comment
There was a problem hiding this comment.
No full review at all. Mainly just looked at the stuff in src/lib/utils.
| template <concepts::contiguous_strong_type TreeNode, | ||
| concepts::strong_span AuthPathSS, | ||
| concepts::tree_node_index TreeNodeIndex, | ||
| concepts::tree_layer_index TreeLayerIndex, | ||
| typename Address> | ||
| requires concepts::tree_address<Address, TreeLayerIndex, TreeNodeIndex> | ||
| inline void treehash( | ||
| StrongSpan<TreeNode> out_root, | ||
| std::optional<AuthPathSS> out_auth_path, | ||
| std::optional<TreeNodeIndex> leaf_idx, | ||
| size_t node_size, | ||
| TreeLayerIndex total_tree_height, | ||
| uint32_t idx_offset, | ||
| concepts::tree_hash_node_pair<TreeNodeIndex, TreeLayerIndex, Address, StrongSpan<TreeNode>> auto node_pair_hash, | ||
| concepts::tree_gen_leaf<TreeNodeIndex, TreeLayerIndex, Address, StrongSpan<TreeNode>> auto gen_leaf, | ||
| Address& tree_address) { |
There was a problem hiding this comment.
😲
Any chance we could wrap that into a reasonable class that removes some complexity from this interface? Off the top of my head, I don't know enough to give useful suggestions. Though, on first glance, that seems like a nightmare to use and/or understand.
Can we go through the usage of this in a pair-programming session at one point please?
There was a problem hiding this comment.
Yeah, I admit that this construct looked much better in my head. The goal of this template hell is that the calling party only calls this function with its own strong types while all types of treehash are deduced automatically without the need to pass any template parameters. But yeah, I would love to get your input on this in a pair-programming session!
randombit
left a comment
There was a problem hiding this comment.
Started a review. I haven't gotten into the core implementation yet so this is just some initial comments, I will do a full review asap.
This comment was marked as outdated.
This comment was marked as outdated.
Sorry, something went wrong.
This comment was marked as outdated.
This comment was marked as outdated.
Sorry, something went wrong.
This comment was marked as outdated.
This comment was marked as outdated.
src/lib/pubkey/hss_lms/lms.cpp
Outdated
| throw Decoding_Error("Unsupported LMS algorithm type"); | ||
| } | ||
| throw Decoding_Error("Unsupported LMS algorithm type"); |
There was a problem hiding this comment.
Please use unique error messages: If you see one of those in some bug report log, you'll want to know which code path was taken.
There was a problem hiding this comment.
... same below, for the hash functions.
This comment was marked as outdated.
This comment was marked as outdated.
Sorry, something went wrong.
|
rebased to current master |
|
I force pushed the changes here, to:
|
|
#3869 is approved; I'll review LMS after this is rebased post merge |
Done. I merged #3869 and rebased. No history rewrite was done. |
randombit
left a comment
There was a problem hiding this comment.
Various small comments/questions but overall lgtm
| * @return The LMS public key. | ||
| * @throws Decoding_Error If parsing the public key fails. | ||
| */ | ||
| static LMS_PublicKey from_bytes_or_throw(BufferSlicer& slicer); |
There was a problem hiding this comment.
This is an internal API so maybe doesn’t matter that much but passing a BufferSlicer as a parameter feels very odd to me. I would think you would just pass a span and then as required construct a BufferSlicer to perform your parsing.
There was a problem hiding this comment.
I agree that we can pass a span here instead. This would be suitable but inconsistent with signature parsing, where passing the slicer is quite sensible (see below). I have no hard feelings for both options.
There was a problem hiding this comment.
Perhaps my two cents; talking from experience in #4024: I totally agree, that any loosely coupled API shouldn't pass around BufferSlicer or BufferStuffer references. Though, for tightly coupled internal APIs (e.g. utility functions in the same compilation unit), I find this very much convenient.
Accepting a span, as @randombit suggested, has the drawback that the caller must know how many bytes the callee will want to consume or emit. Usually, that can be determined, but it typically requires some extra calculations that were already done to determine the overall size of the final serialized structure. Just passing the Buffer*** reference and trusting that the callee will be responsible, is saving some cycles and also noise in the code.
That said: We should always remember to validate that the Buffer*** is full/empty when expected at the very end of the marshalling, to check that everything checked out as expected.
c299e55 to
fe90321
Compare
|
Rebased to fix conflicts on master (likely introduced by merging #3933). |
e82658a to
5f1db48
Compare
cc8845d to
10ec77a
Compare
reneme
left a comment
There was a problem hiding this comment.
Just a few ad-hoc remarks. Will go through the implementation one final time tomorrow.
reneme
left a comment
There was a problem hiding this comment.
Still didn't find time for another full review pass. But no general objection to merging this from my side.
Some cleanup and addition of common utility functions Co-authored-by: Philippe Lieser <philippe.lieser@rohde-schwarz.com> Co-authored-by: René Meusel <rene.meusel@rohde-schwarz.com>
Implementation of the Hierarchical Signature System (HSS) with Leighton-Micali Hash-Based Signatures (LMS). Based on RFC 8554. Co-authored-by: Philippe Lieser <philippe.lieser@rohde-schwarz.com> Co-authored-by: René Meusel <rene.meusel@rohde-schwarz.com>
Integration into pk_algs, tests and documentation. Co-authored-by: Philippe Lieser <philippe.lieser@rohde-schwarz.com> Co-authored-by: René Meusel <rene.meusel@rohde-schwarz.com>
Pull Request Dependencies
Description
This is adding the Hierarchical Signature System (HSS) with Leighton-Micali Hash-Based Signatures (LMS) as defined in RFC 8554.
The first commit (9dddcf6) contains some preparations, mainly common utility functions, and minor cleanup. HSS-LMS is implemented in the second commit (ba36c5e).
For this algorithm, we tried to find a way to generalize the logic to construct a Merkle tree, which is used in all hash-based signature algorithms so far. We introduce the tree_hash.h containing a generalized (and highly flexible) logic for creating Merkle trees. We only apply it for HSS-LMS in this PR but aim to apply it for (at least) SPHINCS+ in a follow-up PR.
If you are interested, you can drop some comments and suggestions.
#3105