この大会は2018/3/17 5:30(JST)～2018/3/22 5:00(JST)に開催されました。
今回もチームで参戦。結果は2955点で1516チーム中16位でした。
自分で解けた問題をWriteupとして書いておきます。
IRC (MISC 10)
freenodeで#angstromctfチャネルに入る。
11:04 *topic : Need help from an admin? All of the channel operators are admins. | You didn't forget your password, login is currently down! All will be well soon. | IRC flag: actf{irc} | ?ngstromCTF 2018 will start sometime soon PM EDT :: https://angstromctf.com/ | Everything is dead sorry...but soon it shall be reborn
actf{irc}
WARMUP (CRYPTO 10)
暗号はパッと見た感じシーザー暗号。
myjd{ij_fkwizq}
しかし復号できず。問題文の「it's a fine cipher.」からAffine暗号と推測。https://www.dcode.fr/affine-cipher でブルートフォースで復号。
A=19,B=12 ACTFITBEGIN
actf{it_begins}
BACK TO BASE-ICS (CRYPTO 20)
Part 1: 011000010110001101110100011001100111101100110000011011100110010101011111011101000111011100110000010111110110011000110000 Part 2: 165 162 137 145 151 147 150 164 137 163 151 170 164 63 63 Part 3: 6e5f7468317274797477305f733178 Part 4: dHlmMHVyX25vX20wcmV9
それぞれエンコードしているものを復号し、結合する。
Part1: 2進数 Part2: 8進数 Part3: hexエンコード Part4: Base64エンコード
e1 = '011000010110001101110100011001100111101100110000011011100110010101011111011101000111011100110000010111110110011000110000' flag1 = '' for i in range(0, len(e1), 8): flag1 += chr(int(e1[i:i+8], 2)) e2 = '165 162 137 145 151 147 150 164 137 163 151 170 164 63 63 ' e2 = e2.split(' ') flag2 = '' for i in range(len(e2) - 1): flag2 += chr(int(e2[i], 8)) e3 = '6e5f7468317274797477305f733178' flag3 = e3.decode('hex') e4 = 'dHlmMHVyX25vX20wcmV9' flag4 = e4.decode('base64') flag = flag1 + flag2 + flag3 + flag4 print flag
actf{0ne_tw0_f0ur_eight_sixt33n_th1rtytw0_s1xtyf0ur_no_m0re}
XOR (CRYPTO 40)
XORキーは1文字のようなので、平文がactfで始まることを前提に復号する。
with open('ciphertext.txt', 'r') as f: data = f.read().strip().decode('hex') key = ord(data[0]) ^ ord('a') flag = '' for i in range(len(data)): flag += chr(ord(data[i]) ^ key) print flag
actf{hope_you_used_a_script}
INTRO TO RSA (CRYPTO 50)
p, q, e, cがわかっているので、そのまま復号する。
p = 169524110085046954319747170465105648233168702937955683889447853815898670069828343980818367807171215202643149176857117014826791242142210124521380573480143683660195568906553119683192470329413953411905742074448392816913467035316596822218317488903257069007949137629543010054246885909276872349326142152285347048927 q = 170780128973387404254550233211898468299200117082734909936129463191969072080198908267381169837578188594808676174446856901962451707859231958269401958672950141944679827844646158659922175597068183903642473161665782065958249304202759597168259072368123700040163659262941978786363797334903233540121308223989457248267 e = 65537 c = 4531850464036745618300770366164614386495084945985129111541252641569745463086472656370005978297267807299415858324820149933137259813719550825795569865301790252501254180057121806754411506817019631341846094836070057184169015820234429382145019281935017707994070217705460907511942438972962653164287761695982230728969508370400854478181107445003385579261993625770566932506870421547033934140554009090766102575218045185956824020910463996496543098753308927618692783836021742365910050093343747616861660744940014683025321538719970946739880943167282065095406465354971096477229669290277771547093476011147370441338501427786766482964 n = p * q phi = (p - 1) * (q - 1) x = 0 while True: if (phi * x + 1) % e == 0: d = (phi * x + 1) / e break x = x + 1 m = pow(c, d, n) flag = ('%x' % m).decode('hex') print flag
actf{rsa_is_reallllly_fun!!!!!!}
OFB (CRYPTO 120)
4の倍数の長さになるよう\x00を付ける。その後4バイトずつの配列にする。
4バイト単位で暗号化しているが、PNGのフォーマットを前提にx, a, cがわかる。
x1 = a * x0 + c mod m x2 = a * x1 + c mod m x3 = a * x2 + c mod m x2 - x1 = a * (x1 - x0) mod m x3 - x1 = a * (x2 - x0) mod m a = (x2 - x1) * modinv(x1 - x0, m) c = x1 - (x0 * a) mod m
これで4バイト単位にxor鍵が割り出せるので、復号できる。
import struct def lcg(m, a, c, x): return (a * x + c) % m def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) m = pow(2, 32) with open('flag.png.enc', 'rb') as f: ciphertext = f.read() PNG_HEAD = '\x89PNG\x0d\x0a\x1a\x0a\x00\x00\x00\x0d' x = [] for i in range(0, len(PNG_HEAD), 4): iXor = int(ciphertext[i:i+4].encode('hex'), 16) iPlain = int(PNG_HEAD[i:i+4].encode('hex'), 16) x.append(iXor ^ iPlain) x1 = x[2] - x[1] alpha = x[1] - x[0] g1, p1, q1 = egcd(alpha, m) if g1 == 1: mod_inv = p1 % m elif g1 == -1: mod_inv = - p1 % m else: modinv = 0 a = (x1 * mod_inv) % m c = (x[1] - x[0] * a) % m flag = '' x = x[0] for i in range(0, len(ciphertext), 4): flag += struct.pack('>I', x ^ struct.unpack('>I', ciphertext[i:i+4])[0]) x = lcg(m, a, c, x) while True: if flag[-1] == '\x00': flag = flag[:-1] else: break with open('flag.png', 'wb') as f: f.write(flag)
復号したPNG画像にフラグが書いてあった。
actf{pad_rng}
SSH (CRYPTO 150)
公開鍵をPEM形式に変換し、内容を確認する。
$ ssh-keygen -f id_rsa.pub -e -m PKCS8 > id_rsa.pub.pem $ openssl rsa -pubin -text < id_rsa.pub.pem Public-Key: (2048 bit) Modulus: 00:be:5d:95:8b:09:b2:29:1c:f0:bd:36:51:1c:91: 55:e2:29:f8:ae:8d:cc:ae:e1:55:2c:96:69:b8:1b: 53:2a:36:3b:4f:34:76:94:12:86:7c:cf:92:cb:40: ad:de:f5:20:0a:05:dc:de:f0:9c:8d:a3:09:82:fa: 54:13:d9:52:f4:e7:db:3d:a7:39:51:9f:ab:77:d5: 74:de:52:36:6c:96:03:ac:e8:87:c0:cb:f3:2c:52: 47:ce:c1:42:28:e8:a7:2a:a5:25:67:99:e5:4c:40: f3:a2:2d:46:42:cd:af:5e:0d:d0:77:33:11:58:e7: d8:4d:ba:87:56:d5:31:a4:bb:4d:2b:a3:e7:9c:29: 97:2f:27:eb:8d:0b:f9:df:81:e2:e9:cd:a2:3b:0d: de:ad:23:c0:0a:ae:bf:a0:f5:38:32:77:a2:21:77: 72:9a:9c:b5:ee:58:c4:70:19:b6:cb:32:2d:7f:b9: a4:1d:f3:a2:d5:62:df:d2:02:f9:06:3b:5e:5e:50: 42:cf:ef:6d:dc:fe:41:23:28:67:e1:c1:22:a8:dc: c1:8c:e5:1e:fb:b8:cc:5f:9b:c0:f3:29:6f:10:91: ca:30:10:ed:85:12:73:d4:ca:40:67:57:53:da:89: 6a:e5:fc:fa:01:59:3a:7c:84:d5:18:c5:03:c0:ae: e5:81 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAvl2ViwmyKRzwvTZRHJFV 4in4ro3MruFVLJZpuBtTKjY7TzR2lBKGfM+Sy0Ct3vUgCgXc3vCcjaMJgvpUE9lS 9OfbPac5UZ+rd9V03lI2bJYDrOiHwMvzLFJHzsFCKOinKqUlZ5nlTEDzoi1GQs2v Xg3QdzMRWOfYTbqHVtUxpLtNK6PnnCmXLyfrjQv534Hi6c2iOw3erSPACq6/oPU4 MneiIXdympy17ljEcBm2yzItf7mkHfOi1WLf0gL5BjteXlBCz+9t3P5BIyhn4cEi qNzBjOUe+7jMX5vA8ylvEJHKMBDthRJz1MpAZ1dT2olq5fz6AVk6fITVGMUDwK7l gQIDAQAB -----END PUBLIC KEY-----
n = 0x00be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867ccf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c9603ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d84dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f5383277a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896ae5fcfa01593a7c84d518c503c0aee581
秘密鍵は大部分がマスクされている。与えられた情報から秘密鍵を復元することができれば、フラグが得られそう。
https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pemを参考
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
バイナリで構成を見てみる。
version 0x0000 - 0x0006 (30 82 04 A3 02 01 00) 7 modulus 0x0007 - 0x010b (02 82 01 01) 261(257) publicExponent 0x010c - 0x0110 (02 03) 010001 5(3) privateExponent 0x0111 - 0x0214 (02 82 01 00) 260(256) prime1 0x0215 - 0x0298 (02 81 81) 132(129) prime2 0x0299 - 0x031c (02 81 81) 132(129) exponent1 0x031d - 0x03a0 (02 81 81) 132(129) exponent2 0x03a1 - 0x0423 (02 81 80) 131(128) coefficient 0x0424 - 0x04a6 (02 81 80) 131(128)
最初の624バイトが不明。625バイト目以降144バイト分がわかっている。prime1の後半とprime2の前半しかわからない。
prime1: 625-665(下41バイトのみ判明) prime2: 669-768(上100バイトのみ判明)
片方の素数の上位ビット半分以上が判明しているため、Coppersmith's Attackを行い、素数を割り出す。
# solve.sage n = 0x00be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867ccf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c9603ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d84dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f5383277a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896ae5fcfa01593a7c84d518c503c0aee581 e = 65537 priv_part = ''' YC2/ZTbmSZFL9t5Em+ic2ayw0nNUSI6XO7+3tcT9TABzh94t9YLhiDcCgYEA0LFZ OUTgvmnWAkwGSo/6huQOu/7VmsM7OBdFntgotOJXALXFqCeT2PMXyWVc9/6ObUZj z9LQUlT6mnzYwFrX4mPPOTY5nvCyjepQlSDA7w49yaRhXKCFRHmEieeFJqzrZoQG ''' der = priv_part.decode('base64') q_pre = der[44:].encode('hex') kbits = 29 * 8 q_bar = int(q_pre + '0' * (29 * 2), 16) PR.<x> = PolynomialRing(Zmod(n)) f = x + q_bar x0 = f.small_roots(X=2^kbits, beta=0.3)[0] q = x0 + q_bar print q
この結果から、p, qは以下の通りとわかる。
q = 146549045227354172989110651205310632574067392372993711861623526130946979713469625772410411197033006823693645223316947254702263484103463390279967082549781844195965622071604103417650285219901124684816890970225510506869249766243257198851929421990982433654502509027141033118789478594390852225097012248592818058247 p = 163982139712862418555526520701188853132435025142588334581109287244065993155706892302449577647543501705795708316995057467949529976798218410513821698432879399377481736303821213515873396833696040164615779257072417113571942677691455176550027493593024586313878742269786944829130979576180492741390980797445630429239
秘密鍵を生成する。
$ rsatool.py -f PEM -o privkey.pem -p 163982139712862418555526520701188853132435025142588334581109287244065993155706892302449577647543501705795708316995057467949529976798218410513821698432879399377481736303821213515873396833696040164615779257072417113571942677691455176550027493593024586313878742269786944829130979576180492741390980797445630429239 -q 146549045227354172989110651205310632574067392372993711861623526130946979713469625772410411197033006823693645223316947254702263484103463390279967082549781844195965622071604103417650285219901124684816890970225510506869249766243257198851929421990982433654502509027141033118789478594390852225097012248592818058247 Using (p, q) to initialise RSA instance n = be5d958b09b2291cf0bd36511c9155e229f8ae8dccaee1552c9669b81b532a363b4f34769412867c cf92cb40addef5200a05dcdef09c8da30982fa5413d952f4e7db3da739519fab77d574de52366c96 03ace887c0cbf32c5247cec14228e8a72aa5256799e54c40f3a22d4642cdaf5e0dd077331158e7d8 4dba8756d531a4bb4d2ba3e79c29972f27eb8d0bf9df81e2e9cda23b0ddead23c00aaebfa0f53832 77a22177729a9cb5ee58c47019b6cb322d7fb9a41df3a2d562dfd202f9063b5e5e5042cfef6ddcfe 41232867e1c122a8dcc18ce51efbb8cc5f9bc0f3296f1091ca3010ed851273d4ca40675753da896a e5fcfa01593a7c84d518c503c0aee581 e = 65537 (0x10001) d = 620075bb457b95d4d34ee586ae6957c87e090b7beeb2dd486712ec4c1ead1adf1e7b712bd6a10ee1 744f431a0228f512d076223617b2d0ebed3aa3bae3190faf0b2a003c75b2c2bb988ea882c7da42de 9bf7c922122c2cfd5542a87b2f9f35ded18281962b51338780a5ae1f2cc70d1023967db729a8167b 71d0a45a1c99590f3c4bfa59f6cb99808d1b8c4e5c0ca7feeec7f2c88f6cee0a343be1f1217c23c2 ec0e779740374cffda319dc8797a0b010a58b0ad79e33adc3ca088dcbf4fdb68da954c49b3aa693f 0e0545d6845e3413d720a2df5c98158e4b45d2bd6e2ea08672db20644ea9aec7c192c1087b970564 cd929d43e5ea32f1c1e19a266adb84ed p = e984b0820151d7ed6a86569073ea12e64d36fa33bc360082cd1e87ad0618f6dd6f0dbac674170c3d 11f1e8ea1208c48ee3c6313f7703138fc2d2dc8e94fdd4a427bd92a420de8a025d0423e80351acaa 2c92bfe5e11729602dbf6536e649914bf6de449be89cd9acb0d27354488e973bbfb7b5c4fd4c0073 87de2df582e18837 q = d0b1593944e0be69d6024c064a8ffa86e40ebbfed59ac33b3817459ed828b4e25700b5c5a82793d8 f317c9655cf7fe8e6d4663cfd2d05254fa9a7cd8c05ad7e263cf3936399ef0b28dea509520c0ef0e 3dc9a4615ca08544798489e78526aceb668406cb284ebe0ee0120defe7405ffe7d76fb6bb469183c b262822c9b6f3407 Saving PEM as privkey.pem
$ ssh -i privkey.pem ctf@web.angstromctf.com -p 3004 The authenticity of host '[web.angstromctf.com]:3004 ([162.243.30.173]:3004)' can't be established. ECDSA key fingerprint is 85:61:bc:f6:51:7c:c9:44:ec:b3:bd:e3:f6:fc:d0:d6. Are you sure you want to continue connecting (yes/no)? yes Warning: Permanently added '[web.angstromctf.com]:3004,[162.243.30.173]:3004' (ECDSA) to the list of known hosts. Welcome to Ubuntu 16.04.4 LTS (GNU/Linux 4.4.0-116-generic x86_64) * Documentation: https://help.ubuntu.com * Management: https://landscape.canonical.com * Support: https://ubuntu.com/advantage actf{ssh_keys_not_broken_enough} Connection to web.angstromctf.com closed.
actf{ssh_keys_not_broken_enough}
