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を送ってやと計算してもらうことだが、三者は送られてきたパラメータが であることを確認しているのでこれはできない。それならばはどうか。三者の秘密鍵が偶数の場合はとなってしまうので途中でエラーになるが、すべて奇数ならばとに落ち着く。

というわけでを送りつつがそれぞれ奇数になる組み合わせを引くまでガチャする。実際はガチャ用のコードを整えている間に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に教えてもらったけど、がそれぞれ偶数の場合でも解けて、1度目の介入では適当な値を渡して、2度目でだけを送るようにすればshareがの偶奇に応じてかになるので、↑の方法より確率を上げることができる。

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というゲームらしく、相手が出してきた手と自分が出してきた手の和が偶数になるように値を選んで送れば勝ちとなる。相手は手をの間から一つ選び、 と毎回ことなる乱数を用いてとして渡してくれる。

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

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

ところでここからがよくわかっていないんだけど、チームメイトのS3v3ru5に教えてもらい手元で実験した感じだと、の値によってヤコビ記号がうまく働いたり働かなかったりする。うまく働くケースに限って持金を全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 を渡すことができ、かつ適当なメッセージに署名をしてもらえるので、向こうが指定したメッセージに署名するとフラグがもらえる。

楕円曲線上の離散対数問題が解けでもしない限りそんなことはできない。ところが与えられている楕円曲線のパラメータを見てみると、位数が小さい素因数としてを持っているとS3v3ru5が教えてくれた。このとき、適当な楕円曲線上の点に対してをかけた の位数は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()