ふるつき

v(*'='*)v かに

Securinets CTF 2021 Quals writeup

楽しく解ける問題ばかりで評価が高い。BOSS問という感じの問題はなかったので割と解かれていた印象。唯一PoWが面倒な形式だったのでもうちょっと丁寧に作ってほしかった感じはある

MiTM

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

名前のとおりにAlice Bob Carol三者のDiffie Hellman鍵共有プロセスに介入して、任意のパラメータの交換を改竄できる。ただし三者は鍵共有のあと、互いの鍵が一致しているかを確かめるために、それぞれの鍵のfingerprintが一致することを確認している。したがって、三者の鍵を同じにしつつ、鍵の中身を知ることができるような改竄の仕方を考える必要がある。

一番簡単な方法は0や1を送って 0^a = 0 1^a = 1と計算してもらうことだが、三者は送られてきたパラメータ x 1 \lt x \lt p であることを確認しているのでこれはできない。それならば -1はどうか。三者秘密鍵 a,b,cが偶数の場合は -1^a \equiv 1 \mod pとなってしまうので途中でエラーになるが、すべて奇数ならば -1^a \equiv -1 \equiv p-1 \mod p p-1に落ち着く。

というわけで p-1を送りつつ a,b,cがそれぞれ奇数になる組み合わせを引くまでガチャする。実際はガチャ用のコードを整えている間にyoshikingがガチャを当てて解いていた。

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import hashlib
import time

while True:
    time.sleep(1)
    sock = Socket("crypto1.q21.ctfsecurinets.com", 1337)
    p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45

    sock.sendlineafter("Forward to Bob: ", str(p - 1))
    AB = int(sock.recvlineafter("Carol: "))
    if AB == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Carol: ", str(AB))
    print("[+] progress 1")

    sock.sendlineafter("Forward to Carol: ", str(p - 1))
    BC = int(sock.recvlineafter("Alice: "))
    if BC == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Alice: ", str(BC))
    print("[+] progress 2")

    sock.sendlineafter("Forward to Alice: ", str(p - 1))
    CA = int(sock.recvlineafter("Bob: "))
    if CA == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Bob: ", str(CA))
    print("[+] progress 3")

    print(sock.recvline())
    line = sock.recvline().decode()
    if "ABORT" in line:
        sock.close()
        continue

    key = hashlib.sha1(long_to_bytes(p - 1)).digest()[:16]
    iv, cipher = bytes.fromhex(line[:32]), bytes.fromhex(line[32:])
    aes = AES.new(key, AES.MODE_CBC, iv)
    print(aes.decrypt(cipher))

    break

あとでyoshikingに教えてもらったけど、 a,b,cがそれぞれ偶数の場合でも解けて、1度目の介入では適当な値を渡して、2度目でだけ p-1を送るようにすればshareが a,b,cの偶奇に応じて 1 p-1になるので、↑の方法より確率を上げることができる。

Shilaformi

import signal
from secret import flag
from Crypto.Random import random
from Crypto.Util.number import getPrime

#Odds and evens (hand game)
#https://en.wikipedia.org/wiki/Odds_and_evens_(hand_game)

def pad(choice, n):
    return 2*random.randint(1, n//2 - 1) + choice

def send(choice, n):
    choice = pad(choice, n)
    return pow(2, choice, n )

signal.alarm(360)
print ("Let's play odds and evens! If I win you loose 5 times the amount of money you have bet! I choose odd.\n")

WALLET = 10
while WALLET > 0:
    print("Your current wallet is {} $.\n".format(WALLET))

    if WALLET > 133337:
        print("Wow, You've got filthy rich. Here's your flag: {}".format(flag))
        exit()

    n = getPrime(1024)*getPrime(1024)
    print ("Public Modulus : {}\n".format(n))

    bet = int(input("Place your bet : "))
    assert bet <= WALLET and bet > 0

    choice = random.randint(0, 5)
    print ("Here's my choice : {}\n".format(send(choice, n)))

    player = int(input("Shilaaafooooooormi: "))
    assert player >= 0 and player < 6

    if (choice + player ) & 1:
        print("You lose.")
        WALLET -= 5*bet
    else:
        print("You win.")
        WALLET += bet

print("You got no money left in your wallet. Make sure to come back later!")

いわゆるOdds and evensというゲームらしく、相手が出してきた手と自分が出してきた手の和が偶数になるように値を選んで送れば勝ちとなる。相手は手 x 0 \le x \le 5の間から一つ選び、 n = pq と毎回ことなる乱数 rを用いて y = 2^{2r + x} \mod nとして渡してくれる。

このとき、 yから xの偶奇を判断する問題は、平方剰余問題(quadratic residuosity problem)として知られている 平方剰余問題と行った場合には aから a \equiv x^2 \mod nを満たす xを探す問題を指していそう。この問題は平方剰余の判定問題で、一般的な名前があるのかは知らない。ある値 aがある剰余の法 nの上で平方剰余か(= x^2 \equiv  a \mod nとなる xが存在するか)を調べるためにはルジャンドル記号、あるいはヤコビ記号を使うことができる。ルジャンドル記号は剰余の法が素数である場合に使える記号であり、ヤコビ記号はルジャンドル記号を拡張して合成数にも適用可能にしたものである。ただし、一部の正確性は失われている

大雑把に言えば、 Jacobi(a, n) = 1 のとき aは平方剰余かもしれないし、そうでないかもしれない。一方で Jacobi(a, n) = -1のとき、 aは必ず平方剰余ではない。したがって、与えられた手 y nについて Jacobi(y, n)をみて、その値が1の時はOdds and evensに勝てる確率は1/2であり、その値が1のときは必ず勝つことができる。

ところでここからがよくわかっていないんだけど、チームメイトのS3v3ru5に教えてもらい手元で実験した感じだと、 nの値によってヤコビ記号がうまく働いたり働かなかったりする。うまく働くケースに限って持金を全betし、勝てるかわからないときは1だけ掛けることで持金を増やした。

from ptrlib import Socket
import proofofwork
import gmpy2
import random

sock = Socket("crypto2.q21.ctfsecurinets.com", 1337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

# sock = Socket("localhost", 19999)

while True:
    current = int(sock.recvregex(r"wallet is ([0-9]+) \$.\n")[0])
    print(current)
    if current > 133337:
        sock.interactive()
    n = int(sock.recvlineafter("Modulus : "))
    print("[+] got modulus")

    # check n
    flag = True
    for choice in range(0, 6):
        x = 2*random.randint(1, n//2 - 1) + choice
        y = pow(2, x, n)
        if (x % 2 == 0) != (gmpy2.jacobi(y, n) == 1):
            flag = False
    print("[+] check: {}".format(flag))

    bet = 1
    if flag:
        # surely win
        bet = current
    sock.sendlineafter("bet : ", str(bet))

    y = int(sock.recvlineafter("choice : "))
    sock.sendlineafter("mi: ", str(1 if gmpy2.jacobi(y, n) == -1 else 0))
    if b"win" in sock.recvline():
        current += bet
        print("Win! current money: {}".format(current))
    else:
        current -= bet*5
        print("Loose... current money: {}".format(current))

        if current <= 0:
            print("LOOSE")
            break

Sign It!

from Crypto.Util.number import inverse
from Crypto.Random import random
from fastecdsa.curve import Curve
from fastecdsa.point import Point
import hashlib
import signal

class Server():
    def __init__(self, curve, G):
        self.G = G
        self.order = curve.q
        self.d = random.randrange(1, self.order - 1)
        self.P = (self.d * self.G)

    def sign(self, msg):
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        k = random.randrange(1, self.order - 1)
        r = (k * self.G).x % self.order
        s = (inverse(k, self.order) * (z + r * self.d)) % self.order
        return (r, s)

    def verify(self, msg, sig):
        r, s = sig
        s %= self.order
        r %= self.order
        if s == 0 or r == 0:
            return False
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        s_inv = inverse(s, self.order)
        u1 = (z * s_inv) % self.order
        u2 = (r * s_inv) % self.order
        W = u1 * self.G + u2 * self.P
        return W.x == r


signal.alarm(360)
# S256 curve params
p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883
S256 = Curve("S256", p, a, b, q, gx, gy)

PROOF = "Give me flag."
print("Welcome to the ECDSA testing of our probably secure S256 Curve. First choose your own generator then try to sign this message '{}' to prove us wrong.\n".format(PROOF))

print("Choose your point (x y) : ")

try:
    x = int(input("x : "))
    y = int(input("y : "))
    G = Point(x, y, curve=S256)
    S = Server(S256, G)

    sample = "No flags for you."
    print("Here's a sample signature: msg = '{}' , signature = {}".format(
        sample, S.sign(sample)))

    while True:
        msg = input("Message : ").strip()
        r = int(input("r : "))
        s = int(input("s : "))
        if S.verify(msg, (r, s)):
            print("Valid signature.")
            if msg == PROOF:
                from secret import flag
                print("Here you go : {}".format(flag))
                exit()
        else:
            print("Invalid signature.")

except Exception as e:
    print(e)
    exit()

ECDSAに関する問題。こちらからはいわゆるBase Point  Gを渡すことができ、かつ適当なメッセージに署名をしてもらえるので、向こうが指定したメッセージに署名するとフラグがもらえる。

楕円曲線上の離散対数問題が解けでもしない限りそんなことはできない。ところが与えられている楕円曲線のパラメータを見てみると、位数 qが小さい素因数として 157を持っているとS3v3ru5が教えてくれた。このとき、適当な楕円曲線上の点 Gに対して q/157をかけた G' = (q/157)G の位数は157になる。位数が小さければ離散対数問題は簡単にとける。

import hashlib
from ptrlib import Socket
import proofofwork

p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883

EC = EllipticCurve(GF(p), [a, b])
G = EC(gx, gy)
G2 = (q // 157) * G  # 157 is small factor of order

# sock = Socket("localhost", 19999)
sock = Socket("crypto2.q21.ctfsecurinets.com", 13337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

sock.sendlineafter("x : ", str(G2[0]))
sock.sendlineafter("y : ", str(G2[1]))

r, s = sock.recvregex(r"signature = \(([0-9]+), ([0-9]+)\)")
msg = "No flags for you."
z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
r, s = int(r), int(s)

for k in range(157):
    if (k*G2)[0] == r:
        print("[+] found k: {}".format(k))
        break
else:
    raise ValueError("[-] failed to calculate discrete log")

d = (s*k - z)*inverse_mod(r, 157) % 157
print("[+] found d: {}".format(d))


PROOF = "Give me flag."
z = int(hashlib.sha256(PROOF.encode()).hexdigest(), 16)
r = int((k * G2)[0])
s = (int(inverse_mod(k, 157)) * (z + r * d)) % 157


sock.sendlineafter("Message : ", PROOF)
sock.sendlineafter("r : ", str(r))
sock.sendlineafter("s : ", str(s))
sock.interactive()