Is it safe to use RSA as a proof-of-work system?

Question

Suppose I devised the following challenge-response proof-of-work system:

A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed number of times, say, 256.

The server then sends the signed nonce to the client, along with the "private" exponent (which is much larger) and modulus, asking it to un-sign it using the private key 256 times, sending the answer back for the server to verify. Because the private operation takes about 300 times longer at 2048 bits, the client will take longer to un-sign the key than the server took to sign it.

Is this usable/secure? Or does the generation of the modulus outweigh any gains in the difference in signing time? If so, how could I make it usable, if at all?

Answer 1

Edit: I just realized that the scheme that was proposed has serious security problems, and should not be used.

The question is rather confused and ambiguous, but there seems to be a serious security problem. If I understand the proposal correctly, you are giving the client the private exponent $d$ and the modulus $n$ and the iteration count $k$ (say, $k=256$) and a challenge $a$, and it is the client's job to respond with $$\textrm{proof} = a^{d^k} \bmod n.$$

This is not secure. Once the client knows $d$ and $n$, it is trivial to factor $n$ into $n=pq$. Thus the client learns the primes $p$ and $q$. Once the client knows this factorization, the scheme falls apart, as explained below.

In particular, the client can use the Chinese remainder theorem and Fermat's little theorem to greatly speed up the computation of the proof. First, the client works out the value of $\textrm{proof} \bmod p$, as follows: $$\textrm{proof} \equiv a^{d^k} \equiv a^{d'} \pmod p,$$ where $d' = d^k \bmod p-1$. Note that $d'$ can be computed efficiently: first we reduce $d$ modulo $p$, then we compute $d'$ using square-and-multiply (or another efficient exponentiation algorithm). Through a similar process, the client can recover the value of $\textrm{proof} \bmod q$. Finally, the client can combine these values using the Chinese remainder theorem to recover the value of $\textrm{proof} \bmod n$ and send it to the server.

How much work does the client have to do? If $k=256$ and $e=3$, the client does 8 squarings modulo $p-1$, 8 squarings modulo $q-1$, one modular exponentiation modulo $p$, one modular exponentiation modulo $q$, and then a Chinese remainder computation (which is very fast and basically requires one or two extended Euclidean algorithm computations on $\gcd(p,q)$). This is not much more work than the server has to do to create the challenge.

In summary: the client can solve the puzzle using not much more computation than it takes the server to create the puzzle in the first place. There are shortcut methods that the client can use to greatly speed up its computation, and as a result, the server has little or no advantage over the client. This is not a good proof-of-work system.

---

There are other ways to build proof-of-work schemes other than using RSA. Some of them are secure, and do give the server a major advantage over the client. For example, one standard scheme is to give the client a random 20-bit string $r$, and ask the client to respond with a value $x$ such that the first 20 bits of $\textrm{SHA256}(x)$ are equal to $r$. It will take the client about $2^{20}$ steps of computation to find such an $r$, but the server can check the client's answer very quickly -- merely by hashing a single value -- which is much faster than RSA.

Therefore, you should avoid the RSA scheme described in this question. Instead, use other proof-of-work schemes that have been more carefully vetted.

Answer 2

Is this usable? Or does the generation of the modulus outweigh any gains in the difference in signing time?

No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, this would be very impractical and nobody would use it).

But the problem is that the advantage of the server on the client is asymptotically more or less zero, so this is quite useless as a proof of work scheme. See D.W.'s answer for one way of breaking the scheme.

Another way similar to D.W.'s is to realize that your scheme requires the client to compute, given a random nonce $a$ and a work factor $k$, modulus $n$ and private exponent $d$:

$$\text{proof} = ((a^d)^d)^{\cdots ~ k ~ \text{times}} ~ \text{mod} ~ n$$

And this is equal to:

$$\text{proof} = a^{d^k} ~ \text{mod} ~ n$$

But because the client knows $d$ (you gave it to him!) he can factorize $n$ in constant time and compute $\varphi{(n)} = (p - 1)(q - 1)$, which gives him the ability to reduce the inner exponent:

$$\text{proof} = a^{d^k ~ \text{mod} ~ \varphi{(n)} } ~ \text{mod} ~ n$$

The client can calculate this in $\log{k}$ modular multiplications or squarings by $d$, and $\log{n}$ (on average) modular multiplications or squarings by $a$. But the server has to do pretty much the same amount of work - the only difference is it saves some time because $e$ is smaller than $d$. The gain is minimal and very difficult to control, since there's a point where you just can't make $e$ any smaller and need to increase $n$ to compensate.

In conclusion, this is not a good proof-of-work scheme, as it provides basically no control over the work factor desired and the server will need to work about just as much as the client for realistic values of $n$ and $k$.

---

If so, how could I make it usable, if at all?

However, it's possible to take your scheme a step further to make it cleaner (and not depend on RSA). The idea is to choose a "difficulty factor" $t$, a random number $a$, a large $n = pq$, and ask the client to compute:

$$\text{proof} = a^{2^t} ~ \text{mod} ~ n$$

The client will require $t$ squarings to achieve this (there is no known way to do better, and it cannot be parallelized to any significant degree), while the server, knowing the factorization of $n$ (since it generated it) can just compute:

$$e = 2^t ~ \text{mod} ~ \varphi{(n)}$$

And hence, from Euler's Theorem:

$$\text{proof} = a^e ~ \text{mod} ~ n$$

Which the server can then compute in logarithmic time. In effect, the server only needs $O(\log{nt})$ time, but the client needs $O(t)$ time. By making $t$ arbitrarily large, you can fine-tune the amount of work you want the client to do, linearly, but the work stays logarithmic for the server, which is practical.

The generation cost is also irrelevant, because the server can generate it once and reuse it all the time with different values of $a$ (that's not always true, but in this case it is - the attacker can't use the results of a previous proof of work to quickly solve another assuming $a$ is random and $n$ is large).

Note your scheme doesn't care if the client can factorize $n$ since you are basically giving away $d$, but in this scheme it is imperative that $n$ be large enough so that factorization is not possible. But this is easy to address, just create a 2048-bit modulus (or 4096-bit if you are paranoid) and be done with it.

---

For more details and supporting theory on this method, see:

Time-lock puzzles and timed-release Crypto, Ron Rivest, Adi Shamir, David Wagner.

Puzzle description for the MIT time capsule.