#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」

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」

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」

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」

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 問で力尽きました（泣）。