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

- Calculate the signature of factors of message
`M`

to be signed, separately - Combine them by multiplication over modulus to get the signature of
`M`

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

Based on Unpadded RSA Digital Signature about which you can read here-

https://github.com/ashutosh1206/Crypton/tree/master/Digital-Signatures/Unpadded-RSA-Digital-Signatures

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

`ls`

– list all files in a directory`dir`

– list all files in a directory`cd`

– change directory`cat`

– print contents of a file`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:

1 | if __name__ == '__main__': |

Code for signing and verification:

1 | class RSA: |

Public Key parameters:

1 | n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967 |

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 `M`

– `M'`

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

- Send $ M’ = M*r^e\mod n $ to the server for signing
- Server returns $ S’ = M’^d\mod n $ as the signature
- 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:

1 | elif cmd == 'sign': |

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:

shlex.split(s[, comments[, posix]]):

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:

1 | a1 = 5725328683166829573239696644736240987222390612782623055767221457947054498869585432340114750452041306184448080561441333680416149749123302833656168850455057339213913581521304928546906376611483092028381845790493432777394243854337713411345364484121624102094225644920832183140485060698003427784263235045715418018795065546699975383883994070801087888721917493323512583065933510612272433999960862552551149518567321442699741438495127366658724949796547041565239963015841490137522112601645871932398680285229468715982238164777462030319794517434842874408662003862620669880489659970497227134709174593842886547439340217672886958414 |

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

:

1 | from pwn import * |

Sent the output of this program : `3286528875824401323909738437973876263592285806330579480892716506518162827346653750918786020868708715139678726879607460041269108522675282498402520621523389272103654713166804420533254300067188665431989937719789771867495287196004112328231136647620797482594454217627892295088550097078966118082243832222765083683047277465759456839136022908583598231243751555795311046311162221140862960084937519772113462693851907783421750089642112372898894301499330629729122091682821183290574224020212593879335785676788440979384299829273671811506630292428551584104516339852500307548336792024342745894475402553988453055201621075073017268754`

to the server and got the flag!

**VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}**