この大会は2021/9/4 1:00(JST)～2021/9/5 13:00(JST)に開催されました。
今回もチームで参戦。結果は490点で523チーム中80位でした。
自分で解けた問題をWriteupとして書いておきます。
https://7b000000074648ad280b2018-sanity-check.challenge.master.allesctf.net:31337/robots.txtにアクセスすると、フラグが書いてあった。
ALLES!{1_nice_san1ty_ch3k}
この大会は2021/8/28 8:00(JST)～2021/8/29 20:00(JST)に開催されました。
今回もチームで参戦。結果は1890点で157チーム中22位でした。
自分で解けた問題をWriteupとして書いておきます。
フラグの各文字について、以下のように暗号化している。
pow(g, r*m, p)
rは未知だが、以下の式が成り立つので、pow(g, r, p)が算出できる。
pow(g, r*m, p) = pow(pow(g, r, p), m, p)
あとはmをブルートフォースで割り出せばフラグが求められる。
from Crypto.Util.number import * with open('output.txt', 'r') as f: p = int(f.readline().rstrip()) g = int(f.readline().rstrip()) cs = eval(f.readline().rstrip()) d = inverse(ord('C'), p - 1) g_r0 = pow(cs[0], d, p) d = inverse(ord('a'), p - 1) g_r1 = pow(cs[1], d, p) assert g_r0 == g_r1 g_r = g_r0 flag = '' for c in cs: for code in range(32, 127): if pow(g_r, code, p) == c: flag += chr(code) break print flag
CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}
LFSRの問題。rをz3で求め、復号する。
from z3 import * from Crypto.Util.number import * def LFSR(r): while True: yield r & 1 b = (r & 1) ^\ ((r & 2) >> 1) ^\ ((r & 8) >> 3) ^\ ((r & 16) >> 4) r = (r >> 1) | (b << 63) r = BitVec('r', 64) lfsr = LFSR(r) flag_head = 'CakeCTF{' m = bytes_to_long(flag_head[::-1]) ## add '0' to arrange b_ct = '0' + bin(0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053)[2:] s = Solver() for i in range(len(flag_head) * 8): s.add(((m & 1) ^ next(lfsr)) == int(b_ct[i])) m >>= 1 res = s.check() if res == sat: m = s.model() r = m[r].as_long() else: exit(1) lfsr = LFSR(r) bin_flag = '' for i in range(len(b_ct)): b = int(b_ct[i]) ^ next(lfsr) bin_flag = str(b) + bin_flag flag = long_to_bytes(int(bin_flag, 2))[::-1] print flag
CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}
アンケートに答えたら、フラグが表示された。
CakeCTF{w4s_th1s_CTF_p13c3_0f_c4k3_4U?}
この大会は2021/8/28 19:30(JST)～2021/8/29 19:30(JST)に開催されました。
今回もチームで参戦。結果は910点で157チーム中33位でした。
自分で解けた問題をWriteupとして書いておきます。
XOR暗号。keyを求めて、復号する。
enc = '2506110631060d103c5a15582036045b3c075734640015580d10531e0d1c134a2f' enc = enc.decode('hex') flag_head = 'wormcon{' key = '' for i in range(len(flag_head)): key += chr(ord(flag_head[i]) ^ ord(enc[i])) assert key[:4] == key[4:] key = key[:4] print '[+] key =', key flag = '' for i in range(len(enc)): flag += chr(ord(enc[i]) ^ ord(key[i%len(key)])) print '[*] flag =', flag
実行結果は以下の通り。
[+] key = Rick
[*] flag = wormcon{n3v3r_g0nn4_6iv3_y0u_up!}
wormcon{n3v3r_g0nn4_6iv3_y0u_up!}
暗号処理の概要は以下の通り。
・FLAG: wormcon{}の中身
・FLAGの文字は英数字とアンダースコアのみ
・otp :ランダム8bit整数
・otpm: otpの上8bit
・otpl: otpの下8bit
・FLAGの各文字について
・偶数番目はencrypt(ord(ch), otpm, otpl)
・奇数番目はencrypt(ord(ch), otpl, otpm)
・暗号化データを16進表記で出力otpをブルートフォースで実行し、英数字とアンダースコアになるようXORで復号する。
#!/usr/bin/env python3 def splitit(n): return (n >> 4), (n & 0xF) def decrypt(n, key1, key2): m, l = splitit(n) d = ((m ^ key1) << 4) | (l ^ key2) return d def is_alpha(s): alpha = b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_' for c in s: if c not in alpha: return False return True with open('out.txt', 'r') as f: cipher = bytes.fromhex(f.read().split(' ')[-1]) for otp in range(256): otpm, otpl = splitit(otp) FLAG = [] for i, ch in enumerate(cipher): if i % 2 == 0: dec = decrypt(ch, otpm, otpl) else: dec = decrypt(ch, otpl, otpm) FLAG.append(dec) FLAG = bytes(FLAG) if is_alpha(FLAG): break flag = 'wormcon{%s}' % FLAG.decode() print(flag)
wormcon{x0r_n1bbl3_c1ph3r_15_4_h0m3_br3w3d_c1ph3r}
DES-ECBモードなので、ブロック単位で同じ平文は同じ暗号文に対応する。ブロック単位でシャッフルしているが、その関係性は変わらないので、対応する平文を構成していけばよい。
with open('flag.png.enc', 'rb') as f: flag_enc = f.read() with open('ff_error.png', 'rb') as f: pt = f.read() with open('ff_error.png.enc', 'rb') as f: ct = f.read() pt = [pt[i:i+8] for i in range(0, len(pt), 8)] ct = [ct[i:i+8] for i in range(0, len(ct), 8)] flag = '' for i in range(0, len(flag_enc), 8): index = ct.index(flag_enc[i:i+8]) flag += pt[index] with open('flag.png', 'wb') as f: f.write(flag)
wormcon{ECB_lacks_diffiusion}
換字式暗号。Unicodeで対応していることに注意して、まずはASCII文字に変換する。また6バイト目が頻度的にスペースと推測できるので、その変換をする。
with open('flag.enc', 'rb') as f: enc = f.read() enc = enc.replace('\xe3\x81\x83', 'A') enc = enc.replace('\xe3\x80\xB7', 'B') enc = enc.replace('\xe3\x80\xB4', 'C') enc = enc.replace('\xe3\x81\x81', 'D') enc = enc.replace('\xe3\x81\x8A', 'E') enc = enc.replace('\xe3\x81\x86', 'F') enc = enc.replace('\xe3\x80\xB0', 'G') enc = enc.replace('\xe3\x81\x82', 'H') enc = enc.replace('\xe3\x80\xBE', 'I') enc = enc.replace('\xe3\x80\xBD', 'J') enc = enc.replace('\xe3\x80\xB2', 'K') enc = enc.replace('\xe3\x80\xBA', 'L') enc = enc.replace('\xe3\x80\xB8', 'M') enc = enc.replace('\xe3\x80\xB6', 'N') enc = enc.replace('\xe3\x80\xB5', 'O') enc = enc.replace('\xe3\x80\xBB', 'P') enc = enc.replace('\xe3\x80\xB3', 'Q') enc = enc.replace('\xe3\x80\xBC', 'R') enc = enc.replace('\xe3\x80\xB1', 'S') enc = enc.replace('\xe3\x81\x84', 'T') enc = enc.replace('\xe3\x81\x85', 'U') enc = enc.replace('\xe3\x81\x88', 'V') enc = enc.replace('\xe3\x81\x87', 'W') enc = enc.replace('\xe3\x80\xBF', 'X') enc = enc.replace('\xe3\x81\x80', 'Y') enc = enc.replace('\xe3\x80\xB9', 'Z') enc = enc.replace('E', ' ') print enc
あとはquipqiupで復号する。
THERE WAS ONCE A KING OF SCOTLAND WHOSE NAME WAS ROBERT BRUCE HE HAD NEED TO BE BOTH BRAVE AND WISE FOR THE TIMES IN WHICH HE LIVED WERE WILD AND RUDE THE KING OF ENGLAND WAS AT WAR WITH HIM AND HAD LED A GREAT ARMY INTO SCOTLAND TO DRIVE HIM OUT OF THE LAND BATTLE AFTER BATTLE HAD BEEN FOUGHT SIX TIMES HAD BRUCE LED HIS BRAVE LITTLE ARMY AGAINST HIS FOES AND SIX TIMES HAD HIS MEN BEEN BEATEN AND DRIVEN INTO FLIGHT AT LAST HIS ARMY WAS SCATTERED AND HE WAS FORCED TO HIDE HIMSELF IN THE WOODS AND IN LONELY PLACES AMONG THE MOUNTAINS ONE RAINY DAY BRUCE LAY ON THE GROUND UNDER A RUDE SHED LISTENING TO THE PATTER OF THE DROPS ON THE ROOF ABOVE HIM HE WAS TIRED AND SICK AT HEART AND READY TO GIVE UP ALL HOPE IT SEEMED TO HIM THAT THERE WAS NO USE FOR HIM TO TRY TO DO ANYTHING MORE AS HE LAY THINKING HE SAW A SPIDER OVER HIS HEAD MAKING READY TO WEAVE HER WEB HE WATCHED HER AS SHE TOILED SLOWLY AND WITH GREAT CARE SIX TIMES SHE TRIED TO THROW HER FRAIL THREAD FROM ONE BEAM TO ANOTHER AND SIX TIMES IT FELL SHORT POOR THING SAID BRUCE YOU TOO KNOW WHAT IT IS TO FAIL BUT THE SPIDER DID NOT LOSE HOPE WITH THE SIXTH FAILURE WITH STILL MORE CARE SHE MADE READY TO TRY FOR THE SEVENTH TIME BRUCE ALMOST FORGOT HIS OWN TROUBLES AS HE WATCHED HER SWING HERSELF OUT UPON THE SLENDER LINE WOULD SHE FAIL AGAIN NO THE THREAD WAS CARRIED SAFELY TO THE BEAM AND FASTENED THERE I TOO WILL TRY A SEVENTH TIME CRIED BRUCE HE AROSE AND CALLED HIS MEN TOGETHER HE TOLD THEM OF HIS PLANS AND SENT THEM OUT WITH MESSAGES OF CHEER TO HIS DISHEARTENED PEOPLE SOON THERE WAS AN ARMY OF BRAVE SCOTCHMEN AROUND HIM ANOTHER BATTLE WAS FOUGHT AND THE KING OF ENGLAND WAS GLAD TO GO BACK INTO HIS OWN COUNTRY I HAVE HEARD IT SAID THAT AFTER THAT DAY NO ONE BY THE NAME OF BRUCE WOULD EVER HURT A SPIDER THE LESSON WHICH THE LITTLE CREATURE HAD TAUGHT THE KING WAS NEVER FORGOTTEN HE TOLD US THE FLAG WAS CAREFUL FREQUENCY ANALYSIS BREAKS SUBSTITUTION CIPHER HE ALSO SUGGESTS THE USER TO JOIN THE WORDS WITH UNDERSCORE AND PUT THE RESULT IN THE FLAG WRAPPER BEFORE SUBMISSION
wormcon{CAREFUL_FREQUENCY_ANALYSIS_BREAKS_SUBSTITUTION_CIPHER}
アンケートに答えたら、フラグが表示された。
wormcon{Th4nK5_f0R_F33dB4ck}
この大会は2021/8/28 2:00(JST)～2021/8/29 14:00(JST)に開催されました。
今回もチームで参戦。結果は4204点で428チーム中28位でした。
自分で解けた問題をWriteupとして書いておきます。
Discordに入り、#welcome-flagチャネルのメッセージを見ると、フラグが書いてあった。
FwordCTF{Welcome_To_FwordCTF_2021}
サーバの処理概要は以下の通り。
・key: ランダム32バイト文字列 ・フラグを暗号化して表示 ・以下繰り返し ・メニュー表示 ・1を選択した場合 ・msg: ランダム32バイト ・cipher: msgを暗号化 ・cipherとkeyの各文字が異なる場合はcipherを表示 そうでない場合は、leakのメッセージを表示 ・2を選択した場合 ・k: keyを16進表記で入力 ・cipher: 暗号文を16進表記で入力 ・復号(XOR -> AES-ECB復号) →FwordCTFが含まれていたら、フラグを表示 ・3を選択した場合、終了
暗号化の処理概要は以下の通り。
・平文が16バイトの倍数でない場合、パディング ・AES-ECBでkeyを使って暗号化 ・cipherとkeyでXOR(文字列が短い方は繰り返し文字列にする)
2で鍵と暗号文を指定できるので、適当な鍵で"FwordCTF"を暗号化したものを指定すればよい。
#!/usr/bin/env python3 import socket from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def xor(a, b): return bytearray([a[i % len(a)] ^ b[i % len(b)] for i in range(max(len(a), len(b)))]) def encrypt(msg): aes = AES.new(key, AES.MODE_ECB) if len(msg) % 16 != 0: msg = pad(msg, 16) cipher = aes.encrypt(msg) cipher = xor(cipher, key) return cipher s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('52.149.135.130', 4869)) for _ in range(3): data = recvuntil(s, b'\n').rstrip() print(data) key = b'\x00' * 16 msg = b'FwordCTF' cipher = encrypt(msg) key_hex = key.hex() cipher_hex = cipher.hex() data = recvuntil(s, b'> ') print(data + '2') s.sendall(b'2\n') data = recvuntil(s, b': ') print(data + key_hex) s.sendall(key_hex.encode() + b'\n') data = recvuntil(s, b': ') print(data + cipher_hex) s.sendall(cipher_hex.encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data)
実行結果は以下の通り。
Welcome to Enc/Dec Oracle.
Here is the encrypted flag : fe4fe57726fd997b8973129764ad10c880a12d48f3f8604cb0ae3219a47ee019bf8670d05a1fb38da5fbd056f67aad4b2e14b32a565544fe41111a0ada03a8019b8ff6dc00caa62b700b6c2d82a9be75
1- Encrypt
2- Decrypt
3- Leave
> 2
Key : 00000000000000000000000000000000
Ciphertext : 94d0974bbcfc8739501c6985a3a50500
Well done ! Here is your flag : b'FwordCTF{N3v3r_x0r_w1thout_r4nd0m1s1ng_th3_k3y_0r_m4yb3_s3cur3_y0ur_c0d3}'
FwordCTF{N3v3r_x0r_w1thout_r4nd0m1s1ng_th3_k3y_0r_m4yb3_s3cur3_y0ur_c0d3}
サーバの処理概要は以下の通り。
・p: 1024bit素数 ・secret: 1以上p-1以下ランダム整数 ・以下繰り返し ・メニュー表示 ・1を選択した場合 ・magic_word: json形式で入力 ・"Boombastic"のチケットと一致していたら、フラグを表示 ・2を選択した場合 ・word: ランダム16バイトの16進表記 ・wordのチケットを表示 ・3を選択した場合、終了
チケットの計算は以下の通り。
・y: msgのsha256ダイジェストの数値化 ・r = ((y**2 - 1) * (inverse(secret**2, p))) % p ・s = ((1 + y) * (inverse(secret, p))) % p
inverse(secret, p) = Aとして、式を変形していく。
r = ((y**2 - 1) * (A**2)) % p
s = ((1 + y) * A) % p
↓
s**2 % p = ((y**2 + y*2 + 1) * (A**2)) % p
= (r + 2 * (y + 1) * (A**2)) % p
= (r + 2 * s * A) % p
↓
A = ((s**2 - r) * inverse(s * 2, p)) % pAを算出できるので、ここから"Boombastic"のチケットを計算できる。
#!/usr/bin/env python3 import socket from Crypto.Util.number import inverse from json import loads, dumps import hashlib def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def get_ticket(code, A): y = int(hashlib.sha256(code.encode()).hexdigest(),16) r = ((y**2 - 1) * (A**2)) % p s = ((1 + y) * A) % p return {'s': hex(s), 'r': hex(r), 'p': hex(p)} sc = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sc.connect(('52.149.135.130', 4872)) data = recvuntil(sc, b'> ') print(data + '2') sc.sendall(b'2\n') data = recvuntil(sc, b'\n').rstrip() print(data) data = recvuntil(sc, b'\n').rstrip() print(data) ticket = loads(data.split(' : ')[1]) s = int(ticket['s'], 16) r = int(ticket['r'], 16) p = int(ticket['p'], 16) A = ((s**2 - r) * inverse(s * 2, p)) % p magic_word = dumps(get_ticket("Boombastic", A)) data = recvuntil(sc, b'> ') print(data + '1') sc.sendall(b'1\n') data = recvuntil(sc, b': ') print(data + magic_word) sc.sendall(magic_word.encode() + b'\n') data = recvuntil(sc, b'\n').rstrip() print(data)
実行結果は以下の通り。
______________
_(______________()
______ _- | ||
| |_ _- | ||
| |_|_ | Boombastic ||
|______| -_ | ||
/\ -_|______________||
/ \
/ \
/ \
1- Enter Cinema
2- Get a ticket
3- Leave
> 2
Your ticket : {"s": "0x82f654c827f93d5687273115817c50a5a5eb1f3f52d552a463319968622737864cd35d08ea1aeff856a6d2cd339dfa596944056787254324a395e224369d7ba619300720197935fa763d7aeb88c7475365d43496f75fb1fe819dbc7315c03897235fe7f7ff77e249107ab4be0cee3ce23b9beaa09f9f46eb39db12df4186ef6e", "r": "0xdbada907e4cd5fea81984ba32c377669e55cb1a732a98dc1e61baaeb785293dbff0d963f2c09531ee24019aafb46d7b180547c6b9a9c35f4abf227f08a159a19a90e49c076356ab53693d5ff4e387d780c2c5324e95ed20d33027685cd7c6ac54b692680eb2ec6779468e08e96d28a4dfcadee27437685d0ca5ba41194462a0f", "p": "0xddb53eca8ab4c59353a59b59f40f874105fa5ae78c8b6d0933f1c9fc068c2932e90d564e37f6db498e0c704e91253b5873480ca505907f2ec01ce56342e30248479501c7171c410c575bef1c0d00cf48ca98a968f786a42826e9ec59f8016e09d9421a7e41237831e92b0cb492b786609e53a5b4341e9ad87535a758fbd2b997"}
1- Enter Cinema
2- Get a ticket
3- Leave
> 1
Enter the magic word : {"s": "0x66f451a57a0aaa9fa295a49c3829d403deea227b165d94d6d20be8e05a450fa2a2ea7c1ccdbf4f2ef3662462ea6869fd561e2a211977197d9c6e0fc307e3b2b5a684dc615bb7838abe501008853dbf1d14a606fe690274cbecf400ad7a5a1dd54d36bfce7a5a4ebada04be4ea53369b0f2dd631e4c7455d8126ea9023c64c3af", "r": "0x423eb22fbcbce63aa40ea60bc79dd106819b083a2dd6aaf14f36cb8fa3162d94e473bae5b269fb886ec544ddf749433411aaad7efd1a4e8b7d76e889f414720136e75cc6948de85e27f57a925fa2a94ed5951205eb5c2c23bb1a134e3e8ef3df58a60d4bdc5fdff9085982ddcb1c4caf661b8f2b9e7a6fa29cf85fb15f8a851", "p": "0xddb53eca8ab4c59353a59b59f40f874105fa5ae78c8b6d0933f1c9fc068c2932e90d564e37f6db498e0c704e91253b5873480ca505907f2ec01ce56342e30248479501c7171c410c575bef1c0d00cf48ca98a968f786a42826e9ec59f8016e09d9421a7e41237831e92b0cb492b786609e53a5b4341e9ad87535a758fbd2b997"}
Here is your flag : FwordCTF{4ct_l1k3_a_V1P_4nd_b3c0m3_a_V1P}, enjoy the movie sir.
FwordCTF{4ct_l1k3_a_V1P_4nd_b3c0m3_a_V1P}
この大会は2021/8/21 9:00(JST)～2021/8/23 9:00(JST)に開催されました。
今回もチームで参戦。結果は4940点で904チーム中44位でした。
自分で解けた問題をWriteupとして書いておきます。
問題にフラグが書いてあった。
corctf{h3lP_n0N3_0f_uS_Kn0W_rU$t_d3sp1t3_t3@m_nAm3!!!}
1文字ずつ暗号化しているので、ブルートフォースで復号する。
fib = [1, 1] for i in range(2, 11): fib.append(fib[i - 1] + fib[i - 2]) def c2f(c): n = ord(c) b = '' for i in range(10, -1, -1): if n >= fib[i]: n -= fib[i] b += '1' else: b += '0' return b with open('flag.enc', 'r') as f: enc = f.read().split(' ') flag = '' for c in enc: for code in range(32, 127): if c2f(chr(code)) == c: flag += chr(code) break print flag
corctf{b4s3d_4nd_f1bp!113d}
適当にメールアドレスを入力して送信すると、https://devme.be.ax/graphqlにPOSTしていることがわかる。GraphQLが使われているようだ
$ get-graphql-schema https://devme.be.ax/graphql """Exposes a URL that specifies the behaviour of this scalar.""" directive @specifiedBy( """The URL that specifies the behaviour of this scalar.""" url: String! ) on SCALAR type Mutation { createUser(email: String!): User } type Query { users: [User]! flag(token: String!): String! } type User { token: String! username: String! }
GraphQLで問い合わせをする。Endpointを https://devme.be.ax/graphql に設定する。
まず以下のクエリを投げる。
query {
users {
token
username
}
}すると、以下のようなレスポンスが返ってきた。
{
"data": {
"users": [
{
"token": "3cd3a50e63b3cb0a69cfb7d9d4f0ebc1dc1b94143475535930fa3db6e687280b",
"username": "admin"
},
:
:
]
}
}次にadminのtokenでクエリを投げる。
query {
flag(token: "3cd3a50e63b3cb0a69cfb7d9d4f0ebc1dc1b94143475535930fa3db6e687280b")
}すると、以下のようなレスポンスが返ってきた。
{
"data": {
"flag": "corctf{ex_g00g13_3x_fac3b00k_t3ch_l3ad_as_a_s3rvice}"
}
}
corctf{ex_g00g13_3x_fac3b00k_t3ch_l3ad_as_a_s3rvice}
nを素因数分解する。
$ python -m primefac 50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293 50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293: 2365186141 2602521199 2772696307 2753147143 2963383867 2719924183 2436598001 3721186793 4276173893 4098491081 2525697263 3319529377 2575495753 3686523713 2657405087 3941016503 2752963847 2322142411 2703629041 3589083991 3684423151 3760232953 3335574511 4073647147 2746638019 3488338697 4152726959 3012495907 3959814431 2223202649 2733527227 3625437121 2278427881 3865448239 3646337561 3380851417 4198942673 2157385673 3453863503 2572542211 3291377941 3648309311 2824169389 2944751701 3860554891 3130133681 3522596999 2695978183 2707095227 2293226687 4252196909 3833706949 2148630611 2854321391 2682518317 2491570349 3539958743 2388797093 4135004413 3638373857 3303691121 3464370241 2932152359 2371079143 3056689019 3174322859 3177943303 3833824031 3346647649 2858807113 3716991893 2661720221 4091945483 2424270803 2459187103 3411506629 2444333767 3861767519 2724658201 3238771411 3854175641 2949007619 3285444073 4205028467 3180301633 2216411683 3279018511 3789253133 3035438359 3961738709 3943871257 2647129697 4270521797 2510750149 2240170147 3057815377 4227099257 4045323871 3398567593 2230630973 2959325459 3083881387 3789746923 2710524571 2841115943 4235456317 2944722127 4141964923 3978832967 3278196319 2672301743 3811207403 3991834969 3228764447 3623581037 3986329331 3923208001 2636069911 3200434847 3013564231 4218138251 3487902133 3417563069 3359249393 4006267823 3994425601 4140261491 4056085883
あとは通常通りphiを求め、復号する。
from Crypto.Util.number import * e = 65537 with open('output.txt', 'r') as f: n = int(f.readline().rstrip()) c = int(f.readline().rstrip()) primes = [2365186141, 2602521199, 2772696307, 2753147143, 2963383867, 2719924183, 2436598001, 3721186793, 4276173893, 4098491081, 2525697263, 3319529377, 2575495753, 3686523713, 2657405087, 3941016503, 2752963847, 2322142411, 2703629041, 3589083991, 3684423151, 3760232953, 3335574511, 4073647147, 2746638019, 3488338697, 4152726959, 3012495907, 3959814431, 2223202649, 2733527227, 3625437121, 2278427881, 3865448239, 3646337561, 3380851417, 4198942673, 2157385673, 3453863503, 2572542211, 3291377941, 3648309311, 2824169389, 2944751701, 3860554891, 3130133681, 3522596999, 2695978183, 2707095227, 2293226687, 4252196909, 3833706949, 2148630611, 2854321391, 2682518317, 2491570349, 3539958743, 2388797093, 4135004413, 3638373857, 3303691121, 3464370241, 2932152359, 2371079143, 3056689019, 3174322859, 3177943303, 3833824031, 3346647649, 2858807113, 3716991893, 2661720221, 4091945483, 2424270803, 2459187103, 3411506629, 2444333767, 3861767519, 2724658201, 3238771411, 3854175641, 2949007619, 3285444073, 4205028467, 3180301633, 2216411683, 3279018511, 3789253133, 3035438359, 3961738709, 3943871257, 2647129697, 4270521797, 2510750149, 2240170147, 3057815377, 4227099257, 4045323871, 3398567593, 2230630973, 2959325459, 3083881387, 3789746923, 2710524571, 2841115943, 4235456317, 2944722127, 4141964923, 3978832967, 3278196319, 2672301743, 3811207403, 3991834969, 3228764447, 3623581037, 3986329331, 3923208001, 2636069911, 3200434847, 3013564231, 4218138251, 3487902133, 3417563069, 3359249393, 4006267823, 3994425601, 4140261491, 4056085883] phi = 1 for p in primes: phi *= p - 1 d = inverse(e, phi) m = pow(c, d, n) flag = long_to_bytes(m) print flag
corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
以下のようにすると、すべてテストをクリアする。
def f(a, b):
return a + b
You passed 10/10 test cases.flagの1文字目'c'(ASCIIコード99)を想定して、以下のようにすると、必ず1つテストをクリアする。
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[0]) - 94
You passed 1/10 test cases.プログラムで組もうとしたが、うまくいかなかったため、手動で同様に確認していく。
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[1]) - 106
You passed 1/10 test cases.
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[2]) - 109
You passed 1/10 test cases.
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[3]) - 94
You passed 1/10 test cases.
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[4]) - 111
You passed 1/10 test cases.
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[5]) - 97
You passed 1/10 test cases.
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[6]) - 118
You passed 1/10 test cases.ここまでで"corctf{"の確認ができた。英単語で想像しながら、以降の確認を進める。
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[7]) - 37
You passed 1/10 test cases.
>>> chr(37+12)
'1'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[8]) - 97
You passed 1/10 test cases.
>>> chr(97+12)
'm'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[9]) - 40
You passed 1/10 test cases.
>>> chr(40+12)
'4'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[10]) - 91
You passed 1/10 test cases.
>>> chr(91+12)
'g'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[11]) - 37
You passed 1/10 test cases.
>>> chr(37+12)
'1'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[12]) - 98
You passed 1/10 test cases.
>>> chr(98+12)
'n'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[13]) - 39
You passed 1/10 test cases.
>>> chr(39+12)
'3'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[14]) - 83
You passed 1/10 test cases.
>>> chr(83+12)
'_'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[15]) - 87
You passed 1/10 test cases.
>>> chr(87+12)
'c'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[16]) - 100
You passed 1/10 test cases.
>>> chr(100+12)
'p'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[17]) - 83
You passed 1/10 test cases.
>>> chr(83+12)
'_'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[18]) - 91
You passed 1/10 test cases.
>>> chr(91+12)
'g'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[19]) - 36
You passed 1/10 test cases.
>>> chr(36+12)
'0'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[20]) - 96
You passed 1/10 test cases.
>>> chr(96+12)
'l'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[21]) - 90
You passed 1/10 test cases.
>>> chr(90+12)
'f'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[22]) - 83
You passed 1/10 test cases.
>>> chr(83+12)
'_'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[23]) - 42
You passed 1/10 test cases.
>>> chr(42+12)
'6'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[24]) - 85
You passed 1/10 test cases.
>>> chr(85+12)
'a'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[25]) - 39
You passed 1/10 test cases.
>>> chr(39+12)
'3'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[26]) - 37
You passed 1/10 test cases.
>>> chr(37+12)
'1'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[27]) - 44
You passed 1/10 test cases.
>>> chr(44+12)
'8'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[28]) - 88
You passed 1/10 test cases.
>>> chr(88+12)
'd'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[29]) - 90
You passed 1/10 test cases.
>>> chr(90+12)
'f'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[30]) - 89
You passed 1/10 test cases.
>>> chr(89+12)
'e'★
def f(a, b):
with open('flag.txt', 'r') as f:
flag = f.read()
return ord(flag[31]) - 113
You passed 1/10 test cases.
>>> chr(113+12)
'}'★
corctf{1m4g1n3_cp_g0lf_6a318dfe}
サーバの処理概要は以下の通り。
・g, p = gen() ・p: 512bit素数 ・g: 1以上p未満のランダム整数 ・g, p表示 ・x: flagの数値化 ・enc = pow(g, x, p) →表示 ・64回以下繰り返し ・div: 数値入力 ・pow(g, x//div, p)を表示
x = div * A + Bとする。
pow(g, x//div, p) = pow(g, A, p) pow(g, x, p) = pow(g, div * A + B, p) = pow(pow(g, A, p), div, p) * pow(g, B, p)
Bをブルートフォースで満たすものを探す。divが256の場合、64回以下にぎりぎり収まりxを算出できる。
import socket from Crypto.Util.number import * from sympy import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('crypto.be.ax', 6000)) data = recvuntil(s, '\n').rstrip() print data g = int(data.split(': ')[1]) data = recvuntil(s, '\n').rstrip() print data p = int(data.split(': ')[1]) data = recvuntil(s, '\n').rstrip() print data enc = int(data.split(': ')[1]) pre_enc = enc div = 256 flag = '' for i in range(64): data = recvuntil(s, '> ') print data + str(div) s.sendall(str(div) + '\n') data = recvuntil(s, '\n').rstrip() print data try_enc = int(data) for code in range(32, 128): if (pow(try_enc, 256, p) * pow(g, code, p)) % p == pre_enc: flag = chr(code) + flag div *= 256 pre_enc = try_enc break print flag
実行結果は以下の通り。
g: 938704359798247984965381279824099435075931121376035180404730584296803228146055366289360007527739449318564313808932643069047000199775542050858681088809714
p: 12758016385711921042759606784720425769932843161270886387401662287652499479043545806136388863077228551485068356641311576552082197259066132677399659104143237
encrypted flag: 10233215747566956022625748008909217897066441167345523666832895303893576531656901707054584955689434924909579739499813780524341530594559079862285737415095783
give me a number> 256
12196813933365486023859438176683589185345436461502547248127770140617031950228305431105042976884777618987187832218365658344339568841474461545965354106556134
give me a number> 65536
11859257412904377862548936564648859100062098033679187963999630549877040553104710339334794724558066411601999511375244562447111277726751836232526715603386687
give me a number> 16777216
3869658603280459927363722968343719429413499772483322303467630698563721379059667142629631362262145253170037931151870612197617260759089918656244677296835866
give me a number> 4294967296
8179951756128427868557091781055727096036389193353723018645707245264652073535858159998878560744800415022927235001865568145558065985030335044578512212829240
give me a number> 1099511627776
11547979536875539029274828782686580647676701399586965694871454376778247969663739630344835827493825146193280612088679354586379953489495005401061274095437614
give me a number> 281474976710656
7464271714106242357544774819990652651147179965504505987927283746941315126971370814296838110279045462282867665745554898514348150105300031465264431316349027
give me a number> 72057594037927936
7121652938049042609918610590701398185252818226112652538903146769281653462411381291061570855761783996967884646693622919701651314633638793464367583447934598
give me a number> 18446744073709551616
10309681090594016215263617939359445359527160105790240525427252025846197145738841494607699937302269302325902550713321902848542069179845598825788469816682957
give me a number> 4722366482869645213696
2632624315534458125573371200389571797584494102823749957933466525483602338776847807578765761887905820546299368882763061103444316534203345289049473751424026
give me a number> 1208925819614629174706176
6882633041988810321511866260856805547274738434928440568778008216459495318998583812251152734302150034391801112187267689817747558028516770061024235144668056
give me a number> 309485009821345068724781056
3302620547580129102355084784922786993710668468601265971577224543588737138271425458694777291071962432708379315464322696446318744427852201159816040115072518
give me a number> 79228162514264337593543950336
9263084916835386688537641282309141784950663810151188404518512690228237567785794421252882248666102132569518166684979063018511412897216739095854596520826021
give me a number> 20282409603651670423947251286016
8352176017871865279928448745283727531675052683722324584388602234736201436163770273950805703882128191573437995399457953092211974219719634296831666655774736
give me a number> 5192296858534827628530496329220096
2400640545330218816012955292216052790373889496336244313646553888397857846056260273313588058701274430270179795026170480487444854903541009286736602954722667
give me a number> 1329227995784915872903807060280344576
7900452747161470462683428086340694584774122867130297382018910738844547150890453763103371685928125924474737861527225202089487190133592211102586374230308585
give me a number> 340282366920938463463374607431768211456
147006477813875092016311247496158276028535558571869052017382267211780567557884949451942256789377134762748494893817854198212055960114491118461567444767273
give me a number> 87112285931760246646623899502532662132736
3794806189142100433983441476705761164578947857742693911407326122044716629984417653677936207026620341775123524012832787704609619971831013588995122323088979
give me a number> 22300745198530623141535718272648361505980416
10767681136530712660957493092740981641274948707979178813508239119276982282969787756893118851507339471440215270208640310447032258150287801266731732240341952
give me a number> 5708990770823839524233143877797980545530986496
9922311225100716006450549034369247543513074759452728179066534050246023791011495198842091753953981888228962676518340441366121453535944829871359485776984394
give me a number> 1461501637330902918203684832716283019655932542976
2143198837215177740749966491243537990742883341965849194296382231086568353794429026725662318300294947569213250977826311912790159023869268665619430932684561
give me a number> 374144419156711147060143317175368453031918731001856
5706634625748873101338249470016891185439760680163130025126031623815310170518977231896134947276947134090590459509363863433372800600893627555874499662740354
give me a number> 95780971304118053647396689196894323976171195136475136
6779053287194844096177545645691090128636733931775930611274377570183952868617133741805525646795147340609974118093841338169682380388038971127406188004656956
give me a number> 24519928653854221733733552434404946937899825954937634816
2937637450867803962816869813792649130731753274220819408831029302435868351830888731383737920087981669902505342784837030632608890299540677803568393681002878
give me a number> 6277101735386680763835789423207666416102355444464034512896
3803704383316624166833146023132444173676261941643439622649858688514616663768294047527625117330450963212735668927124754668822884249467379668147428687540401
give me a number> 1606938044258990275541962092341162602522202993782792835301376
1781810280290686344931071575775405691992989660336962829154485686526627954398735699168168904577865598615518866242474052353861846852432916257867396168724690
give me a number> 411376139330301510538742295639337626245683966408394965837152256
6404180309226982854778691176239083569510838010241861850745499665526978191268360097650896249887089918649737896260943419135122317400581491662135988115414814
give me a number> 105312291668557186697918027683670432318895095400549111254310977536
10869254507228542585106579608399720306442830493713864147376133468399305694919162373186873927369756226471199861278876118425233016150578340211723883753032006
give me a number> 26959946667150639794667015087019630673637144422540572481103610249216
2250381304134628039987408756176270520952270306152441566038365456973203300448847523144811830666131177958083474768224973410486268929971721980885887339302863
give me a number> 6901746346790563787434755862277025452451108972170386555162524223799296
10943390928249764906307528179744065889914884882391221048217494504235827808064363174425956596724680130877945865731612012994608424209647953639411646135203775
give me a number> 1766847064778384329583297500742918515827483896875618958121606201292619776
4967764951018736475210687112717537345691617910988014025120803311771189357661657369443404137698109340952712210030682045852740080326645847140037783151605697
give me a number> 452312848583266388373324160190187140051835877600158453279131187530910662656
4498004672714691324508102133973460255690954586325568566006223926342031348628822834838958881130755126069061772527293139957765376813754711537458039841838504
give me a number> 115792089237316195423570985008687907853269984665640564039457584007913129639936
10116865156012933814571546773243476874029552241192411214419368562788358481284666403364754250793619472100058195832267436193559229922162225472035531908325558
give me a number> 29642774844752946028434172162224104410437116074403984394101141506025761187823616
9355615963645589572138469092019937068446664134465295559314588197483294869609874037143654532439952091834426532490506188114204483215916533030223773571955585
give me a number> 7588550360256754183279148073529370729071901715047420004889892225542594864082845696
5833254491777271294803540590675442595637891746576157135948029345928966152664230619245466101774128516048859458975760673197520554555731653365276649580659986
give me a number> 1942668892225729070919461906823518906642406839052139521251812409738904285205208498176
5613949354863882766324420192268948331202718481289680426126016414461802506192576031480852440362641535745675005801779883386593052507392210995965479688373312
give me a number> 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056
6491160563510619121067915603011629526853489142571142178892777098793519448795270433681842425092544060346312908842206946207043752506150186031312926963600559
give me a number> 127314748520905380391777855525586135065716774604121015664758778084648831235208544136462336
3675486921973699471648689241249554121223993766982337832778730052490350452319167109758549000189121824033749273585685980934521287553587365683963440654363932
give me a number> 32592575621351777380295131014550050576823494298654980010178247189670100796213387298934358016
9105113322836196591957258416876789093841882421638059589035122558045087130046311321118979261259828833077930766104592642085685914643108463001077503779342565
give me a number> 8343699359066055009355553539724812947666814540455674882605631280555545803830627148527195652096
5795646971497437090185027700381788235097509990924448093693675241914732821141751338120492037595715434510059865387546680608753349043166576603610773876387742
give me a number> 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576
4740631949822397876963522700830258574514251047967613547683081085284566950631632720169891594266402232205827714608059054577804697026997941664148419405617300
give me a number> 546812681195752981093125556779405341338292357723303109106442651602488249799843980805878294255763456
1968670598230695564597580681623235305411420333974339183965950998875200180741367794340214479713403562860087706673101507206355547986870953111358793050821240
give me a number> 139984046386112763159840142535527767382602843577165595931249318810236991948760059086304843329475444736
3043678937191475004079919820226264144717341669110693589341292932129295566099688650816293636497369307385296080455020164074181109239331594824671397452151977
give me a number> 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852416
4761045775579323902368759976126383661151353143047412228678666619972819194814098805208344655440001440859139821535454090314154239213553854832145677252906333
give me a number> 9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440502746218496
11359010378521700598521459686290004677542301703853944643103302608741645407601440449437988428944220837600898829984889353355165785515999693896774088787976147
give me a number> 2348542582773833227889480596789337027375682548908319870707290971532209025114608443463698998384768703031934976
7066001515181996968969338417693736570154119545888725190693314512722756987088312553937198374294092371804318781197598913452870874536356164791351406183597379
give me a number> 601226901190101306339707032778070279008174732520529886901066488712245510429339761526706943586500787976175353856
8625470789475853172667859098209192598403728159957947814269823646752445916756420449942298476000240244723278809845672707932007454345099277622316624104478714
give me a number> 153914086704665934422965000391185991426092731525255651046673021110334850669910978950836977558144201721900890587136
2605783610714299506772349254086134597447185714443639916760931474102942664365160345917122114599395164571717848234274811080627743708383426932290173389982357
give me a number> 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306816
11160810904855932067299384417245659263398598283227428645482306818530082082027295800840425622273054862910225460920292500519711251965939593379669237693828177
give me a number> 10086913586276986678343434265636765134100413253239154346994763111486904773503285916522052161250538404046496765518544896
4367563332051160018705754366735116818535972478295777239394069078472036337062755597743851967991018153722955710559943678903555281288341029365681178908452091
give me a number> 2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376
12236932664811176725580212505478175662623227019491142396534462494512005563969541123171662916091802671613817108790331500481967304024426368084685955773518128
give me a number> 661055968790248598951915308032771039828404682964281219284648795274405791236311345825189210439715284847591212025023358304256
8782966492068779471334605738915664571093438480575708693091451162774129014976837656229472220660055277204068859290663295907983562022141541916707582993496583
give me a number> 169230328010303641331690318856389386196071598838855992136870091590247882556495704531248437872567112920983350278405979725889536
8740584604476436228101563465255830898320681800670952834680598527307071748508387886476330159074243051302532350014604086436050036162808647125905597907861950
give me a number> 43322963970637732180912721627235682866194329302747133987038743447103457934462900359999600095377180907771737671271930809827721216
12703459573242570856701596284619918480118216211351374577946324917893062779713441867164393582686415305268342347896204892444867139910931382148086372188329141
give me a number> 11090678776483259438313656736572334813745748301503266300681918322458485231222502492159897624416558312389564843845614287315896631296
3753692899857419991613192959907937249432983073674848008926165414853096790902666120931208867199017351938953229792051244712711408376361797290944579278418402
give me a number> 2839213766779714416208296124562517712318911565184836172974571090549372219192960637992933791850638927971728600024477257552869537611776
4346674035199926085815776396944169763549120584032489736291183132464963139576507743248996120103379130642414417484453618876182303235455914352253956058227261
give me a number> 726838724295606890549323807888004534353641360687318060281490199180639288113397923326191050713763565560762521606266177933534601628614656
9301776106258870602989619840187135833729070846448826724408963724367488945859017377601413838774916944085174019164171244811553548629925667865945387193126302
give me a number> 186070713419675363980626894819329160794532188335953423432061490990243657757029868371504908982723472783555205531204141550984858016925351936
3956376702554439914756007139019113585848978725397533727580375383654661515065520387392051515382794116364899288465903340650986145099754295618026611421908688
give me a number> 47634102635436893179040485073748265163400240214004076398607741693502376385799646303105256699577209032590132615988260237052123652332890095616
1174700802421594743913873658560103186938748452484200708487685481826348485846096916557752791176606722948157888266484677184721940171128966216298626592326501
give me a number> 12194330274671844653834364178879555881830461494785043558043581873536608354764709453594945715091765512343073949692994620685343654997219864477696
11082045743688880951516679912618874039056949487740349952263011317088634453489201382641790618101463136007282340404420259774291503801780305064159061395265693
give me a number> 3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290176
2765555006834400302764644631715279064190493333356686085387502538818346503951334264525654555177372632101686266045867203905356041400565701776648613048809050
give me a number> 799167628880894011233688890827050574271641124522232614619944181664095165137859998750798362384253944616915694367080095461234681773897801038410285056
7209267691571029432279155956089862867104715232859022819644143599704904435292167458680152157970253250402470537124301032508635677454138218218169282642287776
give me a number> 204586912993508866875824356051724947013540127877691549342705710506008362275292159680204380770369009821930417757972504438076078534117837065833032974336
10823571709980070463076247401617985760330555627761224202910928186143416124107619328738904916924411509945178859066257469926761468102905096523389940136955630
give me a number> 52374249726338269920211035149241586435466272736689036631732661889538140742474792878132321477214466514414186946040961136147476104734166288853256441430016
12300108933482917857460196443329219737125332851710834832907694728415647818766415867434947279848658712504502065968371230393793439353650119623737026859245168
give me a number> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
1
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}
暗号処理の概要は以下の通り。
・p, q, r: 2048bit素数→出力 ・n = pow(p, q) * r ・a1: 0以上n以下ランダム整数 ・a2 = n - a1 ※a1 % p != 0、a2 % p != 0 ・t = pow(a1, n) + pow(a2, n) ・x = v(p, t) ・tの素因数分解した中にpの何乗が含まれているかを返す。 ・xの文字列化とflagのxorの16進化したものを出力
p, q, rの値を小さくして、試したところx = q * 2であることがわかる。このことを前提に復号する。
from Crypto.Util.number import long_to_bytes from Crypto.Util.strxor import strxor import binascii with open('output.txt', 'r') as f: p, q, r = map(int, f.readline().rstrip().split(' ')) ct = eval(f.readline().rstrip()) flag = strxor(binascii.unhexlify(ct), long_to_bytes(q * 2, len(ct) / 2)) print flag
復号結果は以下の通り。
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
添付のDiscordの画像では右側が切れているため、p, qの途中の値が不明。
735426165606478775655440367887380252029393814251587377215443983568517874011835161632 289108065126883603562904941748653607836358267359664041064708762154474786168204628181 9145476916585122917284319282272004045859138239853037072761 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 341078269246532299656864881223 679098724593514422867704492870375465007225641192338424726642090768164214390632598250 39563231146143146482074105407
nの実際の値から、隠れている桁数を見てみる。
73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376 28910806512688360356290494174865360783635826735966404106470876215447478616820462818166737130578830362439690332321627911068539 9145476916585122917284319282272004045859138239853037072761
p, qはこのような値。
[p] 108294440701045353595867242719660522374526250640690193563048263854806748525172379331***************************************** 341078269246532299656864881223 [q] 679098724593514422867704492870375465007225641192338424726642090768164214390632598250***************************************** 39563231146143146482074105407
わかっている範囲からCoppersmithの定理を参考に復号する。
#!/usr/bin/sage from Crypto.Util.number import * n = 73542616560647877565544036788738025202939381425158737721544398356851787401183516163221837013929559568993844046804187977705376289108065126883603562904941748653607836358267359664041064708762154474786168204628181667371305788303624396903323216279110685399145476916585122917284319282272004045859138239853037072761 e = 65537 ct = 2657054880167593054409755786316190176139048369036893368834913798649283717358246457720021168590230987384201961744917278479195838455294205306264398417522071058105245210332964380113841646083317786151272874874267948107036095666198197073147087762030842808562672646078089825632314457231611278451324232095496184838 beta = 0.5 epsilon = beta^2/7 pbar = 108294440701045353595867242719660522374526250640690193563048263854806748525172379331 * 10 ^ 71 + 341078269246532299656864881223 pbits = pbar.nbits() kbits = (10 ^ 41).nbits() PR.<x> = PolynomialRing(Zmod(n)) f = x * (10 ^ 30) + pbar f = f.monic() x0 = f.small_roots(X=2^kbits, beta=0.5)[0] p = int(x0 * (10 ^ 30) + pbar) q = n // p assert p * q == n print '[+] p =', p print '[+] q =', q phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(ct, d, n) flag = long_to_bytes(m) print '[*] flag:', flag
実行結果は以下の通り。
[+] p = 10829444070104535359586724271966052237452625064069019356304826385480674852517237933153064479807396839988036432397395969825028341078269246532299656864881223
[+] q = 6790987245935144228677044928703754650072256411923384247266420907681642143906325982502924686164657029534309292920660089520491839563231146143146482074105407
[*] flag: corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}
corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}
サーバの処理概要は以下の通り。
・key: ランダム16バイト文字列 ・encrypt(flag)の16進文字列を表示 ・iv: ランダム16バイト文字列 ・ctr: ivからカウンター初期値を設定 ・flagをパディングし、AES-CTRで暗号化 ・iv + 暗号化データを返す ・以下繰り返し ・暗号化データをivと一緒に指定 →復号結果のパディングがおかしい場合、0を返す。 →復号結果のパディングが正しい場合、1を返す。
$ nc babypad.be.ax 1337 f94c4d4934d775551a0f332d9b446f783eac64e802a309baa18066176d3dc64a419ebb3ae725258391db54a0710a552b >
iv + 2ブロック暗号文が出力される。CBC Padding Oracle Attackと同様の考え方で、適当なバイトでXOR鍵を求めていき、復号する。
import socket from Crypto.Util.Padding import unpad from Crypto.Util.number import * from Crypto.Util.strxor import strxor def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('babypad.be.ax', 1337)) data = recvuntil(s, '\n').rstrip() print data enc_flag = data.decode('hex') iv = enc_flag[:16] ct = enc_flag[16:] key = ['', ''] for i in range(32): for k in range(256): try_ct = iv + 'a' * (32 - i - 1) + chr(k) if i < 16: try_ct += strxor(key[1], chr(i + 1) * i) else: try_ct += strxor(key[0], chr(i - 15) * (i - 16)) try_ct = try_ct.encode('hex') data = recvuntil(s, '> ') print data + try_ct s.sendall(try_ct + '\n') data = recvuntil(s, '\n').rstrip() print data if data == '1': if i < 16: key[1] = chr(k ^ (i + 1)) + key[1] else: key[0] = chr(k ^ (i - 15)) + key[0] break key = ''.join(key) flag = unpad(strxor(ct, key), 16) print flag
実行結果は以下の通り。
7b9fbe5e8123df3448092d9677689f3c692e555920ddd4903a999ccc6601a6a4fa433c708c3eecd19071ae0bba6f0265
> 7b9fbe5e8123df3448092d9677689f3c6161616161616161616161616161616161616161616161616161616161616100
0
> 7b9fbe5e8123df3448092d9677689f3c6161616161616161616161616161616161616161616161616161616161616101
0
> 7b9fbe5e8123df3448092d9677689f3c6161616161616161616161616161616161616161616161616161616161616102
0
> 7b9fbe5e8123df3448092d9677689f3c6161616161616161616161616161616161616161616161616161616161616103
0
：
> 7b9fbe5e8123df3448092d9677689f3c1751372a44abbfc37edbd3ac4275d285
0
> 7b9fbe5e8123df3448092d9677689f3c1851372a44abbfc37edbd3ac4275d285
0
> 7b9fbe5e8123df3448092d9677689f3c1951372a44abbfc37edbd3ac4275d285
0
> 7b9fbe5e8123df3448092d9677689f3c1a51372a44abbfc37edbd3ac4275d285
1
corctf{CTR_p4dd1ng?n0_n33d!}
corctf{CTR_p4dd1ng?n0_n33d!}
アンケートに答えていくと、最後にフラグが表示されていた。
corctf{thanks_for_playing!}
この大会は2021/8/14 4:00(JST)～2021/8/17 4:00(JST)に開催されました。
今回もチームで参戦。結果は2300点で602チーム中88位でした。
自分で解けた問題をWriteupとして書いておきます。
Discordに入り、#generalチャネルのトピックを見ると、フラグが書いてあった。
ractf{so_here_we_are_again}
画像の場所を地図上で指し示す問題。
画像検索すると、"Palazzo Cosentini"であることがわかる。
36.9233815,14.7276226の位置にあるので、Google Mapの位置と見比べながら位置を指定する。赤丸の位置でSubmitしたら、フラグが通った。
Ghidraでデコンパイルする。
bool main(int param_1,undefined8 *param_2) { undefined8 uVar1; FILE *pFVar2; FILE *pFVar3; size_t __size; void *__ptr; int *piVar4; char *pcVar5; uint uVar6; uint uVar7; size_t sVar8; long in_FS_OFFSET; bool bVar9; undefined local_40 [8]; long local_38; local_38 = *(long *)(in_FS_OFFSET + 0x28); if (param_1 < 3) { bVar9 = false; fprintf(stderr,"usage: %s <in file> <out file>\n",*param_2); } else { pFVar3 = fopen((char *)param_2[1],"rb"); pFVar2 = stderr; if (pFVar3 == (FILE *)0x0) { uVar1 = param_2[1]; piVar4 = __errno_location(); pcVar5 = strerror(*piVar4); fprintf(pFVar2,"failed to open input file %s: %s\n",uVar1,pcVar5); bVar9 = true; } else { fseek(pFVar3,0,2); __size = ftell(pFVar3); rewind(pFVar3); __ptr = malloc(__size); fread(__ptr,1,__size,pFVar3); fclose(pFVar3); uVar7 = rdseed(); rdseedIsValid(); printf("Seed: 0x%08X\n",(ulong)uVar7); uVar7 = rngInit(local_40,uVar7); if (__size != 0) { sVar8 = 0; uVar6 = 0; do { if (uVar6 == 0) { uVar7 = rngNext32(local_40); } uVar6 = uVar6 + 1 & 3; *(byte *)((long)__ptr + sVar8) = *(byte *)((long)__ptr + sVar8) ^ (byte)(uVar7 >> 0x18); sVar8 = sVar8 + 1; uVar7 = uVar7 >> 0x18 | uVar7 << 8; } while (__size != sVar8); } pFVar3 = fopen((char *)param_2[2],"wb"); pFVar2 = stderr; bVar9 = pFVar3 == (FILE *)0x0; if (bVar9) { uVar1 = param_2[2]; piVar4 = __errno_location(); pcVar5 = strerror(*piVar4); fprintf(pFVar2,"failed to open ouput file %s: %s\n",uVar1,pcVar5); } else { fwrite(__ptr,1,__size,pFVar3); fclose(pFVar3); } free(__ptr); } } if (*(long *)(in_FS_OFFSET + 0x28) == local_38) { return bVar9; } /* WARNING: Subroutine does not return */ __stack_chk_fail(); } void rngInit(undefined4 *param_1,undefined4 param_2) { *param_1 = param_2; return; } void rngNext32(int *param_1) { *param_1 = *param_1 * 0x17433a5b + -0x481e7b5d; return; }
4バイトごとにLCGが走る。4バイトの暗号化のkeyは、LCGで生成された数値を8ビットごとにabcdと定義すると以下のように変わる。
1バイト目：abcd→a 2バイト目：bcda→b 3バイト目：cdab→c 4バイト目：dabc→d
フラグがractf{から始まることを前提に復号する。
def rngNext32(r): return (r * 0x17433a5b - 0x481e7b5d) & 0xffffffff with open('secret', 'rb') as f: enc = f.read() pre_flag = 'ractf{' rng = 0 for i in range(4): rng *= 256 rng += ord(enc[i]) ^ ord(pre_flag[i]) flag = '' for i in range(len(enc) / 4 + 1): for j in range(4): if i * 4 + j < len(enc): flag += chr(ord(enc[i*4+j]) ^ ((rng >> (24 - j * 8)) & 0xff)) rng = rngNext32(rng) print flag
復号すると以下の文字列になる。
ractf{CL04K_3NGa6ed}sikeyouthoughttheflagwasthislongフラグは先頭部分で通った。
ractf{CL04K_3NGa6ed}
この大会は2021/8/13 22:30(JST)～2021/8/15 22:30(JST)に開催されました。
今回もチームで参戦。結果は210点で604チーム中120位でした。
自分で解けた問題をWriteupとして書いておきます。
Discordに入り、#generalチャネルのトピックを見ると、フラグが書いてあった。
inctf{welcome_t0_inctf_internationals_2021}
暗号処理の概要は以下の通り。
・pad = 0xDEADC0DE ・sze = 64 ・mod = 2**64の次の素数 ・obj = RNG(128ビットランダム整数) ・128ビットランダム整数(最上位は1) ・seed = gen_seed(val=128ビットランダム整数) ・ret = [val % mod] ・val >>= 64 ・63回以下繰り返し ・val = pow(i ^ ret[i] ^ pad, 3, mod) ・retに(val % mod)を追加 ・val >>= sze ・retを返す。 ・wrap() ・out1: 64個のobj.next()の16進数16バイトの配列の連結 ・out2: 64個のobj.next()の16進数16バイトの配列の連結 ・cip: out1から生成したkeyでAES-CBC暗号 →暗号化データとivを返す ・cipにout2を追加 ・cip(暗号化データ, iv, out2)を出力 ◇RNG.next() ・a, b, c, d: seed[ctr^i](i=0～3) ・k: ctrが奇数の場合1、偶数の場合2 ・a, b, c, d = (k*a-b)%mod, (b-c)%mod, (c-d)%mod, (d-a)%mod ・ctr += 1 ・ctrが64の場合、wrap()を実行 ・aを返す。 ◇RNG.wrap() ・hsze = 32 ・64回以下繰り返し ・r1 = seed[i] ・r2 = seed[(i+32)%64] ・seed[i] = ((r1^pad)*r2)%mod ・ctr = 0
ctr = 63の場合 a, b, c, d = seed[63], seed[62], seed[61], seed[60] a = (seed[63] - seed[62]) % mod b = (seed[62] - seed[61]) % mod c = (seed[61] - seed[60]) % mod d = (seed[60] - seed[63]) % mod out2[63] = (seed[63] - seed[62]) % mod ctr = 62の場合 a, b, c, d = seed[62], seed[63], seed[60], seed[61] a = (2 * seed[62] - seed[63]) % mod b = (seed[63] - seed[60]) % mod c = (seed[60] - seed[61]) % mod d = (seed[61] - seed[62]) % mod out2[62] = (2 * seed[62] - seed[63]) % mod
簡単な連立方程式となるので、算出するための式は簡単に書ける。
seed[63] = (out2[63] * 2 + out2[62]) % mod seed[62] = (out2[63] + out2[62]) % mod ： ||<< これでout2を生成する前まで戻せる。wrapも順に戻せるか見てみる。 >|| i = 63の場合 r1 = seed[63] r2 = seed[31] seed[63] = ((seed[63] ^ pad) * seed[31]) % mod →seed[63] = ((seed[63] * inverse(seed[31], mod)) % mod) ^ pad ：
wrapも順に戻せば、out1を復元することができる。あとは鍵を生成し、AES-CBC復号すれば、フラグが得られる。
#!/usr/bin/python3 import hashlib, gmpy2, pickle from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from Crypto.Util.number import * class RNG(): pad = 0xDEADC0DE sze = 64 mod = int(gmpy2.next_prime(2**sze)) def __init__(self, seed_val, seed=None): if seed == None: assert seed_val.bit_length() == 64*2, "Seed is not 128 bits!" self.seed = self.gen_seed(seed_val) self.wrap() else: self.seed = seed self.ctr = 0 def gen_seed(self, val): ret = [val % self.mod] val >>= self.sze for i in range(self.sze - 1): val = pow(i ^ ret[i] ^ self.pad, 3, self.mod) ret.append(val % self.mod) val >>= self.sze return ret def wrap(self, pr=True): hsze = self.sze//2 for i in range(self.sze): r1 = self.seed[i] r2 = self.seed[(i+hsze)%self.sze] self.seed[i] = ((r1^self.pad)*r2)%self.mod self.ctr = 0 def next(self): a, b, c, d = (self.seed[self.ctr^i] for i in range(4)) mod = self.mod k = 1 if self.ctr%2 else 2 a, b, c, d = (k*a-b)%mod, (b-c)%mod, (c-d)%mod, (d-a)%mod self.ctr += 1 if self.ctr==64: self.wrap(pr=False) return a pad = 0xDEADC0DE sze = 64 mod = int(gmpy2.next_prime(2**sze)) with open('enc.pickle', 'rb') as f: data = pickle.load(f) cip = bytes.fromhex(data['cip']) iv = bytes.fromhex(data['iv']) leak = data['leak'] out2 = [int(leak[i:i+16], 16) for i in range(0, len(leak), 16)] seed = [-1] * 64 for i in range(63, -1, -1): if i % 2 == 1: seed[i] = (out2[i] * 2 + out2[i^1]) % mod else: seed[i] = (out2[i] + out2[i^1]) % mod for i in range(63, -1, -1): r1 = seed[i] r2 = seed[(i + 32) % 64] seed[i] = ((r1 * inverse(r2, mod)) % mod) ^ pad obj = RNG(0, seed=seed) out1 = ''.join([format(obj.next(), '016x') for i in range(64)]) key = hashlib.sha256(bytes.fromhex(out1)).digest()[:16] cipher = AES.new(key, AES.MODE_CBC, iv) flag = unpad(cipher.decrypt(cip), 16).decode() print(flag)
inctf{S1mpl3_RN65_r_7h3_b35t!_b35e496b4d570c16}
暗号処理の概要は以下の通り。
・pvkey, pbkey = gen_key(FLAGのビット数) ・b = gen_inc_list(FLAGのビット数) ・b = [(16ビットランダム整数+5)の次の素数] ・bの要素数がFLAGのビット数になるまで以下繰り返し ・val: ランダム16ビット整数 ・bの数列の合計＋val以上になる素数をbに追加 →bは超増加数列になる。 ・bを返す。 ・q: bの最後の要素 ・ランダム8ビット整数の回数だけ以下繰り返し ・q: qの2倍の次の素数 ・r: bの最後の要素 + ランダム128ビット整数 ・pb = [(r*i)%q for i in b] ・(b, r, q), pbを返す。 ・cip = encrypt(FLAG, pbkey) ・msg: FLAGの2進数表記 ・msgの各ビットで、1だった場合に対応するpbkeyの値を合計する。 →この合計値を返す。
Merkle-Hellmanナップサック暗号になっていることがわかるので、LLLを使って復号する。
#!/usr/bin/sage import pickle from Crypto.Util.number import long_to_bytes def is_valid_vector(b): if b[0] != 0: return False for i, x in enumerate(b): if i != 0 and abs(x) != 1: return False return True with open('enc.pickle', 'rb') as f: data = pickle.load(f) cip = data['cip'] pbkey = data['pbkey'] matrix_size = len(pbkey) + 1 m_list = [ [0 for _ in range(matrix_size)] for _ in range(matrix_size) ] for i in range(matrix_size - 1): m_list[i][0] = pbkey[i] m_list[i][i+1] = 2 m_list[matrix_size - 1][i+1] = -1 m_list[matrix_size - 1][0] = - cip llled = Matrix(ZZ, m_list).LLL() flag_vecs = [] for basis in llled: if is_valid_vector(basis): flag_vecs.append(basis) for v in flag_vecs: bin_flag = '' for _bit in reversed(v[1:]): c = ("1" if _bit == 1 else "0") bin_flag = bin_flag + c flag = long_to_bytes(int(bin_flag, 2)).decode() print(flag)
inctf{wr5_m4_b4g?}
