Welcome to the Debugmen blog. We use this site to post tools, security findings, CTF writeups and anything else we find worthy of release to the public.

Tenable CTF: ECDSA Implementation Review

ECDSA Implementation Review

Overview

As the challenge name implies, this problem has to do with the given implementation of Elliptic Curve Digital Signature Algorithm (ECDSA).

They give us a python script that generates a private & public key, two randomly generated hashes to act as hashed data to digitally sign, the signatures of those hashes and finally an flag that’s been encrypted with AES using the private key generated for the ECDSA :

import ecdsa
import random
from Crypto.Cipher import AES
import binascii

def pad(m):
    return m+chr(16-len(m)%16)*(16-len(m)%16)

gen = ecdsa.NIST256p.generator
order = gen.order()
secret = random.randrange(1,order)
 
pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
 
nonce1 = random.randrange(1, 2**127)
nonce2 = nonce1
 
# randomly generate hash value
hash1 = random.randrange(1, order)
hash2 = random.randrange(1, order)
 
sig1 = priv_key.sign(hash1, nonce1)
sig2 = priv_key.sign(hash2, nonce2)

s1 = sig1.s
s2 = sig2.s

print("r: " + str(sig1.r))
print("s1: " + str(s1))
print("s2: " + str(s2))
print("")
print("hashes:")
print(hash1)
print(hash2)
print("")
print("order: " + str(order))
print("")

aes_key = secret.to_bytes(64, byteorder='little')[0:16]

ptxt =  pad("flag{example}")
IV = b'\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0'
cipher = AES.new(aes_key, AES.MODE_CBC, IV)
ctxt = cipher.encrypt(ptxt.encode('utf-8'))

print("Encrypted Flag:")
print(binascii.hexlify(ctxt))

and the program output printing a bunch of the values:

r: 50394691958404671760038142322836584427075094292966481588111912351250929073849
s1: 26685296872928422980209331126861228951100823826633336689685109679472227918891
s2: 40762052781056121604891649645502377037837029273276315084687606790921202237960

hashes:
777971358777664237997807487843929900983351335441289679035928005996851307115
91840683637030200077344423945857298017410109326488651848157059631440788354195

order: 115792089210356248762697446949407573529996955224135760342422259061068512044369

Encrypted Flag:
b'f3ccfd5877ec7eb886d5f9372e97224c43f4412ca8eaeb567f9b20dd5e0aabd5'

Stealing the Private Key

Without much background in how ESDA works I looked up the wikipedia page for it and found that if you use the same k value, then the private key can be recovered.

https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

In this case, k is the nonce1 and nonce2 variables and they are both the same value. 🤔

Furthermore, the wikipedia page also tells you how to recover such private key in this situation. So all thats left to do is recover the private key and use that key as the key to AES decrypt the flag

import ecdsa
import random
from Crypto.Cipher import AES
import binascii
from ecdsa.numbertheory import inverse_mod
import IPython

# The vars given

r = 50394691958404671760038142322836584427075094292966481588111912351250929073849
s1 = 26685296872928422980209331126861228951100823826633336689685109679472227918891
s2 = 40762052781056121604891649645502377037837029273276315084687606790921202237960


h1 = 777971358777664237997807487843929900983351335441289679035928005996851307115
h2 = 91840683637030200077344423945857298017410109326488651848157059631440788354195

n = order = 115792089210356248762697446949407573529996955224135760342422259061068512044369

enc_flag = b'f3ccfd5877ec7eb886d5f9372e97224c43f4412ca8eaeb567f9b20dd5e0aabd5'

# Solve for k
z1=h1
z2=h2

# multiply with the inverse_mod to do 'division' in (mod `order`) space
k = (((z1 - z2) % order) * inverse_mod(s1-s2 ,order)) % order
print('k = ', k)

# mapping it to the vars from the original problem
nonce1 = nonuce2 = k

# Private Key i.e secret

secret = priv_key = (((s1*k) - z1) * inverse_mod(r, n)) % n
print('secret = ', secret)
aes_key = secret.to_bytes(64, byteorder='little')[0:16]

IV = b'\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0'
cipher = AES.new(aes_key, AES.MODE_CBC, IV)
ctxt = cipher.decrypt(binascii.unhexlify(enc_flag))

print(ctxt)
print(binascii.hexlify(ctxt))

and thus, the flag:

flag{cRypt0_c4r3fully}

P.S.

To verify I properly recovered the private key, I inserted the values I calculated back into the original script and got the same signatures which means my key must be the correct.