この大会は2022/8/6 9:00(JST)～2022/8/8 9:00(JST)に開催されました。
今回もチームで参戦。結果は1071点で978チーム中77位でした。
自分で解けた問題をWriteupとして書いておきます。
kcehc-ytinas (misc)
問題の画像にフラグが書いてある。
corctf{}
tadpole (crypto)
(a * s0 + b) % p = s1
(a * s1 + b) % p = s2
:a * s0 + b - s1 と a * s1 + b - s2 のGCDはpの倍数になる。算出した結果、このGCDは素数だったため、pとなり、文字列化したものがflag.txtの内容になる。
#!/usr/bin/env python3 from Crypto.Util.number import * with open('output.txt', 'r') as f: params = f.read().splitlines() a = int(params[0].split(' ')[-1]) b = int(params[1].split(' ')[-1]) s0 = 31337 s1 = int(params[2].split(' ')[-1]) s2 = int(params[3].split(' ')[-1]) p = GCD(a * s0 + b - s1, a * s1 + b - s2) assert isPrime(p) flag = long_to_bytes(p).decode() print(flag)
実行結果は以下の通り。
corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm
corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs}
luckyguess (crypto)
サーバの処理概要は以下の通り。
・p = 2**521 - 1 ・a, b: 521ビットランダム整数 →表示 ・x, y: 数値入力 ・r: 20ビットランダム整数 ・r回以下を実行 ・x = (x * a + b) % p ・xとyが一致していたら、フラグが表示される。
x = (x * a + b) % pの計算結果、数値が変わらないxを探したい。
(x * a + b) - x = ((a - 1) * x + b) % p = 0
以下を指定すれば、rがいくつでも成り立つ。
x = (- b * inverse(a - 1, p)) % p y = x
#!/usr/bin/env python3 import socket from Crypto.Util.number import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) p = 2**521 - 1 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('be.ax', 31800)) data = recvuntil(s, b'\n').rstrip() print(data) a = int(data.split(' ')[-1]) data = recvuntil(s, b'\n').rstrip() print(data) b = int(data.split(' ')[-1]) x = (- b * inverse(a - 1, p)) % p y = x data = recvuntil(s, b': ') print(data + str(x)) s.sendall(str(x).encode() + b'\n') data = recvuntil(s, b'? ') print(data + str(y)) s.sendall(str(y).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
a = 4496702450299806666453832352896272067591803868391465137420208302940258369380071436162833748847621418782395740876184132823788142924697833411894369979180668818
b = 5264591053321672221313008073184006566971295393561687430668344183063642535819535395657748525569075676534278222486221423611586430427129902239842794687536930639
enter your starting point: 2735417212112793604137313523887142455327338863599240337781053390694812213723193400050215322192075006002747944014987641909121980753467616522947894040488226130
alright, what's your guess? 2735417212112793604137313523887142455327338863599240337781053390694812213723193400050215322192075006002747944014987641909121980753467616522947894040488226130
wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}
corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}
Microsoft ❤️ Linux (rev)
$ file m_3l.exe m_3l.exe: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, no section header $ strings m_3l.exe >ci!>Uy<cjx<8e,,<p Well done! Sadly, Linus Torvalds has embraced, extended and extinguished the other half of the flag :( $Incorrect :( $Well done! Sadly, Microsoft has embraced, extended and extinguished the other half of the flag :( Incorrect :(
以下の文字列をCyberChefのXOR Brute Force、鍵長1で復号する。
>ci!>Uy<cjx<8e,,<p → Key = 0d: 3nd,3Xt1ngu15h!!1}
Ghidraでデコンパイルすると、該当するデータが以下のように見える。
DAT_00100210 XREF[1]: entry:00100071(R)
00100210 6c undefined1 6Ch
00100211 ed ?? EDh
00100212 4e ?? 4Eh N
00100213 6c ?? 6Ch l
00100214 8e ?? 8Eh
00100215 cc ?? CCh
00100216 6f ?? 6Fh o
00100217 66 ?? 66h f
00100218 ad ?? ADh
00100219 4c ?? 4Ch L
0010021a 4e ?? 4Eh N
0010021b 86 ?? 86h
0010021c 6c ?? 6Ch l
0010021d 66 ?? 66h f
0010021e 85 ?? 85h
0010021f 66 ?? 66h f
00100220 0f ?? 0Fh
00100221 8e ?? 8Eh
00100222 3e ?? 3Eh >
00100223 63 ?? 63h c
00100224 69 ?? 69h i
00100225 21 ?? 21h !
00100226 3e ?? 3Eh >
00100227 55 ?? 55h U
00100228 79 ?? 79h y
00100229 3c ?? 3Ch <
0010022a 63 ?? 63h c
0010022b 6a ?? 6Ah j
0010022c 78 ?? 78h x
0010022d 3c ?? 3Ch <
0010022e 38 ?? 38h 8
0010022f 65 ?? 65h e
00100230 2c ?? 2Ch ,
00100231 2c ?? 2Ch ,
00100232 3c ?? 3Ch <
00100233 70 ?? 70h p前半が"corctf{"から始まることを想定して2進数の値を確認する。
>>> bin(ord('c'))[2:].zfill(8)
'01100011'
>>> bin(0x6c)[2:].zfill(8)
'01101100'
>>> bin(ord('o'))[2:].zfill(8)
'01101111'
>>> bin(0xed)[2:].zfill(8)
'11101101'
>>> bin(ord('r'))[2:].zfill(8)
'01110010'
>>> bin(0x4e)[2:].zfill(8)
'01001110'左へ3ビットシフトし、はみ出した分は右にループさせる。前半と後半の復号結果を結合すると、フラグになる。
#!/usr/bin/env python3 with open('m_3l.exe', 'rb') as f: data = f.read() data1 = data[0x210:0x222] data2 = data[0x222:0x234] flag1 = '' for d in data1: b = bin(d)[2:].zfill(8) new_b = b[3:] + b[:3] flag1 += chr(int(new_b, 2)) key2 = 0x0d flag2 = '' for d in data2: flag2 += chr(d ^ key2) flag = flag1 + flag2 print(flag)
corctf{3mbr4c3,3xt3nd,3Xt1ngu15h!!1}
exchanged (crypto)
暗号処理の概要は以下の通り。
・p: 固定の素数 ・a, b, s: p未満ランダム整数 ・p, a, b, s出力 ・a_priv, b_priv: p未満ランダム整数 ・A: a_priv回f(s)実行 ※f(s): (a * s + b) % p ・B: b_priv回f(s)実行 ・A, B出力 ・shared: b_priv回f(A)実行 ・key: sharedを文字列化したもののsha256ダイジェストの先頭16バイト ・iv: ランダム16バイト文字列 ・iv + [flagをAES-CBCで暗号化]の16進数表記を出力
s1 = (a * s0 + b) % p s2 = (a * s1 + b) % p s3 = (a * s2 + b) % p ↓ s2 - s1 = (a * (s1 - s0)) % p s3 - s2 = (a * (s2 - s1)) % p = (a * a * (s1 - s0)) % p ↓ sn+1 - sn = (a**n * (s1 - s0)) % p ↓ pow(a, a_priv, p) = ((f(A) - A) * inverse(f(s) - s, p)) % p
このDLPを解き、a_privを求める。
f(shared) - shared = a**a_priv * (f(B) - B) % p ↓ (a * shared + b) - shared = a**a_priv * (f(B) - B) % p ↓ (a - 1) * shared + b = a**a_priv * (f(B) - B) % p ↓ shared = (a**a_priv * (f(B) - B) - b) * inverse(a - 1, p) % p
上記により、sharedを求めれば、keyがわかり、フラグを復号することができる。
#!/usr/bin/env sage from Crypto.Util.number import * from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from hashlib import sha256 def f(s): return (a * s + b) % p with open('output.txt', 'r') as fr: params = fr.read().splitlines() p = int(params[0].split(' ')[-1]) a = int(params[1].split(' ')[-1]) b = int(params[2].split(' ')[-1]) s = int(params[3].split(' ')[-1]) A = int(params[4].split(' ')[-1]) B = int(params[5].split(' ')[-1]) ct = bytes.fromhex(params[6]) X_A = ((f(A) - A) * inverse(f(s) - s, p)) % p R = IntegerModRing(p) a_priv = discrete_log(R(X_A), R(a)) print('[+] a_priv =', a_priv) shared = int((pow(a, a_priv, p) * (f(B) - B) - b) * inverse(a - 1, p) % p) print('[+] shared =', shared) key = sha256(long_to_bytes(shared)).digest()[:16] iv = ct[:16] ct = ct[16:] cipher = AES.new(key, AES.MODE_CBC, iv=iv) flag = unpad(cipher.decrypt(ct), 16).decode() print('[*] flag =', flag)
実行結果は以下の通り。
[+] a_priv = 63497966771228335993935218724355716676359926182967975463093060105894867914802051403524263838451533117998140812842659902100945139428076742018151358770711075499718955791059569760306592803008376586431708302909649602374612770031446609941268056564386982932718212036534269872682126736591975854896102855270700008372
[+] shared = 86382471144674987516192390676739968790606018844855369676663312319897424264589519056860582366433954661923689613455950996957073708730586503567240461427068073600946731416068482076340126294642483394238838801798961052802865121895198819944744990914204503217602305639165324158861726404756338767093146109002421799336
[*] flag = corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}
corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}
hidE (crypto)
サーバの処理概要は以下の通り。
・p, q: 512ビット素数 ・n = p * q ・phi = (p - 1) * (q - 1) ・random.seed(int(time.time())) ・nを表示 ・以下繰り返し ・x: "1", "2", "3"から選択 ・xが"1"の場合 ・flagを暗号化して表示 ・e: 1以上n以下のランダム整数 ・pt: flagの数値化 ・ct = pow(pt, e, n) ・ctの文字列化を16進数表記で返す ・xが"2"の場合 ・msg: hexで入力 ・msgをhexデコードして、暗号化して表示 ・xが"3"の場合、終了
eの再取得の条件をできるだけ正しいものにするために、"2"を選択してeを取得し、取得できたeからGCD(e, phi)が2より大きいものをできるだけ集める。その条件から"1"の選択により2つのeを推測し、対応するctを取得し、Common Modulus Attackによりフラグを復号する。
#!/usr/bin/env python3 import socket import random import time import math import binascii import gmpy2 from Crypto.Util.number import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def commom_modules_attack(c1, c2, e1, e2, n): gcd, s1, s2 = gmpy2.gcdext(e1, e2) if s1 < 0: s1 = - s1 c1 = gmpy2.invert(c1, n) elif s2 < 0: s2 = - s2 c2 = gmpy2.invert(c2, n) v = pow(c1, s1, n) w = pow(c2, s2, n) x = (v * w) % n return x s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('be.ax', 31124)) # arrange seed = int(time.time() - 0.92) random.seed(seed) data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) n = int(data.split(' ')[-1]) ok = [] ng = [] for _ in range(16): data = recvuntil(s, b': ') print(data + '2') s.sendall(b'2\n') data = recvuntil(s, b': ') print(data + '02') s.sendall(b'02\n') data = recvuntil(s, b'\n').rstrip() print(data) ct = bytes_to_long(binascii.unhexlify(data.split(' ')[-1].encode())) while True: e = random.randint(1, n) if pow(2, e, n) == ct: ok.append(e) break else: ng.append(e) ps = [] for p in range(100): if isPrime(p): for v_ok in ok: for v_ng in ng: if GCD(v_ng, p) == p and GCD(v_ok, p) == 1: if p not in ps: ps.append(p) p_mult = 1 for p in ps: p_mult *= p es = [] cs = [] for _ in range(2): data = recvuntil(s, b': ') print(data + '1') s.sendall(b'1\n') data = recvuntil(s, b'\n').rstrip() print(data) ct = bytes_to_long(binascii.unhexlify(data.split(' ')[-1].encode())) cs.append(ct) while True: e = random.randint(1, n) if GCD(e, p_mult) == 1: break es.append(e) m = commom_modules_attack(cs[0], cs[1], es[0], es[1], n) flag = long_to_bytes(m).decode() print(flag)
100%成功するわけではないが、何回か実行し、成功した実行結果は以下の通りとなった。
Secure Encryption Service
Your modulus is: 100441865619649378327411672611065384009678541478296740785037651890715045575097534735728258948356210109119098621834146040918288856216227335820807190579935830941844864899436808591597411868589841498023638713884299205329379884680708425329513629944504571472006538006678795572250308583657883848458360292045182818929
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 1c713e78e8c0cd67c07e33c2078dde622beaacb3f15c3dc95ad9174d40b562f88442e2388a8aae17a9e30ac2f06e60c751636a8ad4b65882bd3fc0892c8d7064e6794cf08dd7a9ce1c8da1225dff6330d2e44eacce2774aa46acaedd04881f62e55acfa2457687806f36b5d01dc81d56beeb7a119838a2af6c17b186f2e59089
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 3273254bbbbdb532a4c0c3da2f0bd10d7871d6a925f81756b99365fad8bbf1c1f553e508ad5cf0211ffc7f7053fc31ec1ad7a9468f44fd570319a633c0508b357e387943ace4c1b415ccc8e351a6459ead7f7719d1d613c3d8884b5b6dcb0dd8d3e83a9effc30f8c52ca9aaeae9c4123c7020764865ce6df6a9f31b1e6ffab16
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 8e9e3eb5928f7ce91c85a143f56bd86aba82af74e7d94aa4345f45ed364a7a26ff89bcc674fe19dbf0564dadcbc7cdb2b8d424829260c946def0939c5a4e5997cc4a59fc10624f1a957d56a1510dc3b6be38b58efe75b2c937dc26486fd128b6970e0a7fe600bcfd075d138c568444d903b6b9804e49dbf9e681675674cb2648
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 5b21fc94591495318ff10a623def92fb996c0c878b8e5c09d453a98bf1e3e4ad1ba51ccf4ab906ad2955d5df6cb6812fe5f61a888e5fa81c5f2a3fdc8cd1c375df3ef0075c1a4d723b3d34151a055fd45f2741583ca277aa50d2316653a3cc709d36c71efe033836c2b9cb4d5db8e4b0e83245c987ee2ea6ee49649849869376
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 48c63e2346b6ffaec1b3680cb3ae83896379612cb491b735ef85f03c30a36fdaedeaad4d4b2182972cb6d97b868668fa6ae5ddd98ced1a4f16979ac4440dec81ed2cff78630673cc816231e54785602ac19f31b8d6591a5437815859443e844417da0361df3e6410a5b6e2cf3fa61a754ede485f05017c6ffadbabdaaa52994a
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 238ff7ad3b205fdd581e44781a6dccc1b785745e7cbdea7a0b469b7e8a0bb9120ec27c83308888c99655795ef28c693bd0691742f3434a4e4d9d4405e758036223c3512938ec13df0d703b44a1e85096d2759fe994b82395d394fe9df172dc424b6eba17984581cf6db6d44de1d1b98742580641b6afd46dc671e0bb18d9854c
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 856ef0586917d222c338c7c40088dd4d0a38e4dab80e4d3c947b8d2d68e8fd898a928fa1d5e74a8fb4bfb3804e17eddef4967ca5d5c3e5be033045cffb5745a0d65cde116c370c3eb125e2205ac2fbb1a1842568e81b79ecab18ae6ac4c57e0774ca206d87b4b5a74733e71c8a94001dbac45d1c588b51f8d39be204309c8970
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 4f26819cfcb5caa491ba9af612a2d520c9cb281e048c2a0dd5805ccf36fda3cd0531699b3d9f3395dcdc61748024a6a99842e4a217fe17b6722aee3d2406f6317268ee045b1b694929aaa18632a95a756b41d0633b8ff05ccb5e8104de1ece54f547f9b48e89c452eab2ff8bec9f3256cdad49de37b95bb8740a327557ab0048
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 6637b2318da9e7e035f6c69d4782299f3857fec067cd5c3ed0ece1c2ed5cb0b4d16a7cf2e5439e84cabbd75b6cf9635dfc25d67039d2087abe8df95b2f74df99b5ea78713736cda5123e65bb4bb445e7fdfcea733b6b177c7e6f558b3561c32ae9bad46394cbb47c4c3602f19977d19614d7f5c78a2b48d1b1a91847e01c3bd1
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 70fd5921b23c58c4769347d4c90978b61b4d3dfa2739d51a4abc6811866ca35e7404160f938b4379018f1251d4d49185a71343c7930913a1f99926283f3ce1d6c4a04320be517f9c7bb6b4afc4e22981e0888414bee19ce8e69d0352d27a627f2128fb1377fa20ed0f9e198d59a1c84b60a60f8494290dcf1bf7190b5d8368a4
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 64a4716d166adb618e60b55acff6f55a60ea8d19967f56f168775b4677a586a37ca82ac1bfedff7530b5b41d4d011dc0b80f37537515ddad795ad016fefe74ee061d573269ec187c59d06bb42500c399a66c91561b4c2de4c87921559871985f6c698aa776f8fa594999a811b24cfd81dba41201d8830be1d057ea063c447f68
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 20a504b1c72f3db1465a89b0603c0ad208f5f9fe3f67e6abd901a991328323bb732e5a84d8b6c4cb8c755610d1c0fffcd8fc7f30b424c224b8a07516ec99c528af054529213979bc99112a7c40b55588ee641125f8850ee10ce350745ac75007446d44fac52b0b5cfd95b8005359fe6ced4af13aea3ee0319953b32701ecc07b
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 66bde99c575a9ab3ef65f380c1dc466cccf62b6221305cf94f111d78ee88daf9d9a6893819469011a6a0cfcbfab149a9c46ba6bca9412cec337a0c7a3ce8efd8e181f549a558ab2b8282e83a07fd6890ebd9bc09003d6d2202f3beaba50412d8853fcd88eb23342954e301f568fd5f3d1625b99fce3efe18ce7f9b61d326ba8a
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 076c15bf6e586e95dc1d03e2f48ddf6213413de381161e65174bcb58339e14d452ac81d33f134e6c4819b525820c49d68f2cd0ccd6351901f26838981a7ca6188bd99c77ed38fc3db124784db34bb848f7fb20504150b1d51da644cafd86d949c17b5cb87e47a340f6c83b543b6bc786695934d8a65343e7d50b549a8b9f603e
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 78b49972cd061171be34ecb6d08c182a1c1dd5d6a2aa41a158ee8b5261b2c38c9519f9d0d91b372d63b62aeeec38637be79d5640d08534de2823b07c33d0b964d1387814354f68e8fb9e19f2e349c3c6663480bbc1876bc8213d0e71172153dc7c4a52a1a6a6c5cc771f9d7d9446658bba073bc2bb79a37e508a15732613d8a2
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 2
Enter your message in hex: 02
Here is your encrypted message: 4706873cb52c8151dec9d38aeb90712e021b92382299bbd88cd5fb6f3c92893f29d469acb2dd04243ea4b740d04560a9905972ea87fcb5acdb387d654a2f9f2972e1a4b85787caaaa4a6434a5115c1c1fcb80d44491526637d7f376946e320e3a6749e7c2f2b70e0297dea726de6a6ce7a9b515596adc497fcac842451132bfc
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 1
Here is your encrypted flag: 768b36dec8a2bb0962b3fa2bb17fa6dfae8c3a77c70c17668490a9c30fe27f02e0c4b89853f095deb307015f33ca6e50b3607da1caac456756bbfbf64fa2cdc24fc43b0070cbc8a06f29d7cc1902335b7b27ab2d9b6fc696ff69c29b550a70551b67f596c406784b9fb00dcc01fee10bb1cf0f7d7b2cfdc57740ad49c643f3f2
Options
-------
(1) Encrypt flag
(2) Encrypt message
(3) Quit
Choose an option: 1
Here is your encrypted flag: 258871f01c6f2090b29a7614151e1817e12b58049cc9ec4ee287e8ba2221e51c47a3fc1bbf47e0735834bc72937095958a534f5bb579645779bcd54b20b7c6b0d6a62607f031ec0d8549590f45abad25b4ba7a863f03369ba6902424e10e84289d274ee63065fb6970fd57da910336240f3b54dab83a3d03d1701433ee345e14
corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}
corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}
survey (misc)
すべてのアンケートに答えたら、最後のページにbase64文字列が提示されているので、デコードすれば良さそう。
$ echo Y29yY3Rme2hvcGVfeW91X2hhZF9mdW59 | base64 -d corctf{hope_you_had_fun}
corctf{hope_you_had_fun}
