# Blind - Volga CTF Qualifiers 2019

tl;dr solving RSA Digital Signature using it’s homomorphic property:

1. Calculate the signature of factors of message M to be signed, separately
2. Combine them by multiplication over modulus to get the signature of M

Challenge Points: 200
Challenge Solves:
Solved by: s0rc3r3r, v4d3r

There are various bash commands the program allows us to execute on the server:

1. ls – list all files in a directory
2. dir – list all files in a directory
3. cd – change directory
4. cat – print contents of a file
5. exit – exit the program

Notice in the given source code that the server allows execution of ls and dir commands without a
signature, while it requires signature of the whole command when we want to execute cd, cat, exit
commands.

Code on the server side that takes input:

Code for signing and verification:

Public Key parameters:

We only know values of public key parameters, hence we cannot sign any command by ourselves. But, there’s a catch: the server can sign any string for us using a sign functionality, provided that the string does not start with cat or cd.

We instantly moved our focus onto the sign functionality to check for potential vulnerabilities.

## Preliminary Analysis

At first, we thought that we can easily solve this challenge using Blinding Attack on unpadded RSA Digital Signatures because of the conditions persisting in the challenge: https://masterpessimistaa.wordpress.com/2017/07/10/blinding-attack-on-rsa-digital-signatures/

The basic idea behind “Blinding Attack on unpadded RSA Digital Signatures” is that we send a modified form of message MM' for the server to sign; retrieve the signature S' of M' and then compute signature S of M.

We as an attacker are doing all of this to get the signature of M, which we wouldn’t have got directly since M is blacklisted (Server does not sign M, similar to our challenge)

Attack:

1. Send $M’ = M*r^e\mod n$ to the server for signing
2. Server returns $S’ = M’^d\mod n$ as the signature
3. Compute signature of $M$ as: $S = (S’*(r^{-1}\mod n))\mod n$

Verification (Whether calculated value of S is the actual value)
$S^e\mod n = S’^e*r^{-e}\mod n$
$= M’^{d*e}* r^{-e}\mod n$
$= M*r^e*r^{-e}\mod n$
$= M\mod n$

Reaching a dead end: The above attack cannot be applied to our challenge. Why? Let us look closely at the sign functionality:

Notice that there is a command shlex.split(message) that splits the string message using shell-like syntax. As per the documentation in https://docs.python.org/2/library/shlex.html#shlex.split:

Split the string s using shell-like syntax. If comments is False (the default), the
parsing of comments in the given string will be disabled (setting the commenters attribute of the shlex instance to the empty string). This function operates in
POSIX mode by default, but uses non-POSIX mode if the posix argument is false.

Due to this, our payload (ie. M’) will get split into parts and since signature of 0th index is generated, we cannot get the signature of the entire value of M’.

We tried solving this problem with multiple values of r, but the string always seemed to split. Dead end.

## Vulnerability

Our motive is to get the signature of cat flag, so that we can execute this command on the server.

Integer representation of cat flag is 7161132565001953639

Now, what if we can get the signatures of all factors of integer representation of cat flag? Then we can multiply all of them over $mod n$ to get the signature of cat flag! Awesome! Let us express this mathematically:

$M = p_1^{q_1}*p_2^{q_2}*p_3^{q_3}*…*p_a^{q_b}$
$S_1 = (p_1^{q_1})^d\mod n$
$S_2 = (p_2^{q_2})^d\mod n$
$S_3 = (p_3^{q_3})^d\mod n$

$S_a = (p_a^{q_b})^d\mod n$

Thus, we can write:
$(S_1 * S_2 * S_3 * … * S_a)\mod n =$
$= ((p_1^{q_1})^d * (p_2^{q_2})^d * (p_3^{q_3})^d * … * (p_a^{q_b})^d) \mod n$
$= ((p_1^{q_1}) * (p_2^{q_2}) * (p_3^{q_3}) * … * (p_a^{q_b}))^d \mod n$
$= M^d\mod n$

One more condition – none of the factors should be splittable by shlex.split(), otherwise we will encounter the same situation we faced in Preliminary Analysis!

We noticed that one of the factors in the integer representation of cat flag gets split by shlex.split(), hence we need to find some other command that follows our criteria.

We choose cat ../blind/flag as our payload. Integer representation of this string is 33817492399895531149817342615476077617511 with factors [3, 7, 37, 41, 12253, 11467349, 7554940736454483508504759]

Let us see how to use these factors to get the flag!

## Attack

We sent the factors as base64 encoded text and got their respective
signatures:

Then we wrote a simple script to compute signature of cat ../blind/flag:

Sent the output of this program : 3286528875824401323909738437973876263592285806330579480892716506518162827346653750918786020868708715139678726879607460041269108522675282498402520621523389272103654713166804420533254300067188665431989937719789771867495287196004112328231136647620797482594454217627892295088550097078966118082243832222765083683047277465759456839136022908583598231243751555795311046311162221140862960084937519772113462693851907783421750089642112372898894301499330629729122091682821183290574224020212593879335785676788440979384299829273671811506630292428551584104516339852500307548336792024342745894475402553988453055201621075073017268754 to the server and got the flag!

VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}