Square CTF 2021 Writeup - よっちんのブログ

この大会は2021/11/20 10:00(JST)～2021/11/21 10:00(JST)に開催されました。
今回もチームで参戦。結果は350点で119チーム中33位でした。
自分で解けた問題をWriteupとして書いておきます。

Huge Primes (web 50)

2つの値を指定し、その積が指定された数値になるようにする。整数の積である必要はないので、10で割った小数と、10を指定する。

$ curl http://challenges.2021.squarectf.com:8001/factors -d 'a=2295215232333250568867076121467149822545168433013799099035647304074168401499770179900991006696491789640050147.7&b=10'
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hugeprimes</title>
  </head>
  <body>
    <h2> 22952152323332505688670761214671498225451684330137990990356473040741684014997701799009910066964917896400501477 is a very large number that is the product of two primes (aka a semiprime)
    <h2>Input two numbers, a and b, that multiply together to equal this very large number, and input them below. Assume that a >= 2 and b >= 2</h2>
    <form action="/factors" method="POST">
      <input type="text" placeholder="a" name="a">
      <input type="text" placeholder="b" name="b">
      <button type="submit">Submit</button>
    </form>
    Correct! Here is your flag: flag{984ur9q83ndj934jd}
  </body>
</html>

flag{984ur9q83ndj934jd}

Im a credential ghoul (cryptography 300)

サーバに公開鍵が512個あるので、まずすべてダウンロードする。

$ for i in `seq -f %04g 0 511`; do wget -q http://challenges.2021.squarectf.com:5001/pubkeys/u$i.pub; done

この中で共通の素数を持つものがないか総当たりで探し、秘密鍵を生成する。

#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import itertools

e = 65537
ns = []
for i in range(512):
    pub_fname = 'pubkeys/u%04d.pub' % i
    with open(pub_fname, 'r') as f:
        pub_data = f.read()

    pubkey = RSA.importKey(pub_data)
    ns.append(pubkey.n)
    assert pubkey.e == e

for c in list(itertools.combinations(ns, 2)):
    p = GCD(c[0], c[1])
    if p > 1:
        q1 = c[0] // p
        q2 = c[1] // p
        user1 = 'u%04d' % ns.index(c[0])
        user2 = 'u%04d' % ns.index(c[1])
        print('[+] p =', p)
        print('[+] q1 =', q1)
        print('[+] q2 =', q2)
        print('[+] user1 =', user1)
        print('[+] user2 =', user2)
        break

phi1 = (p - 1) * (q1 - 1)
phi2 = (p - 1) * (q2 - 1)
d1 = inverse(e, phi1)
d2 = inverse(e, phi2)

key1 = RSA.construct((p * q1, e, d1))
key2 = RSA.construct((p * q2, e, d2))

with open('%s.key' % user1, 'w') as f:
    f.write(key1.exportKey().decode())

with open('%s.key' % user2, 'w') as f:
    f.write(key2.exportKey().decode())

実行結果は以下の通り。

[+] p = 17463372436955753648792542219049798496440392478334817703597906046050274590975100926422968957811477629971817622078856399337732226965891684031073278499213347840694895156134020171316651099408899333274891685059478163525451277313480419111552124073559622763208712509958724703319669341026064264826853306880143092678542228429404022432065686205640000031568402748549930830860680560907987325490183313276458587458132539924074953725532032449607842804001044964321207164320272098523232102393111917753723599585540402452042816761749256831951342214059623987774236694788563143868975079506355063364657073115366816541576681744003048909949
[+] q1 = 17118999727521268367327580890606825660717289393236717285547848824934877203157536483348536830541312807876965153910031163580874417600137499722137159830880703380581209180979080664738321339534806053333572599887413183029080918388598068274964159992330901853618167499266703828256482478504160926108684501834181442981292002430665296091869423323645927781347133218864532305052211471248166369266611597953138463812285666643207996060561226163171266826058571892902981020383780141766219602057486259877997447300587564470608554804005874041752980481380729046225826073876576169291459558613667282676314069201608025345057184737061077957961
[+] q2 = 18609577408079079024167523822003585548314351436825090658223198972088519599111725551878384447745125714074762007779408034571593216418239674794258454488236136468189562280867032732461524599188099043047947978747620113380460752504594378059378274598391848669686735143169437757367230613344030546152541218079722833373991045033476858989661805041289961206664571039077287907620466330768614047004609790980579947045236973848912638402813455835912084788535354508820086092033945692925149764319545038070558669310516309989446706197785674207230441663694046199224024725179489022922316395372398303994810675282726070648713959376128600744689
[+] user1 = u0170
[+] user2 = u0340

生成した秘密鍵の一つでssh接続する。

$ ssh -i u0170.key u0170@challenges.2021.squarectf.com -p 2222
The authenticity of host '[challenges.2021.squarectf.com]:2222 ([18.119.52.238]:2222)' can't be established.
ECDSA key fingerprint is SHA256:Cb0Ovh8g2M7ABFnTeI3E2TrQjUZszvB0rFiOjfH+tSA.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[challenges.2021.squarectf.com]:2222,[18.119.52.238]:2222' (ECDSA) to the list of known hosts.
flag{HEADLINE:new_prime_found_today_at_the_lage_integer_collider}
Connection to challenges.2021.squarectf.com closed.

flag{HEADLINE:new_prime_found_today_at_the_lage_integer_collider}