Subject: [lamps] WGLC comments on draft-ietf-lamps-cms-hash-sig

From: Jim Schaad <[email-masked]>
Date: Sun, 3 Feb 2019 22:03:03 -0800

After having read this document through with the intention of doing WGLC
comments, I did not feel that it is ready for progression.  My comment
follow:

1.  There should not be a reference in the abstract.

2.  The document has at least minimal information on how to use this with
for issuing a certificate on the public key.  This should be noted in the
abstract.

3.  Section 1 - Introduction - I imagine that there is a fixed number of
times that one can use a single ECDSA private key for signature creation.
(My first guess would be Q, but I have never thought about it before.)  It
would be better to describe what the limitation on the number of signatures
is rather than just saying that it is fixed.  "Limited number of signatures"
might be better than "fixed number of signatures"

4.  Section 1 - It is not clear to me that the HSS/LMS signature algorithm
does have small private keys.  In order to be even slightly efficient (and
possibly even correct, I would need to track this down farther), one needs
to keep state about the entire current path as part of the private key.
This does not seem to be small.  If one did recompute the tree every time
then it would not be low computational cost.

5. Section 2.1 - The two sentences in paragraph #2 about what a signed key
is does not seem to jive with my understanding of things or to be really
descriptive.  "Each signed public key is represented by the public key for
that layer of the HSS structure signed by the private key at in the previous
level."  

6. Section 2.1 - Paragraph #3 - You need to specify the type of stand-alone
tree that you are talking about.  My first read on this was a stand along
HSS tree - and that did not make any sense.  Is this really a stand-along
tree or a stand-along signature?

7. Section 2.1 - Are "lms_signature" and "lms_signature_on_message" the same
thing?  If so then they should be named in a consistent manner.

8.  Section 3 - As I am sure I have said before, I would really like to see
an id-alg-hss-lms-hashsig-direct version that omits the extra hash
operation.

9.  Section 4 - I think that you should A) repeat the note that a value of L
represents a stand along LMS tree w/o HSS.  B) Some text about which
lms_public_key is included here.

10.  Section 5 - I am unclear on what the text about having a random string
as part of the hash computation means.  This does not appear to have
anything to do with the actual value of digestAlgorithms so clarity about
what is being said and why it is of importance would be nice

11. Section 6.1 - I don't know what is going to happen with this, but EKR
has raised a big stink for the OSCORE document about the idea that one can
reliably save state of the keys 

12.  Section 6.1 - I don't think this is exactly what is said in the CFRG
document.  It states that each tree must be generated independently which
may not be read as the same thing as what this paragraph says.

13.  s/sate/state/

14.  Section 6.2 - I am unclear why this is a security consideration for
this document.  This would seem to be better placed as introductory material
rather than here.  There is nothing about what needs to be dealt with as a
potential problem for implementing what is presented here.

15. Appendix A - if you really mean it about id-alg-mts-hashsig then you
should probably add it to the ASN.1 module as "id-alg-mts-hashsig OBJECT
IDENTIFIER ::= id-alg-hss-lms-hashsig"

Jim

---

From: Russ Housley <[email-masked]>
Date: Tue, 5 Feb 2019 13:01:46 -0500

Jim:

Thanks for doing such a careful review.

> 1.  There should not be a reference in the abstract.

Indeed.  Once an RFC number is assigned, it will be easy to replace with "RFC XXXX".  Until then, this approach helps the reader find the right document.

> for issuing a certificate on the public key.  This should be noted in the

I suggest:

   ... In addition, the algorithm identifier and public key
   syntax are provided. ...

> might be better than "fixed number of signatures"

The number depends on the size of the tree used.  I think it is too early in the document to give a way to compute the exact number; however, it might be useful to say:

   ... The HSS/LMS signature algorithm can only be used for a
   fixed number of signing operations.  The number of signing operations
depends upon the size of the tree; each node in the tree is used for
one and only one signing operation. ...

> then it would not be low computational cost.

[HASHSIG] says:

   ... Private keys can be made very small by appropriate key
   generation, for example, as described in Appendix A. ...

And, Appendix A computes the private key using a Hash function.  So, if SHA-256 is used, the private key is 256 bits.

> that layer of the HSS structure signed by the private key at in the previous

I do not think it is wrong, and I am not sure what is unclear to you.  I offer different words to see if this work better:

   An HSS signature as specified in [HASHSIG] carries the number of
   signed public keys (Nspk), followed by that number of signed public
   keys, followed by the LMS signature as described in Section 2.2.  The
   public key for the top-most LMS tree is the public key of the HSS
   system.  The LMS private key in the parent tree signs the LMS public
   key in the child tree, and the LMS private key in the bottom-most
   tree signs the actual message. The signature over the public key and
   the signature over the actual message are LMS signatures as described
   in Section 2.2.

> tree or a stand-along signature?

It really is a stand alone HSS tree; a tree with no children.  Is this more clear?

   The elements of the HSS signature value for a stand-alone tree (a top

> thing?  If so then they should be named in a consistent manner.

Yes.  Fixed in my edit buffer.

> an id-alg-hss-lms-hashsig-direct version that omits the extra hash

As I have said before, the processing in RFC 5652 assumes that a signature is applied to a message digest.  How would you describe the processing in this document?

> lms_public_key is included here.

It is a stand alone HSS tree when L = 1.  I will add that,  Regardless, it contains the public key for the top-most LMS tree.

> what is being said and why it is of importance would be nice

See Section 4.5 in [HASHSIG].  Step 4 says:

     4. set C to a uniformly random n-byte string

And then, it gets passed along in the signature value itself:

      6. return u32str(type) || C || y[0] || ... || y[p-1]

> reliably save state of the keys 

The implementation needs to pay attention.  An HSM makes this easier.

> may not be read as the same thing as what this paragraph says.

Yes.  Corrected:

   When generating a LMS key pair, an implementation must generate each
   key pair independently of all other key pairs in the HSS tree.

> 13.  s/sate/state/

Fixed in my edit buffer.

> potential problem for implementing what is presented here.

Moved to Section 1.3, Algorithm Considerations.

> IDENTIFIER ::= id-alg-hss-lms-hashsig"

Good idea.

Russ

---

From: Tim Hollebeek <[email-masked]>
Date: Tue, 5 Feb 2019 19:26:43 +0000

> > 11. Section 6.1 - I don't know what is going to happen with this, but
> > EKR has raised a big stink for the OSCORE document about the idea that
> > one can reliably save state of the keys
> 

Indeed.  We're working with our HSM partners to incorporate these 
algorithms into their products in a foolproof way.  It requires a little
bit of care but it isn't rocket science.

-Tim

---

From: Jim Schaad <[email-masked]>
Date: Tue, 5 Feb 2019 11:29:01 -0800

> -----Original Message-----
> From: Russ Housley <[email-masked]>
> Sent: Tuesday, February 5, 2019 10:02 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; SPASM <[email-masked]>
> Subject: Re: [lamps] WGLC comments on draft-ietf-lamps-cms-hash-sig
> 
> Jim:
> 
> Indeed.  Once an RFC number is assigned, it will be easy to replace with
"RFC
> XXXX".  Until then, this approach helps the reader find the right
document.

Perhaps this paragraph from the id-nits draft should be changed in that
case.

  An Abstract should be complete in itself, so it should contain no
   citations unless they are completely defined within the Abstract.
   Abbreviations appearing in the Abstract should generally be expanded
   in parentheses.  There is a small set of reasonable exceptions to
   this rule; for example, readers don't need to be reminded of what
   "IP" or "TCP" or "MIB" means.  In the end, therefore, this is a
   judgment call, but please err on the side of explicitness.

(I am only ragging you on this because you are the last listed author.)

> 
> > 2.  The document has at least minimal information on how to use this
> > with for issuing a certificate on the public key.  This should be
> > noted in the abstract.
> 
> I suggest:
> 

Looks good.

> 
> > 3.  Section 1 - Introduction - I imagine that there is a fixed number
> > of times that one can use a single ECDSA private key for signature
creation.
> > (My first guess would be Q, but I have never thought about it before.)
> > It would be better to describe what the limitation on the number of
> > signatures is rather than just saying that it is fixed.  "Limited number
of
> signatures"
> The number depends on the size of the tree used.  I think it is too early
in the
> document to give a way to compute the exact number; however, it might be
> useful to say:
> 
> depends upon the size of the tree; each node in the tree is used for one
and
> only one signing operation. ...

You are saying that you don't think a way should be given to compute the
exact number and then you go ahead and give a formula which is both
technically accurate and wrong from the point of view of a CMS signature
usage.  From that point of view the count is the number of leaves in the
tree.  I think up to the semi-colon is sufficient.

> 
> > 4.  Section 1 - It is not clear to me that the HSS/LMS signature
> > algorithm does have small private keys.  In order to be even slightly
> > efficient (and possibly even correct, I would need to track this down
> > farther), one needs to keep state about the entire current path as part
of
> the private key.
> > This does not seem to be small.  If one did recompute the tree every
> > time then it would not be low computational cost.
> 
> [HASHSIG] says:
> 
> And, Appendix A computes the private key using a Hash function.  So, if
SHA-
> 256 is used, the private key is 256 bits.

Sure - but in that case the computation cost on the signature is not small.
You are then going to do a minimum 32 extra hash operations in the signature
computation.  I don't know the effective range of the coef function so I
don't know if that is noise or not.  But if it is noise then I don't know
that I would consider the range of 1000 hash operations to be low
computational cost.

> 
> > 5. Section 2.1 - The two sentences in paragraph #2 about what a signed
> > key is does not seem to jive with my understanding of things or to be
> > really descriptive.  "Each signed public key is represented by the
> > public key for that layer of the HSS structure signed by the private
> > key at in the previous level."
> 
> I do not think it is wrong, and I am not sure what is unclear to you.  I
offer
> different words to see if this work better:
> 

Yes that is clearer.

> 
> > 6. Section 2.1 - Paragraph #3 - You need to specify the type of
> > stand-alone tree that you are talking about.  My first read on this
> > was a stand along HSS tree - and that did not make any sense.  Is this
> > really a stand-along tree or a stand-along signature?
> 

Given that you now define a stand-alone tree that is fine.  It just does not
jive with my idea of a stand-along tree.

> 
> > 7. Section 2.1 - Are "lms_signature" and "lms_signature_on_message"
> > the same thing?  If so then they should be named in a consistent manner.
> 
> > 8.  Section 3 - As I am sure I have said before, I would really like
> > to see an id-alg-hss-lms-hashsig-direct version that omits the extra
> > hash operation.
> 
> As I have said before, the processing in RFC 5652 assumes that a signature
is
> applied to a message digest.  How would you describe the processing in
this
> document?

No it does not assume that.  It assumes that the signature is applied to a
message.  For a signed CMS message with attributes the message that is
signed is the DER encoded attributes.  The fact that the signature operation
does (or does not) apply a hash function internally is not part of CMS it is
part of the signature operation.  The signature function is
sha256-with-RSA-encryption it is not RSA-encryption.   Please remember that
using EdDSA signatures does not have that extra hash operation but signs the
encoded attributes directly.  In section 4.5 of the McGrew document there is
no inherit limitation on the length of "message" as there is with RSA where
the message is limited to the number of bits of the key.

If you say that the hash function needs to be applied before the signature
operation then the following is correct.

IF (signed attributes are absent)
THEN message = content
ELSE  message-digest attributes = Hash(content)
         Message = DER(SignedAttributes)

IF (doing direct)   // or if EdDSA
THEN md = message
ELSE  md = Hash(message)

Sign(md)

You could also skip the set IF statement if you wanted to say that the
function is "Sign(md, Hash)"  In my source code the hash function is not
part of the CMS processing it is part of the cryptographic operation.  Thus
means that I would use "Sign(message)" and forget about the extra hash
operation entirely.

> 
> > 9.  Section 4 - I think that you should A) repeat the note that a
> > value of L represents a stand along LMS tree w/o HSS.  B) Some text
> > about which lms_public_key is included here.
> 
> It is a stand alone HSS tree when L = 1.  I will add that,  Regardless, it
contains
> the public key for the top-most LMS tree.

I think that should be fine.

> 
> > 10.  Section 5 - I am unclear on what the text about having a random
> > string as part of the hash computation means.  This does not appear to
> > have anything to do with the actual value of digestAlgorithms so
> > clarity about what is being said and why it is of importance would be
> > nice
> 

Right, so this would seem to be something that can be said in the security
considerations about the strength of the hash function, but is nothing like
the seeded hash functions of RFC 6210 where a random number was generated as
carried in the parameters area of the hash function.  

> > 12.  Section 6.1 - I don't think this is exactly what is said in the
> > CFRG document.  It states that each tree must be generated
> > independently which may not be read as the same thing as what this
> paragraph says.
> 
> Yes.  Corrected:
> 
> > 14.  Section 6.2 - I am unclear why this is a security consideration
> > for this document.  This would seem to be better placed as
> > introductory material rather than here.  There is nothing about what
> > needs to be dealt with as a potential problem for implementing what is
> presented here.
> 
> > 15. Appendix A - if you really mean it about id-alg-mts-hashsig then
> > you should probably add it to the ASN.1 module as "id-alg-mts-hashsig
> > OBJECT IDENTIFIER ::= id-alg-hss-lms-hashsig"
> 
> Good idea.

Jim

---

From: Jim Schaad <[email-masked]>
Date: Tue, 5 Feb 2019 11:55:05 -0800

> From: Tim Hollebeek <[email-masked]>
> Sent: Tuesday, February 5, 2019 11:27 AM
> To: Russ Housley <[email-masked]>; Jim Schaad
> <[email-masked]>
> Cc: SPASM <[email-masked]>; [email-masked]
> Subject: RE: [lamps] WGLC comments on draft-ietf-lamps-cms-hash-sig
> 
> 

Sure - if you put it into an HSM then this should be fine.  Are you going to
put in a statement that signature creation can ONLY be done from an HSM and
thus it is never to be implemented in software?  

Jim

---

From: Tim Hollebeek <[email-masked]>
Date: Tue, 5 Feb 2019 20:40:16 +0000

Nope - but well designed software APIs can also help.

-Tim

> From: Jim Schaad <[email-masked]>
> Sent: Tuesday, February 5, 2019 2:55 PM
> To: Tim Hollebeek <[email-masked]>; 'Russ Housley'
> <[email-masked]>
> Cc: 'SPASM' <[email-masked]>; [email-masked]
> > > > 11. Section 6.1 - I don't know what is going to happen with this,
> > > > but EKR has raised a big stink for the OSCORE document about the
> > > > idea that one can reliably save state of the keys
> > >
> > algorithms into their products in a foolproof way.  It requires a
> > little bit of care but it isn't rocket science.
> >
> > -Tim
> 
> Sure - if you put it into an HSM then this should be fine.  Are you going
to put
> in a statement that signature creation can ONLY be done from an HSM and

---

From: Jim Schaad <[email-masked]>
Date: Tue, 5 Feb 2019 13:19:23 -0800

Given that what EKR was worrying about was things like - what happens if the
computer crashes between the point where you generate the signature and the
data gets flushed back to the hard disk,  don't think that saying something
like the statement below is going to be satisfactory.  For OSCORE the
document discussed a situation where you were writing back an updated IV
counter that would be "significantly" higher than the last one used for the
purpose of dealing with that delay and it was not considered to be
sufficient by him.

Jim

> Sent: Tuesday, February 5, 2019 12:40 PM
> To: Jim Schaad <[email-masked]>; 'Russ Housley'
> <[email-masked]>

---

From: Russ Housley <[email-masked]>
Date: Tue, 5 Feb 2019 17:32:50 -0500

Jim:

The Security Considerations of [HASHSIG] are pretty clear, and RFC 8391 has a similar security concern when a more in the three get used more than once.

Russ

> On Feb 5, 2019, at 4:19 PM, Jim Schaad <[email-masked]> wrote:
> 
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

---

From: Russ Housley <[email-masked]>
Date: Tue, 5 Feb 2019 17:33:42 -0500

Jim:

Dropping the parts where we reached agreement.

>>> of times that one can use a single ECDSA private key for signature creation.
>>> signatures is rather than just saying that it is fixed.  "Limited number of
>>> signatures" might be better than "fixed number of signatures"
>> 
>> The number depends on the size of the tree used.  I think it is too early in the
>> depends upon the size of the tree; each node in the tree is used for one and

I am saying that at this point in the document, we have not defined all of the variables that are needed to give a formula.  Okay, I'll drop the part after the semi-colon in my proposed text.

>>> farther), one needs to keep state about the entire current path as part of
>>> the private key.
>> SHA-256 is used, the private key is 256 bits.
> 

Using OpenSSL speed, I get these results for SHA-256 and RSA-20148, respectively:

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
sha256           73006.69k   160765.21k   274290.52k   331870.58k   361368.23k

                  sign    verify    sign/s verify/s
rsa 2048 bits 0.000986s 0.000030s   1013.7  33114.4

So, even if one does a 1000 additional hash operations to keep the private key small, I still think it can be characterized as fast.

>> As I have said before, the processing in RFC 5652 assumes that a signature is
>> applied to a message digest.  How would you describe the processing in this
>> document?
> 

I think I get your point. You would like to see an alternative that allows the structure described in Section 3 of RFC 8419.  I would like to hear what other on this list think before I work on it.

> the seeded hash functions of RFC 6210 where a random number was generated
> as carried in the parameters area of the hash function.  

Correct.  The security benefits of the hash structure used are described in the Security Considerations of [HASHSIG].

Russ