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

["A.Huelsing" <[e-mail]>]

Am 07-11-15 um 01:29 schrieb Watson Ladd:
>
>
> On Nov 6, 2015 6:49 AM, "A.Huelsing" <[e-mail]
> <mailto:[e-mail]>> wrote:
> >
> > 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)
>
> 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).

> Stateful schemes seem to have a very small range of application.
> >
> > 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
> >
> > Am 05-11-15 um 13:25 schrieb Watson Ladd:
> > > On Wed, Nov 4, 2015 at 5:50 PM, David McGrew (mcgrew)
> <[e-mail] <mailto:[e-mail]>> wrote:
> > >> Hi Watson and Zooko,
> > >>
> > >>
> > >> -----Original Message-----
> > >> From: Cfrg [mailto:[e-mail]
> <mailto:[e-mail]>] On Behalf Of Watson Ladd
> > >> Sent: Wednesday, November 04, 2015 6:48 AM
> > >> To: Zooko Wilcox-OHearn
> > >> Cc: [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> > >> Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-03.txt
> > >>
> > >> On Tue, Nov 3, 2015 at 1:23 AM, Zooko Wilcox-OHearn
> > >> <[e-mail] <mailto:[e-mail]>> wrote:
> > >>> Dear folks:
> > >>>
> > >>> Is there a better way for me to register my objections to this
> scheme
> > >>> 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.
> > > 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.
> > >
> > >> 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.
> > > 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.
> > >> David
> > >>
> > >>> Regards,
> > >>>
> > >>> Zooko
> > >>>
> > >>> _______________________________________________
> > >>> Cfrg mailing list
> > >>> [e-mail] <mailto:[e-mail]>
> > >>> https://www.irtf.org/mailman/listinfo/cfrg
> > >>
> > >>
> > >> --
> > >> "Man is born free, but everywhere he is in chains".
> > >> --Rousseau.
> > >>
> > >> _______________________________________________
> > >> Cfrg mailing list
> > >> [e-mail] <mailto:[e-mail]>
> > >> https://www.irtf.org/mailman/listinfo/cfrg
> > >>
> > >
> > >
> >
>