Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-03.txt

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Tue, 3 Nov 2015 06:23:52 +0000

Dear folks:

Is there a better way for me to register my objections to this scheme
than my earlier post to CFRG about it?

Regards,

Zooko

---

From: Watson Ladd <[email-masked]>
Date: Wed, 4 Nov 2015 06:48:07 -0500

> than my earlier post to CFRG about it?

To be clear: This scheme will fail in very nasty, very obvious ways
anytime you have backups of your machine, or restart your VM, or crash
at just the wrong moment.  Proposing it, and expecting it to be used
widely, will inevitably lead to these problems on a mass scale. Is
this really what we want to tell people to use?

>
> Regards,
>
> Zooko
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Wed, 4 Nov 2015 17:46:27 +0000

I believe both draft-mcgrew-hash-sigs and https://datatracker.ietf.org/doc/draft-huelsing-cfrg-hash-sig-xmss/ focus on public key signatures. I might be wrong, but I think they were not envisioned for filesystem integrity. 

For example the MLS-tree hierarchical tree in draft-mcgrew-hash-sigs or the XMSS hierarchical tree could be used to sign FPGA images that are checked for integrity by the FPGA loader before loading the image. But the tree is not updated on the fly as the filesystem changes as in Tahoe-LAFS or elsewhere. The schemes have the advantage of being based on well-studied problems with simple primitives and can be post-quantum secure. 

Another usecase could be in a PKI environment where a public key is verified using the root and the path to the root of the LMS, XMSS (or even SPHINCS) hierarchical tree structure. That would be a replacement of the cert chains we have today. R. Housley introduces these MTS signature algorithms in Cryptographic  Message Syntax https://datatracker.ietf.org/doc/draft-housley-cms-mts-hash-sig 

Can you elaborate a little more where they would fail in public key auth scenarios like the above?

Rgs,
Panos

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Wednesday, November 04, 2015 6:48 AM
To: Zooko Wilcox-OHearn <[email-masked]>
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-03.txt

> than my earlier post to CFRG about it?

To be clear: This scheme will fail in very nasty, very obvious ways anytime you have backups of your machine, or restart your VM, or crash at just the wrong moment.  Proposing it, and expecting it to be used widely, will inevitably lead to these problems on a mass scale. Is this really what we want to tell people to use?

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 4 Nov 2015 09:56:20 -0800

> this really what we want to tell people to use?

I agree.  This is IMO far too fragile to be acceptable for new applications.

It also has problems like this: "I - an identifier for the private
key.  This value is 31 bytes
long, and it MUST be distinct from all other such identifiers."

What security disaster, if any, happens if that isn't the case?

In any case, there are hash-based signatures that don't require
randomness.  Those might be a much better bet for new applications.

--Andy

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Wed, 4 Nov 2015 22:50:02 +0000

Hi Watson and Zooko,

      -----Original Message-----
      From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
      Sent: Wednesday, November 04, 2015 6:48 AM
      To: Zooko Wilcox-OHearn
      Cc: [email-masked]; [email-masked]; [email-masked]
      Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-03.txt

      > than my earlier post to CFRG about it?

      To be clear: This scheme will fail in very nasty, very obvious ways anytime you have backups of your machine, or restart your VM, or crash at just the wrong moment.

Section 10.1 documents some of the concerns that you raise and provides some guidance.  Probably stronger guidance is needed; if you have suggestions, please let us know.

      Proposing it, and expecting it to be used widely, will inevitably lead to these problems on a mass scale.

Hash based signatures are well suited for some applications, such as the long-term protection of firmware that is checked in embedded systems.   In these cases postquantum security is essential, the verifier needs to be compact, and signing is a relatively rare operation.    For other applications they are less well suited.

      Is this really what we want to tell people to use?

Like Winston Churchill said about democracy, they are the worst postquantum secure digital signatures, except for all the others.

For sure the issue of synchronization of state in hash based signatures schemes is a major issue, and there might be scenarios where they will never be appropriate, such as VM environments in which VMs are cloned.   It may be the case that these types of signatures need to have a different interface that would better ensure the security of implementations.   But in any case, given their postquantum security and solid theoretical foundations, they deserve to be studied more to see what their limits are.

David

      > [email-masked]<mailto:[email-masked]>

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Thu, 5 Nov 2015 07:25:27 -0500

On Wed, Nov 4, 2015 at 5:50 PM, David McGrew (mcgrew) <[email-masked]> wrote:
> To be clear: This scheme will fail in very nasty, very obvious ways anytime
> you have backups of your machine, or restart your VM, or crash at just the
> wrong moment.
>
> Section 10.1 documents some of the concerns that you raise and provides some
> guidance.  Probably stronger guidance is needed; if you have suggestions,
> please let us know.
>
> Hash based signatures are well suited for some applications, such as the
> long-term protection of firmware that is checked in embedded systems.   In
> these cases postquantum security is essential, the verifier needs to be
> compact, and signing is a relatively rare operation.

How does the rarity of signing decrease the problems posed by backups?
If anything, embedding implementations into hardware or ROM is likely
to lead to lots of backups of the private key, and any restore will
cause problems. There are workarounds, but they have costs with
reducing the number of possible signatures. Alternatives like SPHINCS
are post quantum secure and do not have this extremely likely failure
mode.

> Like Winston Churchill said about democracy, they are the worst postquantum
> secure digital signatures, except for all the others.
>
> For sure the issue of synchronization of state in hash based signatures
> schemes is a major issue, and there might be scenarios where they will never
> be appropriate, such as VM environments in which VMs are cloned.   It may be
> the case that these types of signatures need to have a different interface
> that would better ensure the security of implementations.   But in any case,
> given their postquantum security and solid theoretical foundations, they
> deserve to be studied more to see what their limits are.

It's not about the security of an implementation, but a deployment.
Back up your computer? You've revealed your secret key. Ensure HVM
failures won't render your hardware unupdatable? You've revealed your
secret key. Does Cisco really think that a single point of failure for
updating firmware is acceptable?

The CFRG is not a CRYPTO reviewer panel. Publishing this draft will
lead to it being used in products.

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Thu, 5 Nov 2015 13:31:27 +0000

Hi Watson,

      -----Original Message-----
      From: Watson Ladd [mailto:[email-masked]]
      Sent: Thursday, November 05, 2015 7:25 AM
      To: David McGrew (mcgrew)
      Cc: Zooko Wilcox-OHearn; [email-masked]; [email-masked]; [email-masked]
      Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-03.txt

      On Wed, Nov 4, 2015 at 5:50 PM, David McGrew (mcgrew) <[email-masked]<mailto:[email-masked]>> wrote:
      > Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
      > <[email-masked]<mailto:[email-masked]>> wrote:
      >> Dear folks:
      >>
      > at just the wrong moment.
      >
      > Section 10.1 documents some of the concerns that you raise and
      > provides some guidance.  Probably stronger guidance is needed; if you
      > have suggestions, please let us know.
      >
      > these cases postquantum security is essential, the verifier needs to
      > be compact, and signing is a relatively rare operation.

It doesn't, as you already know, but rarity of signing makes state synchronization easier.

      If anything, embedding implementations into hardware or ROM is likely to lead to lots of backups of the private key, and any restore will cause problems. There are workarounds, but they have costs with reducing the number of possible signatures.
       Alternatives like SPHINCS are post quantum secure and do not have this extremely likely failure mode.

I agree that stateless signatures are also worth investigating.

      > Like Winston Churchill said about democracy, they are the worst
      > postquantum secure digital signatures, except for all the others.
      >
      > For sure the issue of synchronization of state in hash based
      > signatures schemes is a major issue, and there might be scenarios where they will never
      > given their postquantum security and solid theoretical foundations,
      > they deserve to be studied more to see what their limits are.

      It's not about the security of an implementation, but a deployment.
      Back up your computer? You've revealed your secret key. Ensure HVM failures won't render your hardware unupdatable? You've revealed your secret key. Does Cisco really think that a single point of failure for updating firmware is acceptable?

Like many other vendors, Cisco is looking into postquantum security, including hash based signatures with stateful components.

      The CFRG is not a CRYPTO reviewer panel. Publishing this draft will lead to it being used in products.

This is total BS.  The IRTF chartered CFRG to be a “forum for discussing and analyzing general cryptographic aspects of security protocols, and to offer guidance on the use of emerging mechanisms and new uses of existing mechanisms”.

David

---

From: "A.Huelsing" <[email-masked]>
Date: Fri, 6 Nov 2015 12:49:47 +0100

Hi,

as an author of one of the stateful hash-based signature drafts (XMSS)
and an author of the (stateless) SPHINCS scheme let me share same
comments on the discussion.

Let me start with two general comments:

1. The main reason to use one of these schemes is to achieve
post-quantum security. There exist other proposals that claim to achieve
this but they lack a detailed security analysis (the problems they are
based on aren't well studied, at least for specific parameters or they
have incredibly bad performance). That's the big plus for hash-based
signature schemes: We got proofs that breaking the scheme means breaking
the security of the used hash function and the security of hash
functions is a well understood topic.

2. We are planning to also write an I-D for SPHINCS as soon as we are
done with XMSS. SPHINCS essentially uses XMSS as one of it's main
building blocks, so having a draft for XMSS significantly simplifies
writing one for SPHINCS.

Now coming to your concerns:

It is true that there exists a bunch of scenarios where you should stay
away from stateful schemes as Zooko and Watson mentioned. Usage on
virtual machines is probably the most important one. That was also the
main motivation to develop SPHINCS. However, SPHINCS has two drawbacks:
It's signatures are rather large with 41kB and signing becomes really
slow on resource constrained devices [1]. Although verification time is
not too bad, it is significantly slower than XMSS. That's why it might
be reasonable to use a stateful scheme in such scenarios. Especially on
smart cards and similar resource constrained devices I would clearly
suggest to go for one of the stateful schemes instead of SPHINCS. For
those it is possible to make sure that a signature is only returned
after the new key state was written to NVM, it is also known how to
protect against fault attacks that try to change the stored index: you
can use a forward secure version of XMSS, in that case no information
about previous one-time keys is left on a card. Consequently, such a
fault attack would simply be a DOS attack (given that this requires
direct access to the hardware this could also be achieved easier by an
attacker). There are other, similar scenarios where it is also easily
possible to prevent copies of the secret key. (Note: Only signing (SK)
is stateful, verification (PK) is stateless, I was not sure if this was
clear from some comments)

Summing up: Yes, we should probably put a more visible warning sign into
the drafts to clarify the restrictions and keep people from using a
stateful scheme without being able to protect the secret key in the
required ways. Otherwise, I do not see why we should not publish such an
I-D. Your argument is a bit like: We should not standardize any scheme
where wrong usage implies a break (which means: almost all crypto).   

Cheers,

Andreas

[1] Andreas Hülsing and Joost Rijneveld and Peter Schwabe. ARMed SPHINCS
-- Computing a 41KB signature in 16KB of RAM.
https://eprint.iacr.org/2015/1042

---

From: Watson Ladd <[email-masked]>
Date: Fri, 6 Nov 2015 19:29:22 -0500

> clear from some comments)

Let's consider this further. There is no backup: if you sit on that card,
or put it in the microwave because it's wet and needs to be dried out, the
key dies. So if this card is the only copy of the key needed to update
every router in the world, I doubt anyone is comfortable with that.

Stateful schemes seem to have a very small range of application.
> >> To be clear: This scheme will fail in very nasty, very obvious ways
anytime
> >> Section 10.1 documents some of the concerns that you raise and
provides some
> >> Proposing it, and expecting it to be used widely, will inevitably lead
to
> >> these problems on a mass scale.
> >>
postquantum
> >> given their postquantum security and solid theoretical foundations,
they

---

From: Russ Housley <[email-masked]>
Date: Fri, 6 Nov 2015 20:11:30 -0500

Watson:
> Let's consider this further. There is no backup: if you sit on that card, or put it in the microwave because it's wet and needs to be dried out, the key dies. So if this card is the only copy of the key needed to update every router in the world, I doubt anyone is comfortable with that.
> 
I naive approach to backup could lead to a serious security problem, but there are approach to backup that ensure that tree nodes are not reused.  For example, one could assign a subtree to each of the hardware modules that have the private key.  If one of them fails, then the signature space is lost, but there is not a security failure.

Russ

---

From: "A.Huelsing" <[email-masked]>
Date: Mon, 9 Nov 2015 09:43:17 +0100

Am 07-11-15 um 01:29 schrieb Watson Ladd:
>
>
> On Nov 6, 2015 6:49 AM, "A.Huelsing" <[email-masked]
> <mailto:[email-masked]>> wrote:
> >
> > Hi,
> >
> Let's consider this further. There is no backup: if you sit on that
> card, or put it in the microwave because it's wet and needs to be
> dried out, the key dies. So if this card is the only copy of the key
> needed to update every router in the world, I doubt anyone is
> comfortable with that.
>

Well, that's why you should not simply put a static public key into your
devices but at least two (probably more) and allow for the possibility
to update public keys. Otherwise, imagine what happened if the key is
compromised... Hence, this does not seam to be a reasonable solution
even for stateful schemes (remember, more copies, higher risk of loosing
one).

> > > On Wed, Nov 4, 2015 at 5:50 PM, David McGrew (mcgrew)
> <[email-masked] <mailto:[email-masked]>> wrote:
> > >> Hi Watson and Zooko,
> > >>
> > >>
> > >> From: Cfrg [mailto:[email-masked]
> <mailto:[email-masked]>] On Behalf Of Watson Ladd
> > >> Cc: [email-masked] <mailto:[email-masked]>;
> [email-masked] <mailto:[email-masked]>;
> [email-masked] <mailto:[email-masked]>
> > >> <[email-masked] <mailto:[email-masked]>> wrote:
> > >>> Dear folks:
> > >>>
> > >> Proposing it, and expecting it to be used widely, will inevitably
> lead to
> signatures
> > >>> [email-masked] <mailto:[email-masked]>
> > >> [email-masked] <mailto:[email-masked]>