Pull the flag…if you can.
nc blind.q.2019.volgactf.ru 7070
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:
- 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
The valid r ended up being the number 408479, the full code to this challenge is:
from pwn import *
Now running it and obtaining the flag:
$ python blind.py