Subject: [Cfrg] Alternatives to McGrew's hash based signatures

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Oct 2014 07:28:17 -0700

Dear all,
Recently a rather large team from industry and academia has produced
SPHINCS, a hash based signature scheme claiming stateless security,
and faster signing and verification with smaller signatures at the 128
bit level than has been hitherto achieved.

The paper is https://huelsing.files.wordpress.com/2013/04/eprint_sphincs.pdf.

Before we consider standardizing the McGrew draft, I'd like to know
how these compare and differ. I haven't had the time to do that
thoroughly yet.

Sincerely,
Watson Ladd

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 8 Oct 2014 09:55:20 -0500

Some might find "signatures are 41Kb" a bit of a stopping point.

--  
Principal Security Engineer, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Oct 2014 08:07:19 -0700

> Some might find "signatures are 41Kb" a bit of a stopping point.

Some might find that being unable to use a key if restored from a
backup is a stopping point. But that's what the McGrew draft does.
Maybe we need both.

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 09 Oct 2014 09:41:35 +0100

On 8 October 2014 16:07:19 BST, Watson Ladd <[email-masked]> wrote:
>Some might find that being unable to use a key if restored from a backup is a stopping point. But that's what the McGrew draft does.

Stateful signatures are unpleasant to implement. Difficulties with serialisation/paralellisation, etc.

>Maybe we need both.

Maybe we do: these are different schemes with different sets of desirable properties?

- --
/akr

---

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Thu, 9 Oct 2014 15:54:55 +0000

Hi, thanks for the mention of SPHINCS! I'm one of the authors of
SPHINCS. (Disclaimer: the other authors are the smart ones.)

The reason why I care about SPHINCS is that I would never want to rely
on durable update of mutable state. I come primarily from a
practical/engineering background. I've been doing security audits for
a living (with my company https://LeastAuthority.com). I've also
worked quite a lot in the storage world—databases, filesystems, cloud
storage, etc.

To me, the idea that you have to guarantee that a state update (i.e. a
previously unused sequence number or nonce) is durably written, or
else you leak your private signing key to an attacker… that's a
show-stopper. I disbelieve that any commodity hardware and software in
use today can do that safely.

Regards,

Zooko

---

From: David Leon Gil <[email-masked]>
Date: Thu, 9 Oct 2014 13:51:02 -0400

> use today can do that safely.

I don't think this is out of reach, really; the only trick is writing
the new key
to durable storage before you write the signature. (In fact, I'd write the key
to high-durability/availability distributed storage....wait. :)

(Getting to, say, a 2^-128, or other cryptographically small,
probability of failure
does seem out of reach.)

> Maybe we do: these are different schemes with different sets of desirable properties?

I think these schemes can be hybridized:

Take a stateful hash signature system (say tree-based); but use a small SPHINCS
instance at each leaf node. In that case, the size of the SPHINCS instances
only needs to be large enough for "misuse-resistance", not collision-resistance.
(It seems possible to, instead, embed stateful leaves into a SPHINCS
instance, but
perhaps less convenient unless the leaves are chains.)