H@cktivityCon 2021: Sausage Links

Reading time ~3 minutes

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…

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.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

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:

  • 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
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

  • 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 == 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}

MetaRed 2021 - 4th Stage: Maradona 1,2 and 3

Here's three more binary exploitation challenges from the 4th edition of MetaRed CTF 2021. Each was the same theme but different exploits...… Continue reading

MetaRed 2021 - 3rd Stage: Note Server

Published on November 05, 2021

Killer Queen CTF: Binary Exploitation

Published on October 30, 2021