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 . Hmm… having a small exponent is usually not a good practice. First, I tried computing the roots to , where is the signature and 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 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)) 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: