swapped - openECSC - Walkthrough

Intro

This is a write-up for the challenge swapped of the openECSC competition. The challenge was rated as easy and contains two files, chall.py and output.txt.

output.txt content

I’m providing this file for anyone working through the challenge on their own.

N = 15645291629336676173452523665479966641549663029511406922591627966349033854046461193916717587062784418418884041906894266710723352555629413165733211432574714724004524581719819852210320366618663431805409883744870339931343799548264088641101056234665541662805740785444731719105742156418645804539912980832903937448988084182871628785371716750244543974032357033441587174836969377753263270293383555610133209593432713310685211342360724932526513920507234878706128843474723033064828822921829907489228281701101437766108791767842228037434455575223463208459227453856056734072769319409732570763152508416296704941384742389346373085251
primes = [94702418154069635448485990005812615732260709417810154777837589115235171329961, 74740302032029936941793075214256318553133624399259255906193982952217517713919, 102417040721788813587907777725516982121419224708689428235647237143694063731851, 110268372205108623872549220976509054352279361862090847192197359610994000662509, 114200462961848536195586358334261595124477794941339353745390412567741427558883, 76300261044316868422252787233676317217009570883746437967825127771465936890989, 91517240214721832452392104102512611974053170999965066779447192941005813525309, 77317657917806590177226699455009338787500605142123634032609118473192309822853, 64629840611708126358703960554236940650077675398378064917681587536063531344737]
e_residues = [73202545289090958105687519874164891582323813822403077825610814725240657081993, 47334322483582084750084183902844304846210665951321623916519242495793904908981, 76424012313967398382519263910578352948737432324795476941000596659630686417001, 1053045462242093797655189267336319584537875621561480110537943803387439305390, 31857341508561418414122204330395977484386970269736729202158964842913145088812, 30854214342268324841001078882562466126856145492568629680291251884285063089410, 71855994814286115581120401888066847776430565778117155851631781539231524733782, 65022384125458125147781746598237844903797802157282167031848529625742374276711, 45186685716073291045995972293483783519162221831221111538382446713678053488783]

Analysis

The challenge code starts by defining two primes p,q with each 1024 bits, then it will multiply these two primes and generate N now it will generate e, this is a 500 bits large prime. With that prime and Euler’s totient, d is calculated. Next d and e is switched and 9 new primes are generated. These primes are now used and e is calculated modulo against these primes. This is now saved in e_residues which is outputted. The primes p and q are now used to generate an AES key by simply concatenating these numbers together as strings. With this AES key the flag is encrypted.

This is a implementation oriented on RSA - Two primes multiplied, Euler’s totient and the inverse to calculate d and a prime e to calculate d.

from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
if p > q:
	p, q = q, p
N = p * q

e = getPrime(500)
d = pow(e, -1, (p-1)*(q-1))
e, d = d, e

primes = [getPrime(256) for _ in range(9)]
e_residues = [e % p for p in primes]

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256

flag = open('flag.txt', 'rb').read()
key = sha256((str(p) + str(q)).encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()

open('output.txt', 'w').write(f'''\
{N = }
{primes = }
{e_residues = }
ct = {ct}
''')

To find the flag we must recover the two primes p and q. For that I started recovering e or d, not the prime (getPrime(500)) but the other number (the switch makes it hard to refer to the right number).

To do recover the number CRT (Chinese Reminder Theorem) can be used. CRT solves the following problem for x.

\[\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}\]

Next we need to find d or originally e, for that another well known method can be used. The e can be found using the Wiener’s attack. This attack is possible if d or e is smaller than:

\[d < \tfrac{1}{3}n^{1/4}\]

For a 2048-bit n, the attack may work if the prime is smaller than 510.42 bits, so because we have a prime smaller than 510 bits the attack will most likely succeed.

After recovering e,d the last step is to factor n, this can be done using a simple algorithm explained here. The full code to factor p and q I wrote in sage math Python, this allows the use of some helper functions.

from sage.all import *

N = 15645291629336676173452523665479966641549663029511406922591627966349033854046461193916717587062784418418884041906894266710723352555629413165733211432574714724004524581719819852210320366618663431805409883744870339931343799548264088641101056234665541662805740785444731719105742156418645804539912980832903937448988084182871628785371716750244543974032357033441587174836969377753263270293383555610133209593432713310685211342360724932526513920507234878706128843474723033064828822921829907489228281701101437766108791767842228037434455575223463208459227453856056734072769319409732570763152508416296704941384742389346373085251
primes = [94702418154069635448485990005812615732260709417810154777837589115235171329961, 74740302032029936941793075214256318553133624399259255906193982952217517713919, 102417040721788813587907777725516982121419224708689428235647237143694063731851, 110268372205108623872549220976509054352279361862090847192197359610994000662509, 114200462961848536195586358334261595124477794941339353745390412567741427558883, 76300261044316868422252787233676317217009570883746437967825127771465936890989, 91517240214721832452392104102512611974053170999965066779447192941005813525309, 77317657917806590177226699455009338787500605142123634032609118473192309822853, 64629840611708126358703960554236940650077675398378064917681587536063531344737]
e_residues = [73202545289090958105687519874164891582323813822403077825610814725240657081993, 47334322483582084750084183902844304846210665951321623916519242495793904908981, 76424012313967398382519263910578352948737432324795476941000596659630686417001, 1053045462242093797655189267336319584537875621561480110537943803387439305390, 31857341508561418414122204330395977484386970269736729202158964842913145088812, 30854214342268324841001078882562466126856145492568629680291251884285063089410, 71855994814286115581120401888066847776430565778117155851631781539231524733782, 65022384125458125147781746598237844903797802157282167031848529625742374276711, 45186685716073291045995972293483783519162221831221111538382446713678053488783]

# Copied from https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack
def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x**2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None

# https://di-mgt.com.au/rsa_factorize_n.html
def factor_from_edn(e, d, n):
    k = e*d - 1

    t = k
    s = 0
    while t % 2 == 0:
        t //= 2
        s += 1

    for a in range(2, 100):
        g = power_mod(a, t, n)
        if g == 1 or g == n-1:
            continue
        for r in range(s):
            x = power_mod(g, 2^r, n)
            if x != 1 and x != n-1:
                p = gcd(x-1, n)
                if 1 < p < n:
                    q = n // p
                    return (p, q)
    return None

d = crt(e_residues, primes)
e = wiener(d,N)

p,q = factor_from_edn(e, d, N)


print(f"p = {p}")
print(f"q = {q}")

Running the script will give you:

$ sage factor_n.sage
p = 120180800648793269529537358173196762645172015716941093930461418827640354634563604372221225171188445310835749521688284494353614901804934293003635530627167684709520027350625271848585918013980548024626428764021596562148588994932320953162608024728288099129657079317400850452977186365879747395996088186262363444087
q = 130181289730771733733284720989144899041307109817072744297945850313296760182143674396965368137009604270678332728929082826597790067528062124990316220313942958969199994948887007336747189752382937421154322332891704523711454624332122692331233670314012092506753240557427942488064554625786271142312410971085776538773

With these factors the flag can easily be decrypted. For that I build a small Python script.

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256

p = 120180800648793269529537358173196762645172015716941093930461418827640354634563604372221225171188445310835749521688284494353614901804934293003635530627167684709520027350625271848585918013980548024626428764021596562148588994932320953162608024728288099129657079317400850452977186365879747395996088186262363444087
q = 130181289730771733733284720989144899041307109817072744297945850313296760182143674396965368137009604270678332728929082826597790067528062124990316220313942958969199994948887007336747189752382937421154322332891704523711454624332122692331233670314012092506753240557427942488064554625786271142312410971085776538773
ct = bytes.fromhex("e32fe4a8d6ac6aa94797cd338471c3c06311bf8836731779fa94208a862127aa2f714cb7e63e498eb1f81ab94161a72aa5bee26dcb8fbd90f3f3ca1dbb2c85ef")


key = sha256((str(p) + str(q)).encode()).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(ct),16).decode()
()

print(flag)

$ python3 decrypt.py
openECSC{0h_n0!M4yb3_I_sh0uldn'7_sw4p_e_4nd_d_4f73r_4ll...}