Heidelberg, Germany, after a lovely day in march at the TROOPERS Conference 2019 I find myself in a traditional german restaurant. It's cold, it's loud, the food is 6/10, I'm sober and me and Parzel are waiting for Packetwars to start.

Nice! A crypto challenge! "Fun with Finite Fields" is the name.

The only prior information about the challenge is the name: "Fun with Finite Fields" - OK probably Elliptic Curve cryptography... I'm scared - I only know one (textbook) attack on EC signatures. That's all I need, as I will find out.

## How the challenge works:

We find the lonely challenge server waiting for my TCP connection. I get this prompt after connecting with netcat:

Note the display of the public key - we will need that for later.

'Generating secure k' - What a surprise, this is probably the textbook example I was thinking about. How the attack works will unfold shortly, but let's look first what the server has to offer.

Two commands of interest:
- Sign command: Enter a command and retrieve it's EC crypto signature.
- Execute command:  Enter a command and it's signature and retrieve it's output.

Alright, let's execute 'ls':

Pretty straight forward: The challenge clearly wants us to forge a signature for a 'cat flag.txt' command.

Let's see what server.py looks like (execute 'cat server.py'):

import ecdsa
import os
import sys
import secrets

print("Welcome to the secure shell.")
print("Setting up")
print("Generating key")

sk = ecdsa.SigningKey.generate() # uses NIST192p
vk = sk.get_verifying_key()

print("Using the following verification key:")
print(vk.to_pem().decode('utf-8'))

"""https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Security says it is important to have a secure random k
so make sure we generate it properly"""
print("Generating secure k")
k = secrets.randbelow(sk.curve.order)

def sign():
allowed_cmds = [ 'ls', 'pwd', 'cat server.py']
cmd = input("Command to sign:")
if cmd not in allowed_cmds:
print("Illegal command, only allowed commands are %s" % allowed_cmds)
else:
sig = sk.sign(cmd.encode("utf-8"), k=k)
print("Signature: %s" % sig.hex())

def execute():
cmd = input("Command to execute: ")
signature = input("Signature: ")
signature = bytes.fromhex(signature)
try:
vk.verify(signature, cmd.encode('utf-8'))
print("Correct signature, executing command")
os.system(cmd)
print("Invalid signature")
return

'1': sign,
'2': execute,
'3': sys.exit
}
while True:
print("1. Sign command")
print("2. Execute command")
print("3. Exit")
cmd = input("Select:")
try:
except KeyError:
print("Invalid selection")


The textbook vulnerability is right there: k is not generated randomly for each signature but only once and reused for different signatures!

BTW: Nice hint in the code:
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
It states there:
As the standard notes, it is not only required for k to be secret, but it is also crucial to select different k for different signatures, otherwise the equation in step 6 can be solved for the private key.

## La solución:

All we need to do is follow the instructions on Wikipedia:

Let's resolve the symbols here:
- n : group order (all operations are mod n)
- k : cryptographically secure random integer from [1,n-1]
- z : SHA1(message) mod n, where message will be signed (SHA1 is default)
- (r, s) : the signature of message (yes the signature is a tuple)

### How the attack works:

Using the public key from the greeting message, we can infer n, the group order.
We just need to parse the public key, which is best done within python-ecdsa.

We also need to parse the 2 signatures we obtained from the 'ls' and 'cat server.py' commands.
Additionally we compute z and z' by hashing 'ls' and 'cat server.py' with SHA1.

We can then compute k and finally the private key.
Using the private key, we finally can forge signatures to commands of our choice.

### Attack and results:

Let's feed the public key and the 2 signatures into our python script:

import ecdsa
import gmpy

pub_key_string = "MEkwEwYHKoZIzj0CAQYIKoZIzj0DAQEDMgAEs6zGswjq+TmkijBDMrGuWX37pEhzZInHVrlPQ0evnumbG0j/++KDmdhdkn5aVY1e"

m1 = "ls"

m2 = "cat server.py"
sig2 = "cd03afe9a551932e598f26bce4d9f6ebdaf90cf0235346f21d50eb70af1677f6c53eb32575af83bb0cd7a7566bbb19ff"

# Generate own key-pair to access utility functions
sk = ecdsa.SigningKey.generate() # uses NIST192p
vk = sk.get_verifying_key()

# Parse public key from the server and obtain n
veri_key = vk.from_pem(pub_key_string)
n = veri_key.pubkey.order

# Parse the 2 signatures
r1, s1 = ecdsa.util.sigdecode_string(bytes.fromhex(sig1), order=n)
r2, s2 = ecdsa.util.sigdecode_string(bytes.fromhex(sig2), order=n)

# Hash the commands (ls, cat server.py) and transform them into numbers
h1 = ecdsa.keys.sha1(m1.encode("utf-8"))
z1 = ecdsa.util.string_to_number(h1.digest())
h2 = ecdsa.keys.sha1(m2.encode("utf-8"))
z2 = ecdsa.util.string_to_number(h2.digest())

# Perform math according to wikipedia
k=((z1 - z2) * gmpy.invert(s1 - s2, n)) % n
print("k: ", k)
r_inv = gmpy.invert(r1,n)
d_a = ((s1*k - z1) * r_inv) % n

# Sign own command (cat flag.txt) using the obtained secret exponent
COMMAND = "cat flag.txt"
sk_new = sk.from_secret_exponent(d_a)
print("Command: ", COMMAND)
sig = sk_new.sign(COMMAND.encode("utf-8"), k=k)
print("Signature: ", sig.hex())


The forged signature to our own command ('cat flag.txt') is presented to the server:

That's it: The flag is right there!

All in all I must say, the only big challenge was to fiddle with python-ecdsa to parse the public key and signatures.
It's nice to work with python-ecdsa and get familiar with the library since I have not worked much with Elliptic Curve cryptography.
I definitely learned alot about the framework and how use it.
I hope someone will find help in the textbook implementation of this attack.

Cheers

Niknax