BSides Noida CTF | kotf_returns

#bsidesnoidactf

from hashlib import sha1
from random import randint
from sys import exit
from os import urandom
from Crypto.PublicKey import DSA
from Crypto.Util.number import bytes_to_long, getPrime

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


def message_hash(x):
    return bytes_to_long(sha1(x).digest())


def nonce(s, padding, i, q):
    return (pow(message_hash(s), rot, chop) + padding + i) %q


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 = (message_hash(m) * w) % q
    u2 = (r * w) % q
    v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
    return v == r

def pow_solve():
    pow_nonce = urandom(4)
    print(f"Solve PoW for {pow_nonce.hex()}")
    inp = bytes.fromhex(input())
    if sha1(pow_nonce + inp).hexdigest().endswith('000000'):
        print("Correct PoW. Continue")
        return True
    print("Incorrect PoW. Abort")
    return False


try:
    if not pow_solve():
        exit()
    L, N = 1024, 160
    dsakey = DSA.generate(1024)
    p = dsakey.p
    q = dsakey.q
    h = randint(2, p - 2)

    # sanity check
    g = pow(h, (p - 1) // q, p)
    if g == 1:
        print("oopsie")
        exit(1)

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

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

    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)
        # nonce generation remains the same
        k = nonce(m, pad, i, q)
        if k < 1:
            exit()
        r = pow(g, k, p) % q
        if r == 0:
            exit()
        s = (pow(k, q - 2, q) * (message_hash(m) + x * r)) % q
        if s == 0:
            exit()
        # No hash leak for you this time
        print(f"<r={r}, s={s}>")

    print("ok im done for now. You visit the flag keeper...")
    print("for flag, you must bring me signed message for 'give flag'")

    r1 = int(input())
    s1 = int(input())
    if verify(r1, s1, b"give flag"):
        print(open("flag.txt").read())
    else:
        print("Never gonna give you up")
except:
    print("Never gonna let you down")

redpwn CTF 2021 | Keeper of the Flagとなにか関連しているらしい

DSAでrelated kなのでshatteredであわせてやるだけ

from ptrlib import Socket
from hashlib import sha1
import proofofwork

def message_hash(x):
    return int(sha1(x).hexdigest(), 16)

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

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

z1 = message_hash(m1)
z2 = message_hash(m2)
assert z1 == z2

# sock = Socket("localhost", 9999)
sock = Socket("nc 34.105.241.228 1338")

prefix = bytes.fromhex(sock.recvlineafter("PoW for ").decode())
s = proofofwork.sha1("??????????????????????????????????000000", text=prefix + b"?????")
print(sha1(s).hexdigest())
sock.sendline(s[len(prefix):].hex())


p, q, g, y = [int(x) for x in sock.recvregex(r"p=(\d+), q=(\d+), g=(\d+), y=(\d+)")]

sock.sendlineafter("please\n", m1.hex())
r1, s1 = [int(x) for x in sock.recvregex(r"r=(\d+), s=(\d+)")]

sock.sendlineafter("please\n", m2.hex())
r2, s2 = [int(x) for x in sock.recvregex(r"r=(\d+), s=(\d+)")]


P.<k> = PolynomialRing(GF(q))

x1 = (k*s1 - z1) * inverse_mod(r1, q)
x2 = ((k+1)*s2 - z2) * inverse_mod(r2, q)
f = x1 - x2
roots = f.roots()
print(roots)

assert len(roots) > 0
k = int(roots[0][0])

x = int((k*s1 - z1) * inverse_mod(r1, q) % q)
assert pow(g, x, p) == y

m = b"give flag"
k = 2
r = int(pow(g, k, p)) % q
s = (int(pow(k, q - 2, q)) * (message_hash(m) + x * r)) % q
sock.sendlineafter("give flag'", str(r))
sock.sendline(str(s))

sock.interactive()