botan icon indicating copy to clipboard operation
botan copied to clipboard

Published 20 hours ago • verified publisher icon randombit

HSS-LMS Signature Algorithm Implementation

Open FAlbertDev opened this issue 1 year ago • 8 comments

Pull Request Dependencies

  • #3869

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

FAlbertDev avatar Sep 27 '23 10:09 FAlbertDev

Coverage Status

coverage: 91.857% (-0.2%) from 92.028% when pulling 24c8b6c6eb7bcbfa2c430d0658984492c7255cfe on Rohde-Schwarz:pl/lms into bf86f1a9f99aa1fc62f9884d0bda8193fb1d57b7 on randombit:master.

coveralls avatar Sep 28 '23 07:09 coveralls

This PR is now ready! Any review is welcome ❤️

FAlbertDev avatar Sep 29 '23 14:09 FAlbertDev

Thanks again for your review, @reneme! I addressed your suggestions in https://github.com/randombit/botan/pull/3716/commits/a4c5df28bc9126a3f4de5fc3b02ec523863184a4.

FAlbertDev avatar Oct 20 '23 14:10 FAlbertDev

rebased to current master

lieser avatar Oct 31 '23 10:10 lieser

I force pushed the changes here, to:

  1. take advantage of the changes in #3869
  2. squash and clean up the history

reneme avatar Jan 12 '24 08:01 reneme

Thanks for your detailed and comprehensive review, @reneme 👍 I addressed your suggestions in 1f3befe.

FAlbertDev avatar Jan 16 '24 14:01 FAlbertDev

Rebased to (latest) master after #3888.

reneme avatar Jan 17 '24 07:01 reneme

Rebased after the underlying #3869 needed to get conflicts resolved after #3908 was merged. Also, the code here needed minor conflict resolving due to #3908.

reneme avatar Feb 16 '24 15:02 reneme

#3869 is approved; I'll review LMS after this is rebased post merge

randombit avatar Mar 21 '24 17:03 randombit

I'll review LMS after this is rebased post merge

Done. I merged #3869 and rebased. No history rewrite was done.

reneme avatar Mar 21 '24 20:03 reneme

Rebased to fix conflicts on master (likely introduced by merging #3933).

reneme avatar Apr 08 '24 11:04 reneme