2023 N1CTF Crypto Writeups

2023-10-23

字数统计: 2.7k字 | 阅读时长≈ 16分

NeSE got the first place. Here are the detailed writeups for three crypto challenges solved by me.

e2W@rmup

Welcome 2 N1CTF2023! （＾ω＾）

80 pt , 49 solves

Source code

import hashlib
import ecdsa
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from secret import flag

def gen():
    curve = ecdsa.NIST256p.generator
    order = curve.order()
    d = randint(1, order-1)
    while d.bit_length() != 256:
        d = randint(1, order-1)
    pubkey = ecdsa.ecdsa.Public_key(curve, curve * d)
    privkey = ecdsa.ecdsa.Private_key(pubkey, d)
    return pubkey, privkey, d

def nonce_gen(msg, d):
    msg_bin = bin(msg)[2:].zfill(256)
    d_bin = bin(d)[2:].zfill(256)
    nonce = int(msg_bin[:128] + d_bin[:128], 2)
    return nonce

def sign(msg, privkey, d):
    msg_hash = bytes_to_long(hashlib.sha256(msg).digest())
    nonce = nonce_gen(msg_hash, d)
    sig = privkey.sign(msg_hash, nonce)
    s, r = sig.s, sig.r
    return s, r

pk, sk, d = gen()
msg = b'welcome to n1ctf2023!'
s, r = sign(msg, sk, d)
print(f's = {s}')
print(f'r = {r}')

m = pad(flag, 16)
aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
cipher = aes.encrypt(m)
print(f'cipher = {cipher}')

"""
s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
"""

Lattice Solver and Optimization

The signature nonce generation of ECDSA is in this form ( $\ell = 128$ ),

$k = 2^{\ell}h_{msb} + d_{msb}$

This form of nonce generation originates from a backdoor in Bitcoin ECDSA signatures for private key theft. For more details, one may refer to this paper: The Curious Case of Half-Half Bitcoin ECDSA Nonces.

The equation for the signature is only related to the private key d:

$s = k^{-1} (h + dr) \mod n \\ \iff s(2^{\ell}h_{msb} + d_{msb}) = h + ( 2^{\ell}d_{msb} + d_{lsb})r \mod n \\ \iff r^{-1}s(2^{\ell}h_{msb} + d_{msb}) - h r^{-1} = 2^{\ell} d_{msb} + d_{lsb} \mod n \\ \implies \underbrace{\left(2^{\ell}-s r^{-1}\right)}_A d_{\mathrm{msb}}+d_{\mathrm{lsb}}+\underbrace{\left(h-2^{\ell} s h_{\mathrm{msb}}\right) r^{-1}}_b=0 \bmod n$

For the equation, $A \cdot d_{msb} + d_{lsb} + b = 0 \mod n$ , an affine equation over $\mathbb{Z}_n$ , where $d_{msb}$ and $d_{lsb}$ are both less than $2^{\ell} = 2^{128}$ and $n \approx 2^{256}$ , one can construct a simple lattice to recover the private key :

$B=\left[\begin{array}{lll} n & 0 & 0 \\ A & 1 & 0 \\ b & 0 & 2^{\ell} \end{array}\right]$

The lattice $L(B)$ contains the short vector $v_t=\left(-d_{\mathrm{lsb}}, d_{\mathrm{msb}}, 2^{\ell}\right)$ . The $\operatorname{det} L(B)=\operatorname{det} B=n 2^{\ell}$ , the $\operatorname{dim} L=3$ , and the $\left|v_t\right|_2 \leq \sqrt{3} \cdot 2^{\ell}$ , calculate the corresponding Gaussian heuristic,

$\begin{aligned} \operatorname{gh}(L(B)) & \approx \sqrt{\operatorname{dim} L /(2 \pi e)} \operatorname{det} L(B)^{1 / \operatorname{dim} L} \\ & = \sqrt{3 /(2 \pi e)} (n \cdot 2^{\ell})^{1/3} \\ & \approx \sqrt{3 /(2 \pi e)} 2^l < \sqrt{3} \cdot 2^{\ell} \end{aligned}$

Therefore, the aforementioned lattice may not necessarily yield a solution using the general LLL algorithm (with a success rate of 27.1%).

A series of optimization methods mentioned in paper include:

Recentering: Recentering the positive range $[0, 2^l]$ to $[ -2^{l-1},2^{l-1} ]$ , resulting in a success rate of 76.2%.
Brute forcing: Attempting to enumerate some of the most significant bits of $d_{msb}, d_{lsb}$ and then constructing a lattice is equivalent to reducing the magnitude of the target vector. The success rate of a four-bit brute force combined with recentering reaches 99.6%.
Sieving with predicate: The success rate of Sieving with a predicate in combination with Recentering is 99.99%.

Here, I directly applied the Recentering optimization and recovered the private key successfully. We can also attempt to solve the Closest Vector Problem (CVP) to approximate our target solution which might be a better way to derive the private key.

Exp

Exploit in sagemath 9.5

from hashlib import sha256
import ecdsa
from Crypto.Util.number import *
from Crypto.Cipher import AES

def hhecdsa_to_lattice(msg, sig, recentering = True):
    h = int(sha256(msg).hexdigest(),16)
    hmsb = h >> 128
    curve = ecdsa.NIST256p.generator
    n = curve.order()
    r,s = sig
    A = (2**128 - s * int(inverse_mod(r,n))) % n
    b = (h - 2**128 * s * hmsb) * int(inverse_mod(r,n)) % n
    L = 2**128
    if recentering:
        b = (b + (A + 1) * 2**127) % n
        L = 2**127
    M = [
        [n, 0, 0],
        [A, 1, 0],
        [b, 0, L]
    ]
    return matrix(ZZ, M)

def parse_possible_solutions(L):
    sols = []
    for row in L:
        if row[-1] == 2**127:
            # print("case 1")
            dlsb =  int(-row[0] + 2**127)
            dmsb =  int(row[1] + 2**127)
            d = (dmsb << 128) + dlsb
            sols.append(d)
        elif row[-1] == -2**127:
            # print("case 2")
            dlsb =  int(2**127 - row[0])
            dmsb =  int(2**127 - row[1])
            d = (dmsb << 128) + dlsb
            sols.append(d)
    return sols

s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
msg = b'welcome to n1ctf2023!'

sig = (r,s)
M = hhecdsa_to_lattice(msg, sig, True)
# L = M.LLL()
L = M.BKZ(block_size = 25)
# for row in L:
#     print(row)
ds = parse_possible_solutions(L)

d = ds[0]
aes = AES.new(long_to_bytes(int(d)), mode=AES.MODE_ECB)
pt = aes.decrypt(cipher)
print(f'pt = {pt}')

e2D1p

Based on N1CTF 2022 “ezdlp”. Easy dlp too, try again : ) .

293 pt, 12 solves

Source Code

from Crypto.Util.number import *
import os
FLAG = os.environ.get('FLAG', b'n1ctf{XXXXFAKE_FLAGXXXX}')
assert FLAG[:6] == b'n1ctf{' and FLAG[-1:] == b'}'
FLAG = FLAG[6:-1]


def keygen(nbits):
    while True:
        q = getPrime(nbits)
        if isPrime(2*q+1):
            if pow(0x10001, q, 2*q+1) == 1:
                return 2*q+1

def encrypt(key, message, mask):
    return pow(0x10001, message^mask, key)


p = keygen(512)
flag = bytes_to_long(FLAG)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

print(f'message = {messages}')
print(f'enc = {enc}')

Recovering Modulus

Yet another challenge similar to n1ctf 2022 ezdlp. We are given 200 samples $ms = [m_1,\cdots ,m_{200}], cs = [c_1, \cdots, c_{200}]$ :

$c_i = 0x10001^{s \oplus m_i} \mod p$

where $p,s$ are unknown and $s$ is the flag we want.

The basic approach is similar to that of n1ctf last year. At this point, we consider the impact of the XORing mask on the final result, considering it bit by bit where $m^{\{i\}}$ represents the i-th bit of $m$ .

$\begin{aligned} c & = 0x10001^{s \oplus m} \\ &= 0x10001^{s + \sum_{i =0}^{159} m^{\{i\}} (-1)^{s^{\{i\}}} 2^i} \end{aligned}$

Therefore, convert all masks into bit vectors to construct a matrix $M \in \mathbb{Z}^{200 \times 159}$ where $M[i] = ( m^{\{0\}}_i, \cdots , m^{\{159\}}_i)$ . First, compute the left null space and then process the LLL reduction (which can be directly calculated in an extended lattice).

$B = \begin{bmatrix} 2^{256}M & || &I_{200} \end{bmatrix} \\ \implies L = \mathcal{LLL}(B)$

This will yield a series of small exponents $e_i$ that satisfy the following equations (the first equation has already been explicitly included in matrix M since the 159-th bit of all $m_i$ is 1):

$\sum_{1}^{200} e_i = 0, \\ \sum_{1}^{200} e_i \cdot M[i] = \vec 0$

This results in $\prod c_i^{e_i} = 0 \mod p$ . The negative exponents (taking absolute values) and positive exponents are calculated as left value and right value respectively. By subtracting these two, we can obtain an integer multiple of p. Through multiple sets of data, we can compute the GCD to recover $p$.

Recovering Flag Bit

After recovering the modulus p, we consider the solutions of matrix $M$ for the following target vectors separately, i.e., we find the vector $E_i \in \mathbb{Z}^{1\times 200}$ that satisfies:

$E_0 \cdot M = (1,0,\cdots,0) \\ E_1 \cdot M = (0,1,\cdots,0) \\ \cdots \\ E_{159} \cdot M = (0,0,\cdots,1) \\ \tag{EQ1}$

This means by using such a combination ( $E_i$ ) of the masks and ciphertexts, we can ensure that the final mask only affects one bit in $\prod_{e_j \in E_i} c_j^{e_j} \mod p$ . Since the extra relation $\sum_{e_j \in E_i} e_j = 0$ , the final result is something in this format $(0x10001)^{2^i} (-1)^{s_i}$ . Then we can determine the flag bit $s^{\{i\}}$ by the result of $\prod_{e_j \in E_i} c_j^{e_j} \mod p$ .

However, the above equation is unlikely to have a solution in the ring of integers. Settle for second best, we can find a solution set in the field of rational numbers (QQ), and then convert it to the ring of integers. The equations in the integer ring are :

$E_0 \cdot M = (n_0,0,\cdots,0) \\ E_1 \cdot M = (0,n_1,\cdots,0) \\ \cdots \\ E_{159} \cdot M = (0,0,\cdots,n_{159}) \\ \tag{EQ2}$

The solutions $E_1,E_2,\cdots, E_{159}$ to $\text{EQ2}$ and $n_1, n_2, \cdots, n_{159}$ are all derived from the solutions of $\text{EQ1}$ in the rational number field, and then converted to integer ring. For implementation details, please refer to the exploit code.

Let $E_i = (e_1, ..., e_{200})$ . Adding the constraint of $\sum_{1}^{200} e_j = 0$ ensures that for each $E_i$ , the following equation holds :

$\prod_j c^{e_j} = (0x10001)^{n_i * 2^i} (-1)^{s_i}\mod p$

In this way, you can determine the value of the flag bit by bit. (The highest bit of flag is already known, that is 1 since flag is 159-bit long in code).

Exp

Exploit in sagemath 9.5.

LLL & GCD Deriving modulus

def int2zzvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(ZZ, map(int,bitstr))

messages = [] # omit
enc = [] # omit
m_vecs = [int2zzvector(num) for num in messages]
M = matrix(ZZ, m_vecs)
M *=  2**256
sample_number = len(messages)
flag_len = 159

La = block_matrix(ZZ,[M,identity_matrix(sample_number)],ncols =2)
L = La.LLL()

kp = 0    
for row in L:
    if all([num ==  0 for num in row[:flag_len]]):
        print(row)
        expons = row[flag_len:]
        rv = 1
        lv = 1
        print(sum(expons) == 0)
        for i, expon in enumerate(expons):
            if expon > 0 :
                rv *= pow(enc[i], expon)
            else:
                lv *= pow(enc[i], -expon)
        kp = gcd(lv-rv, kp)
        # filter small factors
        kp =  factor(kp, limit = 2**20)[-1][0]
        if kp.nbits() <= 513 and is_prime(kp):
            print(kp)
            break

Recovering flag bit by bit :

import random
from tqdm import tqdm

def int2zzvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(ZZ, map(int,bitstr))

def int2bitvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(GF(2), map(int,bitstr))

def v2s(v, padlen = 159):
    ret = []
    for _ in range(padlen):
        if v & 1:
            ret.append(0)
        else:
            ret.append(1)
        v >>= 1
    return vector(ZZ, ret)

messages =  [] # omit
enc = [] # omit
p = 25070940894294854944213724808057610995878580501834029791436842569011975159898869595617649716256078890953233822913946718277574163417715224718477846001735447

sample_number = len(messages)
flag_len = 159

m_vecs = [int2zzvector(num) for num in messages]
base_power_vals = [ZZ(pow(0x10001, 2**i, p)) for i in range(flag_len)][::-1]
Zp = GF(p)

M = matrix(ZZ , m_vecs).T

# adding extra equation x1 + x2 + .. + x200 = 0
M = M.insert_row(0, [1]*sample_number)

# solve bit by bit , high bit is 1
flagbit = "1"
for i in tqdm(range(1, flag_len)):
    t = vector(ZZ, [0 for j in range(flag_len + 1)])
    t[i + 1] = 1
    sol = M.solve_right(t)
    # get integer solutions
    denoms = set()
    for y in sol:
        denoms.add(y.denom())
    max_denom = max(denoms)
    integer_sol = max_denom * sol
    integer_target = max_denom * t
    assert M * integer_sol == integer_target
    assert sum(integer_sol) == 0
    
    final_c = 1
    for idx, num in enumerate(integer_sol):
        final_c *= ZZ(pow(enc[idx], num, p))
        final_c %= p
    # print(integer_target)
    # print(ZZ(final_c))
    # print(ZZ(pow(base_power_vals[i], -max_denom, p)))
    if ZZ(final_c) == ZZ(pow(base_power_vals[i], max_denom, p)):
        flagbit += "0"
    else:
        assert (final_c * ZZ(pow(base_power_vals[i], max_denom, p))) % p ==  1
        flagbit += "1"
    
flag = int(flagbit,2).to_bytes(20,"big")
print(flag)

e2$m4

I hope to make sm4 random through new components, but when I get some characteristic of ciphertext, it seems to be very bad :( .

390 pt , 6 solves

Attachment

The challenge attachment : sm4-chall.zip.

Solution

Unexpected solution orz.

Brute-forcing the four round keys by the ciphertexts generated by different dance time. Each round key is 32 bits, and the practical complexity of recovering 4 round keys would be $2^{34}$ . The method to verify the correctness of the round keys is as follows.

The process for each round of encryption includes the following two steps:

tfunc : buf[i+4] = buf[i] ^ tfunc(buf[i+1]^buf[i+2]^buf[i+3]^rk[i]) , related to the round key, irrelevant to the dance time (dance box).
pfunc : buf[i+1:i+5] = pfunc(buf[i+1:i+5]) , related to the dance time (dance box), irrelevant to the round key which can be inversed directly without the round key.

Specifically, upon the execution of the dance function, Sbox within the pfunc are changed. Notably, there exist only two combinations of Sbox for pfunc. We accordingly denote these two Sbox combinations and their corresponding p-functions as pfunc1 and pfunc2.

Rounds before dance time $i < dt$ :

$c^i \stackrel{\text{tfunc},rk_i}{\longrightarrow} t \stackrel{\text{pfunc}_1}{\longrightarrow} c^{i+1}$

Rounds after dance time $i \ge dt$ :

$c^i \stackrel{\text{tfunc},rk_i}{\longrightarrow} t \stackrel{\text{pfunc}_2}{\longrightarrow} c^{i+1}$

Suppose the dance time is set at 32-rd and 31-st rounds for two identical plaintexts that are encrypted into ciphers denoted as $c_1$ and $c_2$ . The dance Sbox in the last round used in each case is the same. By exhaustively enumerating the round key for the last round and decrypting it for one round, we derive the possible ciphertexts after the 31 rounds of encryption, referred to as $c_1^{31}$ and $c_2^{31}$ . At this point, the dance box used in pfunc differs between the two. It’s crucial to note that pfunc is independent of the round key. Therefore, we proceed by passing $c_1^{31}$ and $c_2^{31}$ through the inverse process of pfunc to obtain $t_1 =\mathcal{pfunc_1}^{-1}(c_1^{31})$ and $t_2 =\mathcal{pfunc_2}^{-1}(c_1^{31})$ . If the last round key ( $rk_{32}$ ) chosen by us is correct, then the resulting ciphertexts $t_1$ and $t_2$ should be identical due to the prior 30 rounds of encryption being completely identical.

After recovering round key $rk_{32}$ , we can recover the round $rk_{31}$ by decrypting one round for ciphertexts with dance-round being 31,30 and do the same process to brute force round key.

Since the recent hitcon, where I laboriously ran an exhaustive enumeration with a complexity of $2^{32}$ , I’ve come to realize that implementing such an enumeration for all bit-operation encryption/hash in the C language is indeed efficient (a few minutes). My final exploit implemented in C costs 4 mins to recover the last 4 round keys using single-core.

$ time ./main
Brute force interval:  00000000 - ffffffff !
process : a7f80000 / ffffffff
round key = 0xa7f844bf
Brute force interval:  00000000 - ffffffff !
process : 592e0000 / ffffffff
round key = 0x592e60ac
Brute force interval:  00000000 - ffffffff !
process : 99bd0000 / ffffffff
round key = 0x99bd33bb
Brute force interval:  00000000 - ffffffff !
process : 9f2a0000 / ffffffff
round key = 0x9f2a616d
round keys: 0xa7f844bf 0x592e60ac 0x99bd33bb 0x9f2a616d

real    4m2.067s
user    4m2.027s
sys     0m0.030s

The intended solution uses the DFA attack to recover the round keys since the four bytes are independent with time complexity $O(256 * 4)$ . Here is the official writeup using DFA.

EXP

My exploit in C is modified from sm4.c : sm4-solver.zip.

End

Here is the official writeup repository : n1ctf-2023-crypto .