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

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

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   

Am 05-11-15 um 13:25 schrieb Watson Ladd:
> On Wed, Nov 4, 2015 at 5:50 PM, David McGrew (mcgrew) <[e-mail]> wrote:
>> Hi Watson and Zooko,
>>
>>
>> -----Original Message-----
>> From: Cfrg [mailto:[e-mail]] On Behalf Of Watson Ladd
>> Sent: Wednesday, November 04, 2015 6:48 AM
>> To: Zooko Wilcox-OHearn
>> Cc: [e-mail]; [e-mail]; [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]> 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]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>> --
>> "Man is born free, but everywhere he is in chains".
>> --Rousseau.
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>