## September 18, 2021

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…

``````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.py `
• `output.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

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 small`k` 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:

• `n`
• `e`
• `a`
• `g`
• `d`
• `c1`
• `c2`

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
>>> n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659
>>> e = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819
>>> d = 105139577487193794924679137792353224445415748360286951415614751393941533449299
>>> c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158
>>> k = pow(c1,d,n)
>>> k
92449882290632192062695828036356192821408895931839505770706370321296723692758224108358059047687875177218763667938426907916521787525226310445637171357686000666987150706002699570581752483847162567531608798195544732522067279248228215992737333625285922266069987986855921775296450095878528071232840612456334753015
``````

And now we have

• `n`
• `e`
• `a`
• `g`
• `d`
• `c1`
• `c2`
• `k`

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 == K`like:

``````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}
``````

### Interviewing in Tech: Security Engineer & Security Analyst

Landing a job as a security engineer or analyst at a tech company is a significant feat. It requires not only technical acumen but also s...… Continue reading

#### BSides Sydney 2023 Writeups

Published on November 24, 2023

#### DUCTF 2023 Writeups

Published on August 31, 2023