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

1 | import hashlib |

### Lattice Solver and Optimization

The signature nonce generation of ECDSA is in this form (),

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:

For the equation, , an affine equation over , where and are both less than and , one can construct a simple lattice to recover the private key :

The lattice contains the short vector . The , the , and the , calculate the corresponding Gaussian heuristic,

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 to , resulting in a success rate of 76.2%.
- Brute forcing: Attempting to enumerate some of the most significant bits of 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

1 | from hashlib import sha256 |

## e2D1p

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

**293 pt, 12 solves**

### Source Code

1 | from Crypto.Util.number import * |

### Recovering Modulus

Yet another challenge similar to n1ctf 2022 ezdlp. We are given 200 samples :

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 represents the i-th bit of .

Therefore, convert all masks into bit vectors to construct a matrix where . First, compute the left null space and then process the LLL reduction (which can be directly calculated in an extended lattice).

This will yield a series of small exponents 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):

This results in . 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 for the following target vectors separately, i.e., we find the vector $E_i \in \mathbb{Z}^{1\times 200}$ that satisfies:

This means by using such a combination () of the masks and ciphertexts, we can ensure that the final mask only affects one bit in . Since the extra relation , the final result is something in this format . Then we can determine the flag bit by the result of .

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 :

The solutions to and are all derived from the solutions of in the rational number field, and then converted to integer ring. For implementation details, please refer to the exploit code.

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

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

1 | def int2zzvector(num, padlen = 159): |

Recovering flag bit by bit :

1 | import random |

## 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 . 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 :

Rounds after dance time :

Suppose the dance time is set at 32-rd and 31-st rounds for two identical plaintexts that are encrypted into ciphers denoted as and . 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 and . 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 and through the inverse process of `pfunc`

to obtain and . If the last round key () chosen by us is correct, then the resulting ciphertexts and should be identical due to the prior 30 rounds of encryption being completely identical.

After recovering round key , we can recover the round 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 , 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.

1 | $ time ./main |

The intended solution uses the DFA attack to recover the round keys since the four bytes are independent with time complexity . 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 .