Chill

Platform: volgactf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-28 | Status: Solved Techniques: dsa_close_nonce_attack, modular_arithmetic_brute_force, signature_equation_manipulation

Summary

Task: DSA scheme where private key x = flag, two signatures with nonces differing by at most 2^22. Solution: close nonce attack — derive linear equation in x with small unknown delta, brute-force ~4M delta values checking for VolgaCTF{} prefix.

Chill — VolgaCTF 2026

Description

"This key is very important for me. Can you recover it?"

Two files provided: main.sage (SageMath source implementing a DSA signature scheme) and output (DSA parameters and two signatures). The private key x is the flag encoded as a big-endian integer. Two messages (message1, message2) are signed with nonces k1 and k2 where the difference k2 - k1 is bounded by 2^22 (~4 million).

Analysis

DSA Setup

The challenge generates standard DSA parameters:

• Q: 312-bit prime (order of the subgroup)
• P: i * Q + 1 (safe prime construction)
• G: generator of order Q in Z_P*
• X: private key = int.from_bytes(FLAG, 'big')
• Y: public key = G^X mod P ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Critical Vulnerability: Weak Nonce Generator

 python read-only • copy allowed Copy
K = IntegerModRing(2 ^ 22)  # Only 22-bit range!

def get_nonce(q_ring):
    seed = q_ring.random_element()  # Random initial nonce
    while True:
        yield seed
        seed += q_ring(K.random_element())  # Increment by at most 2^22 - 1

The nonce generator starts with a random seed but only adds a value from IntegerModRing(2^22) between consecutive nonces. This means delta = k2 - k1 is in the range [0, 2^22), which is astronomically small compared to the 312-bit modulus Q. This is a textbook DSA close nonce vulnerability. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Both Signatures Succeed on Try #1

The output shows both signatures succeed immediately (no retry loops), confirming exactly one nonce was consumed per signature and k2 = k1 + delta with a single small delta.

Solution

Step 1: Derive Linear Equation in x

From the DSA signature equations:

• s1 ≡ k1^(-1) * (m1 + x * r1) (mod q) → k1 ≡ s1^(-1) * (m1 + x * r1) (mod q)
• s2 ≡ k2^(-1) * (m2 + x * r2) (mod q) → k2 ≡ s2^(-1) * (m2 + x * r2) (mod q)

Subtracting:

k2 - k1 = s2^(-1) * (m2 + x * r2) - s1^(-1) * (m1 + x * r1) ≡ delta (mod q)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Rearranging into A * x + B ≡ delta (mod q):

• A = s2^(-1) * r2 - s1^(-1) * r1 (mod q)
• B = s2^(-1) * m2 - s1^(-1) * m1 (mod q)

Solving for x:

x ≡ A^(-1) * (delta - B) (mod q)

Step 2: Brute-Force delta

Since delta ∈ [0, 2^22), we iterate all ~4.2M values. For each candidate:

1. Compute x_candidate = A^(-1) * (delta - B) mod q
2. Convert to bytes (big-endian)
3. Check if it starts with VolgaCTF{ and ends with }
4. Verify all characters are printable ASCII

Step 3: Optimization

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Precompute x_base = A^(-1) * (-B) mod q and a_inv = A^(-1) mod q, then for each delta:

x(delta) = (x_base + a_inv * delta) mod q

This avoids repeated modular inversions.

Solve Script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
DSA Close Nonce Attack - VolgaCTF "Chill"
k2 - k1 = delta where delta in [0, 2^22)
Brute force delta to recover private key x (the flag)
"""

# Parameters from output
Q = 89521645379584079318742987065681909118957188675394514087242744492602619437714037904131497
P = 1253303035314177110462401818919546727665400641455523197221398422896436672127996530657840959
G = 16384
Y = 127823237045158941730582625621563445929666483248554273743152824494654034455894014975905739
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Signatures
m1 = int.from_bytes(b"message1", "big")
m2 = int.from_bytes(b"message2", "big")

r1 = 47254699426491632965610101269949346494600453771942521995969444555961312439323724548912243
s1 = 49142914699862956549460868259654421292081533671592879185559431485772306799882250976012338

r2 = 62227259830059173165227946717241712337748536991513854581206003064841303072057613486312098
s2 = 58758044816295328671788186997059606359309411177433667660426922567672962397685369980265501

# Compute A, B for: A * x + B = delta (mod q)
s1_inv = pow(s1, -1, Q)
s2_inv = pow(s2, -1, Q)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

A = (s2_inv * r2 - s1_inv * r1) % Q
B = (s2_inv * m2 - s1_inv * m1) % Q
A_inv = pow(A, -1, Q)

# Precompute: x(delta) = (x_base + A_inv * delta) mod Q
x_base = (A_inv * (-B % Q)) % Q
a_inv_int = A_inv

prefix = b"VolgaCTF{"
suffix = b"}"

for delta in range(2**22):
    x_candidate = (x_base + a_inv_int * delta) % Q

    byte_len = (x_candidate.bit_length() + 7) // 8
    if byte_len < 9:
        continue

    try:
        x_bytes = x_candidate.to_bytes(byte_len, "big")
    except (OverflowError, ValueError):
        continue
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    if x_bytes[:9] == prefix and x_bytes[-1:] == suffix:
        try:
            flag = x_bytes.decode("ascii")
            if all(32 <= ord(c) < 127 for c in flag):
                print(f"FOUND! delta = {delta}")
                print(f"x = {x_candidate}")
                print(f"FLAG: {flag}")
                break
        except UnicodeDecodeError:
            pass
# Found at delta = 3517569
# FLAG: VolgaCTF{REDACTED}

Verification

Y = G^x mod P = 16384^x mod P
  = 127823237045158941730582625621563445929666483248554273743152824494654034455894014975905739 ✓

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍