SecurinetsQuals2k21 | MitM Revenge - crypto-writeup-public

#securinetsquals2k21

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
import random
import 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.")

SecurinetsQuals2k21 | MiTMの続き

Diffie-Hellmanがnonce付きで次のように行われる、かつ、介入できるフェーズが減っている

鍵共有ステップは次の通り（ちなみに介入せずに動作してもうまく動かないプロトコルになってる）

step1

Alice → $g^a$ → Bob

Bob → $(g^{ab}, nonce_b)$ → Carol

Carolは $g^{abc} \oplus nonce_b$ を計算する

step2

Bob → $g^b \not \to$ Carol（ $\not \to$ は改ざんできる通信）

Carol → $(g^{bc}, nonce_c)$ $\not \to$ Alice

Aliceは $g^{abc} \oplus nonce_c$ を計算する

step3

Carol → $g^c$ $\not \to$ Alice

Alice → $g^{ca}$ $\not\to$ Bob

Bobは $g^{abc} \oplus nonce_x$ を計算する（ $nonce_x$ は見えない $nonce_a$ を渡すやつ

その後、三人は共有した鍵のFingerPrintが一致しているかどうかを確認する

観察

step1で計算される $g^{abc} \oplus nonce_b$ は一切いじれないので、3人の共有鍵をこれにするようにして、かつ内容を知るしかない
しかも、step2で計算されるAliceの共通鍵 $g^{abc} \oplus nonce_c$ を計算する時点で、Carolの共通鍵と一致している必要がある
CarolからAliceへ渡すパラメータを $(p-1, nonce_c)$ とすると、Aliceの持つ鍵は $p-1 \oplus nonce_c$ または $1\oplus nonce_c$ となるのでこれで寄せることはできそう
BobがCarolに渡す $g^{b}$ をうまく改竄して $c$ の値をうまく知る必要がありそう？
[* cの値を知らなくても、 $x^c$ してくれるタイミングで $g^{ab}$ を渡せばよいのだった]

解法

step1

$g^a$ をうけとる
$(g^{ab}, nonce_b)$ を受け取る

step2

（Bobから） $g^b$ を受けとる
$g^{ab}$ をCarolに送る
（Carolから） $(g^{abc}, nonce_c)$ を受け取る　[* ←ここで $g^{abc}$ がわかる！！！]
$(p-1, g^{abc} \oplus 1)$ を送る。うまくいけば、Aliceの鍵は $(p-1)^a \oplus (g^{abc} \oplus 1) = g^{abc}$ と計算される

step3

$g^c$ を受け取る
$g^c$ をAliceに送る
$g^{ac}$ を受け取る
$(g^{ac}, nonce_b)$ を送ると、Bobは $g^{abc} \oplus nonce_b$ を計算する。これは

step1

の計算と同じ

host, port = "crypto1.q21.ctfsecurinets.com", 13337
conn = remote(host, port)

def recv_num(prefix):
    conn.recvuntil(prefix)
    return int(conn.recvline().strip())

def recv_pair(prefix):
    conn.recvuntil(prefix)
    return ast.literal_eval(conn.recvline().strip().decode())

def send_data(prefix, data):
    conn.sendlineafter(prefix, str(data).encode())

# conn.recvuntil(b"Alice sends to Bob: ")
g_y1 = recv_num(b"Alice sends to Bob: ")
g_y1y2, n2 = recv_pair(b"Bob sends to Carol: ")

g_y2 = recv_num(b"Bob sends to Carol: ")

send_data(b"Forward to Carol: ", g_y1y2)

g_y1y2y3, n3 = recv_pair(b"Carol sends to Alice: ")

new_nonce = g_y1y2y3 ^ n2 ^ 1
send_data(b"Forward to Alice: ", str(p-1) + " " + str(new_nonce))

g_y3 = recv_num(b"Carol sends to Alice: ")
send_data(b"Forward to Alice: ", str(g_y3))
g_y1y3 = recv_num(b"Alice sends to Bob: ")

send_data(b"Forward to Bob: ", str(g_y1y3) + " " + str(n2))

# conn.recvline()
print(g_y1y2y3, n2)
conn.interactive()