Re: [Crypto-panel] [CFRG] Can I have a review of draft-fluhrer-lms-more-parm-sets?

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Thank you for your review; I will be gathering together these editorial comments and updating the draft to reflect them.

I do want to make a response to your "whiny suggeston" (not that I would classify it as whiny).  It is not generally true that a truncated SHA-512 would be faster than SHA-256 on a 64 bit processor (unless the message you're signing is long).

Here's why: the SHA-512 hash compression function takes perhaps 50% more time than the SHA-256 hash compression function - however, it processes twice as much input, and so if you are hashing a long message, you end up processing it perhaps 30% faster.  That's fine for hashing long messages - LMS doesn't spend most of its time doing that.  Instead, a large majority of the hashes are done processing the LM-OTS winternitz chains, and the hashes there are carefully crafted to fit within 55 bytes (the most that SHA-256 can hash with a single hash compression call); replacing SHA-256 with SHA-512 would still have each step do a single hash compression call, but that hash compression call would take 50% longer.

Of course, there are a number of other hash functions within the hierarchy; however the LM-OTS are the large majority (unless you happen to pick a tiny W), and so you'll end up spending more time.

The only exception would be the initial message hash - if you are signing a sufficiently long message, then the bulk of the time would be spent during the initial message hash (where the superior bulk message performance of SHA-512 is relevent) - of course, if there were the case, another possibility would be to just hash the message with SHA-512, and then sign the hash using LMS with SHA-256.

> -----Original Message-----
> From: Jon Callas <[e-mail]>
> Sent: Friday, February 12, 2021 9:04 PM
> To: Stanislav V. Smyshlyaev <[e-mail]>
> Cc: Jon Callas <[e-mail]>; [e-mail]; [e-mail];
> Russ Housley <[e-mail]>; Scott Fluhrer (sfluhrer)
> <[e-mail]>
> Subject: Re: [Crypto-panel] [CFRG] Can I have a review of draft-fluhrer-lms-
> more-parm-sets?
> 
> 
> 
> > On Feb 9, 2021, at 9:41 AM, Stanislav V. Smyshlyaev <[e-mail]>
> wrote:
> >
> > Dear Crypto Review Panel members,
> >
> > We would like to ask you to review additional parameter sets for LMS
> defined in https://datatracker.ietf.org/doc/draft-fluhrer-lms-more-parm-
> sets/
> >
> > We have already obtained support from Russ Housley (thanks a lot, Russ!);
> could we ask for one more review?
> >
> 
> Summary:
> 
> It's great, I approve. Two comments follow; one on consistency of
> terminology that I believe is important and a one about algorithm choice that
> I don't expect to be addressed, but I had to make.
> 
> Consistency in Editing:
> 
> In general, the draft uses "SHA256/192" for the truncated SHA256, and
> "SHAKE256-xxx" for a SHAKE hash. That is to say, a slash is used with SHA and
> a hyphen with SHAKE. Sometimes this is inconsistent and it caused me
> consternation when my brain interpreted a slash to mean SHA and a hyphen
> to mean SHAKE. Given that SHAKE starts with SHA and there's lots of 256s
> being thrown around, it's really, really important to get this right, else
> someone's going to make a mistake that will cause tears. I would even
> support something too clever by half like using "SHA" to mean "SHA256/192"
> for further aid to the mildly dyslexic like me. There are also places where
> "SHA256" is written as "SHA-256." For example, Section 6 has all of these
> inconsistencies. Please be consistent.
> 
> Whiny suggestion:
> 
> There's a construction for a variable-length output version SHA512 called
> "SHA512/t" which is documented in <https://eprint.iacr.org/2010/548.pdf>.
> One a 64-bit processor, SHA512 is faster than SHA256, often like 30-40%
> faster. SHA512/t has changes to IVs to give different outputs. Section 3.1 of
> this draft explains why IV changes aren't needed, so this draft could easily
> have an option for a 192-bit truncation of SHA512. I know that at this date, it's
> a big ask and arguably gilding the lily. It might even be a fine thing for another
> document that throws that in, too. It might also be entirely too much to have
> even more options. I was unable to pull my hands back from the keyboard,
> though, because the whole point of this draft is for smaller, faster signatures
> and the performance improvement of SHA512 leaps to mind. If you wanted
> to add that in, I'd smile -- after all, the name of the draft is "more
> parameters." I don't expect it.
> 
> All in all, a nicely done, elegant draft.
> 
> 	Jon