Hack of the International Stamped Time Server

Question

The International Stamped Time Server (ISTS) broadcasts a time stamp integrity-protected with an RSA-4096 public key $(n,e)$. But mere days after it starts operation, hackers announce they pwned it by rigging the RSA cryptoengine, and publish (at Blackhat) a valid stamp for year 9999 as proof. You wrote the key generator and performed key insertion in the cryptoengine, and are the target of suspicion. Find how the hackers proceeded, and the fastest they could do.

ISTS radioes a 512-byte $s$ changing every minute. Users receive that fixed-size message $s$, compute $r=s^3\bmod n$ (with big-endian convention), split $r$ into $t\mathbin\|h$ with $t$ 448-byte and $h$ 64-byte, and check that $h=\operatorname{SHA512}(t)$, where SHA512 is a cryptographic hash function. Time $t$ starts with the UTC date in ASCII as 2018-07-31 12:25. Bytestring $t$ further contains the date and time in a variety of other scales (TAI, GPS, religious and national calendars..) with all bits precisely defined. That's a simple form of RSA digital signature with message recovery, using public exponent $e=3$.

ISTS computes $s$ from $t$ using a third-party cryptoengine, which you initialized with the RSA private key $(n,d)$ you secretly generated as customary: you picked random probable primes $p$ and $q$ in interval $[2^{2047.5},2^{2048}]$ with $p\bmod3\,=q\bmod 3\,=2$, then computed the ISTS public modulus $n=p\,q$, and the private exponent $d=3^{-1}\bmod(p-1)(q-1)$ using the extended Euclidean algorithm, then discarded $p$ and $q$. The cryptoengine is battery-powered, communicates thru optical fiber, and is housed in a TEMPEST safe in a guarded underground bunker. You checked all that before key insertion, put the only backup of $d$ in the safe, sealed it, and it stayed that way.

The cryptoengine's specification is that, after key insertion, it accepts $t$ (30 s in advance), computes $h=\operatorname{SHA512}(t)$, then $s=(t\mathbin\|h)^d\bmod n$, then checks $s^3\bmod n\,=t\mathbin\|\operatorname{SHA512}(t)$ before $s$ is output, all in constant time. On top of that, $s^3\bmod n\,=t\mathbin\|\operatorname{SHA512}(t)$ and $t$ are independently re-checked before $s$ is broadcast, when the UTC minute changes as precisely determined by an atomic clock. Every communication on the optical fiber after key insertion was logged, and checks, with $t$ having the expected date and format.
Update following two comments: the checks include the prescribed 512-byte size of $s$; the leftmost byte of $n$ happens to be $\mathtt{E5}_\text{h}=\mathtt{11100101}_\text{b}$.

---

That's mildly serious cryptography presented as a puzzle, following suggestion after the puzzle form was deemed inappropriate for Crypto.SE. There's historical precedent on RSA and puzzles: Martin Gardner's August 1977 Mathematical Games column in Scientific American, A new kind of cipher that would take millions of years to break, which was broken only in 1994.

---

Background, as asked: RSA is one of the best established and versatile public-key cryptosystem, probably the simplest for digital signature, and among the fastest for verifiers. Puzzling.SE uses RSA-2048 digital signature to get a green lock icon in your browser.

In this puzzle, RSA's security is based on the difficulty of solving for $s$ the equation $r=s^3\bmod n$ for arbitrary $r$, knowing $r$ and $n$, but not the factorization of $n$ as $n=p\,q$. Such $s$ exists when $0\le r<n$ (with exceptions for $p=q$, which is practically impossible). It is hard to find such $s$, but it is easy to verify one: that only requires two multiplications modulo $n$, to compute $s^2\bmod n$ then $s^3\bmod n$. The result should match $r$.

Finding $s$ is normally performed as $s=r^d\bmod n$ where $d$ is the private exponent. That method requires knowledge of $d$, normally computed using the factorization of $n$.

Given the size of $p$ and $q$ and how they have been generated, it is widely considered impossible with current technology, by a huge margin:

• To compute any $s$ that verifies $r=s^3\bmod n$, given $n$, and a random $r$.
• To obtain a working $d$ or the factorization of $n$, when given $n$ and a cryptoengine that computes $s=r^d\bmod n$ for any $r$ given on input, unless some information leaks out of the cryptoengine by a so-called side-channel (also known as a covert channel).

Many of the classical side-channels are excluded by the problem statement (including timing, electromagnetic emission, noise). Every conceivable precaution was taken so that, after key insertion, the only output of ISTS's cryptoengine that the hackers could use are the $s$ that have been radioed.

^{Note: There's a class of so-called RSA multiplicative forgeries computing $s$ for a new $r$, given only the ability to obtain other $s_i$ matching a number of other chosen $r_i$. These are delights for specialists. However, in the context, the hackers could not choose the $r_i$. Further, a specialist (full disclosure: me) concluded that $r=t\mathbin\|\operatorname{SHA512}(t)$, combined with the high redundancy of $t$, is adequate to prevent such forgeries.}

Answer 1

First approach (via covert channel)

Some basic facts:

• The most significant byte of the modulus $n$ is $11100101_b$.
• $n$ perfectly fits within the $512$ bytes.

The idea is to communicate through the signature $s$, by adding multiples of $n$ while still remaining within the bounds of the $512$-byte restriction.

We rely on the assumption that $n+s < 2^{4096}$, that is, it fits inside the $512$ bytes. This works when most significant byte of the signature $s$ is smaller than $00011010_b$ (if it is larger, we get an overflow). This happens with probability roughly $\frac1{2^4}$: each digit is random and takes value $0$ with probability $\frac12$

Of course, more bits could be communicated; if we have $3n+s < 2^{4096}$, then two bits could be sent by ordering $n$ in normal binary notation as $00, 01, 10, 11$, each time providing two bits of information about one of the factors. Unfortunately, the specified range prohibits faster-than-$1$-bit covert-channel communication.

Although the cryptoengine is not aware of $\phi(n)$, it can be computed since $e$ is small. First, we compute $k'=\lfloor 3d/n \rfloor$. Clearly, $k$ is close to $k'$, so we need only to check a few values. $\phi(n)$ is then computed as $\frac{1}{k} \times (3d - 1)$. Given $\phi(n)$, it is trivial to find $p$ and $q$ (via a quadratic equation). This is a one-time computation and since we have about $30$ seconds to do it, we are fine.

So, what is the most efficient way of communication the factorization of $n$? If assume that the factors are incompressible, then we can send parts of a factor and then use a polynomial-time algorithm to deduce it (see Chapter 11 in the link posted by @Bass). Turns out we need at most $4096 \times \frac14 = 1024$ bits.

Therefore, the time required then is upperbounded (by the assumption of incompressbility) by $16 \times 4096 \times \frac14$ minutes, which is $11$ days, $9$ hours and $4$ minutes.

Related: RSA leak bits to factor N