RSA.md

#RSA

Category: Cryptography

Description

We found a weird service running on a server in the department of EEvil, please figure out what you can do with it and report back.

Solution

Let's connect to the attached service:

root@kali:/media/sf_CTFs/technion/RSA# nc ctf.cs.technion.ac.il 4002
n: 24904245536811480409245815675661694392758028535801875721582010703630062060689241495001670757371873406466897114971057189020453405889353660180358623022849563337489982216631221561407540412262569452748267154277277490917762568981187745475595539181984491818099011458803818224835197184619944312913727125534748360824967762514336432782720512334829226762925818732672055624450097154241869490438077155762928696538809337342775462932070792760307344479319791048512438127511689406699405077740114675468248665572333990574065881689695874207920268021779755290642899537740188430821094368283543239570944738809400575523499221327101926751469
e: 3
c: 17418757890010697571225865872375941584583301381739857579693572032253613879799704468931604087165132303326708151578543017525723650255000655408363696646301705641647860286526561302705881670806109372630603991207895863534232235777297707773553105685257850305087618315765930947473893918572132988826725837272436091177144026010394446869408931962876075336973358559743579282351618347472807482456062260159984711293773104029840038291648170784834513165477761041956578892035771199393262672405372137395064135451840177500263853397595864438101040660899758514083011851709595966771419288273214759911967042630654993984455542783352993074440
root@kali:/media/sf_CTFs/technion/RSA# nc ctf.cs.technion.ac.il 4002
n: 21766492699362511113045963253377707237342047729146350396377621200883744137475734074306422185921456718547534492084550522983040126680141640531962919386517294728251442539892800391153093146422874755632895608959236217757093698624433140571646172407649901980624354914303694827325401962301039434061117950004120025054246638948959261719201152348610098890706808570003172782626652454689783487354163015680457501491713316907009060544542406791982635497583670680227224815376808884453682601144290306149460419370708341238202767092111760709490129557357805078948522003155302412183446727057585328931847422421170165984088685464226650513469
e: 3
c: 13276745128708181233099919020835541148036443732725280634028547068521042287643493808431637397725852881021976408292417715216759851157696372441455270459630162406232369293062846735076268682819547000795981352530834751568136570861388869935008221657584227717922753189117746732845879584814041960677694603647749384545011887696963672509586210923407814361678069103156953014875420903283898624171362999298480789195198923694416285972632158619933651186279721560067803559126737079452173361136173533507631528699920900675782785049744700720592339396988859392141807085625955443511539368156057693694129455234413316811430594227628111701437
root@kali:/media/sf_CTFs/technion/RSA# nc ctf.cs.technion.ac.il 4002
n: 18473096353043141605128653663452648416174731299473752106362058603063730284980752397962949879606783777506771253421342413864480457235067674469343553846553026186572911067675554648668993473165030868527062412561071976264934389359293025980676196524714448432571333144690149358258582542172726817402323390753047130442190533806512650463461449072479528455800781856541756664414668969141615567560250895278163378708524136692285506075011171343723100902339041053410054982510909991189736446434444683712265826719445362731072428588091699176245390996228255030441016453511061349239911220896593008184291359123267938548809512240873694221747
e: 3
c: 730014357977750980995622077939235335031193284345639952307731254144597878843149045426798809310771214915202586021638762323363798516003930902151644504161188546194166646290133878065450605398035396147863719373364327329187878729849837805966629458426486701579644025599344374047686327459363672379352004274625688927649388683203175346373929820529966641230555155399130634310816087625135839754124926912574486175520243469707331235697158369885401659131986232527692054579222663269283078960820194472223014573462755208618182521564139347700726774175765476445763039014246617344171324437339209961438562539438096747483478158309795081750

We've connected three times, and each time we've gotten a different RSA key with a different ciphertext. Only the exponent stays the same: 3.

This looks like a candidate for the Håstad's broadcast attack, which can recover the ciphertext if the same message is sent multiple times using the same small public key exponent. RsaCtfTool can perform this attack.

First, we create three public keys from the values we've received:

root@kali:/media/sf_CTFs/technion/RSA# ~/utils/RsaCtfTool/RsaCtfTool.py --createpub -e 3 -n 24904245536811480409245815675661694392758028535801875721582010703630062060689241495001670757371873406466897114971057189020453405889353660180358623022849563337489982216631221561407540412262569452748267154277277490917762568981187745475595539181984491818099011458803818224835197184619944312913727125534748360824967762514336432782720512334829226762925818732672055624450097154241869490438077155762928696538809337342775462932070792760307344479319791048512438127511689406699405077740114675468248665572333990574065881689695874207920268021779755290642899537740188430821094368283543239570944738809400575523499221327101926751469 > key1.pub
private argument is not set, the private key will not be displayed, even if recovered.
root@kali:/media/sf_CTFs/technion/RSA# ~/utils/RsaCtfTool/RsaCtfTool.py --createpub -e 3 -n 21766492699362511113045963253377707237342047729146350396377621200883744137475734074306422185921456718547534492084550522983040126680141640531962919386517294728251442539892800391153093146422874755632895608959236217757093698624433140571646172407649901980624354914303694827325401962301039434061117950004120025054246638948959261719201152348610098890706808570003172782626652454689783487354163015680457501491713316907009060544542406791982635497583670680227224815376808884453682601144290306149460419370708341238202767092111760709490129557357805078948522003155302412183446727057585328931847422421170165984088685464226650513469 > key2.pub
private argument is not set, the private key will not be displayed, even if recovered.
root@kali:/media/sf_CTFs/technion/RSA# ~/utils/RsaCtfTool/RsaCtfTool.py --createpub -e 3 -n 18473096353043141605128653663452648416174731299473752106362058603063730284980752397962949879606783777506771253421342413864480457235067674469343553846553026186572911067675554648668993473165030868527062412561071976264934389359293025980676196524714448432571333144690149358258582542172726817402323390753047130442190533806512650463461449072479528455800781856541756664414668969141615567560250895278163378708524136692285506075011171343723100902339041053410054982510909991189736446434444683712265826719445362731072428588091699176245390996228255030441016453511061349239911220896593008184291359123267938548809512240873694221747 > key3.pub

All that is left is to trigger the attack:

root@kali:/media/sf_CTFs/technion/RSA# export c1=17418757890010697571225865872375941584583301381739857579693572032253613879799704468931604087165132303326708151578543017525723650255000655408363696646301705641647860286526561302705881670806109372630603991207895863534232235777297707773553105685257850305087618315765930947473893918572132988826725837272436091177144026010394446869408931962876075336973358559743579282351618347472807482456062260159984711293773104029840038291648170784834513165477761041956578892035771199393262672405372137395064135451840177500263853397595864438101040660899758514083011851709595966771419288273214759911967042630654993984455542783352993074440
root@kali:/media/sf_CTFs/technion/RSA# export c2=13276745128708181233099919020835541148036443732725280634028547068521042287643493808431637397725852881021976408292417715216759851157696372441455270459630162406232369293062846735076268682819547000795981352530834751568136570861388869935008221657584227717922753189117746732845879584814041960677694603647749384545011887696963672509586210923407814361678069103156953014875420903283898624171362999298480789195198923694416285972632158619933651186279721560067803559126737079452173361136173533507631528699920900675782785049744700720592339396988859392141807085625955443511539368156057693694129455234413316811430594227628111701437
root@kali:/media/sf_CTFs/technion/RSA# export c3=730014357977750980995622077939235335031193284345639952307731254144597878843149045426798809310771214915202586021638762323363798516003930902151644504161188546194166646290133878065450605398035396147863719373364327329187878729849837805966629458426486701579644025599344374047686327459363672379352004274625688927649388683203175346373929820529966641230555155399130634310816087625135839754124926912574486175520243469707331235697158369885401659131986232527692054579222663269283078960820194472223014573462755208618182521564139347700726774175765476445763039014246617344171324437339209961438562539438096747483478158309795081750
root@kali:/media/sf_CTFs/technion/RSA# ~/utils/RsaCtfTool/RsaCtfTool.py --publickey "key1.pub,key2.pub,key3.pub" --attack hastads --uncipher $c1,$c2,$c3
private argument is not set, the private key will not be displayed, even if recovered.
[*] Multikey mode using keys: key1.pub, key2.pub, key3.pub
[*] Performing hastads attack.

Results for key1.pub,key2.pub,key3.pub:

Unciphered data :
HEX : 0x4d7920667269656e6473206f6620746865206465706172746d656e74206f6620454576696c0a576520637265617465642074686973207365727669636520746f2073707265616420666c61677320616e642066696e616c6c792064657374726f792076616164206d61646d616368210a4865726520616e6f7468657220666c61673a206373746563686e696f6e7b64306e745f336e63727970375f573174685f646966663372336e375f4e7d0a0a4c6f6e67206c697665207468652045456d7069726521
INT (big endian) : 3132885003142236915276407135326599621684031029112740977097919964151992632098465848074475214656916247202716378242592452194335775452342076076535606808258801669687951303323726721880006591144838682165605054606579646404615350292579999242373684736271501760139664991734922853239502427785309606254643932801461751630907597879035853075363089415047448632300007025445307542199951958109161914700194857616238384035540646131140678178489013026299636153697621426843438376375499873242473761
INT (little endian) : 1350489745515449452024592264350242455542847746873501544693324740706538820596057796558574737830317570086592015735561792090222875176636049262251798766296494709461218364854463076405710897568090497343457561073748234581454562000408194052587735293329645226339003865973539943775688120001645892113049966152324116103358974221377625393655903401811809730320701602981512320667100887250537171735664660684548379684015774185243956888623768169647458668091480088190906494945633516302399821
STR : b'My friends of the department of EEvil\nWe created this service to spread flags and finally destroy vaad madmach!\nHere another flag: cstechnion{d0nt_3ncryp7_W1th_diff3r3n7_N}\n\nLong live the EEmpire!'

The flag: cstechnion{d0nt_3ncryp7_W1th_diff3r3n7_N}