Surprise Factor level: Hard Difficulty Dist...

Surprise Factor

level: Hard

Difficulty Distribution Chart

A bar chart representing the number of votes per difficulty level.
User-Rated Difficulty

Target Host 154.57.164.64:32521
Challenge Scenario
The devs were very proud of this one.

"Military-grade ECDSA."

"Masked internals."

"Safe against side channels."

Which, in challenge language, usually means:

"Please break this carefully."

You’re up against a remote signing service that looks clean from the outside and very noisy on the inside. It won’t hand you the key, but it will let you watch just enough of its internals to make questionable life choices.

Somewhere in that noise is a pattern. And if you follow it far enough, you may end up holding something you were never meant to see.

The service signs. The trace leaks. You listen.

Good luck.

//////////////// all the files

=== ./ecdsa.py ===
import hashlib
import secrets
from typing import Any

from bignum import add, inv, mod, mul, div
from trace import TRACE

from ec import G, N, point_add, scalar_mul, to_affine, to_jacobian, randomize_coordinates

TRACE.register("sign", "S")
TRACE.register("verify", "V")

def _hash_message(message):
digest = hashlib.sha256(message).digest()
return int.from_bytes(digest, "big")

def _random_scalar():
scalar = 0
while scalar == 0:
scalar = secrets.randbelow(N)
return scalar

def generate_keypair():
private_key = _random_scalar()
public_key = to_affine(scalar_mul(private_key, G))
if public_key is None:
raise ValueError("unexpected point at infinity while generating keypair")
return private_key, public_key

def _configure_trace(tracked_functions):
TRACE.configure(tracked_functions)
TRACE.reset()

def _record_operation(name):
TRACE.record(name)

def _finalize_trace(operation, tracked_functions, result, trace_path):
payload = dict(result)
payload["trace"] = TRACE.get_trace()

text
if trace_path is not None:
    metadata = {
        "algorithm": "ECDSA",
        "curve": "secp256r1",
        "operation": operation,
        "tracked": sorted(tracked_functions or set()),
    }
    for key in ("hash", "r", "s"):
        if key in payload:
            metadata[key] = hex(payload[key])
    if "valid" in payload:
        metadata["valid"] = payload["valid"]
    TRACE.export_json(trace_path, metadata)

return payload

def sign(privkey, tracked_functions=None, trace_path=None, message_length=32, hash_int=None, nonce=None):
_configure_trace(tracked_functions)
_record_operation("sign")

text
if not 1 <= privkey < N: raise ValueError("private key out of range")
if message_length <= 0: raise ValueError("message_length must be positive")
if hash_int is not None and hash_int < 0: raise ValueError("hash_int must be non-negative")
if nonce is not None and not 1 <= nonce < N: raise ValueError("nonce out of range")

if hash_int is None:
    message = secrets.token_bytes(message_length)
    hash_int = _hash_message(message)

while True:
    current_nonce = nonce if nonce is not None else _random_scalar()

    nonce_mask = secrets.randbelow(N)
    current_nonce = add(current_nonce, mul(nonce_mask, N))

    random_G = randomize_coordinates(G)
    point_r = scalar_mul(current_nonce, random_G)
    point_r = randomize_coordinates(point_r)

    current_nonce = mod(current_nonce, N)
    affine_r = to_affine(point_r)
    r = mod(affine_r[0], N)

    nonce_mask = secrets.randbelow(N)
    denominator = mul(nonce_mask, current_nonce) # masked nonce

    numerator = add(hash_int, mul(r, privkey))
    numerator = mul(nonce_mask, numerator)
    s = div(numerator, denominator, N)

    if r == 0:
        if nonce is not None: raise ValueError("fixed nonce produced r = 0")
        continue
    if s == 0:
        if nonce is not None: raise ValueError("fixed nonce produced s = 0")
        continue

    return _finalize_trace(
        "sign",
        tracked_functions,
        {"hash": hash_int, "r": r, "s": s},
        trace_path,
    )

def verify(hash_int, pubkey, signature, tracked_functions=None, trace_path=None):
_configure_trace(tracked_functions)
_record_operation("verify")

text
r, s = signature
if not (1 <= r < N and 1 <= s < N):
    return _finalize_trace(
        "verify",
        tracked_functions,
        {"valid": False},
        trace_path,
    )

w = inv(s, N)
u1 = mod(mul(hash_int, w), N)
u2 = mod(mul(r, w), N)

point_g = scalar_mul(u1, G)
point_q = scalar_mul(u2, to_jacobian(pubkey))
point_x = point_add(point_g, point_q)
affine_x = to_affine(point_x)
valid = affine_x is not None and mod(affine_x[0], N) == r

return _finalize_trace(
    "verify",
    tracked_functions,
    {"valid": valid},
    trace_path,
)

-e

=== ./all.sh ===
find . -type f -print | while read f; do
echo "=== $f ===" >> ../allfiles.txt cat "$f" >> ../allfiles.txt
echo -e "\n\n" >> ../allfiles.txt
done
-e

=== ./ec.py ===
import secrets
from bignum import add, double, inv, mod, mul, octuple, square, sub, triple
from trace import traceable

P = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
A = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
GX = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
GY = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
N = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
H = 1

INFINITY = (1, 1, 0)
G_AFFINE = (GX, GY)
G = (GX, GY, 1)

@traceable("is_infinity", "I")
def is_infinity(point):
return point[2] == 0

@traceable("to_jacobian", "J")
def to_jacobian(point):
if point is None:
return INFINITY
return (mod(point[0], P), mod(point[1], P), 1)

@traceable("to_affine", "F")
def to_affine(point):
if is_infinity(point):
return None

text
x, y, z = point
z_inv = inv(mod(z, P), P)
z_inv_sq = mod(square(z_inv), P)
z_inv_cu = mod(mul(z_inv_sq, z_inv), P)
affine_x = mod(mul(x, z_inv_sq), P)
affine_y = mod(mul(y, z_inv_cu), P)
return (affine_x, affine_y)

@traceable("randomize_coordinates", "R")
def randomize_coordinates(point):
if is_infinity(point):
return None

text
mask = secrets.randbelow(P)
mask2 = mul(mask, mask)
mask3 = mul(mask2, mask)

x, y, z = point
X = mod(mul(x, mask2), P)
Y = mod(mul(y, mask3), P)
Z = mod(mul(z, mask), P)

return (X, Y, Z)

@traceable("is_on_curve_affine", "C")
def is_on_curve_affine(point):
if point is None:
return True

text
x, y = point
left = mod(square(y), P)
right = mod(add(add(mul(x, square(x)), mul(A, x)), B), P)
return left == right

def _select_coordinate(on_one, on_zero, bit):
mask = -int(bit == "1")
return (on_one & mask) | (on_zero & ~mask)

def _select_point(on_one, on_zero, bit):
return (
_select_coordinate(on_one[0], on_zero[0], bit),
_select_coordinate(on_one[1], on_zero[1], bit),
_select_coordinate(on_one[2], on_zero[2], bit),
)

@traceable("point_double", "D")
def point_double(point):
if is_infinity(point):
return INFINITY

text
x1, y1, z1 = point
if mod(y1, P) == 0:
    return INFINITY

delta = mod(square(z1), P)
gamma = mod(square(y1), P)
beta = mod(mul(x1, gamma), P)

x1_minus_delta = mod(sub(x1, delta), P)
x1_plus_delta = mod(add(x1, delta), P)
alpha = mod(triple(mul(x1_minus_delta, x1_plus_delta)), P)

x3 = mod(sub(square(alpha), octuple(beta)), P)

yz_sum = add(y1, z1)
z3 = mod(sub(sub(square(yz_sum), gamma), delta), P)

gamma_sq = mod(square(gamma), P)
four_beta = double(double(beta))
y3 = mod(sub(mul(alpha, mod(sub(four_beta, x3), P)), octuple(gamma_sq)), P)
return (x3, y3, z3)

@traceable("point_add", "A")
def point_add(point_p, point_q):
if is_infinity(point_p):
return point_q
if is_infinity(point_q):
return point_p

text
x1, y1, z1 = point_p
x2, y2, z2 = point_q

# Jacobian addition intermediates: U1/U2 are normalized X coordinates,
# S1/S2 are normalized Y coordinates.
z1z1 = mod(square(z1), P)
z2z2 = mod(square(z2), P)
u1 = mod(mul(x1, z2z2), P)
u2 = mod(mul(x2, z1z1), P)
s1 = mod(mul(y1, mul(z2, z2z2)), P)
s2 = mod(mul(y2, mul(z1, z1z1)), P)

if u1 == u2:
    if s1 != s2:
        return INFINITY
    return point_double(point_p)

# H = U2 - U1, r = 2 * (S2 - S1), and the derived products used below.
h = mod(sub(u2, u1), P)
doubled_h = mod(double(h), P)
i = mod(square(doubled_h), P)
j = mod(mul(h, i), P)
r = mod(double(sub(s2, s1)), P)
v = mod(mul(u1, i), P)

# X3 = r^2 - J - 2 * V.
x3 = mod(sub(sub(square(r), j), double(v)), P)

# Y3 = r * (V - X3) - 2 * S1 * J.
y3 = mod(sub(mul(r, mod(sub(v, x3), P)), double(mul(s1, j))), P)

# Z3 = ((Z1 + Z2)^2 - Z1^2 - Z2^2) * H.
z1_plus_z2 = add(z1, z2)
z1_plus_z2_sq = mod(square(z1_plus_z2), P)
z3 = mod(mul(mod(sub(sub(z1_plus_z2_sq, z1z1), z2z2), P), h), P)
return (x3, y3, z3)

@traceable("scalar_mul", "M")
def scalar_mul(k, point):
if k == 0 or is_infinity(point):
return INFINITY

text
# Left-to-right binary double-and-add with constant-time point selection.
result = point
for bit in bin(k)[3:]:
    result = point_double(result)
    added  = point_add(result, point)
    result = _select_point(added, result, bit)
return result

-e

=== ./bignum.py ===
from trace import traceable

P256_PRIME = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
P256_MASK = (1 << 256) - 1

@traceable("add", "a")
def add(a, b):
return a + b

@traceable("sub", "s")
def sub(a, b):
return a - b

@traceable("neg", "n")
def neg(a):
return -a

@traceable("mul", "m")
def mul(a, b):
return a * b

@traceable("square", "q")
def square(value):
return mul(value, value)

@traceable("double", "b")
def double(value):
return add(value, value)

@traceable("triple", "t")
def triple(value):
return add(double(value), value)

@traceable("octuple", "o")
def octuple(value):
return double(double(double(value)))

@traceable("half", "h")
def half(value):
return value // 2

@traceable("mod", "r")
def mod(value, modulus):
if modulus <= 0:
raise ValueError("modulus must be positive")
if modulus == P256_PRIME:
return _p256_quasi_reduce(value)
return value % modulus

@traceable("p256_quasi_reduce", "p")
def _p256_quasi_reduce(value):
if value < 0:
reduced = _p256_quasi_reduce(sub(0, value))
return 0 if reduced == 0 else sub(P256_PRIME, reduced)

text
while value.bit_length() > 256:
    high = value >> 256
    low = value & P256_MASK
    value = add(low, high)
    value = add(value, high << 224)
    value = sub(value, high << 192)
    value = sub(value, high << 96)

while value >= P256_PRIME:
    value = sub(value, P256_PRIME)
return value

@traceable("binary_division_odd_modulus", "y")
def _binary_division_odd_modulus(a, b, modulus):
u = b
v = modulus
x1 = a
x2 = 0

text
while u != 1 and v != 1:
    while (u & 1) == 0:
        u = half(u)
        if (x1 & 1) == 0:
            x1 = half(x1)
        else:
            x1 = half(add(x1, modulus))

    while (v & 1) == 0:
        v = half(v)
        if (x2 & 1) == 0:
            x2 = half(x2)
        else:
            x2 = half(add(x2, modulus))

    if u >= v:
        u = sub(u, v)
        x1 = sub(x1, x2)
    else:
        v = sub(v, u)
        x2 = sub(x2, x1)

if u == 1:
    return mod(x1, modulus)
return mod(x2, modulus)

@traceable("inv", "i")
def inv(a, modulus):
a = mod(a, modulus)
return _binary_division_odd_modulus(1, a, modulus)

@traceable("div", "v")
def div(a, b, modulus):
a = mod(a, modulus)
return _binary_division_odd_modulus(a, b, modulus)
-e

=== ./server.py ===
import hashlib, json, secrets, sys

from ecdsa import sign
from ec import G, scalar_mul, to_affine
from secret import PRIVATE_KEY

FLAG = open("flag.txt").read().strip()

MESSAGE_LENGTH = 32
PUBLIC_KEY = to_affine(scalar_mul(PRIVATE_KEY, G))

if PUBLIC_KEY is None:
raise ValueError("unexpected point at infinity while deriving public key")

AVAILABLE_FUNCTIONS = [
"add",
"sub",
"neg",
"mul",
"square",
"double",
"triple",
"octuple",
"half",
"mod",
"p256_quasi_reduce",
"binary_division_odd_modulus",
"inv",
"div",
"is_infinity",
"to_jacobian",
"to_affine",
"randomize_coordinates",
"is_on_curve_affine",
"point_double",
"point_add",
"scalar_mul",
"sign",
"verify",
]

def parse_request(raw_request):
if not raw_request.strip():
raise ValueError("expected a JSON request on stdin")

text
request = json.loads(raw_request)
if not isinstance(request, dict):
    raise ValueError("request must be a JSON object")
return request

def validate_tracked_functions(tracked_functions):
requested = set(tracked_functions)
unknown = sorted(requested.difference(AVAILABLE_FUNCTIONS))
if unknown:
names = ", ".join(unknown)
raise ValueError(f"unknown traceable functions: {names}")
return requested

def emit_response(payload):
print(json.dumps(serialize_response(payload)), flush=True)
return 0

def serialize_response(value):
if isinstance(value, bool) or value is None:
return value
if isinstance(value, int):
return hex(value)
if isinstance(value, list):
return [serialize_response(item) for item in value]
if isinstance(value, dict):
return {key: serialize_response(item) for key, item in value.items()}
return value

def parse_integer(value, field_name):
if isinstance(value, int):
return value
if isinstance(value, str):
return int(value, 0)
raise ValueError(f"{field_name} must be an integer or a string encoding an integer")

def handle_sign(request):
tracked_functions = request.get("track", [])
if not isinstance(tracked_functions, list):
raise ValueError("track must be a JSON array of function names")

text
tracked_functions = validate_tracked_functions(tracked_functions)
result = sign(
    PRIVATE_KEY,
    tracked_functions=tracked_functions,
    message_length=MESSAGE_LENGTH,
)
result["public_key"] = {
    "x": PUBLIC_KEY[0],
    "y": PUBLIC_KEY[1],
}
return result

def handle_submit(request):
private_key = parse_integer(request.get("d"), "d")
candidate_public_key = to_affine(scalar_mul(private_key, G))
valid = candidate_public_key == PUBLIC_KEY
result = {"valid": valid}
if valid:
result["flag"] = FLAG
return result

def handle_request(request, current_hash):
action = request.get("action", "sign")
if action == "sign":
return handle_sign(request), current_hash
if action == "submit":
return handle_submit(request), current_hash

raise ValueError("action must be 'sign', or 'submit'")

current_hash = None
for raw_request in sys.stdin:
if not raw_request.strip():
continue
try:
request = parse_request(raw_request)
response, current_hash = handle_request(request, current_hash)
emit_response(response)
except (TypeError, ValueError, json.JSONDecodeError) as error:
emit_response({"error": str(error)})-e

=== ./trace.py ===
import json
from dataclasses import dataclass, field

@dataclass
class TraceCollector:
tracked_functions: set = field(default_factory=set)
trace: list = field(default_factory=list)
legend: dict = field(default_factory=dict)

text
def register(self, name, symbol):
    self.legend[name] = symbol

def configure(self, tracked_functions):
    self.tracked_functions = set(tracked_functions or set())

def reset(self):
    self.trace.clear()

def record(self, name):
    if name in self.tracked_functions:
        self.trace.append(self.legend[name])

def get_trace(self):
    return list(self.trace)

def export_json(self, path, metadata):
    payload = dict(metadata)
    payload["legend"] = {
        name: symbol
        for name, symbol in self.legend.items()
        if name in self.tracked_functions
    }
    payload["trace"] = self.get_trace()
    with open(path, "w", encoding="ascii") as handle:
        json.dump(payload, handle, indent=2, sort_keys=True)

TRACE = TraceCollector()

def traceable(name, symbol):
TRACE.register(name, symbol)

text
def decorator(func):
    def wrapper(*args, **kwargs):
        TRACE.record(name)
        return func(*args, **kwargs)

    wrapper.__name__ = func.__name__
    wrapper.__doc__ = func.__doc__
    wrapper.__module__ = func.__module__
    return wrapper

return decorator

-e