Challenge Points: 303
Challenge is running on the service: nc 47.75.39.249 23333
After surpassing the Proof of Work, we get the following challenge:
On selecting the option get code, we get the following code that is being used for encryption:
#!/usr/bin/env python3
# -*- coding=utf-8 -*-
from Crypto.Util.number import getPrime, GCD, bytes_to_long
from hashlib import sha256
import random
import signal
import sys, os
signal.alarm(20)
m = b"xxxxxxxxxxxxxx"
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
e = 3
def proof():
strings = "abcdefghijklmnopqrstuvwxyzWOERFJASKL"
prefix = "".join(random.sample(strings, 6))
starwith = str(random.randint(10000, 99999))
pf = """
sha256("%s"+str).hexdigest().startswith("%s") == True
Please give me str
"""%(prefix, starwith)
print(pf)
s = input().strip()
if sha256((prefix+s).encode()).hexdigest().startswith(starwith):
return True
else:
return False
def cmd():
help = """
1. get code
2. get flag
Please tell me, what you want?
"""
while True:
print(help)
c = input().strip()
if c == "1":
return True
elif c == "2":
return False
else:
print("Enter Error!")
def main():
if not proof():
print("Check Failed!")
return
welcom()
if cmd():
f = open("file.py")
print(f.read())
return
mm = bytes_to_long(m)
assert pow(mm, e) != pow(mm, e, n)
sys.stdout.write("Please give me a padding: ")
padding = input().strip()
padding = int(sha256(padding.encode()).hexdigest(),16)
c = pow(mm+padding, e, n)
print("Your Ciphertext is: %s"%c)
if __name__ == '__main__':
main()
Upon selecting the get flag option, the following computation is done:
$$c \equiv (flag + sha256(input))^3\mod n$$
where input is an input string that we give to the server, sha256() is a function that generates integer representation of SHA-256 hash of the input and c is the corresponding ciphertext.
Server then returns c as the output. One important thing to note here is that \(m^3 > n\), hence we cannot directly calculate cube root of the ciphertext.
Public key values:
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
e = 3
Vulnerability
Allowing user controlled padding exposes the challenge to Franklin-Reiter’s related message attack.
I found an easier way to solve this challenge using very basic Algebra and Number Theory concepts, as compared to the attack described in the above hyperlink.
First, we send 2 as an input to the server and get corresponding ciphertext:
c1 = 14550589053226237723784378782911157204367764723816957959635387925652898370034365455451983914571405062459535687617841302966938233065296973978472553109061974458935966754832788411876301179210585984208608247433383774246743661884093657109502619626436726032508763685599880808525861655167503719155953736308920858354069083437923495143680174206534169208623366776314544036377265501358254923029291010047210371394197963442022610746743020719292018028518885149189744832788117626194748311114409968846879212425054195323473068436359069318372735069308398135560733890706617536127579272964863500568572120716434126233695562326533941909353
Next, we send 1 as an input to the server and get corresponding ciphertext:
c2 = 14550589053226237723784378782911157204367764723813789158271625147472004207734354619642445255036997940341703539883653916130592718879734436263217819317202435434496341973502556894834798718992952369685841347018901038478081710519253844078907000973324354805502890255414196801758171762906898874914776720897920729518384393581853690034053515213192846817920534901501370942556249012415259244063185938984570137371682805276444650716010228924732495062415330875872004691866847132147232457398743319930259327973290858489741376000333603734294893832124907092640953321640151851853501528390729805151850605432707293088635480863375398001441
For c1 and c2 we can write the following:
h1 = int(sha256('2').hexdigest(), 16)
h2 = int(sha256('1').hexdigest(), 16)
\(c_1\equiv (m+h_1)^3\mod n\) –> (1)
\(c_2\equiv (m+h_2)^3\mod n\) –> (2)
where m is the flag that we want to calculate!
On expanding (1) we get:
\(\implies c_1 \equiv m^3 + h_1^3 + 3m^2h_1 + 3mh_1^2\mod n\) –> (3)
Similarly, on expanding (2) we get:
\(\implies c_2 \equiv m^3 + h_2^3 + 3m^2h_2 + 3mh_2^2\mod n\) –> (4)
Subtracting (4) from (3), we get:
$$c_1 - c_2 \equiv (h_1-h_2)(h_1^2 + h_1h_2 + h_2^2) + 3m^2(h_1 - h_2) + 3m(h_1 + h_2)(h_1 - h_2)\mod n$$
$$\frac{c_1 - c_2}{h_1 - h_2}\equiv (h_1^2 + h_1h_2 + h_2^2) + 3m^2 + 3m(h_1 + h_2) \mod n$$
If we substitute \(x = \frac{c_1 - c_2}{h_1 - h_2}\), we get: $$3m^2 + 3m(h_1 + h_2) + (h_1^2 + h_1h_2 + h_2^2 - x)\equiv 0\mod n$$ The above equation is quadratic, we also know the values of \(h_1\) & \(h_2\).
According to the quadratic formula, we have:
$$m \equiv \frac{-b;\pm;\sqrt{b^2-4ac}}{2a}\mod n$$
Hence, we can calculate m as:
$$m \equiv \frac{-3(h_1+h_2);\pm;\sqrt{(3(h_1+h_2))^2-12(h_1^2 + h_1h_2 + h_2^2 - x)}}{6}\mod n$$
Wrote the following script to implement the attack:
import hashlib
import gmpy2
from Crypto.Util.number import *
hash1 = int(hashlib.sha256('2').hexdigest(), 16)
hash2 = int(hashlib.sha256('1').hexdigest(), 16)
diff = hash1 - hash2
print "diff: ", diff
# M1 = M2 + diff
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941L
e = 3
c1 = 14550589053226237723784378782911157204367764723816957959635387925652898370034365455451983914571405062459535687617841302966938233065296973978472553109061974458935966754832788411876301179210585984208608247433383774246743661884093657109502619626436726032508763685599880808525861655167503719155953736308920858354069083437923495143680174206534169208623366776314544036377265501358254923029291010047210371394197963442022610746743020719292018028518885149189744832788117626194748311114409968846879212425054195323473068436359069318372735069308398135560733890706617536127579272964863500568572120716434126233695562326533941909353
c2 = 14550589053226237723784378782911157204367764723813789158271625147472004207734354619642445255036997940341703539883653916130592718879734436263217819317202435434496341973502556894834798718992952369685841347018901038478081710519253844078907000973324354805502890255414196801758171762906898874914776720897920729518384393581853690034053515213192846817920534901501370942556249012415259244063185938984570137371682805276444650716010228924732495062415330875872004691866847132147232457398743319930259327973290858489741376000333603734294893832124907092640953321640151851853501528390729805151850605432707293088635480863375398001441
assert c2 < n
assert c1 < n
assert c1 > c2
res = (c1 - c2) / (hash1 - hash2)
a = 3
b = 3*(hash1 + hash2)
c = (hash1**2 + hash1*hash2 + hash2**2) - res
assert b**2 - 4*a*c >= 0
det = gmpy2.iroot(b**2 - 4*a*c, 2)
#Result of the above operation
det = 895117860555194221639962847152553327251877885494596369020458400464169641215830527612022789636620223733091925404109820014339798528983673228478908782900199621057014409705139235003835944181120537080102658020544028036693589036615231884111568905196654L
sol1 = (det - b)/(2*a)
print long_to_bytes(sol1)
Flag: N1CTF{f7efbf4e5f5ef78ca1fb9c8f5eb02635}