Zh3r0 CTF V2 Writeup - よっちんのブログ

この大会は2021/6/4 19:30(JST)～2021/6/6 19:30(JST)に開催されました。
今回もチームで参戦。結果は802点で509チーム中84位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity (Miscellaneous)

ボットとのダイレクトメッセージの画面で、キャプチャの画面があったので、それ通りに入力したら、認証され、たくさんのチャネルが現れた。
#generalチャネルのトピックにフラグが書いてあった。

zh3r0{pepega_welcomes_you}

alice_bob_dave (Cryptography)

コードから以下のことがわかる。

p, q, rが素数で、p*qがn_a、p*rがn_b
d_a * e = phin_a * K1 + 1
d_b * e = phin_b * K2 + 1

d_a * e - 1 と d_b * e - 1の公約数がp-1の倍数
d_a * e - 1 は q -1の倍数
d_b * e - 1 は r -1の倍数

このことを元に、総当たりする。

from Crypto.Util.number import *

with open('out.txt', 'r') as f:
    ct_a = int(f.readline().rstrip().split('=')[1])
    ct_b = int(f.readline().rstrip().split('=')[1])
    d_a = int(f.readline().rstrip().split('=')[1])
    d_b = int(f.readline().rstrip().split('=')[1])
    e = int(f.readline().rstrip().split('=')[1])

gcd = GCD(d_a * e - 1, d_b * e - 1)

assert gcd == 2**2 * 3**2 * 1543 * 36097 * 1014259 * 17275267 * 33878479 * 64555363525704839503363 * 13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377

found = False
for p1 in [1, 3, 9]:
    for p2 in [1, 1543]:
        for p3 in [1, 36097]:
            for p4 in [1, 1014259]:
                for p5 in [1, 17275267]:
                    for p6 in [1, 33878479]:
                        for p7 in [1, 64555363525704839503363]:
                            for p8 in [1, 13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377]:
                                p = 2 * p1 * p2 * p3 * p4 * p5 * p6 * p7 * p8 + 1
                                p_len = p.bit_length()
                                if p_len >= 1024 and p_len < e and isPrime(p):
                                    found = True
                                    break
                            if found:
                                break
                        if found:
                            break
                    if found:
                        break
                if found:
                    break
            if found:
                break
        if found:
            break
    if found:
        break

assert (p - 1) == 2 * 3 * 1543 * 36097 * 1014259 * 17275267 * 33878479 * 64555363525704839503363 * 13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377

q1_mul = (d_a * e - 1) // (p - 1)

assert q1_mul == 2 * 3 * 17 * 28477 * 446123 * 3425679978376722446974230434232163920387229130754907722265986179928914393151313003930026636801644623099638625399801901729015562443496707013076331076237419405886597644185021528782663003968243002532905487627662567073247807979311630226501920897804604814041174853131931494489398720132565094809828020782561

found = False
for q1 in [1, 3]:
    for q2 in [1, 17]:
        for q3 in [1, 28477]:
            for q4 in [1, 446123]:
                for q5 in [1, 3425679978376722446974230434232163920387229130754907722265986179928914393151313003930026636801644623099638625399801901729015562443496707013076331076237419405886597644185021528782663003968243002532905487627662567073247807979311630226501920897804604814041174853131931494489398720132565094809828020782561]:
                    q = 2 * q1 * q2 * q3 * q4 * q5 + 1
                    q_len = q.bit_length()
                    if q_len >= 1024 and q_len < e and isPrime(q):
                        found = True
                        break
                if found:
                    break
            if found:
                break
        if found:
            break
    if found:
        break

r1_mul = (d_b * e - 1) // (p - 1)

assert r1_mul == 2 * 3 * 5 * 7**2 * 1061 * 3628661705374329801288584656206517727469079240696568564912797145160579905203512130357711158521367796173130983769813752899084424100760957640159746556085008812434696654436784654212606745417711422551821253640083639947075320534392852628962946756153019439438678191911446280633672359886787115206132834040058986343

found = False
for r1 in [1, 3]:
    for r2 in [1, 5]:
        for r3 in [1, 7, 49]:
            for r4 in [1, 1061]:
                for r5 in [1, 3628661705374329801288584656206517727469079240696568564912797145160579905203512130357711158521367796173130983769813752899084424100760957640159746556085008812434696654436784654212606745417711422551821253640083639947075320534392852628962946756153019439438678191911446280633672359886787115206132834040058986343]:
                    r = 2 * r1 * r2 * r3 * r4 * r5 + 1
                    r_len = r.bit_length()
                    if r_len >= 1024 and r_len < e and isPrime(r):
                        found = True
                        break
                if found:
                    break
            if found:
                break
        if found:
            break
    if found:
        break

print '[+] p =', p
print '[+] q =', q
print '[+] r =', r

n_a = p * q
n_b = p * r
phin_a = (p - 1) * (q - 1)
phin_b = (p - 1) * (r - 1)
d_a = inverse(e, phin_a)
d_b = inverse(e, phin_b)
pt_a = pow(ct_a, d_a, n_a)
pt_b = pow(ct_b, d_b, n_b)
msg_a = long_to_bytes(pt_a)
msg_b = long_to_bytes(pt_b)
print '[+] msg_a:', msg_a
print '[+] msg_b:', msg_b

実行結果は以下の通り。

[+] p = 177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163
[+] q = 155884012157322571917571429609117477794801005792976713173607792359939561733216007547732077875565730627490168412882054028115468195925968305125054508969875158276459353283308944667481012666571096247936714275405402155862690247593753125976847078582510938772358086998385220759841590572613434454768180423789003022307
[+] r = 152403791625721851654120555560673744553701328109255879726337480096744356018547509475023868657897447439271501318332177621761545812231960220886709355355570370122257259486344955476929483307543879747176492652883512877777163462444499810416443763758426816456424484060280743786614239115245058838657579029682477426407
[+] msg_a: Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_
[+] msg_b: Hey Dave its Bob here.My flag is 70_R3sCue_3742986}

zh3r0{GCD_c0m3s_70_R3sCue_3742986}

chaos (Cryptography)

パラメータの値で検索すると、Chaotic Hash Functionのことが書いてある。https://eprint.iacr.org/2005/403.pdfには衝突について書いてあるので、その値をそのまま使い、投入する。

$ nc crypto.zh3r0.cf 2222
input first string to hash : 0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
input second string to hash : 0124fdce89ab57eaba89370afedc45efbfe54da84832cb1e894c5d830ec3c520
b'zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure} ,courtsey crazy contini : https://littlemaninmyhead.wordpress.com/2015/09/28/so-you-want-to-learn-to-break-ciphers/'

zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}