BackdoorCTF16 – Baby

Worth 200 points, this challenge was presented with the following:

z3r0c00l has a safe repository of files. The filename is signed using z3r0c00l’s private key (using the PKCS-1 standard). Anyone willing to read a file, has to ask for a signature from z3r0c00l. But z3r0c00l is currently unavailable.

Can you still access a file named “flag” on z3rc00l’s repository?

nc hack.bckdr.in 9001

Let us take a look at the public key… 3072 bits and public exponent $e = 3$. Hmm… having a small exponent is usually not a good practice. First, I tried computing the roots to $x^3 - s \bmod n$, where $s$ is the signature and $n$ is the modulus, but then I realized that this was not the way to go. What if we use non-modular squareroot, plain old Babylonian style? After looking around, I also realized that this is Bleicherbacher’s $e = 3$ attack, which I probably should have known about. There is a lot of information about this attack (therefore, I will not describe it here) and, of course, lots of people have already written code for this. Being lazy/efficient, I rewrote a functional code into the the following:

```from libnum import *
from gmpy2 import mpz, iroot, powmod, mul, t_mod
import hashlib, binascii, rsa, os

def get_bit(n, b):
""" Returns the b-th rightmost bit of n """
return ((1 << b) & n) >> b

def set_bit(n, b, x):
""" Returns n with the b-th rightmost bit set to x """
if x == 0: return ~(1 << b) & n
if x == 1: return (1 << b) | n

def cube_root(n):
return int(iroot(mpz(n), 3)[0])

snelhest = hashlib.sha256('flag')
ASN1_blob = rsa.pkcs1.HASH_ASN1['SHA-256']
suffix = b'\x00' + ASN1_blob + snelhest.digest()
sig_suffix = 1

for b in range(len(suffix)*8):
if get_bit(sig_suffix ** 3, b) != get_bit(s2n(suffix), b):
sig_suffix = set_bit(sig_suffix, b, 1)

while True:
prefix = b'\x00\x01' + os.urandom(3072//8 - 2)
sig_prefix = n2s(cube_root(s2n(prefix)))[:-len(suffix)] + b'\x00' * len(suffix)
sig = sig_prefix[:-len(suffix)] + n2s(sig_suffix)
if b'\x00' not in n2s(s2n(sig) ** 3)[:-len(suffix)]: break

print hex(s2n(sig))[2:-1]
```

Ok, so lets try it:

Great!