Reconstructing public keys from signatures

One weird hobby of mine is reasonable properties of cryptographic schemes that nobody promised they do or don’t have. Whether that’s invisible salamanders or binding through shared secrets, anything that isn’t just boring IND-CCA2 or existential unforgeability is just delightful material to construct vulnerabilities with.

Normally, with a signature scheme, you have the public key and want to know whether a given signature is valid. But what if we instead have a message and a signature, assume the signature is valid, and want to know which public key signed it? A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.

Chapter 1: ECDSA

This one is so famous it even has it’s own Wikipedia section. In short, yes, it is very much possible to recover a public key from a single valid signature.

An ECDSA signature are two integers $(r, s)$ such that $sR = zG + rP_A$ , where $R$ is one of the two points with x coordinate $r$ . To reconstruct the public key, we can just solve for $P_A$ and get $P_A = r^{-1}sR - r^{-1}zG$ , where we compute $r^{-1}$ as the inverse of $r$ modulo the order of the elliptic curve.

Public key recovered.

Chapter 2: RSA

Here, it gets a bit tricker. Instead of a single signature, we will need two, $s_1$ and $s_2$ , with corresponding messages $m_1$ and $m_2$ . RSA usually will hash a message and then pad it in some way, but we don’t really care about that part here, and assume that $m$ is already this hashed and padded message. The only important property is that in order to be valid, a RSA signature has to fulfill $s^e = m \mod n$ . To achieve this property, the signer has calculated $s = m^d \mod n$ , with $d\cdot e \mod \varphi(n)$ . $e$ is usually 65537, and we will just assume this value and only recover $n$ . We do this by computing $n' = \gcd(s_1^e - m_1, s_2^e - m_2)$ . Note the lack of modulus operation, this is just a raw exponent, and yes, the result will have roughly 65537 times as many digits as the signature, message, or modulus do. The Euclidean Algorithm is just so efficient, it doesn’t care. Well it cares a little, but I still was able to compute this for a 2048 bit public key within just a few minutes. The result isn’t quite equal to $n$ , though, as there is a 1/4 probability that both numbers were even, and 1/9 that both of them were divisible by 3. But $n$ is supposed to have only two, very large prime divisors, so after doing trial division of the first few hundred primes or so, we can be relatively certain that what is left over is the actual public key.

Chapter 3: A slight detour into Schnorr signatures

Before we go into post quantum signature schemes, we should look at one more classical signature scheme, that while not used much in practice (curse you, patents), is going to be very important to understand for PQ schemes. Schnorr signatures are elliptic curve signatures, that use a specific method to transform a zero knowledge proof into a signature scheme, the Fiat-Shamir transform.

For Schnorr, we have the usual setup of an elliptic curve of order $n$ with generator point $G$ , and public key $P_A = x_AG$

The Zero Knowledge protocol works in the following way:

First, the prover commits to some value $R$ . In the case of Schnorr, this is done by choosing a random value $k$ and setting $R = kG$ .

Next, the verifier issues a challenge $c$ .

The prover now reveals $s = k - c\cdot x_A \mod n$ . The verifier can check that $R = sG + cP_A$ .

This proves that the prover knows $x_A$ , as without foreknowledge of the challenge, the proof $s$ cannot be given for a given commitment without knowing it (or having a quantum computer at hand). However, this proof is zero knowledge, since if one knows the challenge beforehand, it is rather easy to come up with the right commitment and proof, while still keeping the commitment uniformly random, by choosing $s$ randomly, and then computing $R' = sG$ , and “committing” to $R = R' + cP_A$ . This will mean that we do not lose security by playing this game multiple times, and an attacker might as well concentrate on key recovery attacks instead.

To convert this zero knowledge protocol into a signature scheme, we replace the challenger with a hash function. In order to ensure that our commitment was actually committed to, we add it to the hash function as well. In other words the signature scheme looks like this:

Choose $k$ randomly. Set $r$ to the x coordinate of $R = kG$ . Compute $c = H(r || m)$ , and set $s = k - c\cdot x_A$ . We now have two variants, either setting the signature to the tuple $(r, s)$ or to the tuple $(c, s)$ .

In the first case, the verifier computes $c = H(r || m)$ and checks that $sG + cP_A$ has x coordinate $r$ , in the second variant, the verifier first computes $sG + cP_A$ , takes the x coordinate and checks that $c = H(r || m)$ .

Both variants are perfectly secure, and in the case of elliptic curves it really does not matter which one is chosen. But now it gets interesting: Whether or not we can recover the public key depends on the variant. If the signature is $(r, s)$ , we can compute $c = H(r || m)$ and perform the same operation as previously on ECDSA, and compute $P_A = c^{-1}R - c^{-1}sG$ . However, if the signature is $(c, s)$ , we have no way of finding $r$ , as it is a random x coordinate with enough entropy in order to make finding a preimage of $c$ impossible.

Chapter 4: Dilithium

And with that, we go to our first post quantum signature scheme. Dilithium really deserves its own full blog post, but since here we are only interested in recovering public keys, we can simplify it quite a bit. Recall that for a learning with errors scheme, the public key is a vector $t$ and a matrix $A$ modulo some prime $q$ such that $t = As + e \mod q$ with some short vectors $s$ and $e$ . The secret key is the short vector $s$ . For Dilithium, we now use the following zero knowledge proof:

First, the prover commits to the high bits $w_1$ of $Ay$ , where $y$ is shortish. Using the high bits only is similar to adding an error, since the small error also only affects the least significant bits. The challenger then challenges with a small scalar $\mathit{c}$ (this scalar is somehow multidimensional, in a way that I will simply ignore here), and the prover responds with $z = y + \mathit{c} s$ . The challenger can now check that $Az - \mathit{c} t = Ay + \mathit{c}As - \mathit{c}As - \mathit{c}e$ has the same high bits as the commitment $w_1$ .

We are just going to ignore that this protocol would not be zero knowledge, and that Dilithium actually has to use something called Fiat-Shamir with aborts, since, as mentioned, that stuff really should go into its own blog post.

For our purposes, the only question that matters is how this ~~zero~~some knowledge proof is turned into a signature scheme. And here comes the bad news for our public-key-recovering ambitions: It turns out that the commitment $w_1$ is significantly larger than the challenge $\mathit{c}$ , so Dilithium uses the challenge in the signature landing on $(\mathit{c}, z)$ , instead of the commitment, which, as with Schnorr signatures, makes the public key unrecoverable.

A separate, interesting question is if we could recover the public key if $w_1$ was part of the signature instead. If we knew $A$ , we could at least recover the high bits of $t$ , which are the ones that matter. (As it turns out, Dilithium actually doesn’t even include the least significant bits of $t$ in the actual public key, to save a few bits in there).

Without knowledge of $A$ , this becomes a lot of linear algebra, which I haven’t done, you’d certainly need more than one valid signature, as a single signature does not contain enough information to recover that giant matrix.

Part of the reason why I haven’t done that linear algebra is that if we knew $w_1$ through some side channel or similar, we still would have no chance recovering the public key since Dilithium rudely hashes the public key with the message when computing the challenge, destroying any hopes of recovery.

Chapter 5 SPHINCS+

This brings us nicely to SPHINCS+. SPHINCS+ is a hash based signature scheme, meaning that it follows the simple logic that if, at time of public key creation, you already know what you would like to sign, you can just hash that thing and call that your public key instead. If you want to sign a lot of things, you can just pack all of these things into a Merkle tree, and declare the root of that tree to be your public key. If you don’t know what you want to sign, you can just commit to every possible message, by creating commitments for the single bits of a hash. Throw some randomness in there so you don’t by accident reuse your commitments to the point of breaking, and you get SPHINCS+. The scheme probably also deserves its own blog post, but we don’t really need much more for now. A Merkle tree inclusion proof will leak the root node of the Merkle tree, as long as we can observe the initial message of which the inclusion is proven. Unfortunately, loving hashing so much, the authors of SPHINCS+ did the same thing as Dilithium did, and hash in the public key when computing the initial message hash, making the public key unrecoverable. You only need relatively little extra information to recover though, and it is possible that some timing attacks on the verifying logic would suffice to pick back up and continue along the Merkle tree.

Chapter 6: Unbalanced Oil and Vinegar

Lastly, let’s look at a fun candidate in the second onramp called Unbalanced Oil and Vinegar. It again could use its own blog post, but here it is, slightly condensed and leaving out such unnecessary details as what the private key is and how anyone actually computes a valid signature in the first place.

Remember solving quadratic equations in high school? Like just given a value $y$ , find the value $x$ such that $ax^2 + bx + c = y$ ? Now imagine someone turned that into a signature scheme. Of course, even adversaries know that $x_{1,2} = \frac{-b\pm \sqrt{b^2 - 4ac}}{2a}$ , so we will have to increase the difficulty a tiny bit by making things higher dimensional, but the idea remains the same.

A UOV public key is a system of $o$ quadratic equations $(f_i(x_1, x_2, \dots, x_{o+v})_{i=1,\dots o}$ in $o + v$ variables. These equations are homogenous, so we can also describe them via a matrix: $f_i(x) = x^TA_ix$ , where $x$ is a vector. To sign with this, signer computes (via a miraculous trap door, this post is too short to contain) a value $x$ , such that $(f_i(x))_i={1\dots o} = H(m)$ . The real trick to UOV is in the process of how the signer computes this preimage, but we do not care about that, we care about recovering public keys. Clearly, since a UOV signature is much shorter than a UOV public key, a single signature will not suffice to recover the public key, but what if we collect more than just one? What we have is a unknown set of polynomials, evaluated at certain known points (the signatures) getting to certain known images (the hashes of the messages). This sounds like a job for polynomial interpolation!

And indeed, with “just” $\frac{(o+v)(o+v+1)}{2}$ message/signature pairs, we will be able to recover the public key:

We take the basis

$\left(b_i\right)_{i=1}^{\frac{(o+v)(o+v+1)}{2}}=\left(X_i\cdot X_j\right)_{i=1,j=i}^{u+v, u+v}$

and for each message/signature pair $(x_j, y_j)$ , we compute $b_k(x_j)$ . Since we know that $f_i(x_j)=y_j$ , and know that each $f_i$ is a linear combination of the $b_k$ , this gives us a linear equation, which starts having a unique solution once we have collected $\frac{(o+v)(o+v+1)}{2}$ signatures. On top of that, UOV doesn’t hash in the public key (probably because the public key is ginormous), so this works even on the candidate as published.

UOV also features a version with a compressed public key (as mentioned the public key is a tad big). This blog post is already really long, so I just remark that we cannot recover this compressed public key, since it involves a seed and we can’t find preimages of hash functions when the preimage has that much entropy. But the expanded public key is equivalent in any way, so I will still count UOV as a success.

Conclusion

Public keys are public, even when you don’t tell people about them. Signature schemes vary greatly in how easily the keys are recovered, but keep in mind that verification logic is usually not written to be side channel resistant, so even with schemes that do not leak the public key algebraically, there might still be a way for an adversary to recover the public key, and you need to design your protocols to be resilient against that property.