Subject: Re: [Cfrg] irsg review of draft-mcgrew-hash-sigs-12

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 4 Sep 2018 03:43:47 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Stephen Farrell
> Sent: Wednesday, August 29, 2018 9:20 AM
> To: [email-masked]
> Cc: [email-masked]
> Subject: [Cfrg] irsg review of draft-mcgrew-hash-sigs-12
> 
> 
> Hiya,
> 
> This is a nice piece of work, thanks.
Thank you.

> I've a few comments and a bunch of nitty
> things below. From the comments, I'd say that only #1 and #5 really need to
> be resolved before publication, the others (and the nits) aren't the kind of
> thing that ought block progress. (And it could well be that neither #1 nor #5
> really need changes too of course - I do often get things wrong:-)
> 
> Cheers,
> S.
> 
> (1) Shouldn't there be a section like the one in XMSS? [1] If the authors were
> ok with adding something like that, I think that'd be good. Given the earlier
> discussion on the CFRG list that resulted in [1], I'd say the RG ought be asked
> if they no longer think that kind of thing is needed, if the draft is to be
> published as-is.
> 
> 	[1] https://tools.ietf.org/html/rfc8391#section-1.1

Ok, I put it in there.  As LMS shares the same strengths and weaknesses as XMSS, everything in the XMSS section is applicable to LMS; I just copied and pasted.

> 
> (2) Is defining a separate one-time LM-OTS mechainism, as if it could be used
> in isolation, (in section 4) really worthwhile? I'm not sure there are
> applications for that.  If we're really only interested in signature schemes that
> can emit multiple signatures, then I think not presenting this as if it could be
> used alone could be a good idea. (Even if exactly the same thing is defined as
> an internal mechanism.) That said, I do really like the presentation in 4.1 so
> am not asking to change that much, just to say that it's not independently
> useful.  I guess what I dislike is the 1st column of table 1 that gives the
> impression these are usable signature mechanisms, and the IANA registry for
> OTS signature schemes (table 3). This needn't get in the way of publication
> though.

Whether LM-OTS is an independently usable mechanism is something that has changed over time; in the earlier versions of the drafts, it was.  Currently, we don't specify that it is (largely because, just like you, we don't see that as a very useful primitive outside of LMS); the current text attempts to reflect that.

On the other hand, we do need the IANA registry for it, because it does occur within LMS, and it does have multiple possible settings.  Now, we could have an integrated space that specified both the LM-OTS and LMS settings; however, that'd be an non-interoperable change, and as there are multiple implementations now, I would not like to do that.

> 
> (3) As an editorial comment, section 6 isn't near as clear as section 5 for this
> reader - 5 was really well described, but I found 6 quite confusing. If it were
> possible to improve that, that'd be great. I think describing HSS by saying that
> the private keys from the leaves of the parent tree are used to sign the root
> of the child trees would have helped me a lot. (Assuming that the picture on
> slide 19 of [2] illustrates what's going on with HSS, but without introducing
> the reservation idea.) See also the specific nitty comments on section 6
> below. All that said, while it took me a while to understand the text in section
> 6, I did eventually, and I guess an implementer would also, so publication
> without changing this would be ok.

Ok, I tried adding this text near the top of section 6:

    In HSS, we have a
   sequence of L LMS trees, where the public key for each LMS tree is
   signed by one of the leaves of the next LMS tree (and the public key
   of the last tree is effectively the public key for the entire HSS
   system).  For example, if we have a three level hierarchy (L=3), then
   we have:

      One LMS tree (level 2 in the notation we'll use below) that signs
      the message

      A second LMS tree (level 1) that signs the public key for the
      level 2 LMS tree

      A third LMS tree (level 0) that signs the publi key for the level
      1 LMS tree

   The root of the level 0 LMS tree is contained in the HSS public key.

   To verify the LMS signature, we would verify all the signatures:

      We would verify that the level 1 LMS public key is correctly
      signed by the level 0 signature.

      We would verify that the level 2 LMS public key is correctly
      signed by the level 1 signature.

      We would verify that the message is correctly signed by the level
      2 signature.

   We would accept the HSS signature only if all the signatures
   validated.

   During the signature generation process, we sign messages with the
   lowest (level L-1) LMS tree.  Once we have used all the leafs in that
   tree, we would discard it, generate a fresh LMS tree, and sign it
   with the next (level L-2) LMS tree (and when that is used up,
   recursively generate and sign a fresh level L-2 LMS tree.

Do you think that this overview (in addition to the more detailed description already in the draft) is a help?

> 
> (4) There's a lack of guidance as to what is mandatory to implement.  The
> only thing you really say along those lines is that "implementations MUST
> support HSS" with L=1. I think it'd be better if you picked (exactly!) one LMS
> option and said that that was MTI. That's just my opinion and I guess the RG
> were ok with not being that specific, so this oughtn't hold up publication if
> the RG are still ok with that and/or the authors really don't wanna pick one.
> OTOH, pretty much every CFRG RFC that has more than one choice causes
> debate in IETF WGs when it comes time to use those, so if picking one was
> doable, that'd be a fine thing to do I reckon.

That has not been a topic that's come up, either between us, nor on the mailing list.

I don't personally feel comfortable in mandating something without discussing it first.  Does anyone else what to chime in?  Should we mandate that a verifier be able to recognize anything in the draft (which isn't all that many options currently)?

> 
> (5) The IANA registries seem a bit odd: why no HSS registry?

Because there are no HSS-specific opaque values.  The only HSS-specific field in the public key/signature is the L value, which is a small integer (which obviously needn't be registered with IANA)

> Why are the
> code points for the two registries contiguous?

Combination of coincidence and historic accident.

Originally, we had both N=32 and N=16 parameter sets; for some reason, in the -04 version of the draft, the LM-OTS N=32 parameter sets came first (and were assigned values 1 through 4), and in LMS the N=16 parameter sets came first (being assigned values 1 through 4, with the N=32 parameter sets being assigned values 5 through 8).  In the next version of the draft, we removed the N=16 parameter sets (as they weren't quantum-safe), but left the N=32 assigned values the same, giving the structure you see.

> What if IANA are asked to
> register a value of 0x00000005 for the LM-OTS registry?

That would not be an issue at all.  The LMS and LM-OTS registries are separate name-spaces; when parsing a public key or signature, we always know which we are dealing with, and so there are no issue if the same value is given different meanings to the different registries.

> 
> nits
> 
> 
> - 3.3 - too many options, as always :-(

Sigh...  However, there is one saving grace that not many other cryptoalgorithms share; no matter which set of options the user chooses, the security remains the same.  This is not often true in crypto (e.g. a 1024 bit RSA key doesn't have the same security as a 2048 bit key), however it is true here.  Now, different options given different practical tradeoffs (in terms of performance, signature size, number of signatures per key), however I believe that developers can be trusted to accurately weigh those practical concerns.

> 
> - Algorithm 4a: why call out the 4 byte min in step 1? I bet there
>   are other encoding checks an implementer would need to do, and just
> including this one might lead someone to not think about which other checks
> are needed to be safe.  I have the same comment on the length checks in
> other places. (Bear in mind that this is a nit though!)

Actually, I believe that all necessary length checks are listed in the pseudocode.  If you spot a counterexample, please tell me.

> 
> - 5.1: the SHOULD for the hash function being the same for LMS and
>   LM-OTS is a bit odd. I can't think of a reason for using different hashes - e.g.
> afaik there's no (and unlikely to be a) legacy LM-OTS implementation that'd
> be used independently of LMS, so I don't see the reason to not have a MUST
> here. (And MUSTs are
> easier:-)

You aren't the first one to ask.  To quote my answer to the previous person:

As for whether we should allow this [allowing different hash functions in LM-OTS and LMS] as an option, well, we've actually changed our minds about that (version -06 did not).  On the other hand, I do not see any specific reason to forbid it; doing so doesn't cause any unexpected cryptographical weaknesses (other than giving the attacker his choice of two different hash functions to attack).

> 
> - section 5 generally - it'd have been nice to see an equivalent
>   of table 1 here.

Don't we have table 2 in section 5?  It doesn't give signature lengths, but the LMS signature length is a function of both the LM-OTS and the LMS parameter set.

> 
> - section 6: Can trees at different levels have different depths?

Yes, if you look at the parameter set recommendations, we include mismatched parameter sets, such as 15/10 (the top tree has h=15, the bottom tree has h=10).

And, yes, they would appear to be a good idea, at least in some settings; which the LMS trees are identical from a cryptographical standpoint, they aren't from a practical ones.  There are certainly valid reasons why someone might want to top-most tree to be larger.

>   I guess so.  It'd be good to be explicit about that. Can trees at the same level
> have different depths?

Hmmm, there's nothing that a verifier can do to make sure that a signer isn't doing it; would just a simple MUST NOT statement be good enough?

> 
> - 6.4: be better if the table on p31 was an actual table, also be
>   good to list the value of N for each.

I made it into a table; however all current parameter sets have N=32.

> 
> - Appendix F: I'm lazy - I didn't check the test vectors:-)

Bad reviewer; no donut :-)

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 5 Sep 2018 01:03:45 +0100

Hiya,

To be clear: the responses below are such that I'm happy
for my IRSG review to be ready-to-publish. (That said, I'm
even happier to chat more about points below.)

On 04/09/18 04:43, Scott Fluhrer (sfluhrer) wrote:
>> -----Original Message----- From: Cfrg <[email-masked]> On
>> Behalf Of Stephen Farrell Sent: Wednesday, August 29, 2018 9:20 AM 
>> To: [email-masked] Cc: [email-masked] Subject: [Cfrg] irsg review
>> of draft-mcgrew-hash-sigs-12
>> 
>> 
>> Hiya,
>> 
>> I've a few comments and a bunch of nitty things below. From the
>> comments, I'd say that only #1 and #5 really need to be resolved
>> before publication, the others (and the nits) aren't the kind of 
>> thing that ought block progress. (And it could well be that neither
>> #1 nor #5 really need changes too of course - I do often get things
>> wrong:-)
>> 
>> Cheers, S.
>> 
>> (1) Shouldn't there be a section like the one in XMSS? [1] If the
>> authors were ok with adding something like that, I think that'd be
>> good. Given the earlier discussion on the CFRG list that resulted
>> in [1], I'd say the RG ought be asked if they no longer think that
>> kind of thing is needed, if the draft is to be published as-is.
>> 
> Ok, I put it in there.  As LMS shares the same strengths and
> weaknesses as XMSS, everything in the XMSS section is applicable to
> LMS; I just copied and pasted.

Cool.

> 
>> 
>> (2) Is defining a separate one-time LM-OTS mechainism, as if it
>> could be used in isolation, (in section 4) really worthwhile? I'm
>> not sure there are applications for that.  If we're really only
>> interested in signature schemes that can emit multiple signatures,
>> then I think not presenting this as if it could be used alone could
>> be a good idea. (Even if exactly the same thing is defined as an
>> internal mechanism.) That said, I do really like the presentation
>> in 4.1 so am not asking to change that much, just to say that it's
>> not independently useful.  I guess what I dislike is the 1st column
>> of table 1 that gives the impression these are usable signature
>> mechanisms, and the IANA registry for OTS signature schemes (table
>> 3). This needn't get in the way of publication though.
> 
> Whether LM-OTS is an independently usable mechanism is something that
> has changed over time; in the earlier versions of the drafts, it was.
> Currently, we don't specify that it is (largely because, just like
> you, we don't see that as a very useful primitive outside of LMS);
> the current text attempts to reflect that.
> 
> On the other hand, we do need the IANA registry for it, because it
> does occur within LMS, and it does have multiple possible settings.

Not sure I agree really but see #5 below.

> Now, we could have an integrated space that specified both the LM-OTS
> and LMS settings; however, that'd be an non-interoperable change, and
> as there are multiple implementations now, I would not like to do
> that.

Understood. OTOH, if we're dealing with a few implementations
and not much deployment, now is a fine time to fix things that
may cause bugs or confusion later.

> 
>> 
>> (3) As an editorial comment, section 6 isn't near as clear as
>> section 5 for this reader - 5 was really well described, but I
>> found 6 quite confusing. If it were possible to improve that,
>> that'd be great. I think describing HSS by saying that the private
>> keys from the leaves of the parent tree are used to sign the root 
>> of the child trees would have helped me a lot. (Assuming that the
>> picture on slide 19 of [2] illustrates what's going on with HSS,
>> but without introducing the reservation idea.) See also the
>> specific nitty comments on section 6 below. All that said, while it
>> took me a while to understand the text in section 6, I did
>> eventually, and I guess an implementer would also, so publication 
> In HSS, we have a sequence of L LMS trees, where the public key for
> each LMS tree is signed by one of the leaves of the next LMS tree
> (and the public key of the last tree is effectively the public key
> for the entire HSS system).  For example, if we have a three level
> hierarchy (L=3), then we have:
> 
> One LMS tree (level 2 in the notation we'll use below) that signs the
> message
> 
> A second LMS tree (level 1) that signs the public key for the level 2
> LMS tree
> 
> A third LMS tree (level 0) that signs the publi key for the level 1
> LMS tree
> 
> We would verify that the level 1 LMS public key is correctly signed
> by the level 0 signature.
> 
> We would verify that the level 2 LMS public key is correctly signed
> by the level 1 signature.
> 
> We would verify that the message is correctly signed by the level 2
> signature.
> 
> lowest (level L-1) LMS tree.  Once we have used all the leafs in
> that tree, we would discard it, generate a fresh LMS tree, and sign
> it with the next (level L-2) LMS tree (and when that is used up, 
> Do you think that this overview (in addition to the more detailed
> description already in the draft) is a help?

That'd have helped me as a reader yes.

>> (4) There's a lack of guidance as to what is mandatory to
>> implement.  The only thing you really say along those lines is that
>> "implementations MUST support HSS" with L=1. I think it'd be better
>> if you picked (exactly!) one LMS option and said that that was MTI.
>> That's just my opinion and I guess the RG were ok with not being
>> that specific, so this oughtn't hold up publication if the RG are
>> still ok with that and/or the authors really don't wanna pick one. 
>> OTOH, pretty much every CFRG RFC that has more than one choice
>> causes debate in IETF WGs when it comes time to use those, so if
>> picking one was doable, that'd be a fine thing to do I reckon.
> 
> I don't personally feel comfortable in mandating something without
> discussing it first.  

Fair point. We should bear in mind though that discussing this
once in CFRG is maybe better than every IETF WG that wants to
use LMS re-doing the discussion but based on less understanding
of the scheme (if, that is, a CFRG discussion results in selecting
one option as MTI).

> Does anyone else what to chime in?  Should we
> mandate that a verifier be able to recognize anything in the draft
> (which isn't all that many options currently)?

I'd argue for a tighter spec than that myself. (Just as one
input.) My take would be to say that LMS_SHA256_M32_H20 with
LMOTS_SHA256_N32_W8 is the only MTI option for signers or
verifiers.

My argument for that is that I think there'll be applications
for which that could work, if one has a key roll-over scheme
(e.g. last N sigs need to sign a new tree root), and that such
roll-over will absolutely be needed by applications so we ought
not allow so many sigs that people decide to not implement any
key roll-over. h=15 might be too shallow but I'd be fine if
that was the one and only MTI; I'd argue against h=25 as the
only MTI as that may be too deep to force implementers to deal
with key roll-over. I picked LMOTS_SHA256_N32_W8 as that has
the shortest sig which I think will be important for getting
any traction but I wouldn't argue against the w=4 variant if
that had some benefits.

And to be clear: picking an MTI here just means that those who
want to use this won't have to, but can if they want, argue
about what's right for their particular situation.

> Because there are no HSS-specific opaque values.  The only
> HSS-specific field in the public key/signature is the L value, which
> is a small integer (which obviously needn't be registered with IANA)

Hmm. Not sure I agree there - would it be wise to accept
and try to verify an L=2^32 HSS signature? What about API
issues for a library that implements private key handling,
how would an application ask for a 20/15 private key? How
about if someone defines a SHA3 based LMS - do verifiers
have to decode into the signature to find that out?

All that said, I don't have the HSS signature format in
my head really, so the above may not really argue for having
HSS codepoints. (Or they may:-) Or maybe it's fine to not
expect the same level of interop for HSS as for LMS? (I'm
not clear if that's considered an important goal or not.)

> 
>> Why are the code points for the two registries contiguous?
> 

Sounds like a potential source of confusion to me.

> 
> Originally, we had both N=32 and N=16 parameter sets; for some
> reason, in the -04 version of the draft, the LM-OTS N=32 parameter
> sets came first (and were assigned values 1 through 4), and in LMS
> the N=16 parameter sets came first (being assigned values 1 through
> 4, with the N=32 parameter sets being assigned values 5 through 8).
> In the next version of the draft, we removed the N=16 parameter sets
> (as they weren't quantum-safe), but left the N=32 assigned values the
> same, giving the structure you see.

Ah, that history wasn't clear. I don't think it needs to be in the
RFC though. It does mean that my comment #5 oughtn't be blocking
though.

> 
>> What if IANA are asked to register a value of 0x00000005 for the
>> LM-OTS registry?
> 
> That would not be an issue at all.  The LMS and LM-OTS registries are
> separate name-spaces; when parsing a public key or signature, we
> always know which we are dealing with, and so there are no issue if
> the same value is given different meanings to the different
> registries.

So maybe make that point in section 8? If for no other reason, it'd
head off a crazy developer with code that branches on just the code
points and not the combo of alg and codepoint?

>> nits

All your answers below seen entirely fine to me, thanks. I do have
an answer for the one where you ask a question.

> Sigh...  However, there is one saving grace that not many other
> cryptoalgorithms share; no matter which set of options the user
> chooses, the security remains the same.  This is not often true in
> crypto (e.g. a 1024 bit RSA key doesn't have the same security as a
> 2048 bit key), however it is true here.  Now, different options given
> different practical tradeoffs (in terms of performance, signature
> size, number of signatures per key), however I believe that
> developers can be trusted to accurately weigh those practical
> concerns.
> 
>> 
>> are other encoding checks an implementer would need to do, and
>> just including this one might lead someone to not think about which
>> other checks are needed to be safe.  I have the same comment on the
>> length checks in other places. (Bear in mind that this is a nit
>> though!)
> 
> Actually, I believe that all necessary length checks are listed in
> the pseudocode.  If you spot a counterexample, please tell me.

Sorry, don't have one. I'd bet a beer though:-)

>> LM-OTS is a bit odd. I can't think of a reason for using different
>> hashes - e.g. afaik there's no (and unlikely to be a) legacy LM-OTS
>> implementation that'd be used independently of LMS, so I don't see
>> the reason to not have a MUST here. (And MUSTs are easier:-)
> 
> As for whether we should allow this [allowing different hash
> functions in LM-OTS and LMS] as an option, well, we've actually
> changed our minds about that (version -06 did not).  On the other
> hand, I do not see any specific reason to forbid it; doing so doesn't
> cause any unexpected cryptographical weaknesses (other than giving
> the attacker his choice of two different hash functions to attack).
> 
>> 
>> - section 5 generally - it'd have been nice to see an equivalent of
>> table 1 here.
> 
> Don't we have table 2 in section 5?  It doesn't give signature
> lengths, but the LMS signature length is a function of both the
> LM-OTS and the LMS parameter set.

Sure. But the sig len is what some readers will want to know.
If you did pick one MTI then you could report on the sig len
for it.

> Yes, if you look at the parameter set recommendations, we include
> mismatched parameter sets, such as 15/10 (the top tree has h=15, the
> bottom tree has h=10).
> 
> And, yes, they would appear to be a good idea, at least in some
> settings; which the LMS trees are identical from a cryptographical
> standpoint, they aren't from a practical ones.  There are certainly
> valid reasons why someone might want to top-most tree to be larger.
> 
>> I guess so.  It'd be good to be explicit about that. Can trees at
>> the same level have different depths?
> 
> Hmmm, there's nothing that a verifier can do to make sure that a
> signer isn't doing it; would just a simple MUST NOT statement be good
> enough?

If that's even needed? The only bad outcomes I can think of are
1) if a verifier assumes uniformity, non-uniform level-i depths
might trigger some bugs and 2) I guess it'd be harder to get
portability (which is not claimed as a goal here).

> Bad reviewer; no donut :-)

Ah, bummer:-)

Cheers,
S.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 5 Sep 2018 01:50:05 +0000

Now, I am just about ready to push out the latest version of the draft; I thought I'd give you some responses before I do so.

> From: Stephen Farrell <[email-masked]>
> Sent: Tuesday, September 04, 2018 8:04 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>; [email-masked]
> Cc: [email-masked]
> Subject: Re: [Cfrg] irsg review of draft-mcgrew-hash-sigs-12
> 
> 
> Hiya,
> 
> >
> >>
> >> (3) As an editorial comment, section 6 isn't near as clear as section
> >> 5 for this reader - 5 was really well described, but I found 6 quite
> >> confusing. If it were possible to improve that, that'd be great. I
> >> think describing HSS by saying that the private keys from the leaves
> >> of the parent tree are used to sign the root of the child trees would
> >> have helped me a lot. (Assuming that the picture on slide 19 of [2]
> >> illustrates what's going on with HSS, but without introducing the
> >> reservation idea.) See also the specific nitty comments on section 6
> >> below. All that said, while it took me a while to understand the text
> >> in section 6, I did eventually, and I guess an implementer would
> >> also, so publication without changing this would be ok.
> >
> > each LMS tree is signed by one of the leaves of the next LMS tree (and
> > the public key of the last tree is effectively the public key for the
> > entire HSS system).  For example, if we have a three level hierarchy
> > (L=3), then we have:
...
> That'd have helped me as a reader yes.

Rereading it, I saw that the beginning organized the levels backwards compared to the rest of the document, so I reworded it.  I believe that the revised text is equally helpful.

> 
> >> (4) There's a lack of guidance as to what is mandatory to implement.
> >> The only thing you really say along those lines is that
> >> That's just my opinion and I guess the RG were ok with not being that
> >> specific, so this oughtn't hold up publication if the RG are still ok
> >> with that and/or the authors really don't wanna pick one.
> >> debate in IETF WGs when it comes time to use those, so if picking one
> >> was doable, that'd be a fine thing to do I reckon.
> >
> Fair point. We should bear in mind though that discussing this once in CFRG is
> maybe better than every IETF WG that wants to use LMS re-doing the
> discussion but based on less understanding of the scheme (if, that is, a CFRG
> discussion results in selecting one option as MTI).
> 
> > Does anyone else what to chime in?  Should we mandate that a verifier
> > be able to recognize anything in the draft (which isn't all that many
> > options currently)?
> 
> LMOTS_SHA256_N32_W8 is the only MTI option for signers or verifiers.

Hmmm, H=20 takes a bit of time to do key generation.  Now, I do know of a trick that allows you to do an effectively smaller H (while still using that parameter set); the verifier doesn't need to know about it.  However, that trick is not currently described in the draft.

> 
> My argument for that is that I think there'll be applications for which that
> could work, if one has a key roll-over scheme (e.g. last N sigs need to sign a
> new tree root), and that such roll-over will absolutely be needed by
> applications so we ought not allow so many sigs that people decide to not
> implement any key roll-over. h=15 might be too shallow but I'd be fine if that
> was the one and only MTI; I'd argue against h=25 as the only MTI as that may
> be too deep to force implementers to deal with key roll-over. I picked
> LMOTS_SHA256_N32_W8 as that has the shortest sig which I think will be
> important for getting any traction but I wouldn't argue against the w=4
> variant if that had some benefits.

I don't believe "key roll over" can work in general (because verifiers might not hear about the key change).  I would recommend HSS with L=2 (with two H=20 trees, that's literally a trillion signatures, which should be enough for almost any application)

> 
> And to be clear: picking an MTI here just means that those who want to use
> this won't have to, but can if they want, argue about what's right for their
> particular situation.

That is the problem with a single MTI; there are a number of different possible applications, each with different requirements.

> Hmm. Not sure I agree there - would it be wise to accept and try to verify an
> L=2^32 HSS signature?

The draft mandates that 1 <= L <= 8.

> What about API issues for a library that implements
> private key handling, how would an application ask for a 20/15 private key?

For my implementation, the application passes two arrays, one of the LM-OTS parameter sets, and one of the LMS parameter sets.

> How about if someone defines a SHA3 based LMS - do verifiers have to
> decode into the signature to find that out?

That'd be encoded in the LM-OTS and the LMS parameter sets.

> 
> All that said, I don't have the HSS signature format in my head really, so the
> above may not really argue for having HSS codepoints. (Or they may:-) Or
> maybe it's fine to not expect the same level of interop for HSS as for LMS?
> (I'm not clear if that's considered an important goal or not.)
> 
> >
> > Originally, we had both N=32 and N=16 parameter sets; for some reason,
> > in the -04 version of the draft, the LM-OTS N=32 parameter sets came
> > first (and were assigned values 1 through 4), and in LMS the N=16
> > parameter sets came first (being assigned values 1 through 4, with the
> > N=32 parameter sets being assigned values 5 through 8).
> Ah, that history wasn't clear. I don't think it needs to be in the RFC though. It
> does mean that my comment #5 oughtn't be blocking though.
> 
> >
> So maybe make that point in section 8? If for no other reason, it'd head off a
> crazy developer with code that branches on just the code points and not the
> combo of alg and codepoint?

The will mention that, however it's more a note to IANA ("you don't have to keep the values disjoint") more than a note to an implementer (which I wouldn't expect to be confused; we never just a code point in a context which makes it unclear which one it is).

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 5 Sep 2018 09:02:12 +0100

Hiya,

Just on one point... (all else seems good)

On 05/09/18 02:50, Scott Fluhrer (sfluhrer) wrote:
>> And to be clear: picking an MTI here just means that those who want
>> to use this won't have to, but can if they want, argue about what's
>> right for their particular situation.

> That is the problem with a single MTI; there are a number of
> different possible applications, each with different requirements.

I disagree. We have seen cases (e.g. [1]) where CFRG RFCs
leaving in options has lead to IETF WGs debating what to do,
over and over. That seems to me to be CFRG's "fault" as it's
predictable and could affect interop.

In this case, picking one MTI would mean that anyone who wants
to use LMS would just adopt that MTI option if it works for
their application. If it doesn't work for them, then they can
pick another option, but might not be able to use any random
implementation.

Separately, the key roll over issue is something that I don't
think need be addressed in this document, but would need to be
addressed in the IETF since there are LMS options that would
definitely need that. I didn't suggest an HSS option as the
MTI because that'd likely have bigger and more computationally
intensive signatures, so seems to me less likely to encourage
adoption.

I do agree with you though that picking an MTI option would
need the RG to debate the topic. I've no idea if people are
in the mood for that.

Cheers,
S.

[1] https://tools.ietf.org/html/rfc8032#section-4

---

From: Martin Thomson <[email-masked]>
Date: Wed, 5 Sep 2018 18:33:13 +1000

> predictable and could affect interop.

I agree with Stephen here. Though that part of the work might be more
difficult, it is also the most valuable. Getting a tool with multiple knobs
is not a net improvement over having no tool at all, and it can lead to
interop failures.

Too many primitives we get are effectively unusable as a result of having
options. The debate around ed25519 use for DKIM is a great example of that.
RSA-PSS is another great example of a tool with too many independent inputs.

Those who find the one option too constraining can take on the extra costs
of breaking new ground. Most should not have to.

---

From: Richard Outerbridge <[email-masked]>
Date: Wed, 5 Sep 2018 04:43:01 -0400

For shore true, butt there’s always the Lord of the Rings risk: ”One ring to rule them all …”
__outer

> On 2018-09-05 (248), at 04:33:13, Martin Thomson <[email-masked]> wrote:
> 
> On Wed, 5 Sep. 2018, 18:03 Stephen Farrell, <[email-masked] <mailto:[email-masked]>> wrote:
> 
> I agree with Stephen here. Though that part of the work might be more difficult, it is also the most valuable. Getting a tool with multiple knobs is not a net improvement over having no tool at all, and it can lead to interop failures.
> 
> Too many primitives we get are effectively unusable as a result of having options. The debate around ed25519 use for DKIM is a great example of that. RSA-PSS is another great example of a tool with too many independent inputs.
> 
> Those who find the one option too constraining can take on the extra costs of breaking new ground. Most should not have to.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "A. Huelsing" <[email-masked]>
Date: Wed, 5 Sep 2018 13:16:51 +0200

May I refer to the XMSS RFC. We were facing the exact same comment by Stephen
(and the schemes are sufficiently similar to compare). Our solution was to ask
every implementation to implement verification for all SHA2-256 parameters. For
signature generation, we only propose three "standard parameter sets" for
specific settings as a default option but do not ask to support any specific
parameter set.

Cheers,

Andreas

Am 05-09-18 um 10:33 schrieb Martin Thomson:
>
>
> On Wed, 5 Sep. 2018, 18:03 Stephen Farrell, <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>
> difficult, it is also the most valuable. Getting a tool with multiple knobs is
> not a net improvement over having no tool at all, and it can lead to interop
> failures.
>
> Those who find the one option too constraining can take on the extra costs of
> breaking new ground. Most should not have to.
>
>
>

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 5 Sep 2018 12:18:14 +0000

*   Too many primitives we get are effectively unusable as a result of having options. The debate around ed25519 use for DKIM is a great example of that. RSA-PSS is another great example of a tool with too many independent inputs.

Agree.  Unless there are simple use-cases that make it easy to pick which knob to use, such as keylength.  Please define one mechanism.

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 5 Sep 2018 12:19:25 +0000

>For shore true, butt there’s always the Lord of the Rings risk: ”One ring to rule them all …”

Shouldn’t that be addressed at the “higher layer” by allow agility?  I mean the protocol is going to have to expose the knobs, negotiate their settings, etc., etc.

---

From: Richard Outerbridge <[email-masked]>
Date: Wed, 5 Sep 2018 14:46:43 -0400

> On 2018-09-05 (248), at 08:19:25, Salz, Rich <[email-masked]> wrote:
> 

The devil is in the details, yes of course.  That’s the problem, surely?
__outer

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 5 Sep 2018 15:56:15 -0500

> Hmmm, H=20 takes a bit of time to do key generation.  Now, I do know of a trick that allows you to do an effectively smaller H (while still using that parameter set); the verifier doesn't need to k…

This calls to mind
https://physicstoday.scitation.org/do/10.1063/PT.6.1.20180822a/full/ , in
which a very long-running and contentious scientific debate was spawned
from the differences in results when one group used an undocumented "neat
trick" to try to speed up the initial stages of the calculation, but that
trick turned out to change the physics.

How risky is it to be using such a trick but leaving it undocumented?

-Ben

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 5 Sep 2018 22:58:11 +0000

> From: Benjamin Kaduk <[email-masked]>
> Sent: Wednesday, September 05, 2018 4:56 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>
> Cc: Stephen Farrell <[email-masked]>; [email-masked]; [email-masked]
> > Now, I am just about ready to push out the latest version of the draft; I
> thought I'd give you some responses before I do so.
> >
> > > > Does anyone else what to chime in?  Should we mandate that a
> > > > verifier be able to recognize anything in the draft (which isn't
> > > > all that many options currently)?
> > >
> > Hmmm, H=20 takes a bit of time to do key generation.  Now, I do know of a
> trick that allows you to do an effectively smaller H (while still using that
> parameter set); the verifier doesn't need to know about it.  However, that
> trick is not currently described in the draft.
> 
> This calls to mind
> from the differences in results when one group used an undocumented
> "neat trick" to try to speed up the initial stages of the calculation, but that

There's no risk to it.

Here's how it works; instead of generating the full LMS tree during key generation, the signer actually generates a smaller tree, and fakes the rest of the authentication path.

Here's a toy example, suppose we had an LMS tree of height 2 (that is, a total of 4 LM-OTS nodes), but the signer needs to sign only two messages.  He could generate the full tree, constructing all 4 LM-OTS public keys, and forming the internal nodes, and use that to sign the two messages.  However, if you look at the two authentication paths he would generate during the signature operation, the second authentication value is constant for all those signatures.  In addition, the right hand of the Merkle tree is used only to compute that authentication value, and nothing else.  So, what the signer could do is not bother generating those nodes in the tree; instead, he picks an arbitrary value to place into that spot in the authentication path, and not actually bother computing the parts of the tree he'll never use.

If you generalize this concept, if the signature has an authentication path of length h (that is, the verifier expects a Merkle tree of height h), and the signer is happy with signing no more than 2**k signatures, it suffices for him to create a height k Merkle tree, and then fill in the rest of the authentication path with h-k random values (actually, it's slightly trickier, as LMS stirs in the node address in each hash; that's not too hard to handle).

This doesn't reduce the security of the signatures in any way; the verifier cannot use those random values to forge, as he would need to find a preimage to those values.  The signer can't use that part of the tree either (as he doesn't know the preimages either), however we assumed he was happy with 2**k signatures, so he doesn't need to.

With this trick, if we make H=20 the sole MTI, and a signer didn't want to take the time to generate more than 2**15 LM-OTS public keys during key generation time, he could use this trick; the cost would be the signatures would be 160 bytes longer (the 5 faked values in the authentication path) than it needed to be.

The verifier would accept these signatures; in fact, it would have no way of detecting if the signer were using this trick.

So, making H=20 the sole MTI would not be a deal breaker.

BTW: this trick would work with XMSS as well...