この大会は2022/6/4 1:00(JST)~2022/6/5 19:00(JST)に開催されました。
今回もチームで参戦。結果は4095点で118チーム中5位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity check (misc)
Discordに入り、#ruleチャネルのルールの一番最後にフラグが書いてあった。
BtSCTF{good_luck}
Identity (crypto)
x, yについて以下を満たすように指定するとフラグが表示される。
x == pow(generator, y, prime_p) * pubkey) % prime_p
すべてのパラメータがわかっているので、適当なyで計算し、xを求めればよい。
#!/usr/bin/env python3 import socket import json def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('34.107.92.149', 30085)) prime_p = 177722061268479172618036265876397003509269048504268861767046046115994443156284488651055714387194800232244730303458489864174073986896097610603558449505871398422283548997781783328299833985053166443389417018452145117134522568709774729520563358860355765070837814475957567869527710749697252440829860298572991179307 prime_q = 88861030634239586309018132938198501754634524252134430883523023057997221578142244325527857193597400116122365151729244932087036993448048805301779224752935699211141774498890891664149916992526583221694708509226072558567261284354887364760281679430177882535418907237978783934763855374848626220414930149286495589653 generator = 155023513036247948265047543654868687396096131010469506673664792405197011708229660714554316186573661708325589755749538173765363486885279182722265095526282277543504738661074255038508180451933144124775391105622347889120007632958758010276343139080391061202699695556814560529729431091459632136589488173063954346793 pubkey = 93091921640159468106305784288442650651946378295897246569419220256788465679993825629909743857075454596032445144833173746431710294553277863156332557755414563641361390587128850058131535616906913180516458195808877783654160132170722826553007632858895507833301845277489859624212766615307390655119628578839365223546 y = 0 x = (pow(generator, y, prime_p) * pubkey) % prime_p payload = json.dumps({"x": x, "y": y}) data = recvuntil(s, b': ') print(data + payload) s.sendall(payload.encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
send proof in json format: {"x": 93091921640159468106305784288442650651946378295897246569419220256788465679993825629909743857075454596032445144833173746431710294553277863156332557755414563641361390587128850058131535616906913180516458195808877783654160132170722826553007632858895507833301845277489859624212766615307390655119628578839365223546, "y": 0} Verification success BtSCTF{I_d1DN7_m4K3_i7_Ch4113nG1nG}
BtSCTF{I_d1DN7_m4K3_i7_Ch4113nG1nG}
Identity-2 (crypto)
x, yについて以下を満たすように指定するとフラグが表示される。
x == (pow(generator, y, prime_p) * pow(pubkey, c, prime_p)) % prime_p
cのパラメータも実行時にわかり、すべてのパラメータがわかっているので、適当なyで計算し、xを求めればよい。
#!/usr/bin/env python3 import socket import json def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('34.107.92.149', 2439)) prime_p = 136062877477772021443963986821466822423928306636725705955189295265171531194630539497933022412421177627488716473227275120023271715397034546804175879349877168981582602251424924699340785448683074807806407936267383798949594772365085169340683942944085482956202789355681500477966677233789310292180313638378062381719 prime_q = 68031438738886010721981993410733411211964153318362852977594647632585765597315269748966511206210588813744358236613637560011635857698517273402087939674938584490791301125712462349670392724341537403903203968133691899474797386182542584670341971472042741478101394677840750238983338616894655146090156819189031190859 generator = 68695322546411990097618816719880607069395444393834268960741680054974511660271970026150039567236118658479679444015844573677880347686810169165388385685914903968147097279757787122753390447954112451193808647256026282821032909814441591222220915875289906762225085266354556177943238500761050758957943922408034634359 pubkey = 36991800195284720665844271720947930981390989677197504667186660329002236402308726349324091955441781822949964937615015455023644196915268032941399396215222246260792225979887225009692399584709504066456654354497353988045808198493705842231370889778472138080706702885925221219949367522908916161488494916365255595354 data = recvuntil(s, b'\n').rstrip() print(data) chal = json.loads(data) c = chal['c'] y = 0 x = (pow(generator, y, prime_p) * pow(pubkey,c,prime_p)) % prime_p payload = json.dumps({"x": x, "y": y}) print(payload) s.sendall(payload.encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
{"c": 8554508060026173226740607295246315481427823631609160646634016323372970087540956464852944707162677753349119195341916576402218028466551901371599644851155529} {"x": 94209527141091215246160364916298062874273740936838084385724116936981081681291298343374894548823434041566575151153307598728950139107263463064351870013395135637557545179594967732376670015816246625364136115416032390664982895193253147782808215079678053471101913177960586980909603494537253124184157972055892048616, "y": 0} Verification success BtSCTF{NuMb3r_Us3d_0nLy_Tw1c3}
BtSCTF{NuMb3r_Us3d_0nLy_Tw1c3}
xoxoxo (crypto)
1バイト鍵のXOR暗号と推測し、フラグが"B"から始まる前提で復号する。
#!/usr/bin/env python3 with open('xoxoxo', 'r') as f: enc = bytes.fromhex(f.read().rstrip()) key = enc[0] ^ ord('B') flag = '' for c in enc: flag += chr(c ^ key) print(flag)
BtSCTF{0n3_by7e_p4d_r4r3ly_w0rks}
Shorty (crypto)
nをyafuで素因数分解する。
>yafu-x64.exe "factor(56767131765767377932609645263054275838382295575884897700121797017632070969059)" -v -threads 4 06/04/22 19:03:10 v1.34.5 @ RINA-TAKUMI, System/Build Info: Using GMP-ECM 6.3, Powered by GMP 5.1.1 detected Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes measured cpu frequency ~= 2919.493460 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> fac: factoring 56767131765767377932609645263054275838382295575884897700121797017632070969059 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C77 rho: x^2 + 2, starting 1000 iterations on C77 rho: x^2 + 1, starting 1000 iterations on C77 pm1: starting B1 = 150K, B2 = gmp-ecm default on C77 fac: setting target pretesting digits to 23.69 fac: sum of completed work is t0.00 fac: work done at B1=2000: 0 curves, max work = 30 curves fac: 30 more curves at B1=2000 needed to get to t23.69 ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default fac: setting target pretesting digits to 23.69 fac: t15: 1.00 fac: t20: 0.04 fac: sum of completed work is t15.18 fac: work done at B1=11000: 0 curves, max work = 74 curves fac: 74 more curves at B1=11000 needed to get to t23.69 ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default fac: setting target pretesting digits to 23.69 fac: t15: 7.17 fac: t20: 1.04 fac: t25: 0.05 fac: sum of completed work is t20.24 fac: work done at B1=50000: 0 curves, max work = 214 curves fac: 149 more curves at B1=50000 needed to get to t23.69 ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec fac: setting target pretesting digits to 23.69 fac: t15: 28.45 fac: t20: 8.13 fac: t25: 0.74 fac: t30: 0.05 fac: sum of completed work is t23.72 starting SIQS on c77: 56767131765767377932609645263054275838382295575884897700121797017632070969059 ==== sieve params ==== n = 77 digits, 255 bits factor base: 34944 primes (max prime = 878387) single large prime cutoff: 74662895 (85 * pmax) allocating 7 large prime slices of factor base buckets hold 2048 elements using SSE4.1 enabled 32k sieve core sieve interval: 10 blocks of size 32768 polynomial A has ~ 10 factors using multiplier of 1 using SPV correction of 20 bits, starting at offset 32 using SSE2 for x64 sieve scanning using SSE2 for resieving 13-16 bit primes using SSE2 for 8x trial divison to 13 bits using SSE4.1 and inline ASM for small prime sieving using SSE2 for poly updating up to 15 bits using SSE4.1 for medium prime poly updating using SSE4.1 and inline ASM for large prime poly updating trial factoring cutoff at 90 bits ==== sieving in progress ( 4 threads): 35008 relations needed ==== ==== Press ctrl-c to abort and save state ==== 35677 rels found: 17740 full + 17937 from 186367 partial, (10589.02 rels/sec) sieving required 74801 total polynomials trial division touched 2858589 sieve locations out of 49021583360 QS elapsed time = 19.3016 seconds. ==== post processing stage (msieve-1.38) ==== begin with 204107 relations reduce to 51278 relations in 2 passes attempting to read 51278 relations recovered 51278 relations recovered 37175 polynomials freed 12 duplicate relations attempting to build 35665 cycles found 35665 cycles in 1 passes distribution of cycle lengths: length 1 : 17740 length 2 : 17925 largest cycle: 2 relations matrix is 34944 x 35665 (5.1 MB) with weight 1045467 (29.31/col) sparse part has weight 1045467 (29.31/col) filtering completed in 4 passes matrix is 25460 x 25524 (4.0 MB) with weight 839149 (32.88/col) sparse part has weight 839149 (32.88/col) saving the first 48 matrix rows for later matrix is 25412 x 25524 (3.3 MB) with weight 680053 (26.64/col) sparse part has weight 601219 (23.56/col) matrix includes 64 packed rows using block size 10209 for processor cache size 16384 kB commencing Lanczos iteration memory use: 3.0 MB lanczos halted after 403 iterations (dim = 25412) recovered 18 nontrivial dependencies Lanczos elapsed time = 0.8870 seconds. Sqrt elapsed time = 0.0120 seconds. SIQS elapsed time = 20.2011 seconds. pretesting / qs ratio was 0.55 Total factoring time = 31.4245 seconds ***factors found*** P39 = 198575889004568310405059947668702420947 P39 = 285871220571302236301037423024394027697 ans = 1
素因数分解できたので、RSA暗号としてkeyを復号する。
あとはAESと推測して、まずECBモードで復号するが、フラグにならない。
暗号の先頭16バイトをIVとして、CBCモードで復号すると、フラグになった。
#!/usr/bin/env python3 from Crypto.Util.number import * from Crypto.Util.Padding import unpad from Crypto.Cipher import AES import base64 enc_flag = 'TVlfUkFORE9NX0lWX0NCQ3tBV1dLOJ1J/nMvT0BsVlHdmJEgYO5ZPpwU1tPifgcq5pFfxezgomriywd9wf9J693MiGqB3AnaXKF6JnyxDQw=' enc_flag = base64.b64decode(enc_flag) c = 39418869940107296504467504059240015071240032703306554459991103074090231844776 e = 3 n = 56767131765767377932609645263054275838382295575884897700121797017632070969059 p = 198575889004568310405059947668702420947 q = 285871220571302236301037423024394027697 phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) key = long_to_bytes(m) iv = enc_flag[:16] enc_flag = enc_flag[16:] cipher = AES.new(key, AES.MODE_CBC, iv) flag = unpad(cipher.decrypt(enc_flag), 16).decode() print(flag)
BtSCTF{rs4_4nd_sh0r7_k3ys_d0nt_m1x_l1k3_tw0_b17s}
Code book (crypto)
$ nc 34.107.92.149 4444 What is your name? a Here is your encrypted message: 62751a7345c8ef7528b17c13ace71270c42fbd0c5121dfad626395626b942dcb4e65733c45eb661fa356f2feb6ee84e2e05c89b4d261d9951fe6632f0d2fa5c525b9a72a2ae2a3f9fb1831049460d0fd DEBUG MODE ON LOGGING USER INPUT {"username": "a", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd04c376666008f6e42e8066d34f4ba3100ec28d0e54098068706b05b7f69c714c63d9205627136779fdaa848029a1ed521b120bc969ca4a4849feaca85b8b2c90a DEBUG MODE ON LOGGING USER INPUT {"username": "aa", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aaaaaaaa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd0de046e55630d9691bb655055b99875b188c871b167c489f15698ccf0102fc72452012aaf36f9382a475c1e939f0d02b6c8cf5eec385953e22833c030376311ec DEBUG MODE ON LOGGING USER INPUT {"username": "aaaaaaaa", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aaaaaaaaaaaa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd0662c99d1292fc6a6586a088709add2fc9e0f536b0f7422c43175286fa1b0ff4c0f88fd90bce333b4abfd0dfb96d06349e8bc98d98a3aa734a0041d78ebab4012 DEBUG MODE ON LOGGING USER INPUT {"username": "aaaaaaaaaaaa", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aaaaaaaaaaaaaaaa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd009cf7331864195029ac0fb176ca2fab902f3407f34ff7eda3d194a2e49ae2ee190b2911291a2e057682daaa65fcc76f8466c9e5f0355cf8cbd7ec192dfc64861 DEBUG MODE ON LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aaaaaaaaaaaaaaaaa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd0fd2e19347f803cd0ef96662d1ca238b6c42fbd0c5121dfad626395626b942dcb4e65733c45eb661fa356f2feb6ee84e2e05c89b4d261d9951fe6632f0d2fa5c525b9a72a2ae2a3f9fb1831049460d0fd DEBUG MODE ON LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"} $ nc 34.107.92.149 4444 What is your name? aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Here is your encrypted message: f1c424769c602d96e3d7d9649139efd083505c5fbd22f8d37c897dde817e805e83505c5fbd22f8d37c897dde817e805e4c376666008f6e42e8066d34f4ba3100ec28d0e54098068706b05b7f69c714c63d9205627136779fdaa848029a1ed521b120bc969ca4a4849feaca85b8b2c90a DEBUG MODE ON LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"}
以下のようにAES ECBモードで暗号化されると推測できる。
0123456789abcdef {"username": "aa aaaaaaaaaaaaaaa" , "flag": "FFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFF"} PPPPPPPPPPPPPPPP 0123456789abcdef {"username": "aa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa ", "flag": "FFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFF" }PPPPPPPPPPPPPPP
フラグを1文字ずつはみ出させ、ブルートフォースでブロック単位で暗号が一致するものを求めていく。
フラグ1バイト目をはみ出させる場合は、以下のような構成。
0123456789abcdef {"username": "aa aaa", "flag": "? aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaa", "flag": "F FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FF"}PPPPPPPPPPPP
#!/usr/bin/env python3 import socket import json def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) flag = '' for i in range(35): for code in range(32, 127): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('34.107.92.149', 4444)) cmp_pt = ('aaa", "flag": "' + flag)[-15:] try_pt = 'aa' + cmp_pt + chr(code) + 'a' * (35 - i) data = recvuntil(s, b'\n').rstrip() print(data) print(try_pt) s.sendall(try_pt.encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'\n').rstrip() print(data) try_ct = data data = recvuntil(s, b'\n').rstrip() print(data) data = recvuntil(s, b'}') print(data) s.close() if try_ct[32*1:32*2] == try_ct[32*4:32*5]: flag += chr(code) break print(flag)
実行結果は以下の通り。
: What is your name? aas_why_3cb_sucksza Here is your encrypted message: f1c424769c602d96e3d7d9649139efd071b0148352af4709e8e03ebf62397be372957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924 DEBUG MODE ON LOGGING USER INPUT {"username": "aas_why_3cb_sucksza", "flag": "redacted for security reasons"} What is your name? aas_why_3cb_sucks{a Here is your encrypted message: f1c424769c602d96e3d7d9649139efd043642ee30ab2a12b427f8c50237fc14672957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924 DEBUG MODE ON LOGGING USER INPUT {"username": "aas_why_3cb_sucks{a", "flag": "redacted for security reasons"} What is your name? aas_why_3cb_sucks|a Here is your encrypted message: f1c424769c602d96e3d7d9649139efd0b89c902f4933db53c54d40bd04d41f9172957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924 DEBUG MODE ON LOGGING USER INPUT {"username": "aas_why_3cb_sucks|a", "flag": "redacted for security reasons"} What is your name? aas_why_3cb_sucks}a Here is your encrypted message: f1c424769c602d96e3d7d9649139efd09c0a04efd23960a8e629361af9a251dc72957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924 DEBUG MODE ON LOGGING USER INPUT {"username": "aas_why_3cb_sucks} BtSCTF{0h_s0_th1s_1s_why_3cb_sucks}
BtSCTF{0h_s0_th1s_1s_why_3cb_sucks}
Substitute (crypto)
some_catsディレクトリには26個の猫の画像がある。おそらくアルファベットに対応している。catsフォルダには同じ猫の画像の他に、スペースや記号の画像がある。まずは画像ファイルのハッシュ値を元に、catsフォルダの画像を文字に対応付けしてみる。
#!/usr/bin/env python3 from hashlib import * from string import * hashes = [] for i in range(1, 27): fname = 'static/some_cats/%d.jpg' % i with open(fname, 'rb') as f: data = f.read() hashes.append(md5(data).hexdigest()) msg = '' others = {} for i in range(1, 682): fname = 'static/cats/%d.jpg' % i with open(fname, 'rb') as f: data = f.read() h = md5(data).hexdigest() if h in hashes: msg += ascii_uppercase[hashes.index(h)] elif h in others: msg += others[h] else: if i == 4: others[h] = ' ' msg += ' ' elif i == 58: others[h] = '.' msg += '.' elif i == 249: others[h] = ',' msg += ',' elif i == 335: others[h] = '{' msg += '{' elif i == 339: others[h] = '_' msg += '_' elif i == 367: others[h] = '}' msg += '}' print(msg)
文字に対応付けした結果は以下の通り。
GUR PNG VF N QBZRFGVP FCRPVRF BS FZNYY PNEAVIBEBHF ZNZZNY. VG VF GUR BAYL QBZRFGVPNGRQ FCRPVRF VA GUR SNZVYL SRYVQNR NAQ VF BSGRA ERSREERQ GB NF GUR QBZRFGVP PNG GB QVFGVATHVFU VG SEBZ GUR JVYQ ZRZOREF BS GUR SNZVYL. N PNG PNA RVGURE OR N UBHFR PNG, N SNEZ PNG BE N SRENY PNG. GUR YNGGRE ENATRF SERRYL NAQ NIBVQF UHZNA PBAGNPG. OGFPGS{EBG_VF_SHAAVRE_JVGU_N_PNG_GJVFG}QBZRFGVP PNGF NER INYHRQ OL UHZNAF SBE PBZCNAVBAFUVC NAQ GURVE NOVYVGL GB XVYY EBQRAGF. GUR PNG VF FVZVYNE VA NANGBZL GB GUR BGURE SRYVQ FCRPVRF. VG UNF N FGEBAT SYRKVOYR OBQL, DHVPX ERSYRKRF, FUNEC GRRGU NAQ ERGENPGNOYR PYNJF NQNCGRQ GB XVYYVAT FZNYY CERL. VGF AVTUG IVFVBA NAQ FRAFR BS FZRYY NER JRYY QRIRYBCRQ.
quipqiupで復号する。
THE CAT IS A DOMESTIC SPECIES OF SMALL CARNIVOROUS MAMMAL. IT IS THE ONLY DOMESTICATED SPECIES IN THE FAMILY FELIDAE AND IS OFTEN REFERRED TO AS THE DOMESTIC CAT TO DISTINGUISH IT FROM THE WILD MEMBERS OF THE FAMILY. A CAT CAN EITHER BE A HOUSE CAT, A FARM CAT OR A FERAL CAT. THE LATTER RANGES FREELY AND AVOIDS HUMAN CONTACT. BTSCTF{ROT_IS_FUNNIER_WITH_A_CAT_TWIST}DOMESTIC CATS ARE VALUED BY HUMANS FOR COMPANIONSHIP AND THEIR ABILITY TO KILL RODENTS. THE CAT IS SIMILAR IN ANATOMY TO THE OTHER FELID SPECIES. IT HAS A STRONG FLEXIBLE BODY, QUICK REFLEXES, SHARP TEETH AND RETRACTABLE CLAWS ADAPTED TO KILLING SMALL PREY. ITS NIGHT VISION AND SENSE OF SMELL ARE WELL DEVELOPED.
BtSCTF{rot_is_funnier_with_a_cat_twist}