RScA

Description

Following an intervention, our technical teams came back with a secure phone used by a known criminal. Since we have it, we ensured that it was always powered on.

Usually, this phone is used to receive signed instructions from a person higher in the chain of command. The phone only verifies that the signatures of the messages are valid. During a step of reverse engineering, we identified that the cryptographic algorithm used is RSA.

One strong constraint in this case is the public parameters of the cryptographic algorithm are unknown. Moreover, the signature verification is performed securely to thwart the recovery of these parameters.

Your final goal is to forge signatures as if you were higher in the chain of command to set a trap for the members of this criminal organization. To do so, we ask you to recover all the cryptographic parameters used.

The reverse engineering step showed several important points.

First, we found the RSA implementation. Here is what we have recovered where phi is Euler’s totient function:

Function RSA(m, e, phi(N), N):
  r  <- random(0, 2**32)
  e' <- e + r * phi(N)
  accumulator = 1
  dummy = 1
  for i from len(e') - 1 to 0:
    accumulator ← (accumulator * accumulator) mod N
    tmp ← (accumulator * m) mod N
    if (i-th lsb of e') == 1:
      accumulator ← tmp
    else:
      dummy ← tmp
  return accumulator

Second, it turns out that the two modular multiplications

accumulator ← (accumulator * accumulator) mod N
tmp ← (accumulator * m) mod N

are performed using an hardware accelerator.

When the phone boots, the component performing signature verifications reads e and N from a SIM card. Then, N is provided to the accelerator, which stores it in an non-readable SRAM. We cannot reboot the phone as otherwise, the SIM card would be locked, and we don’t have the PIN code.

On the bright side, we managed to get our hands on some partial documentation of the hardware accelerator (attached). We also successfully sniffed the communications on the bus where the signatures are sent.

Since the operation, we have received two signed messages from the criminals. The results of the capture of the bus during the verification of signatures are given to you. Content of the messages is irrelevant for you.

Your goal is to recover all the RSA parameters:

• N : the public modulo,
• p, q : the prime factors of N (p*q = N, and p < q),
• e : the public exponent stored on the phone (0 < e < phi(N)),
• d : the private exponent used to sign the messages (0 < d < phi(N)).

The flag follows the format ECSC{N + p + q + e + d} with the sum N + p + q + e + d written in hexadecimal.