3
$\begingroup$

I was reading about SPHINCS which uses layers of WOTS+ trees and a bottom layer of HORST trees. HORST is a few time signature scheme, using a selection function you can sign at least twice without compromising security.

I was then reading this blogpost where for the description of SPHINCS says:

Signing the same message again should use the same HORST, signing two different messages should make use of two different HORST with good probabilities.

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?

$\endgroup$
5
$\begingroup$

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme.

Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message).

But yes, if we assume that a signer doesn't decide to do this, you are correct; signing the same message twice will produce the same signature.

Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?

I'm not sure what a 'replay attack' would mean for a signature algorithm. For any signature algorithm, the adversary can take a message and valid signature pair, and present it multiple times; the verification algorithm would accept it every time; this is not unique to Sphincs. Now, there may be other things in the protocol to reject this situation; that's not the job of the signature verification algorithm.

In addition, seeing the same signature multiple times would inform the adversary that the same message was being signed multiple times; on the other hand, we don't assume that signature algorithms provide privacy, and so that is also not considered an issue.

BTW: if you look at Sphincs+, things change; they made the signature algorithm nondeterministic (not because they are afraid of determinism, but instead to try to avoid relying on collision resistance of the hash function; everything else within Sphincs+ relies on preimage or second preimage resistance).

$\endgroup$
  • $\begingroup$ You are right about the replay attack, for example you can just include a nonce in the message. Thanks for answering $\endgroup$ – bomberb17 Feb 11 at 19:42
  • $\begingroup$ if you understand how hash-based signature work, you quickly see that to sign something there is no complicated formula involved: you just reveal some hashes. The danger is to re-use hashes that have already been revealed. $\endgroup$ – David 天宇 Wong Feb 12 at 0:07
  • 1
    $\begingroup$ @David天宇Wong: to be more precise, what you need to avoid is allowing someone else generate a valid signatures using only hashes that you have already revealed. $\endgroup$ – poncho Feb 12 at 0:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.