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

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:

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:

if __name__ == '__main__':
    signature = RSA(e, d, n)
    check_cmd_signatures(signature)
    try:
        while True:
            send_message('Enter your command:')
            message = read_message().strip()
            (sgn, cmd_exp) = message.split(' ', 1)
            eprint('Accepting command {0}'.format(cmd_exp))
            eprint('Accepting command signature: {0}'.format(sgn))

            cmd_l = shlex.split(cmd_exp)
            cmd = cmd_l[0]

Code for signing and verification:

class RSA:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def sign(self, message):
        message = int(message.encode('hex'), 16)
        return pow(message, self.d, self.n)

    def verify(self, message, signature):
        message = int(message.encode('hex'), 16)
        verify = pow(signature, self.e, self.n)
        return message == verify

Public Key parameters:

n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537

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:

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:

elif cmd == 'sign':
    try:
        send_message('Enter your command to sign:')
        message = read_message().strip()
        message = message.decode('base64')
        cmd_l = shlex.split(message)
        sign_cmd = cmd_l[0]
        if sign_cmd not in ['cat', 'cd']:
            sgn = signature.sign(sign_cmd)
            send_message(str(sgn))
        else:
            send_message('Invalid command')
    except Exception as ex:
        send_message(str(ex))

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:

a1 = 5725328683166829573239696644736240987222390612782623055767221457947054498869585432340114750452041306184448080561441333680416149749123302833656168850455057339213913581521304928546906376611483092028381845790493432777394243854337713411345364484121624102094225644920832183140485060698003427784263235045715418018795065546699975383883994070801087888721917493323512583065933510612272433999960862552551149518567321442699741438495127366658724949796547041565239963015841490137522112601645871932398680285229468715982238164777462030319794517434842874408662003862620669880489659970497227134709174593842886547439340217672886958414
a2 = 5776900817579263502012073259265509818180931473953964095028741073140216535992257054375246116440046065862853643074894715558531151457900526055666223338716444037946416801889260557746631448235744959721666895834151314372873545396117440546915344971588339888321713407370840066665008973922024295285020709292800829701328566643190598259861295301184002381483184357143538680290525822852565951244544661237922267145309002166424608580975872476837465547277177179918782162708463376167053814440487147846920715285511467401043444572661425003080969287803176544412842577530742363661831683398274133976173820932680497675380697899093178094313
a3 = 4155963451813769577302791073389845717204755193354204177107723759791137213861537907169555010561252098984870316297077233561093440919577716533705862527027635572341881596132667502888815638853987209129336456308824245829451475616207505573424137643792172729002122677680977572751159590242837890118864348598969755423011953553778428711070636416718210613472628516675672215667316425887934111235926710107309335818568274370441938183158876823570714696366648710307355514032732615903765284883341842444746067219956122697416247457607418923494274477486366003554681903862913333883478131160687439125754389907700800229511506420820140176881
a4 = 7333732835514754683989816304075567363802950974133982580631165933436884158121825312333126821218962796115635378302758343237149342000021557522548458808492715954768273158155338442230339125294660171042660511212324532756737755904999829597287107257382410407338457774957688914587591567877547558111839614472733815844380405402292278899593168322163036285466037611599345184076562950936788223669650857392341454169481878024473368857105109389665100811369752194833573897266034467688183505503017939527641533925046034291120325664777921745516757035228881064335488271038413946948482762259373351872651795951815223788992611712310636364795
a5 = 3858934247602421528586827927178657681071234987708191019756328507977797839242117331216987043063717998804199841522874477988630899266666283848318955319432371819139929933452961284529360343618767939742554591429821894870449418101055687065151747384638809299630974127697124542130257501711906476888830069586725865564360891746504520191254352752529483910497890674015624994298622476398282616288243393335738466840172382741546102067479761565439580235728338562099416367868068215244010375030134895072279429932545495229243346117066430309054171871277470954421034664600791121170731091324136510369460120290315288062593843890532348710362
a6 = 21856053383887748303764562438301305387252218840234139732972091958998507298289379540739246080321263742167678970787332216918034023209835833747485760412079639115255267690250958243538326257045131973880032544558781472959547801217447968136713455974556637496673439660120002126747530235469442959440769271265405398205234872089116669659158559815022213457967936307820767046909177739064594219046809499628063928128675138013453695817019253508345702140381806781108655643249001728603826265152523463558984866021169779189990198602770072179096022664945948147297852635857447802426756406961156446823597933686986524124372807916883071492071
a7 = 18778797762800330902974334892555056857772773395824126315180600046227442896308180999724874326593065784504540670735290704911979400055067163959602686255372804749578630507928488984486945745887988355924837689303387483442688805676235968976624216238772697118919915413052694373237203071154129422108995127876819511221302151506888591652758382981047051651646133408243513220241048292688154900557301171108956390602139803578323256030931827987619702033063836508154901681901567115190721043937166257252399431102862318724806309088685206808440495451008820158340331523116271687706255715089701948256496482087765387366009286463575080897976

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

from pwn import *
from Crypto.Util.number import *

n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967

a1 = 5725328683166829573239696644736240987222390612782623055767221457947054498869585432340114750452041306184448080561441333680416149749123302833656168850455057339213913581521304928546906376611483092028381845790493432777394243854337713411345364484121624102094225644920832183140485060698003427784263235045715418018795065546699975383883994070801087888721917493323512583065933510612272433999960862552551149518567321442699741438495127366658724949796547041565239963015841490137522112601645871932398680285229468715982238164777462030319794517434842874408662003862620669880489659970497227134709174593842886547439340217672886958414
a2 = 5776900817579263502012073259265509818180931473953964095028741073140216535992257054375246116440046065862853643074894715558531151457900526055666223338716444037946416801889260557746631448235744959721666895834151314372873545396117440546915344971588339888321713407370840066665008973922024295285020709292800829701328566643190598259861295301184002381483184357143538680290525822852565951244544661237922267145309002166424608580975872476837465547277177179918782162708463376167053814440487147846920715285511467401043444572661425003080969287803176544412842577530742363661831683398274133976173820932680497675380697899093178094313
a3 = 4155963451813769577302791073389845717204755193354204177107723759791137213861537907169555010561252098984870316297077233561093440919577716533705862527027635572341881596132667502888815638853987209129336456308824245829451475616207505573424137643792172729002122677680977572751159590242837890118864348598969755423011953553778428711070636416718210613472628516675672215667316425887934111235926710107309335818568274370441938183158876823570714696366648710307355514032732615903765284883341842444746067219956122697416247457607418923494274477486366003554681903862913333883478131160687439125754389907700800229511506420820140176881
a4 = 7333732835514754683989816304075567363802950974133982580631165933436884158121825312333126821218962796115635378302758343237149342000021557522548458808492715954768273158155338442230339125294660171042660511212324532756737755904999829597287107257382410407338457774957688914587591567877547558111839614472733815844380405402292278899593168322163036285466037611599345184076562950936788223669650857392341454169481878024473368857105109389665100811369752194833573897266034467688183505503017939527641533925046034291120325664777921745516757035228881064335488271038413946948482762259373351872651795951815223788992611712310636364795
a5 = 3858934247602421528586827927178657681071234987708191019756328507977797839242117331216987043063717998804199841522874477988630899266666283848318955319432371819139929933452961284529360343618767939742554591429821894870449418101055687065151747384638809299630974127697124542130257501711906476888830069586725865564360891746504520191254352752529483910497890674015624994298622476398282616288243393335738466840172382741546102067479761565439580235728338562099416367868068215244010375030134895072279429932545495229243346117066430309054171871277470954421034664600791121170731091324136510369460120290315288062593843890532348710362
a6 = 21856053383887748303764562438301305387252218840234139732972091958998507298289379540739246080321263742167678970787332216918034023209835833747485760412079639115255267690250958243538326257045131973880032544558781472959547801217447968136713455974556637496673439660120002126747530235469442959440769271265405398205234872089116669659158559815022213457967936307820767046909177739064594219046809499628063928128675138013453695817019253508345702140381806781108655643249001728603826265152523463558984866021169779189990198602770072179096022664945948147297852635857447802426756406961156446823597933686986524124372807916883071492071
a7 = 18778797762800330902974334892555056857772773395824126315180600046227442896308180999724874326593065784504540670735290704911979400055067163959602686255372804749578630507928488984486945745887988355924837689303387483442688805676235968976624216238772697118919915413052694373237203071154129422108995127876819511221302151506888591652758382981047051651646133408243513220241048292688154900557301171108956390602139803578323256030931827987619702033063836508154901681901567115190721043937166257252399431102862318724806309088685206808440495451008820158340331523116271687706255715089701948256496482087765387366009286463575080897976

res = (a1 * a2 * a3 * a4 * a5 * a6 * a7) % n
print long_to_bytes(pow(res, 65537, n)) == "cat ../blind/flag"
print res

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

VolgaCTF{B1ind_y0ur_tru3_int3nti0n5}