#1. はじめに
2021/3/21 02:00 JST ～ 2021/3/22 02:00 JST に開催された「Securinets CTF Quals 2021」にチーム「N30Z30N」としてソロ参加しました。Welcome 以外に Crypto を 2 問解いたので、Writeup を残します。
※2021/07/22 はてなブログより移転。
#2. Writeup
##2-1. MiTM (Crypto, 559pt)
You managed to get in the middle and control the entire discussion between Alice, Bob and Carol. What are they saying ?
ファイル：「app.py」
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag
import hashlib, random, os
import signal
class DHx():
def __init__(self):
self.g = 2
self.p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45
self.private = random.randint(1, self.p-1)
self.secret = None
def getPublicKey(self):
return pow(self.g, self.private, self.p)
def share(self, x : int):
assert x > 1 and x < self.p
return pow(x, self.private, self.p)
def getSharedSecret(self, x : int):
assert x > 1 and x < self.p
self.secret = pow(x, self.private, self.p)
def getFingerprint(self):
return hashlib.sha256(long_to_bytes(self.secret)).hexdigest()
def checkFingerprint(self, h1 : str, h2 : str ):
return h1 == h2 == self.getFingerprint()
def encryptFlag(self):
iv = os.urandom(16)
key = hashlib.sha1(long_to_bytes(self.secret)).digest()[:16]
return iv.hex() + AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)).hex()
signal.alarm(60)
Alice = DHx()
Bob = DHx()
Carol = DHx()
A = Alice.getPublicKey()
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
B = Bob.share(A)
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
Carol.getSharedSecret(B)
B = Bob.getPublicKey()
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
C = Carol.share(B)
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
Alice.getSharedSecret(C)
C = Carol.getPublicKey()
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
A = Alice.share(C)
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
Bob.getSharedSecret(A)
print ("Alice says: ")
if (Alice.checkFingerprint(Carol.getFingerprint(), Bob.getFingerprint())):
print (Alice.encryptFlag())
else:
print ("ABORT MISSION! Walls have ears; Be careful what you say as people may be eavesdropping.")
Diffie-Hellman 的な鍵交換を Alice、Bob、Carol の 3 人で [Alice→Bob→Carol]、[Bob→Carol→Alice]、[Carol→Alice→Bob]の 3 フェイズで行いますが、どのフェイズでもプレーヤーは配送中のデータを盗聴及び改ざんできます。そして、結果的に 3人の Shared Secret の SHA256 ハッシュが一致すれば暗号化フラグがもらえます。復号キーは Shared Secret なので、ハッシュの一致のほかに Shared Secret を把握する必要があります。
3 人の秘密鍵をそれぞれ a、b、cとすると、改ざんを何もしない場合 Shared Secret は 2^(abc) で一致するので、暗号化フラグはもらえますが Shared Secret そのものが分からないと復号できません。
そこで、SharedSecret を把握もしくはコントロールできないか考えます。getSharedSecret の引数に入れられる整数値は 2 以上 p-1 以下ですが、 これを 「p-1」 に揃えれば良さげです。なぜなら、「3 人の秘密鍵が全部偶数」は 1/8 の確率で発生し、かつそのとき SharedSecret の値は全て「1」となります。
ソルバ「solve.py」
from pwn import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import sys
def decryptFlag(enc):
iv = enc[:16]
key = hashlib.sha1(long_to_bytes(1)).digest()[:16]
return AES.new(key, AES.MODE_CBC, iv).decrypt(enc[16:])
p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45
while(True):
r = remote("crypto1.q21.ctfsecurinets.com", 1337)
r.recv(1000)
for i in range(6):
r.sendline(str(p-1).encode())
print(r.recv(1000))
s = r.recv(1000)
print(s)
if not b"ABORT" in s:
print(decryptFlag(bytes.fromhex(s.split(b"\n")[1].decode())))
exit()
else:
r.close()
面倒なので、input する値は必要な場所以外でもすべて「p-1」に揃えて実装しました。
Securinets{monkey-in-the-middle_efa8cf7dad56f238cc1ff49473da3ae3}
##2-2. MiTM Revenge (Crypto, 757pt)
Oh Crap! You came late, again.
ファイル：「app.py」
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag
import hashlib, random, os
import signal
class DHx():
def __init__(self):
self.g = 2
self.p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45
self.private = random.randint(1, self.p-1)
self.nonce = random.randint(1, self.p-1)
self.secret = None
def getPublicKey(self):
return pow(self.g, self.private, self.p)
def share(self, x : int):
assert x > 1 and x < self.p
return pow(x, self.private, self.p)
def getSharedSecret(self, x : int, nonce : int):
assert x > 1 and x < self.p
self.secret = pow(x, self.private, self.p) ^ nonce
def getFingerprint(self):
return hashlib.sha256(long_to_bytes(self.secret)).hexdigest()
def checkFingerprint(self, h1 : str, h2 : str ):
return h1 == h2 == self.getFingerprint()
def encryptFlag(self):
iv = os.urandom(16)
key = hashlib.sha1(long_to_bytes(self.secret)).digest()[:16]
return iv.hex() + AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)).hex()
signal.alarm(120)
Alice = DHx()
Bob = DHx()
Carol = DHx()
A = Alice.getPublicKey()
print("Alice sends to Bob: {}".format(A))
B = Bob.share(A)
print("Bob sends to Carol: {}".format((B, Bob.nonce)))
Carol.getSharedSecret(B, Bob.nonce)
B = Bob.getPublicKey()
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
C = Carol.share(B)
print("Carol sends to Alice: {}".format((C, Carol.nonce)))
data = input("Forward to Alice: ").strip().split()
C , Carol.nonce = int(data[0]), int(data[1])
Alice.getSharedSecret(C, Carol.nonce)
C = Carol.getPublicKey()
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
A = Alice.share(C)
print("Alice sends to Bob: {}".format(A))
data = input("Forward to Bob: ").strip().split()
A , Alice.nonce = int(data[0]), int(data[1])
Bob.getSharedSecret(A, Alice.nonce)
print ("Alice says: ")
if (Alice.checkFingerprint(Carol.getFingerprint(), Bob.getFingerprint())):
print (Alice.encryptFlag())
else:
print ("ABORT MISSION! Walls have ears; Be careful what you say as people may be eavesdropping.")
先問の応用編（？）です。盗聴の機会は同じですが改ざん機会が減っています。「Alice の公開鍵を Bob に送って、さらにCarol に送る」フェーズでの改ざんができません。さらに、getSharedSecret の処理で nonce をXOR するよう改められていますが、Alice と Carol の nonceは改ざん可能です。
本質的には前問と同じく、「Shared Secret の値を揃えること」と「Shared Secret の値を把握する」ことを両立させる問題です。すなわち、「Carol の Shared Secret （改ざんの余地なし）に合うよう、他の Shared Secret をコントロールする」ことと、「Shard Secretの値をリークする」ことを、盗聴・改ざんの機会を駆使して実現させます。
以下、3 人の秘密鍵をそれぞれ a、b、cとし、具体的な解法を示します。Shared Secret の値は「 2^(abc) XOR [Bob の
nonce]」であることに注意します。
・最初のフェイズで、「Bob の nonce」及び 2^(ab) の値を入手できます。
・2 番目のフェイズの最初の input では、改ざんを行いません（Bob の公開鍵をそのまま流します）。その結果、2^(bc)の値を入手できます。
・2 番目のフェイズの 2 番目の input では、 Shared Secret を最初のフェイズのものと一致させるため、 第二引数（nonce）を Bob の nonce に差し替えて送ります。
・3 番目のフェイズの最初の input では、入手済みの値である 2^(bc) を入れます。その結果、2^(abc) の値を入手できます。
・3 番目のフェイズの 2 番目の input では、Shared Secret を以前の 2 つと一致させるため、 第一引数 には「2」を、第二引数（nonce）には「2^(abc) XOR [Bob の nonce] XOR 2^b」を入れます。この結果、 Shared Secret は「2^b XOR 2^(abc) XOR [Bob の nonce] XOR 2^b」=「2^(abc) XOR [Bob の nonce] 」で前の 2 つと一致します。さらに、2^(abc) の値と 「Bob の nonce」は入手済ですから、Shared Secret の値も判明し、復号にも成功します。
ソルバ「solve.py」
from pwn import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import sys
p = 169622824183424820825728324890204115101468714952998142585574034795946851153950475569207215681807529286667189170420372861538287664283023804761495759297626394111153684529019990561684722443184304549649494421130078368098045597169822975289983997491594344239614944483399038130689027660812095676588300142576532463429
def decryptFlag(enc, k):
iv = enc[:16]
key = hashlib.sha1(long_to_bytes(k)).digest()[:16]
return AES.new(key, AES.MODE_CBC, iv).decrypt(enc[16:])
r = remote("crypto1.q21.ctfsecurinets.com", 13337)
#Phase 1
_res1 = r.recvline()
pub_a = int(_res1.decode().replace("Alice sends to Bob: ", ""))
_res2 = r.recvline()
res2 = _res2.decode().replace("Bob sends to Carol: ", "").replace("(","").replace(")\n","").split(", ")
ab = int(res2[0])
Nonce_b = int(res2[1])
#Phase 2
_res3 = r.recvline()
pub_b = int(_res3.decode().replace("Bob sends to Carol: ", ""))
to_send = str(pub_b).encode()
_res4 = r.recv(1000)
r.sendline(to_send)
_res5 = r.recvline()
res5 = _res5.decode().replace("Carol sends to Alice: ", "").replace("(","").replace(")\n","").split(", ")
bc = int(res5[0])
to_send = str(bc).encode()
_res6 = r.recv(1000)
r.sendline(to_send + b" " + str(Nonce_b).encode())
#Phase 3
_res7 = r.recvline()
pub_c = int(_res7.decode().replace("Carol sends to Alice: ", ""))
to_send = str(bc).encode()
_res8 = r.recv(1000)
r.sendline(to_send)
_res9 = r.recvline()
res9 = _res9.decode().replace("Alice sends to Bob: ", "").replace("(","").replace(")\n","").split(", ")
abc = int(res9[0])
to_send = "2".encode()
ss = abc ^ Nonce_b #Shared Secret
Nonce2 = pub_b ^ ss
_resa = r.recv(1000)
r.sendline(to_send + b" " + str(Nonce2).encode())
s0 = r.recvline()
s = r.recv(1000)
ct = s.replace(b"\n",b"").decode()
print(decryptFlag(bytes.fromhex(ct), ss))
r.close()
汚いプログラムですが、競技中使ったものを（確認用print文以外）ほぼそのまま上げました。
Securinets{master-in-the-middle_bb8f4b012d02284aea258723179dff83}
#3. おわりに
Crypto は この他に RSA 問を含め 3 問がありましたが、上記 2 問で力尽きました（泣）。