GoogleCTF 2022
むずすぎてぴえん。cryptoしか見てないけど全然手が出なかった。。。
復習が捗りますな。とりあえず手を出した
- Cycling
- Maybe Someday
の２つについて解説をまとめることを目標にする。記事は不定期で逐次アップデートしながら書いていく予定。
Update
googleCTFは公式解説出るんですね。ただしソースコードのみなので、頑張って読み解かないといけない。。
Cycling
e = 65537 n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1 ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680 # Decryption via cycling: pt = ct for _ in range(2**1025 - 3): pt = pow(pt, e, n) # Assert decryption worked: assert ct == pow(pt, e, n) # Print flag: print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())
要約
pow(ct, e21025 - 3, n)を求めよ。
解法
完璧なwriteupが出てた。もうこれ見れば十分では。
要約すると、[tex:R = 21025 - 3]として
- pow(ct, eR+1, n)=ctが成立。
- これよりeR+1 | φ(n)であるが、λ(n)をカーマイケル数としてeR+1 = λ(n) = lcm(p-1, q-1) = lcm(2s1s2...sk)なのではと予想。
- これよりR+1 | λ(λ(n)) だが、ここもR+1 = λ(2s1...*sk)=lcm(s1-1,...,sk-1)と予想。
- ここから{s1,...,sk}が求まるので、そこからλ(n)が復元できて、これをφ(n)の代理として後はいつものRSAデコードしておしまい。
（工事中）
コード
出力
Maybe Someday
from Crypto.Util.number import getPrime as get_prime import math import random import os import hashlib # Suppose gcd(p, q) = 1. Find x such that # 1. 0 <= x < p * q, and # 2. x = a (mod p), and # 3. x = b (mod q). def crt(a, b, p, q): return (a*pow(q, -1, p)*q + b*pow(p, -1, q)*p) % (p*q) def L(x, n): return (x-1) // n class Paillier: def __init__(self): p = get_prime(1024) q = get_prime(1024) n = p * q λ = (p-1) * (q-1) // math.gcd(p-1, q-1) # lcm(p-1, q-1) g = random.randint(0, n-1) µ = pow(L(pow(g, λ, n**2), n), -1, n) self.n = n self.λ = λ self.g = g self.µ = µ self.p = p self.q = q # https://www.rfc-editor.org/rfc/rfc3447#section-7.2.1 def pad(self, m): padding_size = 2048//8 - 3 - len(m) if padding_size < 8: raise Exception('message too long') random_padding = b'\0' * padding_size while b'\0' in random_padding: random_padding = os.urandom(padding_size) return b'\x00\x02' + random_padding + b'\x00' + m def unpad(self, m): if m[:2] != b'\x00\x02': raise Exception('decryption error') random_padding, m = m[2:].split(b'\x00', 1) if len(random_padding) < 8: raise Exception('decryption error') return m def public_key(self): return (self.n, self.g) def secret_key(self): return (self.λ, self.µ) def encrypt(self, m): g = self.g n = self.n m = self.pad(m) m = int.from_bytes(m, 'big') r = random.randint(0, n-1) c = pow(g, m, n**2) * pow(r, n, n**2) % n**2 return c def decrypt(self, c): λ = self.λ µ = self.µ n = self.n m = L(pow(c, λ, n**2), n) * µ % n m = m.to_bytes(2048//8, 'big') return self.unpad(m) def fast_decrypt(self, c): λ = self.λ µ = self.µ n = self.n p = self.p q = self.q rp = pow(c, λ, p**2) rq = pow(c, λ, q**2) r = crt(rp, rq, p**2, q**2) m = L(r, n) * µ % n m = m.to_bytes(2048//8, 'big') return self.unpad(m) def challenge(p): secret = os.urandom(2) secret = hashlib.sha512(secret).hexdigest().encode() c0 = p.encrypt(secret) print(f'{c0 = }') # # The secret has 16 bits of entropy. # # Hence 16 oracle calls should be sufficient, isn't it? # for _ in range(16): # c = int(input()) # try: # p.decrypt(c) # print('😀') # except: # print('😡') # I decided to make it non-interactive to make this harder. # Good news: I'll give you 25% more oracle calls to compensate, anyways. cs = [int(input()) for _ in range(20)] for c in cs: try: p.fast_decrypt(c) print('😀') except: print('😡') guess = input().encode() if guess != secret: raise Exception('incorrect guess!') def main(): with open('/flag.txt', 'r') as f: flag = f.read() p = Paillier() n, g = p.public_key() print(f'{n = }') print(f'{g = }') try: # Once is happenstance. Twice is coincidence... # Sixteen times is a recovery of the pseudorandom number generator. for _ in range(16): challenge(p) print('💡') print(f'🏁 {flag}') except: print('👋') if __name__ == '__main__': main()
要約
２バイト乱数をsha512でハッシュ化した文字列をPaillier暗号で暗号化した結果を渡される。この時20回任意の暗号文を一度に与えて、それらが復号成功したかのオラクルを得られるので、そこから平文を当てよ。これを16回連続で成功したらフラグ獲得。
解法
Pailler暗号初めて知ったけど加法準同型暗号なんですね、平文の足し算がgの指数に乗ることで暗号文の積になって保たれるのが本質だが、encrypt時にかける乱数rをdecrypt時に削除するのに|(Z/p2 Z)*| = p(p-1)なのをうまく利用していて、もうこの理屈がわかった時点で満腹感がw
となると明らかに加法準同型性は使うんだろう。あとオラクルから得られる情報として、復号が失敗するのは平文のパディングが想定通りになっているか、つまり
padded_secret = [\x00, \x02, (乱数の125文字), \x00, (secretの128文字)]
の形になっているか、より具体的には
- 復号結果の先頭２文字は\x00\x02の形になっているか
- そこから8文字以降後に\x00が少なくとも１つ存在するか
がチェックできる。
ここから思いつく案として、
m(x) := [0] * 128 + [x] + [0] * 127 (0<=x<256) c(x) := enc(m(x))
として、c0 * c(x)をdecryptさせれば
dec(c0 * c(x)) = m0 + m(x) = [0, 2, (乱数の125文字), ?, x+secret[0], secret[1], ...]
となり、x+secret[0] == 256になった瞬間に桁上がりで? = \x01となるからdecryptは失敗する。これでsecret[0]が割れるから、以下同様にsecret[1], secret[2], ...と順に求まるという作戦は立つ。
しかしoriginal_plain[0]を割る時点でこれだと256回の試行、また8bit毎に分けて考えたとしても32回の試行が必要で、平文が２バイトなことを加味しても、20回しかヒントをもらえない状況だと無理すぎる（本番はここで詰んだ）。
後でふるつき先生のwriteupを覗いて、見落としてたのは以下の１文だと判明した。
secret = hashlib.sha512(secret).hexdigest().encode()
なんとhexdigestしてからencodeしているではないか。ということはsecretに出てくる数字はb'0'~b'9'（48~57）とb'a'~b'f'（97~102）の16通りしかないことになる。
んでどうすんねんという話になるが、結論から言うと「先頭から0, 2, 4, ..., 20文字目にxが少なくとも１つ存在するか」（x = b'0', ..., b'9', b'a', ..., b'f'、つまり48<=x<=57, 97<=x<=102）を判定すれば良い。これは上述のオラクルを利用して
m(x) = [0] * 127 + [1] + [256-x, 0] * 10 + [0] * 108
に対応する暗号文をc0にかけてdecryptさせれば良い。0, 2, 4,...と飛び飛びにしているのは繰り上がりの影響をなくすためである。もし元の平文にxが存在すれば、secret + m(x)は後ろ128byteのどこかに\x00が現れるのでdecrypt成功するし、存在しなければ\x00がどこにも現れないためdecrypt失敗となる。
さて、これで本当に平文が一意に特定可能か心配なので、少し実験してみよう。この手法でsecretの上位20byteの偶数番目に出てくる文字の種類がわかるが、そこから一意に求まる平文がどの程度あるのか数えてみる。
plains = [None] * (1 << 16) # 平文は２バイトなので全部で256*256=65536通り for i in tqdm(range(1<<16)): bi = int("0x{:04x}".format(i), 16) bi = long_to_bytes(bi) plains[i] = hashlib.sha512(bi).hexdigest().encode() # 実際に暗号化する平文はsha512を通した後の文字列 descriptor = defaultdict(int) # descriptor[(平文の上位0,2,...,20文字目に現れる文字種)] = (そんな平文が何種類あるか) for p in plains: desc1 = set([p[i] for i in range(0, 20, 2)]) desc1 = tuple(sorted(list(desc1))) descriptor[desc1] += 1 success = fail = 0 for key, val in descriptor.items(): if val == 1: success += 1 else: fail += 1 print(f"unique percentage = {success * 100 / (success + fail)}%") # unique percentage = 48.15130830489192%
え。。。ダメじゃん。。。確率48%を16回も繰り返して全成功は流石に厳しすぎる。もう少し条件を絞らないといけなそうだ。
ここで、上記の判定はxの16通りしか使っていない。一方得られるオラクルは20回なので、残り４回で何か追加条件を作ろう。
「先頭から1, 3, 5, ..., 21文字目にxが少なくとも１つ存在するか」（x = b'a', ..., b'd'、つまり97<=x<=100）
というのはどうだろうか？これに対応する平文は
m(x) = [0] * 127 + [1] + [0, 256-x] * 10 + [0] * 108
である。この追加条件を加えて平文が一意に決まる確率がどこまで上がるか再度実験してみる。
descriptor = defaultdict(int) # descriptor[(平文の上位0,2,...,20文字目に現れる文字種＋上位1,3,...,21文字目に'a'~'d'のどれが出てくる)] = (そんな平文が何種類あるか) for p in plains: desc1 = set([p[i] for i in range(0, 20, 2)]) desc1 = tuple(sorted(list(desc1))) desc2 = set() for i in range(1, 21, 2): if 97 <= p[i] <= 100: desc2.add(p[i]) desc2 = tuple(sorted(list(desc2))) descriptor[desc1 + desc2] += 1 success = fail = 0 for key, val in descriptor.items(): if val == 1: success += 1 else: fail += 1 print(f"unique percentage = {success * 100 / (success + fail)}%") # unique percentage = 94.97607655502392%
こんな上がるんか！これなら16回連続成功確率は(95/100)16 = 0.44、なかなかいい勝負である。少なくとも十数回トライすればフラグ取れるでしょう。行ったれ！
コード
from collections import defaultdict from tqdm import tqdm from Crypto.Util.number import long_to_bytes from pwn import * # preprocess: collect secret candidates plains = [None] * (1 << 16) for i in tqdm(range(1<<16)): bi = int("0x{:04x}".format(i), 16) bi = long_to_bytes(bi) plains[i] = hashlib.sha512(bi).hexdigest().encode() # preprocess: collect descriptors of secrets descriptor = defaultdict(set) # descriptor[(平文の上位0,2,...,20文字目に現れる文字種＋上位1,3,...,21文字目に'a'~'d'のどれが出てくる)] = (そんな平文たち) for p in plains: desc1 = set([p[i] for i in range(0, 20, 2)]) # 平文の上位0,2,...,20文字目に現れる文字種 desc1 = tuple(sorted(list(desc1))) desc2 = set() # 上位1,3,...,21文字目に'a'~'d'のどれが出てくるか for i in range(1, 21, 2): if 97 <= p[i] <= 100: desc2.add(p[i]) desc2 = tuple(sorted(list(desc2))) descriptor[desc1 + desc2].add(p) # connect to the server HOST = "maybe-someday.2022.ctfcompetition.com" PORT = 1337 io = remote(HOST, PORT) io.recvuntil(b"n = ") n = int(io.recvline()) io.recvuntil(b"g = ") g = int(io.recvline()) def solve_oneround(): io.recvuntil(b"c0 = ") c0 = int(io.recvline()) # create 20 exploits cs = [] for x in range(48, 58): # 0~9それぞれが[0,2,4,..., 20]文字目にあるか m = b"\x00" * 127 + b"\x01" + (long_to_bytes(256 - x) + b"\x00") * 10 + b"\x00" * 108 m = int.from_bytes(m, 'big') c = pow(g, m, n**2) c = c0 * c % n**2 cs.append(c) for x in range(97, 103): # a~fそれぞれが[0,2,4,..., 20]文字目にあるか m = b"\x00" * 127 + b"\x01" + (long_to_bytes(256 - x) + b"\x00") * 10 + b"\x00" * 108 m = int.from_bytes(m, 'big') c = pow(g, m, n**2) c = c0 * c % n**2 cs.append(c) for x in range(97, 101): # a~dそれぞれが[1, 3, 5, ..., 21]文字目にあるか m = b"\x00" * 127 + b"\x01" + (b"\x00" + long_to_bytes(256 - x)) * 10 + b"\x00" * 108 m = int.from_bytes(m, 'big') c = pow(g, m, n**2) c = c0 * c % n**2 cs.append(c) # send 20 exploits for c in cs: c = str(c).encode() io.sendline(c) # get 20 results results = [] for _ in range(20): ret = io.recvline().decode().rstrip() results.append(ret == '😀') # aggregate information appeared = [] for i, ret in enumerate(results[:10]): if ret: appeared.append(48 + i) for i, ret in enumerate(results[10:16]): if ret: appeared.append(97 + i) for i, ret in enumerate(results[16:20]): if ret: appeared.append(97 + i) # crack appeared = tuple(appeared) cand = descriptor[appeared].pop() io.sendline(cand) reply = io.recvline().decode().rstrip() return reply succeeded = True for cnt in range(16): reply = solve_oneround() print(cnt, reply) succeeded &= (reply == '💡') if not succeeded: break if succeeded: print(io.recv().decode().rstrip())
出力
100%|██████████| 65536/65536 [00:00<00:00, 160714.14it/s] [x] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337 [x] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337: Trying 34.78.83.159 [+] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337: Done 0 💡 1 💡 2 💡 3 💡 4 💡 5 💡 6 💡 7 💡 8 💡 9 💡 10 💡 11 💡 12 💡 13 💡 14 💡 15 💡 🏁 CTF{p4dd1n9_or4cl3_w1th_h0mom0rph1c_pr0p3r7y_c0m6in3d_in7o_a_w31rd_m47h_puzz1e}
感想
先頭20文字を見て判別するアイデア、どうやって出すんだろうか。 こんな不確定性のある問題は初めてで、その場合の発想の引き出し方がまだ全然訓練できてない。。
