ECDSA Challenge Part 3 Writeup

ECDSA Challenge Part 3 Writeup

Recovering an ECDSA private key through repeated nonces
Updated on March 19, 2026
10 minute
1922 words
Categories: CTF Writeups
Tags: CTF Cryptography Writeups ECC Cyber Security Pioneers CTF

Challenge Overview

  • CTF: Pioneers25
  • Challenge: PBTF 3
  • Category: Cryptography
  • Author: a_b
  • Files: server.py
  • Connection info: nc 134.112.83.77 1005
  • Description:

Introduction

This is the third and final part of the elliptic-curve challenges series PBTF from Pioneers25. Just like part 2, the curve is still standard P-256. The difference here is that the server does not generate a tiny nonce from the chosen message. Instead, it generates a short list of nonces once at the beginning of the session and then keeps choosing from that same list again and again. In this writeup we show how singning 2 messages with the same nonce immediately reveal the private key.

If you want the slower background on elliptic curves, ECDSA, and why the nonce is such a critical value, read the first part first.

Part 2 is also useful before reading this one, because it shows another way bad nonces break the same signature scheme.

Initial Analysis

server.py

PYTHON 
from Crypto.Util.number import inverse ,bytes_to_long,long_to_bytes
from fastecdsa.curve import P256 as EC
from fastecdsa.point import Point
import random, hashlib
from redacted import *



class ECDSA:
    def __init__(self):

        self.G = Point(EC.gx, EC.gy, curve=EC)
        self.order = EC.q
        self.privkey = random.randrange(1, self.order - 1)
        self.pubkey = (self.privkey * self.G)

    def info(self):
        print(info.format(curve=EC, pubkey=self.pubkey))

    def ECDSA_sign(self, message):

        k = random.choice(k_list)
        r = (k*self.G).x % self.order
        s = inverse(k, self.order) * (h(message) + r * self.privkey) % self.order
        return (r, s)

    def ECDSA_verify(self, message, r, s):
        r %= self.order
        s %= self.order
        if s == 0 or r == 0:
            return False

        s_inv = inverse(s, self.order)
        u1 = (h(message)*s_inv) % self.order
        u2 = (r*s_inv) % self.order
        W = u1*self.G + u2*self.pubkey
        return W.x == r

def h(message):
    return bytes_to_long(hashlib.sha256(message).digest()[:8])

def k_gen(name):
    global k_list
    k_list=[h(long_to_bytes(random.randrange(h(name)))) for _ in range(10)]



if __name__ == "__main__":


    ECDSA = ECDSA()
    print('Identify yourself')
    name = input("> ").strip().encode()
    k_gen(name)
    print(menu)
    for _ in range (10):#limited attempts no bruteforce required
        try:
            print("Choose an option:")
            choice = input("> ").strip()
            if not choice.isdigit():
                print("Please enter a number.")
                continue
            if choice == '1':

                r=int(input("r: ").strip())
                s=int(input("s: ").strip())
                if ECDSA.ECDSA_verify(b'LET ME IN !!!', r, s):
                    print("Valid signature!")
                    print('Welcome ', name.decode())
                    print(f"Here is your flag: {FLAG}")
                else:
                    print("Invalid signature!")


            elif choice == '2':
                print('Provide the message to sign')
                message = input("> ").strip().encode()
                if message==b'LET ME IN !!!':
                    print("You are not allowed to sign this message!")
                    continue
                r, s = ECDSA.ECDSA_sign(message)
                print('Signature: ({},{})'.format(r, s))

            elif choice == '3':
                ECDSA.info()

            elif choice == '4':
                print("Exiting...")
                break

            else:
                print("Invalid choice!")
            print()
        except KeyboardInterrupt:
            print("\nForcing exit :(")
            break
        except Exception as e:
            print("Error:", e)
            print("Please try again.")
            print()
Click to expand and view more

As in part 2, the service uses standard P-256:

PYTHON 
from fastecdsa.curve import P256 as EC
Click to expand and view more

So again the interesting part is not the curve itself, but the nonce generation.

The signing code is:

PYTHON 
def ECDSA_sign(self, message):
    k = random.choice(k_list)
    r = (k*self.G).x % self.order
    s = inverse(k, self.order) * (h(message) + r * self.privkey) % self.order
    return (r, s)
Click to expand and view more

The important part is random.choice(k_list), because it means the nonce is not generated fresh every time. It comes from a list that was prepared earlier.

So the next place to inspect is how that list is built:

PYTHON 
def k_gen(name):
    global k_list
    k_list=[h(long_to_bytes(random.randrange(h(name)))) for _ in range(10)]
Click to expand and view more

At first and like it was the case with the part 2, this function also looks a bit strange, so it is better to read it slowly.

The variable is called name, and this time it really is the user name. The server calls k_gen(name) once, right after the connection starts.

Then this line:

PYTHON 
random.randrange(h(name))
Click to expand and view more

picks a random integer between 0 and h(name) - 1.

That random integer is turned into bytes, hashed, and stored in the list:

PYTHON 
h(long_to_bytes(random.randrange(h(name))))
Click to expand and view more

And because this happens inside:

PYTHON 
[... for _ in range(10)]
Click to expand and view more

the result is a list with 10 values.

So this function builds a list of 10 possible nonces at the start of the session.

After that, every signature simply does:

PYTHON 
k = random.choice(k_list)
Click to expand and view more

So the server is not choosing from the full ECDSA nonce space anymore. It is choosing from a fixed list of only 10 values.

Now we can see why this looks suspicious.

Why repeated nonces are dangerous

Suppose two different messages \(m_1\) and \(m_2\) are signed using the same nonce \(k\) .

Then both signatures share the same point:

\[ R = kG \]

and therefore they also share the same value:

\[ r = x(R) \bmod n \]

If the two signatures are \((r, s_1)\) and \((r, s_2)\) , then:

\[ s_1 = k^{-1}(h(m_1) + dr) \pmod n \] \[ s_2 = k^{-1}(h(m_2) + dr) \pmod n \]

Subtracting gives:

\[ s_1 - s_2 = k^{-1}(h(m_1) - h(m_2)) \pmod n \]

so:

\[ k = \frac{h(m_1) - h(m_2)}{s_1 - s_2} \pmod n \]

and after that:

\[ d = \frac{s_1k - h(m_1)}{r} \pmod n \]

So once a repeated nonce appears, the private key is gone.

That is exactly the attack path in this challenge.

What the Server Lets Us Do

The interaction is the same basic pattern as before:

  • request a signature on any message except LET ME IN !!!
  • submit a signature for the target message
  • read public information

So the flow is clear:

  1. ask for signatures on many chosen messages
  2. wait for the same r value to appear twice
  3. recover the private key
  4. forge the target signature

The only thing to pay attention to is the menu limit. The service gives only 10 actions per session, so there is no room to waste requests. Therefore, it is time for exploitation:

Exploitation

At this point the challenge is about waiting for the nonce to be repeated.

Step 1: Force a repeated r

Because r comes from the point kG, two signatures that use the same nonce must have the same r.

So the natural thing to do is to keep asking for signatures on distinct messages and watch the returned r values.

The exploit uses:

  • msg0
  • msg1
  • msg2
  • …

and stores every tuple (message, r, s).

Why distinct messages? Because when the repeated nonce formulas are used, we need different message hashes. Using different messages guarantees that.

The service allows only 10 actions total, so what we can do is:

  • 9 signature queries
  • 1 final submit

That is still plenty, because the nonces are being chosen from a pool of only 10 values. So a collision is very likely. Once a repeated r shows up, we already solved the challenge.

Step 2: Recover the private key

Suppose the same r appears twice:

  • (r, s_1) on m_1
  • (r, s_2) on m_2

Then the repeated-nonce equations apply directly:

\[ k = \frac{h(m_1) - h(m_2)}{s_1 - s_2} \pmod n \]

and:

\[ d = \frac{s_1k - h(m_1)}{r} \pmod n \]

That is exactly what we compute:

PYTHON 
k_value = ((h(old_message) - h(message)) * pow((old_s - s_value) % N, -1, N)) % N
private_key = ((old_s * k_value - h(old_message)) * pow(r_value, -1, N)) % N
Click to expand and view more

Once the repeated nonce is found, the private key is recovered exactly.

Step 3: Forge the target signature

After that, the rest is just standard ECDSA forging with a known private key.

As in part 2, the cleanest choice is to set:

\[ k = 1 \]

Then:

  • \(R = G\)
  • \(r = x(G) \bmod n\)
  • \(k^{-1} = 1\)

and so:

\[ s = h(m) + dr \pmod n \]

That gives a valid signature for the forbidden message LET ME IN !!!.

Step 4: Match the server hash

As usual, only the first 8 bytes of SHA-256 are used:

PYTHON 
def h(message):
    return bytes_to_long(hashlib.sha256(message).digest()[:8])
Click to expand and view more

Step 5: Submit the signature

Once the private key is known and the target signature is forged, the last step is just to send r and s back to the service.

If everything matches, the server accepts the forged signature and returns the flag.

Recap

Putting everything together, the attack steps are:

  1. Connect to the service.
  2. Request signatures on distinct messages.
  3. Watch the r values.
  4. As soon as one r repeats, recover the nonce.
  5. Recover the private key.
  6. Forge a signature for LET ME IN !!!.
  7. Submit it and recover the flag.

If a session somehow fails to produce a repeated r within the available signing requests, just reconnect and try again. But it is likely to start working from the first try.

Full Solve Script

PYTHON 
#!/usr/bin/env python3

import hashlib
import re

from pwn import context, remote


HOST = "134.112.83.77"
PORT = 1005

P = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
A = (P - 3) % P
GX = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
GY = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
N = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
G = (GX, GY)

TARGET = b"LET ME IN !!!"

context.log_level = "error"


def h(message: bytes) -> int:
    return int.from_bytes(hashlib.sha256(message).digest()[:8], "big")


def point_add(point1, point2):
    if point1 is None:
        return point2
    if point2 is None:
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2:
        if (y1 + y2) % P == 0:
            return None
        slope = ((3 * x1 * x1 + A) * pow((2 * y1) % P, -1, P)) % P
    else:
        slope = ((y2 - y1) * pow((x2 - x1) % P, -1, P)) % P

    x3 = (slope * slope - x1 - x2) % P
    y3 = (slope * (x1 - x3) - y1) % P
    return (x3, y3)


def scalar_mult(scalar: int, point):
    result = None
    addend = point
    while scalar:
        if scalar & 1:
            result = point_add(result, addend)
        addend = point_add(addend, addend)
        scalar >>= 1
    return result


def recover_private_key(signatures):
    seen = {}
    for message, r_value, s_value in signatures:
        if r_value not in seen:
            seen[r_value] = (message, s_value)
            continue

        old_message, old_s = seen[r_value]
        k_value = ((h(old_message) - h(message)) * pow((old_s - s_value) % N, -1, N)) % N
        private_key = ((old_s * k_value - h(old_message)) * pow(r_value, -1, N)) % N
        return private_key

    raise RuntimeError("no repeated nonce found")


def forge_signature(private_key: int):
    r_value = GX % N
    s_value = (h(TARGET) + r_value * private_key) % N
    if s_value == 0:
        raise RuntimeError("unexpected zero s value")
    return r_value, s_value


def solve_once():
    io = remote(HOST, PORT)
    try:
        io.recvuntil(b"> ")
        io.sendline(b"solver")
        io.recvuntil(b"Choose an option:")

        signatures = []
        for index in range(9):
            message = f"msg{index}".encode()
            io.sendline(b"2")
            io.recvuntil(b"> ")
            io.sendline(message)
            output = io.recvuntil(b"Choose an option:").decode("utf-8", "replace")
            r_value, s_value = map(int, re.search(r"Signature: \((\d+),(\d+)\)", output).groups())
            signatures.append((message, r_value, s_value))

            repeated = len({r for _, r, _ in signatures}) != len(signatures)
            if repeated:
                break

        private_key = recover_private_key(signatures)
        forged_r, forged_s = forge_signature(private_key)

        io.sendline(b"1")
        io.recvuntil(b"r:")
        io.sendline(str(forged_r).encode())
        io.recvuntil(b"s:")
        io.sendline(str(forged_s).encode())
        return io.recvuntil((b"}", b"Choose an option:")).decode("utf-8", "replace")
    finally:
        io.close()


def main():
    while True:
        result = solve_once()
        print(result, end="")
        if "Pioneers25{" in result:
            return


if __name__ == "__main__":
    main()
Click to expand and view more

Running the exploit returns:

PLAINTEXT 
Pioneers25{h3r3_c0m35_7h3_n3x7_Bruce_schneier}
Click to expand and view more

I hope this series was fun, it was a nice and fun CTF overall and it was good to play some crypto once again after a few months of relying entirely on AI agents. Take care homies and see you on the next blog ( hopefully it will be another ECC writeup )

Related Posts

Start searching

Enter keywords to search articles

↑↓
↵
ESC
⌘K Shortcut