redpwn CTF 2021 | Keeper of the Flag

#redpwnctf2021

#!/usr/local/bin/python3

from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from random import *
from hashlib import sha1

rot = randint(2, 2 ** 160 - 1)
chop = getPrime(159)

def H(s):
    x = bytes_to_long(sha1(s).digest())
    return pow(x, rot, chop)


L, N = 1024, 160
dsakey = DSA.generate(1024)
p = dsakey.p
q = dsakey.q
h = randint(2, p - 2)
g = pow(h, (p - 1) // q, p)
if g == 1:
    print("oops")
    exit(1)

print(p)
print(q)
print(g)

x = randint(1, q - 1)
y = pow(g, x, p)

print(y)


def verify(r, s, m):
    if not (0 < r and r < q and 0 < s and s < q):
        return False
    w = pow(s, q - 2, q)
    u1 = (H(m) * w) % q
    u2 = (r * w) % q
    v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
    return v == r


pad = randint(1, 2 ** 160)
signed = []
for i in range(2):
    print("what would you like me to sign? in hex, please")
    m = bytes.fromhex(input())
    if m == b'give flag' or m == b'give me all your money':
        print("haha nice try...")
        exit()
    if m in signed:
        print("i already signed that!")
        exit()
    signed.append(m)
    k = (H(m) + pad + i) % q
    if k < 1:
        exit()
    r = pow(g, k, p) % q
    if r == 0:
        exit()
    s = (pow(k, q - 2, q) * (H(m) + x * r)) % q
    if s == 0:
        exit()
    print(H(m))
    print(r)
    print(s)

print("ok im done for now")
print("you visit the flag keeper...")
print("for flag, you must bring me signed message:")
print("'give flag':" + str(H(b"give flag")))

r1 = int(input())
s1 = int(input())
if verify(r1, s1, b"give flag"):
    print(open("flag.txt").readline())
else:
    print("sorry")

2回DSAで署名してくれるので、give flag に署名できれば成功

が連番になっている / sha1が使われている のでshatteredみたいな感じで衝突できる

from pwn import *

with open("shattered-1.pdf", "rb") as f:
    m1 = f.read().hex()

with open("shattered-2.pdf", "rb") as f:
    m2 = f.read().hex()

host, port = "mc.ax", 31538
io = remote(host, port)

io.recvuntil(b"sh -s ")
pow_chall = io.recvline().decode()
io.recvuntil(b"solution: ")
io.sendline(process(["redpow", pow_chall]).recv().strip())

print("completed pow")

p = int(io.recvline().strip().decode())
q = int(io.recvline().strip().decode())
g = int(io.recvline().strip().decode())

y = int(io.recvline().strip().decode())

print(f"p = {p}, q = {q}, g = {g}, y = {y}")

io.recvline()
io.sendline(m1.encode())

h1 = int(io.recvline().strip().decode())
r1 = int(io.recvline().strip().decode())
s1 = int(io.recvline().strip().decode())

io.recvline()
io.sendline(m2.encode())

h2 = int(io.recvline().strip().decode())
r2 = int(io.recvline().strip().decode())
s2 = int(io.recvline().strip().decode())

print(f"h1 == h2 => {h1 == h2}")
print(f"r1 = {r1}, s1 = {s1}")
print(f"r2 = {r2}, s2 = {s2}")

io.recvuntil(b"'give flag':")

h3 = int(io.recvline().strip().decode())
print(f"h3 = {h3}")

print("Solving for x")

P = PolynomialRing(Zmod(q), "a")
a = P.gen()


# k*s1 = h + x*r1
# k*s2 + s2 = h + x * r2

# s1**(-1) * (h + x*r1) = s2**-1((h + x * r2) - s2)

f = inverse_mod(s1, q) * (h1 + a * r1)
f = f - inverse_mod(s2, q) * ((h2 + a * r2) - s2)

roots = f.roots()

print(f"roots = {roots}")
for (poss, _) in roots:
    if int(pow(g, int(poss), p)) == int(y):
        x = int(poss)
        break
else:
    print("Failed")

k = 12903
r3 = int(pow(g, k, p)) % q
s3 = inverse_mod(k, q) * (h3 + x*r3) % q

print(f"r3 = {r3}, s3 = {s3}")

io.sendline(str(r3).encode())
io.sendline(str(s3).encode())
io.interactive()