Signature

Signature

• Category: Crypto
• Score: 469/500
• Solves: 2/428

Description

Another boring crypto challenge about signatures.

Overview

This challenge signs 6 signatures using ECDSA on Secp256k1. The nonce $k$ is generated by xoring hash $z$ and private key $d$. The flag is encrypted with AES-CTR, key are derived from ECDSA private and IV are unknown.

Solution

This challenge is based on jonasnick/ecdsaPredictableNonce.

Need to use two basic facts:

• $a \oplus b = a + b - 2 (a \land b)$
• For two n bits integer $a,b$, $a \land b = \sum_{i=0}^{n-1} 2^i a_i b_i$, where $a_i$ and $b_i$ is their n-th bit.

So $k_i=d \oplus z_i$ can be written as $k_i=d+z_i-2 \sum_{j=0}^{n-1} d_i z_{ij}$. And it can be substituted back to $sk \equiv z+rd \pmod{n}$ to get a bunch of equations that have $d_i$ as their roots.

In Secp256k1, $d$ is a 256 bit number. So in the jonasnick/ecdsaPredictableNonce, you can collect 256 signatures and solve $d_i$ with linear algebra.

But it forgot an important fact: $0 \le d_i \le 1$. This problem can be transform into finding a short vector in lattice, and use LLL to solve it.

Details are in the solution script

After recovering $d$, we still need IV to decrypt the flag with AES-CTR. Notice there is a prefix Congrats! This is your flag: in the plaintext, we can take the first block and xor it with the first block of ciphertext, they decrypt it with the key. This is how AES-CTR works.

from fastecdsa.curve import secp256k1 as CURVE
from Crypto.Cipher import AES
from hashlib import sha256
from operator import xor
import ast

with open("output.txt") as f:
    sigs = []
    for _ in range(6):
        z, r, s = map(int, f.readline().strip().split())
        sigs.append((z, r, s))
    msgct = ast.literal_eval(f.readline())


def recover_d(sigs):
    P = PolynomialRing(Zmod(CURVE.q), "d", 256)
    ds = P.gens()
    dd = sum([2 ** i * di for i, di in enumerate(ds)])
    polys = []
    for z, r, s in sigs:
        d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di in enumerate(ds)])
        # fact: (a xor b) = a + b - 2 * (a and b)
        k = dd + z - 2 * d_and_z
        polys.append((s * k) - (z + r * dd))
    M, v = Sequence(polys).coefficient_matrix()
    print(v.T)
    M = M.T.dense_matrix()
    a, b = M.dimensions()
    B = block_matrix(
        ZZ, [[matrix.identity(b) * CURVE.q, matrix.zero(b, a)], [M, matrix.identity(a)]]
    )
    B[:, :b] *= 2 ^ 64
    print("LLL", B.dimensions())
    for row in B.LLL():
        if row[:b] == 0 and row[-1] == 1 and all(0 <= x <= 1 for x in row[b:-1]):
            dbits = row[b:-1]
            d = int("".join(map(str, dbits[::-1])), 2)
            return d


d = recover_d(sigs)
print(f"{d = }")
key = sha256(str(d).encode()).digest()[:16]
nonce = AES.new(key, AES.MODE_ECB).decrypt(
    bytes(map(xor, b"Congrats! This is your flag: "[:16], msgct[:16]))
)[:8]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(msgct))