ECDSA Challenge Part 2 Writeup

Challenge Overview

CTF: Pioneers25
Challenge: PBTF 2
Category: Cryptography
Author: a_b
Files: server.py
Connection info: nc 134.112.83.77 1004
Description:

Note

congratulations for solving the previous challenge. Now I used a known secure curve.

Introduction

This is the second part of the elliptic-curve challenges series PBTF from Pioneers25. Unlike the first challenge, the curve itself is not broken this time. The service uses the standard P-256 curve, so the weakness has to be somewhere else. The bug was in how the nonce k is being generated.

If you have not read part 1 yet and want a slower introduction to elliptic curves, ECDSA, signatures, and why the nonce matters, I recommend starting here first.

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 *
import numpy as np


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 = k_gen(message.decode())
        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):
    limit=np.array(list(map(ord, name))).prod()
    return h(long_to_bytes(random.randint(0,limit)))

MAX_ATTEMPTS=10

if __name__ == "__main__":


    ECDSA = ECDSA()
    print('Identify yourself')
    name = input("> ").strip().encode()
    test=all(32<b<128 for b in name)
    if not test:
        print("Name must be printable ASCII!")
        exit()
    print(menu)
    for _ in range (MAX_ATTEMPTS):
        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
                test=all(32<b<128 for b in message)
                if test:
                    r, s = ECDSA.ECDSA_sign(message)
                    print('Signature: ({},{})'.format(r, s))
                else:
                    print("Message must be printable ASCII!")

            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
      

The first thing I checked in server.py was whether the challenge was still using one of the custom curves from part 1. It was not:

        
        PYTHON
      
from fastecdsa.curve import P256 as EC

        Click to expand and view more

So this time there is no anomalous-curve trick. The curve is standard P-256, which means the attack has to come from the implementation.

The next step was to inspect the signing code:

        
        PYTHON
      
def ECDSA_sign(self, message):
    k = k_gen(message.decode())
    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 clearly k_gen(), so I looked there next:

        
        PYTHON
      
def k_gen(name):
    limit=np.array(list(map(ord, name))).prod()
    return h(long_to_bytes(random.randint(0,limit)))

        Click to expand and view more

At first, this function looks a bit strange. So it is better to read it slowly, line by line.

The variable is called name, but here it is really the message, because the signing function does this:

        
        PYTHON
      
k = k_gen(message.decode())

        Click to expand and view more

So k_gen() builds the nonce from the message itself.

Now let us read the function slowly.

First:

        
        PYTHON
      
list(map(ord, name))

        Click to expand and view more

This changes the message into a list of ASCII numbers. For example, if the message is "ABC", this becomes:

        
        PYTHON
      
[65, 66, 67]

        Click to expand and view more

Then this line:

        
        PYTHON
      
np.array(...).prod()

        Click to expand and view more

multiplies all those numbers together and stores the result in limit.

So for "ABC", the result is:

\[ 65 \times 66 \times 67 \]

After that, the function does:

        
        PYTHON
      
random.randint(0, limit)

        Click to expand and view more

This means it picks a random integer between 0 and limit, including both ends.

Finally, that random integer is turned into bytes and hashed:

        
        PYTHON
      
h(long_to_bytes(random.randint(0,limit)))

        Click to expand and view more

and the hash becomes the nonce k.

So this function does the following:

turn the message into ASCII integers
multiply them together
call the result limit
pick a random integer in [0, limit]
hash that integer to obtain the nonce

Now we can see why this looks suspicious.

The nonce is not chosen from the full ECDSA range. It comes from a random value inside an interval, and the size of that interval depends only on the chosen message.

So the next question is simple:

Can we choose a message that makes this interval very small?

What the Server Lets Us Do

Like part 1, the service gives a small interactive menu:

validate a signature for LET ME IN !!!
sign an arbitrary message other than LET ME IN !!!
print the public key and curve info

So the flow is clear:

ask for the public key
ask for one chosen-message signature
recover the private key
forge the forbidden signature

In other words, once the nonce generation is understood, the challenge is essentially over. Therefore, it is time for exploitation:

Exploitation

Now the path is clear. The nonce depends on a value inside [0, limit], and limit depends only on the message. So the whole attack is about making limit as small as possible, then trying every possible value in that small range.

Step 1: Choose the smallest allowed message

The service enforces printable ASCII:

        
        PYTHON
      
test=all(32<b<128 for b in message)

        Click to expand and view more

That means the smallest allowed byte is !, whose ASCII value is 33.

If the message is exactly one byte long and equal to !, then:

        
        PYTHON
      
limit = 33

        Click to expand and view more

and the server chooses:

        
        PYTHON
      
random.randint(0, 33)

        Click to expand and view more

That is only 34 possibilities:

\[0,1,2,\ldots,33\]

Normally, an ECDSA nonce should come from a very large space. Here, by choosing the message carefully, we can make that space very small.

This is why the printable-ASCII check matters. We are not free to send any byte we want, so we need the smallest character that still passes the filter.

Step 2: Ask for one signature

Once that is clear, the next step is to ask the service to sign !.

The returned signature is:

\[ (r, s) \]

and because the message is known, the hash is also known.

The only unknown left in the ECDSA equation is the nonce.

But at this point the nonce is one of only 34 possibilities, so it is no longer hard to recover.

Step 3: Recover the private key

Recall the ECDSA signing equation:

\[ s = k^{-1}(h + dr) \pmod{n} \]

Rearranging gives:

\[ d = (sk - h)r^{-1} \pmod{n} \]

So for each possible nonce candidate, a candidate private key can be computed.

The exploit does exactly that:

        
        PYTHON
      
for guess in range(34):
    nonce = h(long_to_bytes(guess))
    candidate = ((s_value * nonce - h(LEAK_MESSAGE)) * r_inverse) % N

        Click to expand and view more

Of course, not every candidate is correct. So the next question is: how do we know which one is the real key?

The answer is simple. The service also gives the public key, so each candidate can be checked by testing:

\[ Q \stackrel{?}{=} dG \]

and keeping the one that reproduces the published public point.

That check is very important. It means we do not have to guess. Once the correct nonce is found, the correct private key is found too.

Step 4: Forge the final signature

Once the private key is known, forging the target signature becomes ordinary ECDSA.

The cleanest choice is to set:

\[ k = 1 \]

Then:

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

so the signature equation becomes:

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

That is exactly what is computed for LET ME IN !!!.

The result is a perfectly valid ECDSA signature, just produced by us instead of the server.

Step 5: Match the server hash

Just like part 1, the hash is not the full SHA-256 digest. The service defines:

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

        Click to expand and view more

So only the first 8 bytes of SHA-256 are used.

Step 6: 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:

Connect to the service.
Read the public key.
Ask for a signature on !.
Enumerate all 34 possible nonce sources.
Recover the private key from the correct nonce.
Forge a signature for LET ME IN !!!.
Submit it and recover the flag.

Full Solve Script

        
  

      

        PYTHON
      

      
      
    
#!/usr/bin/env python3

import hashlib
import re

from pwn import context, remote


HOST = "134.112.83.77"
PORT = 1004

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

LEAK_MESSAGE = b"!"
TARGET_MESSAGE = b"LET ME IN !!!"

context.log_level = "error"


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


def long_to_bytes(value: int) -> bytes:
    if value == 0:
        return b"\x00"
    return value.to_bytes((value.bit_length() + 7) // 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(signature, public_key):
    r_value, s_value = signature
    r_inverse = pow(r_value, -1, N)

    for guess in range(34):
        nonce = h(long_to_bytes(guess))
        candidate = ((s_value * nonce - h(LEAK_MESSAGE)) * r_inverse) % N
        if scalar_mult(candidate, G) == public_key:
            return candidate

    raise RuntimeError("failed to recover the private key")


def sign_message(private_key: int, message: bytes):
    nonce = 1
    r_value = GX % N
    s_value = (h(message) + r_value * private_key) % N
    if s_value == 0:
        raise RuntimeError("unexpected zero signature component")
    return r_value, s_value


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

        io.sendline(b"3")
        info = io.recvuntil(b"Choose an option:").decode("utf-8", "replace")
        public_x, public_y = map(int, re.search(r"public key: (\d+), (\d+)", info).groups())
        public_key = (public_x, public_y)

        io.sendline(b"2")
        io.recvuntil(b"> ")
        io.sendline(LEAK_MESSAGE)
        signed = io.recvuntil(b"Choose an option:").decode("utf-8", "replace")
        r_value, s_value = map(int, re.search(r"Signature: \((\d+),(\d+)\)", signed).groups())

        private_key = recover_private_key((r_value, s_value), public_key)
        forged_r, forged_s = sign_message(private_key, TARGET_MESSAGE)

        io.sendline(b"1")
        io.recvuntil(b"r:")
        io.sendline(str(forged_r).encode())
        io.recvuntil(b"s:")
        io.sendline(str(forged_s).encode())

        result = io.recvuntil((b"Pioneers25{", b"Choose an option:")).decode("utf-8", "replace")
        print(result, end="")
    finally:
        io.close()


if __name__ == "__main__":
    main()

        Click to expand and view more
      

Running the exploit returns:

PLAINTEXT

Pioneers25{d0_n07_45k_7h3_4u7h0r_4b0u7_wh47_PBTF_m34n5}

Click to expand and view more

I hope this was fun and you enjoyed the writeup, now time to see you in the part 3 of this series and the last one.