12
$\begingroup$

I'm implementing WOTS+ in a new language and I can't seem to wrap my head around the fact that WOTS+ XOR's their input with its mask right before hashing it.

I tried to look for any reasoning but so far haven't found any. In my mind I also can't seem to come up with the logic that would make this more secure. For instance, this source says:

In each iteration, PRF is used to generate a key for F and a bitmask that is XORed to the intermediate result before it is processed by F.

But it doesn't explain why this XOR is so important. Why is there a random mask needed in the first place? As far as I can understand, you are supposed to disclose the mask along with the signature and the message in order to get to the final public key that signed it.

$\endgroup$
11
$\begingroup$

It allows the security of the construction to be reduced to second-preimage-resistance, rather than collision-resistance. This is a significant distinction, since brute force against collision-resistance is $2^{n/2}$ while brute force against second-preimage-resistance is $2^n$. In short, this XOR trick allows signatures/keys in the scheme to be half as long for the same level of security.

It is hard to express why the XOR trick helps the proof, without getting into the weeds. But here is a sketch of how to prove security of a Winternitz-like scheme.

The security reduction $\mathcal{S}$ plays the role of an adversary trying to break second-preimage resistance. It has to provide public keys and signatures to an adversary $\mathcal{A}$ trying to break unforgeability. In the event that $\mathcal{A}$ produces a signature forgery, $\mathcal{S}$ should break second-preimage resistance.

In plain Winternitz, we imagine a hash chain starting at $x_0$ and with $x_i = f(x_{i-1})$. The public key is $x_n$. The reduction $\mathcal{S}$ will guess an index $i^*$ such that $\mathcal{A}$ will ask for a signature value later than $i^*$ in the chain, but will generate a forgery consisting of a value at or before $i^*$ in the chain. If the guess is correct, then we want $\mathcal{S}$ to break second-preimage-resistance of $f$ somehow.

$\mathcal{S}$ is itself trying to break second-preimage-resistance. It will request a first-preimage $a$ and try to find a second preimage with $a' \ne a$ and $f(a) = f(a')$. It needs to incorporate $a$ into the hash chain somehow --- ideally, set $x_{i^*} = a$, so that if the adversary computes a preimage of $x_{i^*+1}$, it will be a second-preimage of $a$.

But if $x_{i^*}=a$, then what are $x_0, \ldots, x_{i^*-1}$ such that $x_i = f(x_{i-1})$? The reduction $\mathcal{S}$ can't make a consistent chain. It receives $a$ externally and would need to compute a preimage of $a$.

However, if we augment the scheme in the style of W-OTS+, we have additional $r_i$ values and $x_i = f(x_{i-1} \oplus r_{i-1})$. These $r_i$ values allow the reduction to "patch things together."

The reduction $\mathcal{S}$ chooses $x_0$ and computes a forward chain until $x_{i^*}$, as usual. Then it receives $a$ externally, and chooses $r_{i^*}$ so that $r_{i^*} \oplus x_{i^*} = a$. This means that the input into the next $f$ is $a$. This means that to make a forgery, $\mathcal{A}$ would have to find a preimage to go with $a$. From this point, the rest of the chain is computed normally.

So, the extra XOR just gives the reduction extra flexibility to insert a "trap" into the hash chain --- ensuring that a particular $a$ is used as input to $f$ in the chain, even when the reduction algorithm $\mathcal{S}$ didn't itself choose $a$. And this is exactly what's needed to reduce the signature security to second-preimage resistance.

$\endgroup$
  • 2
    $\begingroup$ Nice answer Mikero. Two interesting illustrations IMHO of the "XOR vs XOR-less" discussion are the hash-based schemes SPHINCS+ and Gravity-SPHINCS, similar at a high-level, but different in their use (or lack thereof) of masks: - Gravity-SPHINCS removes the XOR trick, thus relying on collision-resistance (see ia.cr/2017/933, sec. 3.4). - SPHINCS+ uses WOTS+ unchanged, thus relies on (second) preimage-resistance. There are discussions on whether it makes it makes much of a difference in a quantum world to use one assumption or the other, and as far as I know there is no consensus yet. $\endgroup$ – Thomas Prest Dec 10 '18 at 11:24
  • $\begingroup$ @ThomasPrest I've read the discussion. You mean this one? csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/… By the way I'm marking the answer as valid today, just need some time to read :) $\endgroup$ – peterwilli Dec 10 '18 at 13:01
  • $\begingroup$ Yes, your link is indeed a part of the ongoing discussion :-) (Second-)preimage search enjoys a quadratic speed-up over quantum computers due to Grover's algorithm. For collisions, the speed-up is more limited, and... more debated in some cases (see this recent article on the topic: ia.cr/2017/847 and a follow-up post: blog.cr.yp.to/20171017-collisions.html). But I wouldnt be surprised if the situation evolves in the next years (we still hardly begin to understand quantum computers). $\endgroup$ – Thomas Prest Dec 10 '18 at 15:18
  • $\begingroup$ Maybe I'm too stupid to understand this answer despite the fact I read it carefully like 3 times. So how can an adversary break a plain hash chain with $2^{n/2}$ tries, isn't he need to calculate preimages to begin with which is already takes $2^n$ tries? $\endgroup$ – Calmarius Aug 14 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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