久しぶりにCTFに参加しました。cryptoのある程度以上の難易度の問題を解いたら満足してしまって、昔CTFを開催していたときに「この人いつも特定のジャンルの問題だけ解いて帰るな～」と思って見ていた人の気持ちってこういうことだったんだろうな、と思いました。
取り組んだ問題は面白かったし、解いていて楽しかったです。
[Crypto] AAAA
ほぼ全てがマスクされたOpenSSH形式のRSAの秘密鍵を見せてもらえます。わかるのは鍵の一部のBASE64がTOKYO+INSTITUTE+OF+TECHNOLOGY+DIGITAL+CREATORS+CLUB+TRAPAAAA を含むということだけ。
しかしそれ以外にも、公開鍵と暗号文、それから を貰えます。
RSAの には
という関係があり、適当な整数
を用いて
と書いて両辺
で割ると、与えられている
はほとんど
と一致する事がわかります。
今回の問題設定ではが大きく、ほとんど
くらいの大きさがあることと合わせて考えると
についてを取ると
という式が立ち*1、未知数は
のみで、
の半分程度の大きさになるはずなので、この剰余多項式の小さい根を求めれば
が求まります。
がわかれば
が求められるのであとは
を求めて暗号文を復号すればよいです。
問題に与えられていた文字列はのbase64結果のようでした
from base64 import b64decode, b64encode e = 506184338... n = 12339326... k = 6649705358687... PR.<x> = PolynomialRing(Zmod(e)) f = 1 + k*n - k*x + k f = f.monic() s = int(f.small_roots(X=floor(3 * n**0.5), beta=0.5)[0]) phi = n - s + 1 d = int(pow(e, -1, phi)) c = 91909831... m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:]))
[Crypto] CES
以下のいずれかを合計2回だけ行えるサーバに接続できます。
CESはAESに手を加えたブロック暗号で、subbytesの実装が次のようになっていること以外はオリジナルのAESの実装と同じです。
def concat(a, b): tmp = int("{:064b}".format(a) + "{:064b}".format(b), 2) tmp_bin_list = [int(n) for n in bin(tmp)[2:]] irreducible_poly = [1, 0, 0, 0, 1, 1, 0, 1, 1] res = np.polydiv(tmp_bin_list, irreducible_poly)[1] res = list(map(int, res)) res = [x % 2 for x in res] res = "".join(map(str, res)) res = int(res, 2) return res def sub_bytes(s, round_key): for i, line in enumerate(s): for j, x in enumerate(line): k = bytes_to_long(matrix2bytes(round_key)) res = concat(k, s[i][j]) assert concat(k, res) == s[i][j] s[i][j] = res return s
このconcat, subbytes がどういう実装になっているのかはわかりませんでしたが、assert の条件をながめていると「このsubbytesの実装は線形な変換になっているのでは」と思いました。
AESの各種ステップのうち非線形な変換はsubbytesだけですから、この実装が線形になればCESによる暗号化は線形な変換になります。つまり、平文を鍵
で暗号化したとき、暗号文
の各ビットが
と
の何らかのビットのXORで表せます。鍵の足し方は平文によりませんから、異なる平文
を同一の鍵
で暗号化した
について
となるはずです。
ということを実験したらまさにそうなったので、サーバの実装では1, 2で同じ鍵が使われることを利用して、2で得た暗号化された平文を1で作った適当な平文の暗号文を用いて復号するコードを書きました
from ptrlib import Socket, chunks, xor import ast from problem import bytes2matrix, matrix2bytes, N_ROUNDS, inv_shift_rows, inv_mix_columns def my_decrypt(ciphertext): state = bytes2matrix(ciphertext) for i in range(N_ROUNDS - 1, -1, -1): inv_shift_rows(state) if i > 0: inv_mix_columns(state) plaintext = matrix2bytes(state) return plaintext sock = Socket("ces.web.cpctf.space 30008") sock.sendlineafter("option: ", "2") f_enc = ast.literal_eval(sock.recvlineafter("flag: ").decode()) # type: bytes iv = ast.literal_eval(sock.recvlineafter("iv: ").decode()) sock.sendlineafter("option: ", "1") payload = "A" * len(f_enc) sock.sendlineafter("encrypt: ", payload) enc = ast.literal_eval(sock.recvlineafter("message: ").decode()) # type: bytes iv2 = ast.literal_eval(sock.recvlineafter("iv: ").decode()) flag = b"" for c1, c2 in zip(chunks(f_enc, 16), chunks(enc, 16)): c_wo_k = my_decrypt(xor(c1, c2)) # c_wo_k = (f_i ^ iv1) ^ (m_i ^ iv2) flag_i = xor(xor(c_wo_k, xor(b"A" * 16, iv2)), iv) flag += flag_i print(flag) iv = c1 iv2 = c2
AESがそれっぽく改造されており一見難問にみえるものの、assertで性質をさりげなく表現することで難易度が調節されており、良い問題だったと思います。
*1:s = p + qとおいてます
