From Dusk Till Dawn Finals - 2k26 - KKEEYYS

Challenge

from fastecdsa.curve import P256
from fastecdsa.point import Point
from fastecdsa.util import mod_sqrt
from hashlib import sha256
from typing import Tuple
import os

with open("flag.txt", "r") as f:
    FLAG = f.read().strip()

def hash_to_curve(data: bytes) -> int:
    # perdoname madre por my
    # not constant time hash-to-curve implementation
    h = sha256(data).digest()
    x = int.from_bytes(h, "big") % P256.p
    while True:
        y = mod_sqrt(P256.evaluate(x), P256.p)[0]
        if P256.is_point_on_curve((x, y)):
            return Point(x, y, curve=P256)
        x = (x + 1) % P256.p

def hash_to_scalar(data: bytes) -> int:
    h = sha256(data).digest()
    return int.from_bytes(h, "big") % P256.q

G = P256.G
O = 0 * G
B = [hash_to_curve(f"key_point_{i}".encode()) for i in range(256)]
Gr = hash_to_curve(b"blinding_generator")

def update_digest(digest: bytes, key: str) -> bytes:
    h = sha256()
    h.update(digest)
    h.update(key.encode())
    return h.digest()

def add_key(key: str, value: int, comm: Point, init=False) -> Point:
    assert 0 <= value < P256.q # PUOI MANDARE 0
    r = hash_to_scalar(f"blinding_{key}_{value}".encode())
    coeffs = [
        hash_to_scalar(f"{'init' if init else 'key'}_{key}_{i}".encode()) for i in range(256)
    ]
    points = [value * c * B[i] for i, c in enumerate(coeffs)]
    delta = sum(points, Gr * r)

    return comm + delta

def verify_signature(comm: Point, message: bytes, sig: Tuple[int, int]):
    (s, e) = sig
    assert 0 <= e < P256.q
    assert 0 <= s < P256.q
    r_v = s * Gr + e * comm 
    e_v = hash_to_scalar(message + (r_v.x).to_bytes(32, "big") + (r_v.y).to_bytes(32, "big"))

    return e_v == e

def main():
    print("Welcome to the Secure Key-Value Store!")
    print("You can add add objects to the store. But can you get the flag?")
    print("Commands:")
    print("1. Add key")
    print("2. gimme the flag")

    initial_key = os.urandom(16).hex()
    comm = add_key(initial_key, 1, O, init=True)
    execution_digest = update_digest(b"", initial_key)

    print(f"Your initial key is: {initial_key}")

    for _ in range(300):
        command = int(input("Enter command: "))
        if command == 1:
            key = input("Enter key: ")
            value = int(input("Enter value: "))
            comm = add_key(key, value, comm)
            execution_digest = update_digest(execution_digest, key)
        elif command == 2:
            print("To get the flag, provide a valid signature for the current execution.")
            sig_str = input("signature (space separated): ")
            s_str, e_str = sig_str.strip().split()
            s = int(s_str)
            e = int(e_str)
            if verify_signature(comm, execution_digest, (s, e)):
                print(f"Here is your flag: {FLAG}")
                return
            else:
                print("Invalid signature, exiting :(")
                return
        else:
            print("Invalid command")

if __name__ == "__main__":
    main()

#nc kkeeyyss.challs.till-dawn.fibonhack.it 12002

The challenge presents an ECDSA-based storage system where the final objective is to create a valid signature for the sent keys plus the initial key.

Initial Thoughts

Pre-Image Attack (Not Working)

Not being very confident with elliptic curves, my first focus was trying to understand the hash_to_curve function, especially since the comments mention a non-constant time hash-to-curve implementation.

def hash_to_curve(data: bytes) -> int:
    # perdoname madre por my
    # not constant time hash-to-curve implementation
    h = sha256(data).digest()
    x = int.from_bytes(h, "big") % P256.p
    while True:
        y = mod_sqrt(P256.evaluate(x), P256.p)[0]
        if P256.is_point_on_curve((x, y)):
            return Point(x, y, curve=P256)
        x = (x + 1) % P256.p

In elliptic curve cryptography over a prime field $\mathbb{F}_p$ roughly half of the field elements correspond to valid $x$-coordinates of curve point. That means that the probability of a value given from a PRF (Pseudo-Random-Function) of being a quadratic residue which implies to be a valid point on $E(\mathbb{F}_p)$ is approximately $\frac{1}{2}$:

In our Try-and-Increment algorithm the probability of hitting a valid point follows a geometric distribution with $p_{\text{succ}} = \frac{1}{2}$:

$P(N= k) = (\frac{1}{2})^{k} = \frac{1}{2^{k}}$ $\text{ for } k \in \{1,2,3,\dots\}$

That would imply that:

Given $m_1,m_2$ ; $m_1 \neq m_2$;

$x_{1} = \text{sha256}(m_1) \mod p ; x_{2} = \text{sha256}(m_2) \mod p ; x_{1} > x_{2}$

$\Delta = x_{1} - x_{2} \mod p$, the probability of their iteration paths merging into the exact same curve point is:

$P(\text{Collision} | \Delta) = 1/2^{\Delta}$

Theoretically this would work but it would imply being able to do pre-image attacks on SHA-256 (infeasible)

Squared Hashes (Not Working)

In the add_key function, points are generated by multiplying a user-provided constant by a set of hashes (derived from the key) and a set of base points B. Using the key “point”, one might obtain points = [value * hash_to_scalar(m) * hash_to_curve(m)], but it doesn’t seem possible to exploit this much further.

B = [hash_to_curve(f"key_point_{i}".encode()) for i in range(256)]

def add_key(key: str, value: int, comm: Point, init=False) -> Point:
    assert 0 <= value < P256.q # PUOI MANDARE 0
    r = hash_to_scalar(f"blinding_{key}_{value}".encode())
    coeffs = [
        hash_to_scalar(f"{'init' if init else 'key'}_{key}_{i}".encode()) for i in range(256)
    ]
    points = [value * c * B[i] for i, c in enumerate(coeffs)]
    delta = sum(points, Gr * r)

    return comm + delta

Understanding the verifying protocol

def verify_signature(comm: Point, message: bytes, sig: Tuple[int, int]):
    (s, e) = sig
    assert 0 <= e < P256.q
    assert 0 <= s < P256.q
    r_v = s * Gr + e * comm 
    e_v = hash_to_scalar(message + (r_v.x).to_bytes(32, "big") + (r_v.y).to_bytes(32, "big"))

    return e_v == e

Looking at this verifying algorithm, one can easily realise that it is a Schnorr Signature where the generator is Gr.

Schnorr Signature Protocol on Elliptic Curves

• Let G be the generator curve
• Generate the private key x as an integer
• The public verification key is $y= -x \cdot G$, a point on the curve.

Signing

To sign a message $M$:

• Choose a random $k$ from the allowed set. (nonce)
• Let $r = k \cdot G$.
• Let $e = H ( M || r )$, $r$ as a byte_string
• Let $s = k + x \cdot e$

The signature is the pair $( s , e )$.

Verifying

• $r_v = s\cdot g + e\cdot y$
• $e_v = H ( M || r_v )$

If $e_{v} = e; \text{ which implies } r_v = r$ then the signature is verified.

The Idea

We can see that the protocol is basically using the comm variable as our public key. What we need to do is to manipulate comm so that comm $= d \cdot G$ for a known scalar $d$. Once we know $d$, we can use the following signing algorithm to forge a valid signature:

def sign():
  k = 1 % q_order
  Rpt = E(k * Gr)  # Rpt = k * Gr
  Rpt_x = int(Rpt.xy()[0])
  Rpt_y = int(Rpt.xy()[1])
  e = hash_to_scalar(exec_digest + Rpt_x.to_bytes(32, "big") + Rpt_y.to_bytes(32, "big"))
  s = (k - e * d) % q_order #we use -e*d since after you wil clearly see that we are creating the public key as y = x*G and not y = -x*G
  return (s,e)

Solution

Exploit

Let’s analyze better how comm is constructed and modified:

def add_key(key: str, value: int, comm: Point, init=False) -> Point:
    assert 0 <= value < P256.q # PUOI MANDARE 0
    r = hash_to_scalar(f"blinding_{key}_{value}".encode())
    coeffs = [
        hash_to_scalar(f"{'init' if init else 'key'}_{key}_{i}".encode()) for i in range(256)
    ]
    points = [value * c * B[i] for i, c in enumerate(coeffs)]
    delta = sum(points, Gr * r)

    return comm + delta


def main():
  initial_key = os.urandom(16).hex()
    comm = add_key(initial_key, 1, O, init=True)
    execution_digest = update_digest(b"", initial_key)

    print(f"Your initial key is: {initial_key}")

    for _ in range(300):
        command = int(input("Enter command: "))
        if command == 1:
            key = input("Enter key: ")
            value = int(input("Enter value: "))
            comm = add_key(key, value, comm)
            execution_digest = update_digest(execution_digest, key)
        elif command == 2:
                print("To get the flag, provide a valid signature for the current execution.")
                sig_str = input("signature (space separated): ")
                s_str, e_str = sig_str.strip().split()
                s = int(s_str)
                e = int(e_str)
                if verify_signature(comm, execution_digest, (s, e)):
                    print(f"Here is your flag: {FLAG}")
                    return
                else:
                    print("Invalid signature, exiting :(")
                    return
            else:
                print("Invalid command")

We can clearly see that comm is the sum of the preceding comm + a series of points + Gr*r: We instantly notice that if we didn’t have the initial key we could just send value $= 0$ for $n$ times and have comm = $n \cdot r \cdot Gr$.

But this is not the case since we have that before we can send our keys

$\text{comm } = r \cdot Gr + 1\cdot\text{init-keys} \cdot B_s$.

Then the idea hit me:

We have 300 total interactions. We can build a Linear System to zero out all the $B_{s}$ components such that :

$\text{comm } = r \cdot Gr + 1\cdot\text{init-keys} \cdot B_s + 298 \cdot r \cdot Gr + \text{value }\cdot\text{normal-keys} \cdot B_s = 0 \mod q$.

$\implies \text{comm } = 299 \cdot r \cdot Gr + 1\cdot\text{init-keys} \cdot B_s + \text{value }[i]\cdot\text{normal-keys}[i] \cdot B_s[i] = 0 \mod q ; \text{ for } i \in \{0,1,2,\dots,298\}$

$\implies \text{comm } = (\text{init-keys} + \text{value }[i]\cdot\text{normal-keys}[i])B_s = 0 \mod q; \text{ for } i \in \{0,1,2,\dots,298\}$

Basically we want to find the combination of vectors $\text{value }[i]\cdot\text{normal-keys}[i]$ such that:

$\text{value }[i]\cdot\text{normal-keys}[i] -\text{init-keys} = 0 \mod q \text{ for } i \in \{0,1,2,\dots,298\}$

Then we are going to send to the oracle the various values and keys and at then end we will have comm $= 299 \cdot r \cdot Gr$ such that $299 \cdot r$ is our private key that we will use to sign

Solve Script

from hashlib import sha256

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a_curve = -3
b_curve = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
q_order = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
P256_Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
P256_Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5


Fp = GF(p)
E = EllipticCurve(Fp, [a_curve, b_curve])
E.set_order(q_order)
G = E(P256_Gx, P256_Gy)  

#Setting the curve to standard P256

def mod_sqrt(n, p):
    #idk it should work copied online
    return pow(n, (p + 1) // 4, p)

def is_on_curve(x, y):
    return (y * y - (x * x * x + a_curve * x + b_curve)) % p == 0
    # equation of the p256 curve

def hash_to_curve_point(data):
    h = sha256(data).digest()
    x = int.from_bytes(h, "big") % p
    while True:
        y_candidate = mod_sqrt((x * x * x + a_curve * x + b_curve) % p, p)
        if is_on_curve(x, y_candidate):
            return E(Fp(x), Fp(y_candidate))
        x = (x + 1) % p

def hash_to_scalar(data):
    h = sha256(data).digest()
    return int.from_bytes(h, "big") % q_order

Gr = hash_to_curve_point(b"blinding_generator")
B = [hash_to_curve_point(f"key_point_{i}".encode()) for i in range(256)]


import pwn
io = pwn.remote("kkeeyyss.challs.till-dawn.fibonhack.it", 12002)

def rl(): return io.readline().decode().strip()

for _ in range(5): rl()  # read the banner
initial_key = rl().split(": ", 1)[1].strip()
print(f"initial_key = {initial_key}")


c_init = [hash_to_scalar(f"init_{initial_key}_{i}".encode()) for i in range(256)]
N = 299
keys = [str(j) for j in range(N)]


M = Matrix(Zmod(q_order), 256, N)
for i in range(256):
    for j in range(N):
        M[i, j] = hash_to_scalar(f"key_{keys[j]}_{i}".encode())

target = vector(Zmod(q_order), [(q_order - c_init[i]) % q_order for i in range(256)])
## build the target_vector 

try:
    values_vec = M.solve_right(target)
    values = [int(values_vec[j]) for j in range(N)]
    # solve the matrix obtain vector values
    assert all(0 <= v < q_order for v in values)
    print(f"Solved! First few values: {values[:5]}")
except ValueError as e:
    print(f"No solution: {e}")

    raise

def update_digest(d, k):
    h = sha256()
    h.update(d)
    h.update(k.encode())
    return h.digest()


exec_digest = update_digest(b"", initial_key)
for j in range(N):
    print(f"MIAO __ {j}") # cute counter <3
    if j!= 0:
        io.recvuntil(b"Enter command: ")   
    io.sendline(b"1")
    io.recvuntil(b"Enter key: ")    
    io.sendline(f"{keys[j]}".encode())
    io.recvuntil(b"Enter value: ")
    io.sendline(f"{values[j]}".encode())
    exec_digest = update_digest(exec_digest, keys[j])
    # sending the coefficients


r_init = hash_to_scalar(f"blinding_{initial_key}_1".encode())
R = sum(hash_to_scalar(f"blinding_{keys[j]}_{values[j]}".encode()) for j in range(N)) % q_order
d = (r_init + R) % q_order
print(f"d = {hex(d)}") # creating the private key


import os
k = 1 % q_order
Rpt = E(k * Gr)  # Rpt = k * Gr
Rpt_x = int(Rpt.xy()[0])
Rpt_y = int(Rpt.xy()[1])
e = hash_to_scalar(exec_digest + Rpt_x.to_bytes(32, "big") + Rpt_y.to_bytes(32, "big"))
s = (k - e * d) % q_order # building the signature


io.recvuntil(b"Enter command: ")   
io.sendline(b"2")
io.recvuntil(b"signature (space separated): ") 
io.sendline(f"{s} {e}\n".encode()) # sending the signature
print(rl())

#FORZALAZIO{so_you_find_a_base_then_the_height_and_then_divide_by_2}

Flag

FORZALAZIO{so_you_find_a_base_then_the_height_and_then_divide_by_2}