A good CTF challenge cooked by y011d4 in SECCON CTF 2024. I played with NeSE(Never Stop Exploiting) last weekend.

description

The code about the solution(server.py):

import os
import signal
from secrets import randbelow

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from ecdsa import SigningKey, SECP256k1
from gmpy2 import legendre

flag = os.getenvb(b"FLAG", b"SECCON{this_is_not_a_flag}")

menu = """
1. sign
2. get pubkey
3. encrypt flag
"""


class PRNG:
    """Legendre PRF is believed to be secure
    ex. https://link.springer.com/chapter/10.1007/0-387-34799-2_13
    """

    def __init__(self, initial_state: int, p: int) -> None:
        self._state = initial_state
        self.p = p

    def __call__(self, n_bit: int) -> int:
        out = 0
        for _ in range(n_bit):
            out <<= 1
            tmp = legendre(self._state, self.p)
            out |= (1 + tmp) // 2 if tmp != 0 else 1# -1 -> 0, (0,1) -> 1
            self._state += 1
            self._state %= self.p
        return out


if __name__ == "__main__":
    signal.alarm(600)

    p = int(input("Your favorite 256-bit prime (hex) > "), 16) 
    if p.bit_length() != 256:
        print("p must be 256-bit")
        exit()
    a = randbelow(p)
    prng = PRNG(a, p)

    sk = SigningKey.generate(curve=SECP256k1)
    vk = sk.get_verifying_key()
    assert vk is not None
    assert sk.privkey is not None
    d = sk.privkey.secret_multiplier

    print(menu)

    n_sign = 0
    while True:
        option = int(input("option > "))
        if option == 1:
            if n_sign >= 3333:
                print("Too many signs")
                exit()
            msg = bytes.fromhex(input("msg (hex) > "))
            k = prng(256)
            signature = sk.sign(msg, k=k)
            print(f"signature = {signature.hex()}")
            n_sign += 1
        elif option == 2:
            print(f"pubkey = {vk.to_string().hex()}")
        elif option == 3:
            # You can get the flag only if you break both of PRNG and ECDSA.
            key = (d ^ a).to_bytes(32, "big")
            enc = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16))
            print(f"enc = {enc.hex()}")
        else:
            exit()

Solution

We need to do these steps for the flag:

• Get from ’s property that we can control.
• Get from

Step 1. Recover d, k

The legendre symbol is implemented with a bug. If the module is not a prime , it’s an odd composite number(has some small factors). Then legendre(factor/module)=0.

With this bug, we can choose smooth composite number

Then we can get some good property. For example, when the incremented state number is a multiple of 3, the corresponding bit position of will become 1, so every 3 bits determines one bit position of . Similarly, when it’s a multiple of 5, every 5 bits determines one bit position to be 1, and we can derive many such properties in this way.

Based on the above properties, we can control and directly guess certain bit information of the generated 256-bit . If there are multiple consecutive bits fixed as 1, we can use the exact solving method of lattice basis reduction for solving HNP (Hidden Number Problem) to recover both and . In this problem, we are looking for the relative positions of determined by the product of four numbers: 3, 5, 7, and 11, while starts with 0b1111 and ends with 0b11(at first, I spent nearly 9 hours debugging with the 0b1111 prefix to get , and for some unknown reason, it wouldn’t work with an almost 80-dimensional lattice, even using BKZ-40. Later, my test cases passed, but when applied to the actual challenge, it still wouldn’t produce results).

According to HNP solving principles, with 6 known bits and a 256-bit modulus, we need approximately 43 (256/6) samples to solve for the corresponding and , allowing us to quickly obtain the result. During implementation, although the initial shift is unknown, the relative offset of (starting with 0b1111 and ending with 0b11) remains constant, so we only need to perform BKZ-32 1155 times. Here, we can use multiprocessing to improve speed. Through this method, we successfully solved for the corresponding and , and using , we could recover all sampled values.

Step 2. Recover a

Same property in legendre symbol.

We can get some hints from small factors: every 3 bits could reveal the value of , the same reason as Step 1.

Like this:

• : then is 1??1??1??1??1??1??…..
• : then is ?1??1??1??1??1??1?…..
• : then is ??1??1??1??1??1??1…..

If is a prod of small primes, we can get all the value of . So use CRT to recover

Finally, we can decrypt the encrypt_flag easily to get flag!