I think what makes a addictive CTF for me is when there are great challenges, lots of them, and the difficulty ramp up exists. This CTF had all of that and more. Warmups that were actually good warmups and tricky challenges that seemed impossible at first but were able to be reasoned through. This was a combo RSA challenge so it’s one of my personal favourites. Solution follows…
Sausage Links - Crypto - 468 points
This challenge reads:
The thing about crypto is that you can really see how the sausage is made.
(55 Solves)
Along with the challenge comes one file:
sausage_links.pyoutput.txt
The first file is the crypto algorithm that generated the second, output file. The python code looks like this:
#!/usr/bin/env python3
from gmpy import *
from Crypto.Util.number import *
import gensafeprime
flag = open("flag.txt", "rb").read().strip()
bits = 512
p = getPrime(bits)
q = getPrime(bits)
r = getPrime(bits)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
l = min([p, q, r])
d = getPrime(1 << 8)
e = inverse(d, phi)
a = gensafeprime.generate(2 * bits)
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a // 2, a) != 1:
break
pubkey = (n, e, a, g)
m = bytes_to_long(flag)
k = getRandomRange(2, a)
K = pow(g, k, a)
c1, c2 = pow(k, e, n), (m * K) % a
print("c =", (c1, c2))
print("pubkey =", pubkey)
The output:
c = (75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158,
21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829)
pubkey = (549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659,
32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819,
138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003,
68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148)
So looking over the code it starts off being fairly straight forward multi-prime RSA but then instead of straight encrypting the plaintext, they encrypt a value smallk which is a unknown exponent for an also known multiple of the plaintext large K.
So whatever the solution we know its going to be multi-stage.
The first thing that strikes me is that the generation of d is non standard. We take a 256bit d and derive e. This is the reverse of the usual method of deriving d and results in a vulnerability.
When e is much larger than d RSA is vulnerable to a well known attack called the Wiener attack. In fact the multi-prime variant of the Wiener attack was successful in recovering d given just n and e which we have in output.txt. I used the following sage code for that:
from sage.all import continued_fraction, Integer
def wiener(e, n):
m = 12345
c = pow(m, e, n)
q0 = 1
list1 = continued_fraction(Integer(e)/Integer(n))
conv = list1.convergents()
for i in conv:
k = i.numerator()
q1 = i.denominator()
for r in range(20):
for s in range(20):
d = r*q1 + s*q0
m1 = pow(c, d, n)
if m1 == m:
return d
q0 = q1
n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659
e = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819
print(wiener(e, n))
Which gives us:
sage wienermultiprime.sage
105139577487193794924679137792353224445415748360286951415614751393941533449299
So now lets take stock of what we have, from the public key in the output.txt and from the Wiener attack we have:
neagdc1c2
Since we have d we can recover k because c1 = k^e mod n which is straight RSA. Given we know d we can recover k = c1^d mod n which we do:
$ python3
Python 3.7.3 (default, Dec 20 2019, 18:57:59)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659
>>> e = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819
>>> d = 105139577487193794924679137792353224445415748360286951415614751393941533449299
>>> c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158
>>> k = pow(c1,d,n)
>>> k
92449882290632192062695828036356192821408895931839505770706370321296723692758224108358059047687875177218763667938426907916521787525226310445637171357686000666987150706002699570581752483847162567531608798195544732522067279248228215992737333625285922266069987986855921775296450095878528071232840612456334753015
And now we have
neagdc1c2k
Since we have k, g and a we can now derive big K with K = pow(g, k, a)
>>> a = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003
>>> g = 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148
>>> K = pow(g,k,a)
>>> K
99208625026312969322038863713640017536424384684224429228051632792423668576822030310040517382564862288089386755158402685402748887616148827167071544963123535071562797630137630252731493700131249586093480508436251309418242370721435577759447098729426405067212389216466715901445361120236979290828606839479099319462
Finall we know that c2 = mK mod a of which we know c2, K and a and this is very similar to another problem from a recent CTF called broken rsa. I wrote a module in goRsaTool for this attack so I created a key where n == a and e == Klike:
c = 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829
n = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003
e = 99208625026312969322038863713640017536424384684224429228051632792423668576822030310040517382564862288089386755158402685402748887616148827167071544963123535071562797630137630252731493700131249586093480508436251309418242370721435577759447098729426405067212389216466715901445361120236979290828606839479099319462
Then I solved it with the tool and got the flag~!:
$ goRsaTool -key step4.pub -verbose -attack brokenrsa
rsatool: rsatool.go:92: starting up...
Recovered plaintext:
flag{8e66cb103c88b9306f9766f8d08c4242}