Bad keys

197 Points

---

I captured this encrypted message a while ago. Today, I got into their network and managed to take a snapshot of their key server. I don't think more than 10k messages have been sent between when I captured the message and when I took the snapshot.

You can access the snapshot here: nc 138.68.67.161 60005

---

I solved this challenge with Hyperreality and the help of a stack exchange post. We are given access to a server which gives public, private key pairs. We have a ciphertext c. To solve this challenge, we generate new key pairs and use an algorithm to factor N using (e,d,n) and try to find a weakness in the implementation.

To factor N, I used the algorithm described by fgrieu here which I repeat

1. Compute f <- ed - 1 and express f = 2**s * t
2. Set i = s and a = 2
3. Compute b = a**t mod n
   • If b == 1: set a to the next prime and jump to 3.
4. If i != 1:
   • Compute c = b**2 mod N
   • If c != 1 set b = c and i -= 1
   • Jump to 4.
5. If b == N - 1: set a to next prime and jump to 3.
6. Compute p = gcd(N, b - 1) and q = N // q

Putting this into python, we can write an algorithm to factor generated keys. Note I discard any key pairs that have d < 0. Potentially there's a way to use these, but as I don't have \phi(N) I couldn't see a quick way and it was easier to just grab a different key pair.

from sympy import nextprime
import math 

def find_prime_factors(n,e,d):
    k = e * d - 1
    s = 0 
    t = k

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

    i = s
    a = 2

    while True:
        b = pow(a,t,n)

        if b == 1:
            a = nextprime(a)
            continue

        while i != 1:
            c = pow(b,2,n)
            if c == 1:
                break
            else:
                b = c
                i -= 1

        if b == n - 1:
            a = nextprime(a)
            continue

        p = math.gcd(b-1, n)
        q = n // p
        return p, q

keys = [
((65537, 16730003700605898732103808147265049097309227731116112091966825592580794522488597118108918276114596284933863997925167175825551948545026542789031655603762767594028984696331306133063729472164129741174402731943970446813396896291870363659061827254054595300539660296594191052826127087049878251823692914198236061007), (4549013014706152484948805425702476080901634773768849924147410349265144245094325352773256689814335502044973929887338130723275946764001602033973848404093142468913140303660855127247147909135645926989846389684877266437028310259235212527602515443688484814503867603041563521965407000243692658755982940385673478273, 16730003700605898732103808147265049097309227731116112091966825592580794522488597118108918276114596284933863997925167175825551948545026542789031655603762767594028984696331306133063729472164129741174402731943970446813396896291870363659061827254054595300539660296594191052826127087049878251823692914198236061007)),
((65537, 144517755992564048861504174877857487852987341166328935206455623191881428189718009215250567859676443497706126512409112506483468354898393992286046087915659080819539156733582684190969034177936751150611020408774463197135796355334158803766859705325385107989926116428050293832482242072477621375482173139770930869421), (31054878277053870334567699083035033666991481539365707836985436339949435482182564410613451137034398183899100960896249926435550678884204076984976228025637830486164122358535037197188466113194006283698671271205473089863266402202388548638617988140763543550548546126891968521417488321501698697994048418712496082773, 144517755992564048861504174877857487852987341166328935206455623191881428189718009215250567859676443497706126512409112506483468354898393992286046087915659080819539156733582684190969034177936751150611020408774463197135796355334158803766859705325385107989926116428050293832482242072477621375482173139770930869421)),
((65537, 123741962902154205189909884965124653318102255507428661008324023486380505709197314715589325195416080106121685443970029442140815672039378844508982777903697232853456171326974565483936014318756930718266360727767369367994474730211277431252795244877611270845326337495473012176653152632601881293713941472626554833217), (15541146171592097027910161636143568083087411158302108866129286316376977012869113591162484332262229814509171809654352691430200555358898443156589975814049037029826267580422408827286358483357720841255938886100043208316256177732763374420025617386627628801933221633401610870745630145991479549460332955788507442461, 123741962902154205189909884965124653318102255507428661008324023486380505709197314715589325195416080106121685443970029442140815672039378844508982777903697232853456171326974565483936014318756930718266360727767369367994474730211277431252795244877611270845326337495473012176653152632601881293713941472626554833217))]

e = 65537

for k in keys:
    n = k[0][1]
    d = k[1][0]
    if d > 0:
        p, q = find_prime_factors(n,e,d)
        if p == 1 or q == 1:
            print('[-] Algorithm broken')
        else:
            print("[+] Prime pair found")
            print("p = ", p)
            print("q = ", q)
            print("")

Running this script we get the following prime pairs

[+] Prime pair found
p =  1380623332297453118984873537786777519839182349276676087241139668719694587529609212189422107766171700904217158758941493834627126539787388156700567832193247
q =  12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864081

[+] Prime pair found
p =  12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129865231
q =  11926153121375457949010884635428120250029675016450611713057458832154147128348531323843554423542842489299014770027236460611202063816127702713202828814511491

[+] Prime pair found
p =  10211655910202382811964911729055262513625584135244524229115154619070582543942720064521969215139126418488027025507905871989461676818719689776178201641556303
q =  12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129865839

and we see that for each prime pair, one prime seems to be very close in value. Guessing that the algorithm is generating p as p = nextprime(p) we can find the prime factors of N by starting with one of our found p and going backwards towards 0 until we find a factor.

from Crypto.Util.number import inverse

p0 = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864081

n = 2318553827267041599931064141028026591078453523755133761420994537426231546233197332557815088229590256567177621743082082713100922775483908922217521567861530205737139513575691852244362271068595653732088709994411183164926098663772268120044065766077197167667585331637038825079142327613226776540743407081106744519
e = 65537
c = 2255296633936604604490193777189642999170921517383872458719910324954614900683697288325565056935796303372973284169167013060432104141786712034296127844869460366430567132977266285093487512605926172985342614713659881511775812329365735530831957367531121557358020217773884517112603921006673150910870383826703797655

while True:
    if n % p0 == 0:
        p = p0
        q = n // p
        phi = (p-1)*(q-1)
        d = inverse(e,phi)
        m = pow(c,d,n)
        print(bytes.fromhex(format(m,'x')).decode('utf-8'))
        break
    p0 -= 2

Flag

HackTM{SanTa_ple@s3_TakE_mE_0ff_yOur_l1st_4f2d20ec18}

Original writeup (https://github.com/jack4818/CTF/blob/master/HackTM/readme.md).