Re: [CFRG] [EXTERNAL] pq firmware signing question

[Sophie Schmieg <[e-mail]>]

The SLH-DSA public key is so small because it is the root of a Merkle tree,
with what are essentially other parts of the public key material being part
of the signature. While that construction is necessary for SLH-DSA to work,
you can do the same transform for any digital signature scheme: If (G, S,
V) is a secure signature scheme, and H is a secure cryptographic hash
function, then (G', S', V') where if G creates sk as private and H(pk) as
public key, G' return the same sk as private key, but H(pk) for the public
key. S'(sk, m) is just the concatenation pk || S(sk, m) and V' first
verifies that the hash is indeed the hash of the public key and then
verifies the signature according to V. If you apply this transform to
ML-DSA you get a scheme with the same size for the public key and a
slightly shorter signature compared to SLH-DSA.
The reason to prefer SLH-DSA, especially for firmware signing, is that the
scheme is much more conservative (it has a security reduction to the
security of the used hash function), and that it is far simpler to
implement in hardware (It is just a bunch of hash function calls, which you
need to support for any signature scheme, so you likely already have blocks
for it).

On Mon, Mar 18, 2024 at 9:58 AM Ilari Liusvaara <[e-mail]>
wrote:

> On Mon, Mar 18, 2024 at 03:45:00PM +0000, John Mattsson wrote:
> >
> >   *   The conservative SLH-DSA is security wise quite attractive for
> >       this use case but the keys are a bit big. My hardware people
> >       tells me that they want to keep the amount of burned bytes
> >       small. As ML-DSA is in CNSA 2.0 my feeling is that ML-DSA is
> >       more commercially available. ML-DSA also have better
> >       performance and smaller keys.
>
> It appears that SLH-DSA keys are actually much smaller:
>
> - CNSA 2.0 ML-DSA has 2592 byte public key.
> - AFAICT, SLH-DSA has 64 byte public key.
>
> It is the SLH-DSA signatures that are much larger than ML-KEM
> signatures. However, the retuned sizes below are less than 2.5x the
> 4595 byte ML-DSA signature size.
>
>
> >   *   The private key in trust anchors is typically used a small
> >       amount of times. SLH-DSA tuned for much less than 2^64
> >       signatures is a good fit. The signing speed is almost
> >       irrelevant. The verification speed is important.
>
> Looking at recent paper (eprint 2024/018) on retuning
> SPHINCS+/SLH-DSA:
>
> Category I, 1M signatures
>
> h=18, d=2, a=14, k=12, w=16: Size 4304, cost 968690/762
>
>
> Category III, 1M signatures:
>
> h=24, d=3, a=13, k=16, w=16: Size 9648, cost 890349/1477
>
>
> And 1M signatures seems plenty: To burn through this in a millenia
> takes multiple releases per day (which is extremely fast pace, even for
> single-layer setup).
>
> Advantage of using SPHINCS+ retuned to small number of signatures over
> stuff like XMSS is that there are no state-tracking problems.
>
> However, there is certificational problem here: This will hold, but
> can we get this certified enough?
>
>
>
>
> -Ilari
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg
>


-- 

Sophie Schmieg | Information Security Engineer | ISE Crypto |
[e-mail]