LINE CTF (2021) writeup

2021/3/20 9:00~2021/3/21 10:00 JSTに開催されたLINE CTF(https://linectf.me/)にソロで参加しました。
結果はcryptoを2問解いて150pts、正の点数を取った680チーム中74位でした。

素敵な大会を開催してくださりありがとうございました。

また、大会開始序盤にかなりサーバーが不安定になっており、LINEというビッグネームの開催するCTFでも鯖が不安定になるんだから自分の運用する鯖が不安定になっても仕方ないぞという心理的な余裕を与えてくださいました。ありがとうございます。

babycrypto1(crypto, 106solved, 50pts)

AES-CBC(token++pad(command[0]), iv*)とiv*を得て、復号結果がtoken++pad(command[1])となるようなdataとivの組を求める問題です。ただし、1回だけ(data,iv)を投げてAES-CBC(data,iv)を得ることができます。

AES-CBC(token++pad(command[0]), iv*)の最後から2番目のブロックの値をenc[-2]とします。このとき、最終ブロックの値をpad(command[1])に対応する値、AES-CBC(pad(command[1]), iv=enc[-2])とすればよいです。

from pwn import * # pip install pwntools
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from base64 import b64decode, b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

r = remote('35.200.115.41', 16001)

tcommand = str(r.recv())
print("tcommand_raw: ", tcommand)
tcommand = tcommand[16:-3]
print("tcommand_raw: ", tcommand)
tcommand = b64decode(tcommand)
iv = tcommand[:AES.block_size]
tcommand = tcommand[AES.block_size:]
print("iv: ", iv)
print("tcommand: ", tcommand)

r.recv() # **Cipher oracle**\nIV...: 

#r.send(b64encode(b"\x00"*16))
r.send(b64encode(tcommand[-AES.block_size*2:-AES.block_size]))
r.recv() # Message...: 

r.send(b64encode(b"show"))
cp = b64decode(str(r.recv())[13:-5])
iv2 = cp[:AES.block_size]
cp = cp[AES.block_size:]
print("iv: ", iv2)
print("ciphertext: ", cp)

r.recv() # Enter your command:

x = b64encode(iv+tcommand[:-AES.block_size]+cp[:AES.block_size])
print("x: ", x)

r.send(x)
r.recv()
print(r.recv())
$ python3 solve.py 
[+] Opening connection to 35.200.115.41 on port 16001: Done
tcommand_raw:  b'test Command: JMdGrIg8Fi4UzsalKVjMLoPQ1iOVfHDU7R0Sj96xYRz/WbsVOS/MELeKYuP/sBpy7mGKFHhREq773CleaNQKHAY0HDmVaWHwuuM9ZFIpLep+n24LQmdwgExAAlvSHHck1gcA4W8w2jwOoAP7d4b8BVPouLz6ihLurEWz0YvNgOrUgUvaLDr0HHjNKmrbRgo7vL/7qboHHXHsCmYaf+67B2iVUsDedXJnIn7+0nhxkvntlpSA9xbdn+eiz2ym538y\n'
tcommand_raw:  JMdGrIg8Fi4UzsalKVjMLoPQ1iOVfHDU7R0Sj96xYRz/WbsVOS/MELeKYuP/sBpy7mGKFHhREq773CleaNQKHAY0HDmVaWHwuuM9ZFIpLep+n24LQmdwgExAAlvSHHck1gcA4W8w2jwOoAP7d4b8BVPouLz6ihLurEWz0YvNgOrUgUvaLDr0HHjNKmrbRgo7vL/7qboHHXHsCmYaf+67B2iVUsDedXJnIn7+0nhxkvntlpSA9xbdn+eiz2ym538y
iv:  b'$\xc7F\xac\x88<\x16.\x14\xce\xc6\xa5)X\xcc.'
tcommand:  b'\x83\xd0\xd6#\x95|p\xd4\xed\x1d\x12\x8f\xde\xb1a\x1c\xffY\xbb\x159/\xcc\x10\xb7\x8ab\xe3\xff\xb0\x1ar\xeea\x8a\x14xQ\x12\xae\xfb\xdc)^h\xd4\n\x1c\x064\x1c9\x95ia\xf0\xba\xe3=dR)-\xea~\x9fn\x0bBgp\x80L@\x02[\xd2\x1cw$\xd6\x07\x00\xe1o0\xda<\x0e\xa0\x03\xfbw\x86\xfc\x05S\xe8\xb8\xbc\xfa\x8a\x12\xee\xacE\xb3\xd1\x8b\xcd\x80\xea\xd4\x81K\xda,:\xf4\x1cx\xcd*j\xdbF\n;\xbc\xbf\xfb\xa9\xba\x07\x1dq\xec\nf\x1a\x7f\xee\xbb\x07h\x95R\xc0\xdeurg"~\xfe\xd2xq\x92\xf9\xed\x96\x94\x80\xf7\x16\xdd\x9f\xe7\xa2\xcfl\xa6\xe7\x7f2'
iv:  b'h\x95R\xc0\xdeurg"~\xfe\xd2xq\x92\xf9'
ciphertext:  b'\xa4\r\xc1\xab@six\nf\xb3\x9d\x8f#B9'
x:  b'JMdGrIg8Fi4UzsalKVjMLoPQ1iOVfHDU7R0Sj96xYRz/WbsVOS/MELeKYuP/sBpy7mGKFHhREq773CleaNQKHAY0HDmVaWHwuuM9ZFIpLep+n24LQmdwgExAAlvSHHck1gcA4W8w2jwOoAP7d4b8BVPouLz6ihLurEWz0YvNgOrUgUvaLDr0HHjNKmrbRgo7vL/7qboHHXHsCmYaf+67B2iVUsDedXJnIn7+0nhxkvmkDcGrQHNpeApms52PI0I5'
b'The flag is: LINECTF{warming_up_crypto_YEAH}'

LINECTF{warming_up_crypto_YEAH}です。

babycrypto2 (crypto, 90?solves, 50pts)

AES-CBC(PREFIX++COMMAND[0]++token, iv*)とiv*が与えられて、復号結果がPREFIX++COMMAND[1]++tokenとなるようなdataとivの組を求める問題です。

AES-CBCの復号では、ivを変えることではじめのブロックの復号結果を調整できるのでした。具体的には、dataはAES-CBC(PREFIX++COMMAND[0]++token, iv*)のままで、ivをiv = iv* xor (b"\x00"*9+COMMAND[0]+b"\x00"*3) xor (b"\x00"*9+COMMAND[1]+b"\x00"*3)にすればよいです。

from pwn import * # pip install pwntools
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from base64 import b64decode, b64encode
from Crypto.Cipher import AES


r = remote('35.200.39.68', 16002)

tcommand = str(r.recv())
tcommand = tcommand[16:-3]
print("tcommand_raw: ", tcommand)
tcommand = b64decode(tcommand)
iv = tcommand[:AES.block_size]
tcommand = tcommand[AES.block_size:]
print("iv: ", iv)
print("tcommand: ", tcommand)

r.recv() # Enter your command: 

iv2 = b"\x00"*9 + bytes([a^b for a,b in zip(b"test", b"show")]) +b"\x00"*3
print("iv2: ", iv2)

iv3 = bytes([a^b for a,b in zip(iv, iv2)])
x = b64encode(iv3+tcommand)
r.send(x)
r.recv()
print(r.recv())
$ python3 solve.py 
[+] Opening connection to 35.200.39.68 on port 16002: Done
tcommand_raw:  Fvfm9a6vYTSvxDUFjM8GtlT+ZVKX2yyxyhwxV3nCrsOll3mQb+ps8usBbpU2S8Uv9WPm1Ua4gvxlzOMIAOdwTN+cqXhpbT4mqkPoVnSP84IQbi9ShHa/tkPQxDsKWs7URlrT38wOoc1MZ6dmTPph2WokCjRnwnf2TzshLNzFEK27uj5N1N5Cq6fKxEbWXU0jn1elJXHy+W947lzzI9SLxlrTNXQ8oXZ02B9Z3npXVr2f0W/8Vbz4/Bx+UWlzXS49QXtLgt+65Z8VFbrKbSJxzPAqjy3+XJ/LsslRSQbqhaRGb2H+1CVXCB2msKOeYCKrjQ01CZpdHBIuQHrsL6fuMw==     
iv:  b'\x16\xf7\xe6\xf5\xae\xafa4\xaf\xc45\x05\x8c\xcf\x06\xb6'
tcommand:  b'T\xfeeR\x97\xdb,\xb1\xca\x1c1Wy\xc2\xae\xc3\xa5\x97y\x90o\xeal\xf2\xeb\x01n\x956K\xc5/\xf5c\xe6\xd5F\xb8\x82\xfce\xcc\xe3\x08\x00\xe7pL\xdf\x9c\xa9xim>&\xaaC\xe8Vt\x8f\xf3\x82\x10n/R\x84v\xbf\xb6C\xd0\xc4;\nZ\xce\xd4FZ\xd3\xdf\xcc\x0e\xa1\xcdLg\xa7fL\xfaa\xd9j$\n4g\xc2w\xf6O;!,\xdc\xc5\x10\xad\xbb\xba>M\xd4\xdeB\xab\xa7\xca\xc4F\xd6]M#\x9fW\xa5%q\xf2\xf9ox\xee\\\xf3#\xd4\x8b\xc6Z\xd35t<\xa1vt\xd8\x1fY\xdezWV\xbd\x9f\xd1o\xfcU\xbc\xf8\xfc\x1c~Qis].=A{K\x82\xdf\xba\xe5\x9f\x15\x15\xba\xcam"q\xcc\xf0*\x8f-\xfe\\\x9f\xcb\xb2\xc9QI\x06\xea\x85\xa4Foa\xfe\xd4%W\x08\x1d\xa6\xb0\xa3\x9e`"\xab\x8d\r5\t\x9a]\x1c\x12.@z\xec/\xa7\xee3'
iv2:  b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x07\r\x1c\x03\x00\x00\x00'
b'The flag is: LINECTF{echidna_kawaii_and_crypto_is_difficult}'

LINECTF{echidna_kawaii_and_crypto_is_difficult}です。

babycrypto3(unsolved)

pem形式の証明書が与えられるのでとりあえず読める形にします。私はhttps://8gwifi.org/PemParserFunctions.jsp を使いました。

Algo RSA
Format X.509
 ASN1 Dump
RSA Public Key [15:38:2d:a9:6f:9a:84:2b:85:11:5e:66:c0:c7:30:c4:31:5b:91:fe]
            modulus: 328b14139a2e54b88a4662f1a67cc3acd1929c9b62794bb64916aff02991f80456e4d0eed4d591df7708d5af2e9b4fb5689
    public exponent: 10001

n=0x328b14139a2e54b88a4662f1a67cc3acd1929c9b62794bb64916aff02991f80456e4d0eed4d591df7708d5af2e9b4fb5689, e=0x10001のRSAっぽいです。nをmsieveに投げつつ解法を探りましたがわからず。かなしい。

babycrypto4(unsolved)

ECDSAの(r,s,下16bitがmaskされたk,hash)が20組渡されて秘密鍵dを求める問題。

secp160k1のパラメータはhttps://www.secg.org/SEC2-Ver-1.0.pdf を参照。

なんとなく格子な気がしたので、ECDSAをLLLで殴る話ってあるのかなと思って探してみたらあった。(https://eprint.iacr.org/2019/023.pdf)
よってこの論文やptr-yudai先生のLLLに関するブログ(https://ptr-yudai.hatenablog.com/entry/2020/03/12/223338)を参考にうまいことやろうとしたのですがうまくいかず。格子張り力(ぢから)が足りなかったのかな。かなしい。

どうでもいいのですが、英語の論文に対する心理的な障壁がかなり低くなっていてここ一年で大分成長したなあという気持ちになりました。