BlackAlps 2019 - RSA
RSA signing messages interface. Applying the Wiener attack reveal the private key which is the flag.
Description
You can connect to an online interface for signing messages using textbook RSA signatures.
You know that the implementation is sped up using the Chinese Reminder Theorem. The code is in C and uses GMP. The flag is hidden in the private key.
Author: Alexandre Duc
Access to challenge: nc pwns.blackalps.lan 2003
Details
Points: 325
Category: Crypto
Solution
A file was provided with the public key:
e = 10513223792933632274349320533448576218129675374766661503112877542259996754505900523948354431736909577199565461964672263901071787332928897057169937405631489712178347326293524421872780681091711326163943053191035593861864638536855113950156487006205717925106757859253047319556227298921307209318973486145213255982582751918123702199430965752017143792901871067834261463172441217487866892154259649784335206016568997467769328125994125282594534492667419656457903915950419647320146865058284648534191073596304582912356853107728118759099427052093532903331859278000951328721463534428704043091206164022261669635007985946615702906901
n = 11221440812972542750826454701039569573482291468122754023642431301808216364337580504208927546261064846751137444645007721850331554074395653958374809755680288095560143240497326775255499814897192322006509094928136444964076495884456452342201314951632027439278269272675363784127461966215133117033330722257929906340047840484861406962073199730867359185702574517221991613380708112149916186619683683367149465398791595957139100427923570288149757294714383536806323670486229350435619705109939327290730205072024318283452040961365237688085397132180212466115472928208027059543555688994728169949590682947037991301693477274454730750773
We got a signture from the interface:
8242078563626418948630550999523063403014069845992699287948641647474183457975534713638958314180093141715333896860964444025302760821610136608622436365987736631027479606524491829090280057534857610572501144034920767372299504275258467017697832220763441990002372786680222910145521787445000390003159319981265411741977627205559488528789494131327817905191159485253082332504268921921427157902216281913376881291132110118975610442932659707324062133495038002038883910650072413982703328312166761174385103073501111249303821799235406073596824271197945971350612561787085958469251374203374717958445360391426821582541300735903804168537
We first verify that the Wiener attack can be applied:
In [5]: e < n
Out[5]: True
Then we build the public key with RsaCtfTool:
./RsaCtfTool.py --createpub -n 11221440812972542750826454701039569573482291468122754023642431301808216364337580504208927546261064846751137444645007721850331554074395653958374809755680288095560143240497326775255499814897192322006509094928136444964076495884456452342201314951632027439278269272675363784127461966215133117033330722257929906340047840484861406962073199730867359185702574517221991613380708112149916186619683683367149465398791595957139100427923570288149757294714383536806323670486229350435619705109939327290730205072024318283452040961365237688085397132180212466115472928208027059543555688994728169949590682947037991301693477274454730750773 -e 10513223792933632274349320533448576218129675374766661503112877542259996754505900523948354431736909577199565461964672263901071787332928897057169937405631489712178347326293524421872780681091711326163943053191035593861864638536855113950156487006205717925106757859253047319556227298921307209318973486145213255982582751918123702199430965752017143792901871067834261463172441217487866892154259649784335206016568997467769328125994125282594534492667419656457903915950419647320146865058284648534191073596304582912356853107728118759099427052093532903331859278000951328721463534428704043091206164022261669635007985946615702906901
Then we applied the Wiener attack:
./RsaCtfTool.py --attack wiener --publickey ~/Documents/CTF/BlackAlps/2019/RSA/key.pub --uncipher 8242078563626418948630550999523063403014069845992699287948641647474183457975534713638958314180093141715333896860964444025302760821610136608622436365987736631027479606524491829090280057534857610572501144034920767372299504275258467017697832220763441990002372786680222910145521787445000390003159319981265411741977627205559488528789494131327817905191159485253082332504268921921427157902216281913376881291132110118975610442932659707324062133495038002038883910650072413982703328312166761174385103073501111249303821799235406073596824271197945971350612561787085958469251374203374717958445360391426821582541300735903804168537 --private
-----BEGIN RSA PRIVATE KEY-----
MIIECwIBAAKCAQBY5BQ9OyDBzpDkkZPmT6kALOO+qh5pNdJftqfZpPqFYqw1iuFN
7qnotT07e33N4qlEmKp6enLslYAW1mp09WAgPNaO5Bv/Cxo5U/S3IXo8sg6CdxnP
BB3CMe1k2xVDylgT6Hlxa2Ocd6bL0Nx6naZTyDUzW0bPe4GteV49t+JwLycUzLvh
Rnla38fSkQJSrjRCKmCYQ+m+59fom2IdLtsGu1Kpcp+aziftHbcGAtuSS9WENdUh
kC4Kyx5/WfIGOja4KWPfJOiij1PmHVCfw4Wi0ZjjIs24EB0qdPDP84qo+rDRtmy+
szkzCM/5ke2xK2CLrHuOLYRgDUtIvs/pbDs1AoIBAFNH4NRHpb/U2RItQbXpFfWO
slmVxjTTej2/HFdCbYfaLDarCkBGCpjhzyZf58m0Nxgb3yHe9VT5J+GTCjoZZkiC
qDUonc0JdDCfLDZeyTeMLipHVts3YylQNdLJsT6Mnz3AvpEdThjpE3aFjOc4lodB
3o4y6iBRAMhnZ7Qvw+uUSX1A/yMtvjdjDbursjrGAcHgQuQ6PKHAsYEyRxjhXr6r
eV1VdPEjUjxbauLkJuLUZomYlHtCcdxfUlFCSSN+qYxemOaLAP4CFYT2pxPSPAmN
09qLRlKvxYKs0dKYduhsviIMoIaqdIixDydxRSbLUAEFVVTgqVyHkg3n8bQUaBUC
JUJBMTl7UHduQ3J5cHQwVGg1VWx0MW00dGVDMG1iaW40dDEwbn0CgYEAikGHLGkw
5W/oxdc1wf3ppEtNCjtkJ5O7p9QD3iLfIrBRfVmcrr89xFzAKqxXHosUJXd/l6b7
dU9jICovFjOX7kXx2jYhBHbG8GN13imQJIZ12FASQxl6oE63xmUOy9QRT3szXCVb
4EPh/xIzKXBWglmnMBT25p4b5FLsSni3HB0CgYEApJgFERx6JJ3JVWeYVzcSYutX
Ku4BF9Z7RhONEG5TBf88qyWa+J2pXjYWcOCOvhg1uKWPCAvTkAw0MwMlOq9zaYxV
r2SrUfDVIM8mviifcmpOztGJGGgaHSXI8VvM/sUgBRi+R9AD0BGoBbEWoyUskeWK
57tZ5kRvw+yjtdjF//kCJUJBMTl7UHduQ3J5cHQwVGg1VWx0MW00dGVDMG1iaW40
dDEwbn0CJUJBMTl7UHduQ3J5cHQwVGg1VWx0MW00dGVDMG1iaW40dDEwbn0CgYB+
hJg2kK4jIffY6w52gZO4Mf1rAUpWzSdzwn9XJkOO3TfBQhBrUotA2yOZLcI3Y2Gl
zOcyIVmVN2atUDzKRTbyypBIRiHvFOxvtjgT0Fzsna6WG8vGbMc1oN+I3NdlIb5n
UYaI5yx5VSgFtiP41I9UsxPi0sNGwaoWnjT2DDq2zg==
-----END RSA PRIVATE KEY-----
[+] Clear text : b'EKFX,\r\xa9@\xc3\xa8\x8d\x9f{\xa1WuO\x99\xbe1\xb2hv,\x00\xbdYO\xee\x97\xd2Vzb\x87rt\x1c\xe3\rI\xe6fKP\xc7\xb7H\x1ex\xa7\x1b\xdc\xca\xa5\xfc\x8a\x9e\xe2\x13\xef:I\xe1\x9a\x87D\x0b\t\x1c\xedG\x93?u\xef\x005\xdadi*\xa7Q\xc4\x90\xcdG\xdc\x8d{\x1a.h\x1e\x98G\xddf\xe9W\x13/y=<\x02\xb7\xfbW\xe6\xc9\x12\x94\x9bQ\xe1b\x85lb\x90\xa2\xa3$\x96\xc1!?\x0b\x17\xb5\x06F\x9a\x847\xc1L\xd7z\xbd\xe5\x1d\x0e\x10I\xa2\xf0\x96I\xc4M\xc5;.t\xf6\x08\xe8l\x9b\x18\x04\x0e\xb0j\xbd^\xa8TH\x8c\xeb`\x14\xd5I\xda4\xf8\x15&\x02h\x97\x0b\xf7\x9f.\x98\xc3\xa8\xfe\xf7\xc9\x01\x10%\x912\xc1\xfbD02\x1fT\xc2\xfa\x0f\x9d\xc6\xd0$\x95\xa9f\xfc\x9cv\x0c\x9f\x83\xabG+g\xb29 \x17\x9e\x90\x08d\x0c\xe1\xd0\xf1+\xde%|\xdcY\x98\xa5\xaf\x0b\xc4\xad\xab@(='
We retrieved the private exponent:
$ ./RsaCtfTool.py --dumpkey --key private.key
[*] n: 11221440812972542750826454701039569573482291468122754023642431301808216364337580504208927546261064846751137444645007721850331554074395653958374809755680288095560143240497326775255499814897192322006509094928136444964076495884456452342201314951632027439278269272675363784127461966215133117033330722257929906340047840484861406962073199730867359185702574517221991613380708112149916186619683683367149465398791595957139100427923570288149757294714383536806323670486229350435619705109939327290730205072024318283452040961365237688085397132180212466115472928208027059543555688994728169949590682947037991301693477274454730750773
[*] e: 10513223792933632274349320533448576218129675374766661503112877542259996754505900523948354431736909577199565461964672263901071787332928897057169937405631489712178347326293524421872780681091711326163943053191035593861864638536855113950156487006205717925106757859253047319556227298921307209318973486145213255982582751918123702199430965752017143792901871067834261463172441217487866892154259649784335206016568997467769328125994125282594534492667419656457903915950419647320146865058284648534191073596304582912356853107728118759099427052093532903331859278000951328721463534428704043091206164022261669635007985946615702906901
[*] d: 32949980623925232523625629808672011632097834303758330539120354282153396424798323323465341
[*] p: 97086642978881280359046782994343469373884602337632244453111542585064936692966956158663353303713859551253548462634579052174450678005903781581240717232056135354829999231035557389399807896307654215360776901371761963040138331626524932894678781419678817295118159269458678861257872958448941433336820891562733411357
[*] q: 115581716172980464576407872430244912541461448893557001465033224552918568628563700217560654191080143232361685181123611989553574859951261928584431180314908606110956327745427628576638624729255838664944107148032410314359796287336779869373372017381789395225544888896432444818185549496814901937164125137082390020089
And then the flag:
$ python3 -c "from binascii import unhexlify; print(unhexlify(f'{32949980623925232523625629808672011632097834303758330539120354282153396424798323323465341:x}'))"
b'BA19{PwnCrypt0Th5Ult1m4teC0mbin4t10n}'
Written on November 8, 2019