Hack.lu-Qualifier-2023/Crypto/Spooky Safebox writeup

#!/usr/bin/env python3

import secrets
import os, sys, hmac
import cryptod
from proofofwork import challenge_proof_of_work

FLAG = os.environ.get("FLAG", "flag{FAKE_FLAG}") if "flag" in os.environ.get("FLAG","") else "flag{FAKE_FLAG}"
 
def main():
    print("Welcome to the Spooky Safebox!")
    if not challenge_proof_of_work():
        return
    kpriv, kpub = cryptod.make_keys()
    order = cryptod.get_order()
    encrypted_flag = cryptod.encrypt(kpub, FLAG)
    print("Here is the encrypted flag:", encrypted_flag)
    print("You've got 9 signatures, try to recover Satoshi's private key!")
    for i in range(9):
        msg_ = input("Enter a message to sign: >")
        msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
        checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))
        nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
        sig = kpriv.sign(int(msg, 16) % order, nonce)
        print("Signature",(cryptod.int_to_bytes(int(sig.r)) + bytes.fromhex("deadbeef") + cryptod.int_to_bytes(int(sig.s))).hex())
    
    print("Goodbye!")

if __name__ == '__main__':
    try:
        main()
    except EOFError:
        pass
    except KeyboardInterrupt:
        pass

import ecdsa, ecdsa.ecdsa
from cryptography.hazmat.primitives.kdf.kbkdf import (
   CounterLocation, KBKDFHMAC, Mode
)
from cryptography.hazmat.primitives import hashes
import secrets
from Crypto.Cipher import ChaCha20_Poly1305

def get_order(): return ecdsa.NIST256p.generator.order()
def encrypt_sym(input_bytes: bytes, key:bytes):

    cipher = ChaCha20_Poly1305.new(key=key)
    ciphertext, tag = cipher.encrypt_and_digest(input_bytes)
    return ciphertext + tag + cipher.nonce

def derive_symkey(inp:bytes):
    kdf = KBKDFHMAC(
        algorithm=hashes.SHA3_256(),
        mode=Mode.CounterMode,
        length=32,
        rlen=4,
        llen=4,
        location=CounterLocation.BeforeFixed,
        label=b"safu",
        context=b"funds are safu",
        fixed=None,
    )
    return kdf.derive(inp)
    
def make_keys():
    gen = ecdsa.NIST256p.generator
    secret = secrets.randbelow(gen.order()-1) + 1
    pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
    priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
    return priv_key, pub_key

def int_to_bytes(n: int) -> bytes:
    return n.to_bytes((n.bit_length() + 7) // 8, 'big') or b'\0'

def encrypt(kpub_dest:ecdsa.ecdsa.Public_key, msg:str):
    gen = ecdsa.NIST256p.generator
    r = secrets.randbelow(gen.order()-1) + 1
    R = gen * r
    S = kpub_dest.point * r
    key = derive_symkey(int_to_bytes(int(S.x())))
    cp = encrypt_sym(msg.encode(), key).hex() 
    return cp + "deadbeef" + R.to_bytes().hex()

r = secrets.randbelow(gen.order()-1) + 1
R = gen * r
S = kpub_dest.point * r
key = derive_symkey(int_to_bytes(int(S.x())))
cp = encrypt_sym(msg.encode(), key).hex() 

checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))

nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum

import hmac, secrets, ecdsa
checksum = 2**224 + (int(hmac.new(b"\x00" , b"msg", "sha224").hexdigest(), 16) % (ecdsa.NIST256p.generator.order()-2**224))
nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
ZZ(checksum).nbits(), ZZ(nonce).nbits(), ZZ(nonce-checksum).nbits()

msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()

hmac.new(b"\x00", b"msg", "sha224").hexdigest()

from pwn import *
from tqdm.auto import tqdm

context.log_level = 'info'

def int_to_bytes(n):
    n = int(n)
    return n.to_bytes((n.bit_length() + 7) // 8, 'big') or b'\0'

def solve_pow(challenge, prefix):
    check = lambda s, challenge, prefix: hashlib.sha256((challenge + s).encode('utf-8')).hexdigest()[:len(prefix)] == prefix
    for i in range(0, 2**32):
        if check(str(i), challenge, prefix):
            return challenge + str(i)
    return -1

class IO:
    def __init__(self):
        self.conn = remote("flu.xxx", int(10030))
        self.r = []
        self.s = []
        self.cp = b''
        self.R = b''

    def proof_of_work(self):
        self.conn.recvuntil(b"Please provide a string that starts with ")
        challenge = self.conn.recvuntil(b" ").strip().decode()
        self.conn.recvuntil(b"and whose sha256 hash starts with ")
        prefix = self.conn.recvuntil(b"\n").strip().decode()
        answer = solve_pow(challenge, prefix)
        self.conn.sendlineafter(b"POW: >", answer.encode())

    def get_ciphertext(self):
        self.conn.recvuntil(b"Here is the encrypted flag: ")
        data = self.conn.recvuntil(b"\n").strip()
        cp, R = data.split(b"deadbeef")
        cp = bytes.fromhex(cp.decode())
        R = bytes.fromhex(R.decode())
        return cp, R

    def sign(self, msg):
        self.conn.sendlineafter(b"Enter a message to sign: >", msg)
        self.conn.recvuntil(b"Signature ")
        data = self.conn.recvuntil(b"\n").strip()
        r, s = data.split(b"deadbeef")
        r = int(r, 16)
        s = int(s, 16)
        return r, s

    def io(self):
        self.proof_of_work()
        self.cp, self.R = self.get_ciphertext()
        msg = b"msg"
        sign_data = [self.sign(b"msg") for _ in range(9)]
        self.conn.close()
        
        self.r = [l[0] for l in sign_data]
        self.s = [l[1] for l in sign_data]
        return self.r, self.s
    
io = IO()
io.io()
io.r, io.s, io.cp, io.R

import ecdsa

def ecdsa2sage(curve):
    """
    convert an ecdsa curve to sagemath curve
    e.g.: ecdsa2sage(ecdsa.NIST256p)
    """
    a, b, p = curve.curve.a(), curve.curve.b(), curve.curve.p()
    E = EllipticCurve(GF(p),[a,b])
    Gx, Gy = curve.generator.x(), curve.generator.y()
    G = E(Gx, Gy)
    return E, G

E, G = ecdsa2sage(ecdsa.NIST256p)

class RecoveryEcdsaPublicKey:
    """
    recovery ecdsa public key from signature and hash
    E: ecc
    G: curve generatpr
    usage: Q = RecoveryEcdsaPublicKey(E, G).recovery_and_verify(h0, r0, s0, h1, r1, s1)
    """
    def __init__(self, E, G):
        self.E = E
        self.G = G
        self.n = E.order()
        self.Q = []

    def recovery(self, h:int, r:int, s:int) -> list:
        """
        return: public key
                there will be at most 2 public keys;
                if the signature is wrong, an empty list will be returned
        """
        h, r, s = map(ZZ, (h, r, s))
        Rs = E.lift_x(ZZ(r), all=True)
        self.Q = [inverse_mod(r, self.n)*(s*R-h*G) for R in Rs] 
        return self.Q

    def verify(self, Q, h:int, r:int, s:int) -> bool:
        """
        r, s: a different group of signature to verify public key
        return: whether the Q is a correct public key
        """
        h, r, s = map(ZZ, (h, r, s))
        u1 = h*inverse_mod(s, self.n)
        u2 = r*inverse_mod(s, self.n)
        R = u1 * G + u2 * Q
        return R[0] == r
    
    def recovery_and_verify(self, h0:int, r0:int, s0:int, h1:int=None, r1:int=None, s1:int=None) -> list:
        """
        h0, r0, s0: first group signature, to calculate public keys
        h1, r1, s1: first group signature, to filter correct public key by verify signature
        return: at most 1 public keys if h1,r1,s1 provided 
        """
        self.recovery(h0, r0, s0)
        if None not in [h1,r1,s1]:
            self.Q = [Q for Q in self.Q if self.verify(Q, h1, r1, s1)]
        return self.Q
    
    @classmethod
    def example(cls):
        import ecdsa, secrets, hashlib
        
        # sign
        _private_key = ecdsa.SigningKey.generate(curve=ecdsa.NIST256p)
        _public_key = _private_key.get_verifying_key()
        _h = int(hashlib.sha256(b'msg').hexdigest(), 16)
        _r0, _s0 = _private_key.sign_number(_h)
        _r1, _s1 = _private_key.sign_number(_h)

        # recovery
        _E = EllipticCurve(GF(ecdsa.NIST256p.curve.p()), [ecdsa.NIST256p.curve.a(), ecdsa.NIST256p.curve.b()])
        _G = _E(ecdsa.NIST256p.generator.x(), ecdsa.NIST256p.generator.y())
        _R = RecoveryEcdsaPublicKey(_E, _G)
        _Q = _R.recovery_and_verify(_h, _r0, _s0, _h, _r1, _s1)
        
        assert _Q[0][0] == ZZ(_public_key.pubkey.point.x()) and _Q[0][1] == ZZ(_public_key.pubkey.point.y())
        
RecoveryEcdsaPublicKey.example()

import hmac
import secrets

_hash = lambda k: int(hmac.new(k, b'msg', "sha224").hexdigest(), 16)

class BaseSolver():
    """
    recovery: public key, h
    generate symbols: d, k
    """
    def __init__(self, r:list, s:list, bits:int=226, N:int=9):
        """
        r, s: signature list
        bits: bound of k
        N:    the number of groups
        """
        self.r = [ZZ(i) for i in r]
        self.s = [ZZ(i) for i in s]
        self.bits = bits
        self.N = N
        
        self.n = E.order()
        
        self.h = []
        self.Q = None
        
        self.PR = None
        self.d = None
        self.k = None
        
        self.eq = []

    def recovery_pub(self):
        R = RecoveryEcdsaPublicKey(E, G)
        h0 = _hash(b'\x00')
        Qs = R.recovery(h0, self.r[0], self.s[0])
        self.Q = [Q for Q in Qs if R.verify(Q, _hash(int_to_bytes(Q[0])), self.r[1], self.s[1])][0]

    def recovery_h(self):
        self.h = [_hash(int_to_bytes(ZZ(self.Q[0])*i)) for i in range(self.N)]

    def gen_syms(self):
        syms = ["d"] + [f"k{i}" for i in range(self.N)]
        self.PR = PolynomialRing(GF(self.n), syms)
        self.d, *(self.k) = self.PR.gens()

    def gen_eq(self):
        """
        s*k - (h+d*r) = 0
        """
        self.eq = [self.s[i]*self.k[i] - (self.h[i]+self.d*self.r[i])  for i in range(self.N)]
        
    def base(self):
        self.recovery_pub()
        self.recovery_h()
        self.gen_syms()
        self.gen_eq()
        
class BaseTester:
    def __init__(self, bits:int=226, N:int=9):
        self.bits = bits
        self.N = N
        
        self.private_key = ecdsa.SigningKey.generate(curve=ecdsa.NIST256p)
        self.public_key = self.private_key.get_verifying_key()
        self.d = self.private_key.privkey.secret_multiplier
        self.signs()
        self.solver = BaseSolver(self.r, self.s, bits, N)

    def sign(self, i):
        h = int(hmac.new(int_to_bytes(self.public_key.pubkey.point.x() * i), b'msg', "sha224").hexdigest(), 16)
        k = secrets.randbelow(2 ** 224 - 1) + 1 + 2**224 + int(hmac.new(int_to_bytes(self.private_key.privkey.secret_multiplier) , b"msg", "sha224").hexdigest(), 16) % (ecdsa.NIST256p.generator.order()-2**224)
        r, s = self.private_key.sign_number(h, k=k)
        return r, s, h, k
    
    def signs(self):
        data = [self.sign(i) for i in range(self.N)]
        self.r, self.s, self.h, self.k = map(lambda i: [l[i] for l in data], range(4))

    def test_recovery_pub(self):
        self.solver.recovery_pub()
        assert self.solver.Q[0] == ZZ(self.public_key.pubkey.point.x())
        assert self.solver.Q[1] == ZZ(self.public_key.pubkey.point.y())

    def test_recovery_h(self):
        self.solver.recovery_h()
        assert self.solver.h == self.h
    
    def test_gen_syms(self):
        self.solver.gen_syms()
        assert str(self.solver.d) == "d"
        assert str(self.solver.k) == "[" + ", ".join([f"k{i}" for i in range(self.N)]) + "]"

    def test_gen_eq(self):
        self.solver.gen_eq()
        assert len(self.solver.eq) == self.N
        # k0, d, 1
        monomials = self.solver.eq[0].monomials()
        assert self.solver.d in monomials and self.solver.k[0] in monomials and self.solver.k[1] not in monomials
        for eq in self.solver.eq:
            assert eq(self.d, *(self.k)) == 0
        
    def test(self):
        self.test_recovery_pub()
        self.test_recovery_h()
        self.test_gen_syms()
        self.test_gen_eq()

BaseTester().test()

class Solver1_small_k(BaseSolver):
    """
    small k; with d in the lattice
    """
    def __init__(self, r, s, bits:int=226, N:int=9):
        super().__init__(r, s, bits, N)
        self.base()
        self.eq_resultant = []
        self.L = None
        self.bound = []
        self.T = None
        # self.LLL = self.LLL_enumeration
    
    def resultant(self):
        """
        represent ki by d
        """
        I = Ideal(self.eq)
        t = TermOrder('wdegrevlex', tuple([1] + list(range(self.N+1, 1, -1))))
        I = I.change_ring(self.PR.change_ring(order=t))
        b = I.groebner_basis()
        self.eq_resultant = [eq.monomials()[0] - eq for eq in b]
        
    def lattice(self):
        A = matrix([ZZ(i.coefficients()[0]) for i in self.eq_resultant])
        B = matrix([ZZ(i.constant_coefficient()) for i in self.eq_resultant])
        self.L = block_matrix([
            [ZZ(self.n), 0], 
            [A.stack(B), 1]
        ])
        
    def balance(self):
        self.bound = [2**self.bits]*len(self.eq_resultant) + [2**256, 1]
        self.T = diagonal_matrix([max(self.bound) // i for i in self.bound])
    
    def check(self, v):
        if abs(v[-1]) == 1:
            v*=v[-1]
            secret = v[-2] % self.n
            if self.Q == G*secret:
                print("d = ",secret)
                return secret
                
    def LLL(self):
        B = (self.L*self.T).LLL()/self.T
        for v in B:
            secret = self.check(v)
            if secret is not None:
                return secret      

    def LLL_enumeration(self):
        from tqdm.auto import tqdm
        
        def tqdm_storage(t):
            if hasattr(t, 'container') and t.leave:
                display(t.container)
        
        """
        extend search scope
        """
        from fpylll import IntegerMatrix, LLL
        from fpylll.fplll.gso import MatGSO
        from fpylll.fplll.enumeration import Enumeration, EvaluatorStrategy
        
        A = IntegerMatrix.from_matrix(self.L*self.T)
        LLL.reduction(A)
        M = MatGSO(A)
        M.update_gso()
        size = self.L.nrows()
        sol_cnt = 10000
        enum = Enumeration(M, sol_cnt, strategy=EvaluatorStrategy.BEST_N_SOLUTIONS)
        answers = enum.enumerate(0, size, (size * max(self.bound)**2), 0, pruning=None)
        
        with tqdm(answers) as t:
            d = None
            for _, a in t:
                v = IntegerMatrix.from_iterable(1, size, map(int, a))
                B = v*A
                B = matrix(B)[0]/self.T
                secret = self.check(B)
                if secret is not None:
                    d = secret
                    break
            tqdm_storage(t)
        return d
            
    def solve(self):
        self.resultant()
        self.lattice()
        self.balance()
        return self.LLL()
        
class Tester1(BaseTester):
    def __init__(self, bits:int=226, N:int=9):
        super().__init__(bits, N)
        self.solver = Solver1_small_k(self.r, self.s, bits, N)
    
    def test_resultant(self):
        self.solver.resultant()
        assert len(self.solver.eq_resultant) == self.N
        assert self.solver.eq_resultant[0].monomials() == [self.solver.d, 1]
        for i in range(len(self.solver.eq_resultant)):
            assert self.solver.eq_resultant[i](d=self.d) == ZZ(self.k[i])
        
    def test_lattice(self):
        self.solver.lattice()
        
    def test_balance(self):
        self.solver.balance()
        assert min(self.solver.bound) > 0
        L = self.solver.L * self.solver.T
        print("lattice rows:", L.nrows())
        print("lattice determinant:", L.determinant().nbits())

    def test_LLL(self):
        d = self.solver.LLL()
        assert d == self.d
    
    def test(self):
        self.test_resultant()
        self.test_lattice()
        self.test_balance()
        self.test_LLL()
        
Tester1().test()

d = Solver1_small_k(io.r, io.s).solve()

class Solver2_small_k_resultant_d(Solver1_small_k):
    """
    small k; eliminate d
    """
    def __init__(self, r, s, bits:int=226, N:int=9):
        super().__init__(r, s, bits, N)

    def resultant(self):
        """
        eliminate d
        """
        eq = [self.eq[-1].sylvester_matrix(self.eq[i], self.d).determinant() for i in range(len(self.eq)-1)]
        I = Ideal(eq).groebner_basis()
        self.eq_resultant = [i.monomials()[0]-i for i in I]
    
    def balance(self):
        self.bound = [2**self.bits]*(len(self.eq_resultant)+1) + [1]
        self.T = diagonal_matrix([max(self.bound) // i for i in self.bound])

    def check(self, v):
        if abs(v[-1]) == 1:
            v*=v[-1]
            secret = ZZ(self.eq[0](k0=ZZ(v[0])).univariate_polynomial().roots()[0][0])
            if self.Q == G*secret:
                print("d =",secret)
                return secret

class Tester2(Tester1):
    def __init__(self, bits:int=226, N:int=9):
        super().__init__(bits, N)
        self.solver = Solver2_small_k_resultant_d(self.r, self.s, bits, N)   
        
    def test_resultant(self):
        self.solver.resultant()
        assert len(self.solver.eq_resultant) == self.N - 1
        assert self.solver.eq_resultant[0].monomials() == [self.solver.k[-1], 1]
        for eq in self.solver.eq:
            assert eq(self.d, *(self.k)) == 0

Tester2().test()

d = Solver2_small_k_resultant_d(io.r, io.s).solve()

class Solver3_k_with_unknown_prefix(Solver1_small_k):
    """
    k with unknown preifx
    """
    def __init__(self, r, s, bits:int=224, N:int=9):
        super().__init__(r, s, bits, N)
        self.LLL = self.LLL_enumeration
        
    def resultant(self):
        """
        represent ki by d;
        ki -= k8
        """
        super().resultant()
        self.eq_resultant = [eq - self.eq_resultant[-1] for eq in self.eq_resultant[:-1]]

class Tester3(Tester1):
    def __init__(self, bits:int=224, N:int=9):
        super().__init__(bits, N)
        self.solver = Solver3_k_with_unknown_prefix(self.r, self.s, bits, N)
        
    def test_resultant(self):
        self.solver.resultant()
        assert len(self.solver.eq_resultant) == self.N - 1
        assert self.solver.eq_resultant[0].monomials() == [self.solver.d, 1]
        for eq in self.solver.eq:
            assert eq(self.d, *(self.k)) == 0

Tester3().test()

d = Solver3_k_with_unknown_prefix(io.r, io.s).solve()

class Solver4_k_with_unknown_prefix_eliminate_d(Solver1_small_k):
    """
    k with unknown preifx, eliminate d
    """
    def __init__(self, r, s, bits:int=224, N:int=9):
        super().__init__(r, s, bits, N)
        self.LLL = self.LLL_enumeration
        # ki - k8
        self.eq_difference = []
        
    def resultant(self):
        """
        represent by d;
        ki -= k8
        eliminate d;
        """
        # represent by d
        super().resultant()
        # ki -= k8
        eq = [self.eq_resultant[i] - self.eq_resultant[-1] - self.k[i] for i in range(len(self.eq_resultant)-1)]
        self.eq_difference = eq
        # eliminate d
        eq = [eq[-1].sylvester_matrix(eq[i], self.d).determinant() for i in range(len(eq)-1)]
        I = Ideal(eq).groebner_basis()
        self.eq_resultant = [i.monomials()[0]-i for i in I]

    def balance(self):
        self.bound = [2**self.bits]*(len(self.eq_resultant)+1) + [1]
        self.T = diagonal_matrix([max(self.bound) // i for i in self.bound])        
        
    def check(self, v):
        if abs(v[-1]) == 1:
            v*=v[-1]
            secret = ZZ(self.eq_difference[0](k0=ZZ(v[0])).univariate_polynomial().roots()[0][0])
            if self.Q == G*secret:
                print("d =",secret)
                return secret

class Tester4(Tester1):
    def __init__(self, bits:int=224, N:int=9):
        super().__init__(bits, N)
        self.solver = Solver4_k_with_unknown_prefix_eliminate_d(self.r, self.s, bits, N)
        
    def test_resultant(self):
        self.solver.resultant()
        assert len(self.solver.eq_resultant) == self.N - 2
        assert self.solver.eq_resultant[0].monomials() == [self.solver.k[-2], 1]
        for eq in self.solver.eq:
            assert eq(self.d, *(self.k)) == 0

Tester4().test()

Solver4_k_with_unknown_prefix_eliminate_d(io.r, io.s).solve()

from cryptography.hazmat.primitives.kdf.kbkdf import (
   CounterLocation, KBKDFHMAC, Mode
)
from cryptography.hazmat.primitives import hashes
from Crypto.Cipher import ChaCha20_Poly1305

def get_flag(secret, R, cp):
    def derive_symkey(inp:bytes):
        kdf = KBKDFHMAC(
            algorithm=hashes.SHA3_256(),
            mode=Mode.CounterMode,
            length=int(32),
            rlen=int(4),
            llen=int(4),
            location=CounterLocation.BeforeFixed,
            label=b"safu",
            context=b"funds are safu",
            fixed=None,
        )
        return kdf.derive(inp)

    def decrypt_sym(input_bytes: bytes, key:bytes):
        cipher = ChaCha20_Poly1305.new(key=key, nonce=cp[-12:])
        plaintext = cipher.decrypt_and_verify(input_bytes, cp[-28:-12])
        return plaintext

    
    R = ecdsa.NIST256p.generator.from_bytes(ecdsa.NIST256p.curve, R)
    S = R*secret
    key = derive_symkey(int_to_bytes(int(S.x())))
    flag = decrypt_sym(cp[:-28], key)
    return flag

get_flag(d, io.R, io.cp)