[Crypto] VolgaCtf2019 - Blind

Blind 200

Description:
Pull the flag…if you can.
nc blind.q.2019.volgactf.ru 7070
server.py

Identifying the problem

The server has a set of commands which a client can use, the commands cat and cd to be executed need to be signed by the servers private key, we don’t have access to that key, but we can sign anything besides the commands cat and cd, looking at the code we can see the server is signing our message directly with unpadded RSA, knowing this we can use RSA’s malleability property to forge a signature.

Applying the attack

The signing is done by simply doing:

Where:

• m is the message
• d is the rsa private exponent
• n is the modulus

We know that RSA is homomorphic to the multiplication this means for example that this is true:

To get the flag we need to use the command cat and do something like cat flag to obtain it, so since we can’t do it directly we gotta find an r that modifies our message so it modifies our message to something different than cat , we can then use this property of rsa to forge a signature by nullifying the first division with a multiplication.

For example we first sign our message m divided by an r number like this:

Now we can just sign the number r:

Now we can obtain the final signature we wanted by just multiplying both signatures:

Hence resuming what I showed you in the pictures we can trivially divide our challenge by a number r (provided it is in itself considered valid for signing and the challenge is a multiple of it), say 2, sign it and sign the quotient separately, multiply them and apply modular reduction with the public key’s modulus and hence forge the signature.

Avoiding some problems encountered because of this particular challenge

Because this challenge is using some specific libraries to parse the commands the output of our sign m/r and r can’t contain for example spaces or quote characters otherwise the server will throw an error when using shlex.split(message), the spaces because it’s going to split into multiple commands and the server will only sign part of the command, and the quotes really throws errors if they aren’t closed or escaped so I wrote an function find a valid r:

# Lazy way to find a valid r value
for x in xrange(r_,99999999999):
    try:
        m = safe_unhexlify(M/x)
        t = shlex.split(m)
        b = len(t) == 1
    except ValueError: # some characters like quotes and shit can fuck up the signing because of shlex.split
        continue
    if(M % x == 0 and b):
        r_ = x
        break

The valid r ended up being the number 408479, the full code to this challenge is:

from pwn import *
from binascii import unhexlify,hexlify
import base64
import shlex
import re

N = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537

def safe_unhexlify(n):
    if len("%x" % n) % 2 != 0:
        m = unhexlify("0"+("%x" % n))
    else:
        m = unhexlify("%x" % n)
    return m    

def sign(message, dont_skip=True):
    if (dont_skip):
        print r.recvuntil("Enter your command:\r\n")
    r.sendline("sign "+"sign")
    r.sendline(base64.b64encode(message))
    return re.findall(r'\d+',r.recvuntil("Enter your command:\r\n"))[0]

def cat(signature, command):
    r.sendline(str(signature) + " " + command)
    print r.recv()

r_ =  2
r = remote('blind.q.2019.volgactf.ru',7070)
M = int(hexlify("cat flag"), 16)

# Lazy way to find a valid r value
for x in xrange(r_,99999999999):
    try:
        m = safe_unhexlify(M/x)
        t = shlex.split(m)
        b = len(t) == 1
    except ValueError: # some characters like quotes and shit can fuck up the signing because of shlex.split
        continue
    if(M % x == 0 and b):
        r_ = x
        break
print "r=%d and M=%d" % (r_,M)

mBlinded = sign(m) # M / r_
sBlinded = sign(safe_unhexlify(r_), False)

S = (int(mBlinded) * int(sBlinded)) % N
cat(S,"cat flag")
r.close()

Now running it and obtaining the flag:

$ python blind.py
[+] Opening connection to blind.q.2019.volgactf.ru on port 7070: Done
r=408479 and M=7161132565001953639
Enter your command:

VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}

[*] Closed connection to blind.q.2019.volgactf.ru port 7070