Volga CTF Quals: Crypto write-ups

In this write-up we will discuss solutions of the following crypto challenges:

1. Blind
2. Shifter
3. LG

 

Blind

Solved by: s0rc3r3r, v4d3r

Write-up authored by: s0rc3r3r

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:

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

"""
	Keys
"""

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  to the server for signing
2. Server returns  as the signature
3. To calculate signature S of M
   1. 

Verification (Whether calculated value of `S` is the actual value):

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 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 represent this mathematically:

One more applicable condition – none of the factors should be splittable by shlex.split(), otherwise we will encounter the same situation we faced in the 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:

➜ Blind nc blind.q.2019.volgactf.ru 7070
Enter your command:
1 sign
Enter your command to sign:
Bj/SKHDt0Ts0qLc=
5725328683166829573239696644736240987222390612782623055767221457947054498869585432340114750452041306184448080561441333680416149749123302833656168850455057339213913581521304928546906376611483092028381845790493432777394243854337713411345364484121624102094225644920832183140485060698003427784263235045715418018795065546699975383883994070801087888721917493323512583065933510612272433999960862552551149518567321442699741438495127366658724949796547041565239963015841490137522112601645871932398680285229468715982238164777462030319794517434842874408662003862620669880489659970497227134709174593842886547439340217672886958414
Enter your command:
1 sign
Enter your command to sign:
rvpV
5776900817579263502012073259265509818180931473953964095028741073140216535992257054375246116440046065862853643074894715558531151457900526055666223338716444037946416801889260557746631448235744959721666895834151314372873545396117440546915344971588339888321713407370840066665008973922024295285020709292800829701328566643190598259861295301184002381483184357143538680290525822852565951244544661237922267145309002166424608580975872476837465547277177179918782162708463376167053814440487147846920715285511467401043444572661425003080969287803176544412842577530742363661831683398274133976173820932680497675380697899093178094313
Enter your command:
1 sign
Enter your command to sign:
L90=
4155963451813769577302791073389845717204755193354204177107723759791137213861537907169555010561252098984870316297077233561093440919577716533705862527027635572341881596132667502888815638853987209129336456308824245829451475616207505573424137643792172729002122677680977572751159590242837890118864348598969755423011953553778428711070636416718210613472628516675672215667316425887934111235926710107309335818568274370441938183158876823570714696366648710307355514032732615903765284883341842444746067219956122697416247457607418923494274477486366003554681903862913333883478131160687439125754389907700800229511506420820140176881
Enter your command:
1 sign
Enter your command to sign:
KQ==
7333732835514754683989816304075567363802950974133982580631165933436884158121825312333126821218962796115635378302758343237149342000021557522548458808492715954768273158155338442230339125294660171042660511212324532756737755904999829597287107257382410407338457774957688914587591567877547558111839614472733815844380405402292278899593168322163036285466037611599345184076562950936788223669650857392341454169481878024473368857105109389665100811369752194833573897266034467688183505503017939527641533925046034291120325664777921745516757035228881064335488271038413946948482762259373351872651795951815223788992611712310636364795
Enter your command:
1 sign
Enter your command to sign:
JQ==
3858934247602421528586827927178657681071234987708191019756328507977797839242117331216987043063717998804199841522874477988630899266666283848318955319432371819139929933452961284529360343618767939742554591429821894870449418101055687065151747384638809299630974127697124542130257501711906476888830069586725865564360891746504520191254352752529483910497890674015624994298622476398282616288243393335738466840172382741546102067479761565439580235728338562099416367868068215244010375030134895072279429932545495229243346117066430309054171871277470954421034664600791121170731091324136510369460120290315288062593843890532348710362
Enter your command:
1 sign
Enter your command to sign:
Bw==
21856053383887748303764562438301305387252218840234139732972091958998507298289379540739246080321263742167678970787332216918034023209835833747485760412079639115255267690250958243538326257045131973880032544558781472959547801217447968136713455974556637496673439660120002126747530235469442959440769271265405398205234872089116669659158559815022213457967936307820767046909177739064594219046809499628063928128675138013453695817019253508345702140381806781108655643249001728603826265152523463558984866021169779189990198602770072179096022664945948147297852635857447802426756406961156446823597933686986524124372807916883071492071
Enter your command:
1 sign
Enter your command to sign:
Aw==
18778797762800330902974334892555056857772773395824126315180600046227442896308180999724874326593065784504540670735290704911979400055067163959602686255372804749578630507928488984486945745887988355924837689303387483442688805676235968976624216238772697118919915413052694373237203071154129422108995127876819511221302151506888591652758382981047051651646133408243513220241048292688154900557301171108956390602139803578323256030931827987619702033063836508154901681901567115190721043937166257252399431102862318724806309088685206808440495451008820158340331523116271687706255715089701948256496482087765387366009286463575080897976

Then we write a simple script to generate 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!

 

Shifter

Coming soon!