楽しく解ける問題ばかりで評価が高い。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がの偶奇に応じて
かになるので、↑の方法より確率を上げることができる。
import signal
from secret import flag
from Crypto.Random import random
from Crypto.Util.number import getPrime
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):])
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")
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:
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
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)
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
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()