SPHINCS: practical stateless hash-based signatures

SPHINCS: practical stateless hash-based signatures(sphincs.cr.yp.to)

32 points by mace 11 years ago | 11 comments

AlyssaRowan 11 years ago |

Saw this on Twitter. Skimread the paper already. First thoughts: This is a nice little construct. 41KB signatures, 1K public keys and 1K private keys, and still relatively speedy - and no state! Glory hallelujah! I thought the notes at CFRG for hash-based signatures were fun but the state of a Merkle signature makes them a pain in the arse to deal with. The possibility to not have to carry around state baggage in a vaguely practical system has really brightened up my evening. I'm going to sit here with some rum and mull over the details.

Not sure I'd pick it above Ed25519 or EdDSA over E-521 today, as it's still kind of big and slow by comparison - but compared to its peers, this looks pretty damn good. (Maybe if quantum-security is important to you, you could also use an NTRUSign variant or another lattice-based technique? But ideal lattice schemes, especially signatures, are still relatively unproven and I'm not particularly comfortable with them right now.)

If I was looking for a signature scheme I needed to last a few decades, I'd at least give this some careful thought to see if it met my needs. (Some time after the rum, of course.)

- - -

No, you can't use this to encrypt anything: signatures only. If you don't know the basic theory, a very quick and dirty primer. (Please correct me if I've flubbed a detail, I've already started on the rum. <g>)

Hash-based signature, all the way back from Lamport [1979]: Alice makes a secret list of b pairs of random numbers (=private key); publishes hashes of each and every number in that list (=public key). Then (perhaps later) Alice hashes message she wants to sign, then for each bit in the hash of the message, proves which bit it is by publishing either the first or second number out of those pairs and throwing the other one away (important). Done. Bob verifies by following the same process but checking, for each bit, that the hash of the number for that bit matches the correct bit (0 or 1) in Alice's public key. Great! Bob can't forge signatures because he's only got the random numbers which form the hashes for the correct signature. Unless someone can second-preimage the hash, this is quantum-secure.

What's the problem with Lamport? Alice only gets to use the key once. If she uses her Lamport key twice or more, she's giving Bob enough information to start having a chance (very quickly an overwhelming chance, especially if Bob gets to choose the messages with an adaptive partial hash preimage attack - i.e. massaging the plaintext to contain partial second-preimage collisions of manageably few bits at a time which are the inverse of Alice's published message hash, which is pretty much the worst-case scenario) to forge her signatures. But if she uses it only once and then throws the others away, that can't happen.

Still, a signature scheme you can only use once is pretty, but irritating. One solution? Bung a Merkle hash tree underneath, very broadly speaking: between the root and the leaves, use that to stretch "one time" into "quite a lot of times". The problem? It's stateful, we need to know where in the tree we are. (Also, we can run out of tree.) The concept of needing to count the xth signature and only being able to sign a maximum of y signatures is counterintuitive for those used to other schemes, such as factoring/discrete-log-based signatures. There has been lots of work since the '70s on extending all that however, and a lot of variations, especially since quantum computers started to be able to count to 16, and maybe one day possibly even as high as 20, or even higher - but so far, all the published relatively-practical hash-based signature schemes I've seen are stateful.

What's good about this new SPHINCS construct? It's stateless. Also the public and private keys, as well as the signatures are both remarkably small for a hash-based signature, and it's also pretty fast considering, thanks to some nice tuning choices and, it seems, using ChaCha12 as a sponge function?

cauterize 11 years ago |

I wonder what led to adding the "Special note to law-enforcement agents" section. A past misunderstanding?

RIMR 11 years ago | |

It's realistic. Most law enforcement officers only have a high-school diploma. It isn't unreasonable to think that they would think that "Eliminate the State" was some kind of anti-american anarchic slogan, or that "Hash" was referring to concentrated marijuana...

Cops are a pretty stupid bunch. Not all of them, but quite unfortunately the majority of them...

wahern 11 years ago | |

Previously the U.S. government enjoyed conflating cryptographic algorithms with munitions.

See http://cr.yp.to/export/status.html

Maybe they were thinking (light heartedly) that a practical post-quantum signature scheme might raise the attention of the government again. So they're giving a shout-out to the legions of governments officials that might find themselves on that page once they whip themselves into a panicked frenzy.

mpyne 11 years ago | |

The page has an anarchist-style logo in the upper left. I suspect that this, in addition to the normal stereotyping of "the authorities" as being clueless with regard to technology, is what led to the jibe.

eatitraw 11 years ago | |

I think it is a joke. The authors are probably anarchists.

jessaustin 11 years ago | | |

It's a pun, but that's all. The plain reading of 'We are not talking about eliminating other types of states. We love most states, especially yours! Also, "hash" is another technical term and has nothing to do with cannabis.' does not indicate a serious commitment to anarchism.

scintill76 11 years ago | | |

Daniel J. Bernstein, who is hosting the page, doesn't seem to be public about his politics, but is probably not an anarchist. Since it's associated with several universities, it is probably just a bit of CYA combined with tongue-in-cheek.

floatboth 11 years ago |

"introduce HORS with trees (HORST)"

Would be much better if the data structure was not trees but something whose name started with the letter E...

pbsd 11 years ago | |

Although not stated anywhere, the name could be an homage to Horst Feistel, one of the most influential cryptographers of the 20th century.

glibgil 11 years ago | |

HORS with ents, HORSE