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 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:

Screenshot 2016-06-05 16.15.09


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s