TU CTF 2016 - Secure Auth
To authenticate on a server we had to provide a message signed with a RSA private key. Hopefully the server allows us to sign any message except the one requested with the same key.
Description
We have set up this fancy automatic signing server!
We also uses RSA authentication, so it’s super secure!
nc 104.196.116.248 54321
Details
Points: 150
Category: crypto
Validations: ??
Solution
When we connected to the server, it allowed us to sign any message. Then the server requested to enter the message “get_your_hands_off_my_RSA!” signed with the same private key. Obviously if we submit the same message during the first step we are log out.
To check which kind of encryption it was, we sent \(1\) and the answer was \(1\). We could deduce that plain RSA without padding was used i.e: \(c = m^d \mod n\). However, here \(n\) is unknown. We can make a guess that \(e=65535\) and since \((m^d)^e = m \mod n\) we could recover \(n\) with two messages. We just sent \(m_1 = 2\) and \(m_2 = 3\) to the server and we got their signed versions \(c_1\) and \(c_2\). Then since \(c_1^e = m_1 \mod n\) and \(c_2^e = m_2 \mod n\) we got \(n = \gcd\left((c_1)^e-2, (c_2)^e)-3\right)\). We used python and gmpy2 to compute \(n\):
import gmpy2
p1 = 2
c1 = 1438242638420798550659770696667339503061587298399039115167859387217668016041298644325362936352503542244558858550458689864149937247495146219980629064787725070457091100874718718595684379615029831264304563445895740407478498
9669415716416976943634700112742863193960197312120027334581680378810383183189375758553311410386860957811463706965027839371289711509435783344202675399390663868414563021058027279997968565453588095134958447108844607826268685488308957303644517501130058784899200381504158295372643901703020359389255276602083755593693491381287831187570255825154201817206107917330952054361590281956621332116325736145079491
p2 = 3
c2 = 24166230041237059787088740157531046863881564402880555787415094071037505212806243980447738762074437613735098334490393767909374740598222713459758990881349309266235103729288793764568646412887702434814260187077198153694349046664588314930362892808274302965447686672745794304494585028704149994718148482508062759447942675221627809613810371992898236407250409961982096410989920396315613877786934911257614544725209650490555438972185193262771690628822218095037939304660508704563811757706098952621573919952422557481890298583071226099962187929457126872828775078423870295520402490561817035806244204359736389020935058018356039855243
n = gmpy2.gcd(c1**e -p1, c2**e-p2)
n
After a few minutes of computation we got:
24690625680063774371747714092931245796723840632401231916590850908498671935961736332195862060536688021640067386108834202275189822898599594463635840996761025690456263370146016114156010619769568905940572317842895114700949532134039597475463182795837468991755433866386124620786221838783092089725622611582198259472856998222335236408416769316026577935933861556358082075245487480828539893580743606793508167690532131893625600405714820107050359744864841126038929638426613876368411017300987682339192115588614533886473808385041303878518137898225847735216970008990188644891634667174415391598670430735870182014445537116749235017327
We verified that indeed this value is the correct \(n\). The message to sign to be authenticated was m=”get_your_hands_off_my_RSA!”. The idea to bypass the server was to sign \(m\cdot 2\) which is different than \(m\) and then to sign the inverse of \(2\) modulo \(n\). Finally the correct signature was given by multiplying the two: \((m\cdot 2)^d \cdot (2^{-1})^d \mod n\):
import gmpy2
import binascii
p = int(binascii.hexlify(b'get_your_hands_off_my_RSA!'), 16)
2p = 2*p
inv2 = gmpy2.invert(2,n)
# Here we submit the values to the server
signed2p = 15443163048328392178653572157753694298529243486207445619209245168180820996663277754977799822900598842933580431901873137275739816886482130666484006981333965923258622462097035562111673223298428917395863123681949538244795442561604547937329197276213967529547329897584943615038626633260308572547502478074079055214743747991209087457113287308115248262570228358304330797330525320488349965497762186847177868230469275275152610908436623797270655094268307055490696549161519287246077015992469639643694881623097785443531646120831370771868715835037392318408690124525722295111166234310519078127214036760101417129986509956386462867047
signedinv2 = 17786133810719647133431304733691577155800915488191939149652458278583596104606057742550177283771244643801821136340068117448134576532563256128104172469864145380781595351625433397923606883535535898809867134530807196335895273438187307534752389526288031621122446684472560216219053378020935316965798933447612466369417027209297140982998507840414435757953949655590443562133223563134527260600166509232933047559515699911456734313960969781573549940646465384825832943770558118347174732397752822801911245044133929649704455458585172300853292205217014678640072658882494790781119010474364677419278487061942879879550905457936483449928
print((signedinv2 * signed2p) % n)
It gave us the following valid signature:
16731309037744947405926028571747718963854298965390002727198808171611075973611158728603997341487825480249213585462140621721705101265202241553108259732805730732012422439917896027354259084296598758557279195952085526863232351709194566418049311562248561487590587504210746190069919352300232450715996257931281563810914263141798176828653031180718851152873031741675056595543813218917662466149613065701594193565469205686782466011045874808045523869902250336505402591380957800616790950931308393154964359092946813432795336188787305915519015059512730649067373975490061407596342991545022406186499635623108035721389174787835020868696
Giving this signature to the server make it outputed the flag.