ECDSA

Elliptic Curve Digital Signature Algorithm (ECDSA)¶

Biased on the ElGamal signature scheme
Good versions should use Deterministic randoms from secure hash functions

The signing encodes a Random Point using the private_key and the message hash. This is proof that the signer know the public key.

Usage¶

Using python-ecdsa:

#Generate Key
from ecdsa import SigningKey
sk = SigningKey.generate()
vk = sk.verifying_key
with open("private.pem", "wb") as f:
	f.write(sk.to_pem())
with open("public.pem", "wb") as f:
	f.write(vk.to_pem())

print(f"Uncompressed Public Key: {vk.to_string('uncompressed').hex()}")
print(f"Compressed Public Key:   {vk.to_string('compressed').hex()}")

#Sign Message
test_message = b"This is a test messsage"
sig = sk.sign(test_message)
print(f"Message:   {test_message}")
print(f"Signature: {sig}")

#Validate Signature
try:
	vk.verify(sig, test_message)
	print("good signature")
except BadSignatureError:
	print("BAD SIGNATURE")

Why the signature works¶

Signature Equation:

\[ s = k^{−1} ∗ (h + r ∗ privKey) \pmod{N} \]

Signature Equalities:

\[ s_1 = s^{-1} \pmod{N} = (k^{−1} ∗ (h + r ∗ privKey))^{−1} \pmod{N} = k ∗ (h + r ∗ privKey)^{−1} \pmod{N} \]

Random Point Equalities:

\[ R_1 = (h * s_1) * G + (r * s_1) * pubKey = (h * s_1) * G + (r * s_1) * privKey * G = (h + r * privKey) * (k ∗ (h + r ∗ privKey)^{−1} \pmod{N}) * G = k * (h + r * privKey) * ((h + r ∗ privKey)^{−1} \pmod{N}) * G = k * G \]

Generating a Keypair¶

The Public Key is a compressed x,y coordinated with a parity bit.
The Private Key is a random 256 bit number with a parity bit.

Generating the Keypair:

# The Private key is just a random number mod the Modulus
private_key = (open("/dev/urandom", "rb").read(30) % N-1) +1
# public_key = private_key * G
public_key = EC_mult(private_key, G)

Signing a Message¶

Calculate the Hash of the message h
Generate a random number range [1..n-1] and store it as the private key
Generate k
- Deterministic-ECDSA, k = HMAC(h + private_key)
- Non Deterministic-ECDSA, k = message_key
Calculate the random point R = k * G
- Set r = R.x
Calculate the signature s = k^{-1} * (h + r * private_key) \pmod{N}
- k^{-1} is where (k * k^{-1}) mod N = 1
Return the signature {r, s}.

Signatures are twice as big as the Private key length. This is because both r and s are the same size as the private key.

Implementation¶

Non Deterministic Signature:

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

### ECDSA
def ecdsa_sign(privateKey, curve_generator, message, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order

	#Hash the message
	hashed_message_int = bytes_to_int(hash_obj(message).digest())

	#Generate Random and make a new Point
	message_privatekey, message_publickey = generate_KeyPair(curve_generator)

	#Get Inverse of the message_privatekey
	inverse_message_privatekey = modinv(message_privatekey, order) 

	#Generate S
	# s = (k^-1 * (hash + (private_mult * x_point_k)) % order ) % order
	s = (inverse_message_privatekey * (hashed_message_int + ( privateKey * message_publickey.x)) % order ) % order

	return {"message_x":message_publickey.x, "signature":s}

if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)

	#Create Signature
	signature = ecdsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_x': 33713788222053272944116994952373133006816574331840523836593195672659427182416, 'signature': 29762850178583845985260513726938610357122753240601859968748061248677808151}

Deterministic Signature:

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

### Deterministic ECDSA
def deterministic_ecdsa_sign(privateKey, curve_generator, message, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order
	public_key = privateKey * curve_generator

	#Hash the message
	hashed_message = hash_obj(curve.name.encode('utf-8') + public_key.compressed() + message).digest()
	hashed_message_int = bytes_to_int(hashed_message)

	#Generate Random and make a new Point
	message_random_int = bytes_to_int(hash_obj(hashed_message + int_to_bytes(privateKey)).digest())
	message_publickey = curve_generator * message_random_int

	#Get Inverse of the message_privatekey
	inverse_message_privatekey = modinv(message_random_int, order) 

	#Generate S
	# s = (k^-1 * (hash + (private_mult * x_point_k)) % order ) % order
	s = (inverse_message_privatekey * (hashed_message_int + ( privateKey * message_publickey.x)) % order ) % order

	return {"message_x":message_publickey.x, "signature":s}

if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)
	#4939898551211325557705050936134227494084736863309989380729247740376583402505 Curve25519: x=15059783236178707571372921326432572117947812618812556902447203212690639774217, y=27261639159700502897208347171409964976166642449687224613599179064654646974491

	#### Deterministic ECDSA
	
	#Create Signature
	signature = deterministic_ecdsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_x': 31021640711082967606874736653412318084900442268616466260267648860639766810380, 'signature': 5394634105920027034974249426205873664623852938893490093540580448939351731001}

	#Check Signature
	verify = deterministic_ecdsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Verifying a Message¶

Calculate the Hash of the message
Calculate the modular inverse of the signature proof s^{-1}.
- s^{-1} is where (s * s^{-1}) mod N = 1
Generate the random point used during signing R = (h * s^{-1}) * G + (r * s^{-1}) * pubKey
- Set r_1 = R.x
Validate that the r_1 from the calculation is the same as the provided r
The general idea of the signature verification is to recover the point R' using the public key and check whether it is same point R, generated randomly during the signing process.

Implementation¶

Non-Deterministic Verify:

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

def ecdsa_verify(public_key, message, signature_obj, curve_generator, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order

	#Hash message
	hashed_message_int = bytes_to_int(hash_obj(message).digest()) % order

	#Use the inverse of the signature
	inverse_signature = modinv(signature_obj["signature"], order) 
	
	#Generate Points from x value
	y_values = curve.find_points_by_x(signature_obj["message_x"])
	points = [Point(point_x=signature_obj["message_x"], point_y=y_values[0], curve=curve), Point(point_x=signature_obj["message_x"], point_y=y_values[1], curve=curve)]
	#print(points)

	#R' = (h * s1) * G + (r * s1) * pubKey
	test_point = (inverse_signature * hashed_message_int) * curve_generator + (((signature_obj["message_x"] * inverse_signature) % order) * public_key)

	#Because of the way this is checked there are two possible public keys. The one that is used and the negative point
	return test_point.x == signature_obj["message_x"]

if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)

	#Create Signature
	signature = ecdsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_x': 33713788222053272944116994952373133006816574331840523836593195672659427182416, 'signature': 29762850178583845985260513726938610357122753240601859968748061248677808151}

	#Check Signature
	verify = ecdsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Deterministic Verify:

from ecc_lib import *
import hashlib
from cryptopals_lib import bytes_to_int, int_to_bytes

### Deterministic ECDSA
def deterministic_ecdsa_verify(public_key, message, signature_obj, curve_generator, hash_obj=hashlib.sha256):
	#Derive Information
	curve = curve_generator.curve
	order = curve.order

	#Hash the message
	hashed_message = hash_obj(curve.name.encode('utf-8') + public_key.compressed() + message).digest()
	hashed_message_int = bytes_to_int(hashed_message)

	#Use the inverse of the signature
	inverse_signature = modinv(signature_obj["signature"], order) 
	
	#R' = (h * s1) * G + (r * s1) * pubKey
	test_point = (inverse_signature * hashed_message_int) * curve_generator + (((signature_obj["message_x"] * inverse_signature) % order) * public_key)

	#Because of the way this is checked there are two possible public keys. The one that is used and the negative point
	return test_point.x == signature_obj["message_x"]

if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)
	#4939898551211325557705050936134227494084736863309989380729247740376583402505 Curve25519: x=15059783236178707571372921326432572117947812618812556902447203212690639774217, y=27261639159700502897208347171409964976166642449687224613599179064654646974491

	#### Deterministic ECDSA
	
	#Create Signature
	signature = deterministic_ecdsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_x': 31021640711082967606874736653412318084900442268616466260267648860639766810380, 'signature': 5394634105920027034974249426205873664623852938893490093540580448939351731001}

	#Check Signature
	verify = deterministic_ecdsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Getting a Public Key from a message and a Signature¶

Using the Signature and the message it is possible to get 0-2 public keys to test.

Implementation:

import base64
from ecdsa import SigningKey, VerifyingKey, NIST256p, BadSignatureError, NIST192p

def fixBase64Padding(s):
	return (s + '=' * (4 - len(s) % 4))

def getVerificationKeyFromData(jwt1, jwt2, hashfunction, curve):
	#Make Hash and Signature of first JWT
	part1      = jwt1.split(".")
	hash_1     = hashfunction(b'' + part1[0].encode('utf-8') + b'.' + part1[1].encode('utf-8')).digest()
	signature1 = base64.urlsafe_b64decode(fixBase64Padding(part1[2]))

	#Make Hash and Signature of second JWT
	part2      = jwt2.split(".")
	hash_2     = hashfunction(b'' + part2[0].encode('utf-8') + b'.' + part2[1].encode('utf-8')).digest()
	signature2 = base64.urlsafe_b64decode(fixBase64Padding(part2[2]))

	#Get Possoble keys from signatures
	vf1 = VerifyingKey.from_public_key_recovery_with_digest(signature1, hash_1, curve=curve, hashfunc=hashfunction)
	vf2 = VerifyingKey.from_public_key_recovery_with_digest(signature2, hash_2, curve=curve, hashfunc=hashfunction)

	#Find the common Key
	for x in vf1:
		if x in vf2:
			return x

Attacks¶

Recovering the Initial Random (k) from Signature will allow recovery of the private key

When the random (m) is the same for two different signatures¶

The Math Behind the attack:

\[ random\_output_1 = (random\_number_1 * G) \\ signature_1 = \dfrac{(random\_output_1 * private\_key) + message_1}{random\_number_1} \begin{aligned} random\_output_2 &= (random\_number_2 * G) \\ &= random\_output_1 * signature_2 \\ &= ((random\_output_2 * private\_key) + message_2) /random\_number_2 \\ \end{aligned} \\ \begin{aligned} signature_1 - signature_2 &= \dfrac{(random\_output_1 * singing\_key) + message_1}{random\_number} - \dfrac{(random\_output_2 * singing\_key) + message_2}{random\_number} \\ &= \dfrac{(random\_output_1 * signing\_key) - (random\_output_2 * singing\_key) + message_1 - message_2}{random\_number} \\ &= \dfrac{ message_1 - message_2}{random\_number} \end{aligned} \newline \newline \begin{aligned} signing\_key &= \dfrac{random\_number * signature_1 - message_1}{random\_output_1} \\ & = \dfrac{message_1 * signature_2 - message_2 * signature_1}{random\_output_1} \\ & = \dfrac{signature_1 * \dfrac{message_1 - message_2}{signature_1 - signature_2} - message_1}{random\_output_1} \\ & = \dfrac{\dfrac{message_1 - message_2}{1 - signature_2} - message_1}{random\_output_1} \\ & = \dfrac{\dfrac{message_1 - message_2}{1 - signature_2} - \dfrac{message_1 - message_1 * signature_2)}{1 - signature_2}}{random\_output_1} \\ & = \dfrac{ message_1 * signature_2 - message_2}{random\_output_1 - signature_2} \\ \end{aligned} \]

Implementation:

from ecdsa import SigningKey, VerifyingKey, NIST256p, BadSignatureError, NIST192p
from ecdsa.util import sigdecode_string
from ecdsa.numbertheory import inverse_mod
from ecdsa.ecdsa import Private_key, Public_key, Signature

def generateSigningKey(hash_1, signature1, hash_2, signature2, verify_key):
	N = verify_key.curve.order

	#Get the subtraction of the hash values
	hash_sub = int.from_bytes(hash_1, 'big') - int.from_bytes(hash_2, 'big')

	#Split signature into r,s
	rand1, sign1 = sigdecode_string(signature1, N)
	rand2, sign2 = sigdecode_string(signature2, N)

	#Start Math
	#Get the subtraction of the s values
	signature_sub = sign1 - sign2

	#Get the Multiplicative Inverse Mod N
	signature_sub_inv = inverse_mod(signature_sub, N)

	#Multiply the values
	#k = (s1 – s2)-1(H(m1) – H(m2))
	key = (hash_sub * signature_sub_inv) % N

	#Get Inverse to generate the private exp
	key_inv = inverse_mod(rand1, N)

	#d = (((s1 * k - h1) % N) * r_inv) % self.n
	priv_exp = (((sign1 * key - int.from_bytes(hash_1, 'big')) % N) * key_inv ) % N

	print()
	print(f"K: {key}")
	print(f"X: {priv_exp}")

	priv_key = SigningKey.from_secret_exponent(priv_exp, curve=verify_key.curve)
	pub_key = priv_key.get_verifying_key()

	if pub_key.verify_digest(signature1, hash_1):
		return priv_key

	else:
		print("Bad Signature")

#priv_key = generateSigningKey(hash_1, signature1, hash_2, signature2, verify_key)

Bad Randomness in Nonces¶

Papers:
- Lattice Attacks againstWeak ECDSA Signatures in Cryptocurrencies
- LadderLeak attack
- LadderLeak attack

Timing Attacks Leaking the random (k)¶

Since the random is multiplied with the generator. And Multiplication uses the plus, square method you can leak the binary data of the secret.

Signature Malleability¶

Signature Malleability is if the signature integer is not checked that it is between 0 and the order of the curve. Because the integer is modded you can have a lot of numbers for the

Example of How it works

Zero Padding¶

If there is zero padding in the bytes form of the data then it will output the same number which is still the same number

Example:

#from pycoin.ecdsa import secp256k1_generator, sign, verify
from pycoin.ecdsa.secp256k1 import secp256k1_generator
import hashlib, secrets, pycoin 
from cryptopals_lib import bytes_to_int, int_to_bytes

#print(dir(secp256k1_generator))

def sha3_256Hash(msg):
	hashBytes = hashlib.sha3_256(msg.encode("utf8")).digest()
	return int.from_bytes(hashBytes, byteorder="big")

def signECDSAsecp256k1(msg, privKey):
	msgHash = sha3_256Hash(msg)
	signature = secp256k1_generator.sign(privKey, msgHash)
	return signature

def verifyECDSAsecp256k1(msg, signature, pubKey):
	msgHash = sha3_256Hash(msg)
	valid = secp256k1_generator.verify(pubKey, msgHash, signature)
	return valid

if __name__ == '__main__':
	# ECDSA sign message (using the curve secp256k1 + SHA3-256)
	msg  = "Message for ECDSA signing"
	msg2 = "Message with different data"

	#Generate Random Number between 0, Generator Order
	privKey = secrets.randbelow(secp256k1_generator.order())
	pubKey = secp256k1_generator.raw_mul(privKey)
	signature = signECDSAsecp256k1(msg, privKey)
	print("Message:", msg)
	print("Private key:", hex(privKey))
	print("Signature: r=" + hex(signature[0]) + ", s=" + hex(signature[1]))

	# ECDSA with prepadded signature data
	sig2 = [int_to_bytes(signature[0]), b"\x00\x00" + int_to_bytes(signature[1])]
	sig2 = [bytes_to_int(sig2[0]), bytes_to_int(sig2[1])]
	valid = verifyECDSAsecp256k1(msg, sig2, pubKey)
	print("\nMessage:", msg)
	print("Signature: r=" +  hex(sig2[0]) + ", s=" + hex(sig2[1]))
	print("Signature valid?", valid)

"""
Message: Message for ECDSA signing
Private key: 0x6d193a1a2b66676b983a59a02438d7d913810865d694455ccda94c656719e410
Signature: r=0xfb60b669b2b68d7a4e23512dad6afea14a18cfd8716ceccd70f17575063fc2a4, s=0x7b5f23a85d65d5f5cfce32c692dc1e52976af586807a1669d3581b9eb2e14658

Message: Message for ECDSA signing
Signature: r=0xfb60b669b2b68d7a4e23512dad6afea14a18cfd8716ceccd70f17575063fc2a4, s=0x7b5f23a85d65d5f5cfce32c692dc1e52976af586807a1669d3581b9eb2e14658
Signature valid? True
"""

Duplicate signatures¶

ECDSA is mathematically malleable as well. It consists of two values (r, s) and given one signature it is trivial to calculate a new s' (equal to the order minus the original s) which results in a new valid signature (r, s') over the same message.

Example:

if __name__ == '__main__':
	message = b"Test Message"

	#Generate KeyPair
	privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point)
	print(privateKey, public_point)

	#Message Information
	#Hash Library

	#Create Signature
	signature = ecdsa_sign(privateKey, Curve25519_Generator_Point, message)
	print(signature)
	#{'message_x': 28976191879944715029002043232329621948852541633267460398860125146443746557606, 'signature': 4980853891321906837859819475022323023771859670224468501147526911371058887087}

	#Check Signature
	verify = ecdsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

	#Test Duplicate Signature
	# s = n - s
	signature["signature"] = Curve25519_Generator_Point.curve.order - signature["signature"]
	verify = ecdsa_verify(public_point, message, signature, Curve25519_Generator_Point)
	print(verify)
	#True

Invalid Curve Parameters¶

If a client or server just accepts any curve messing with the parameters can make decryption easy.

Lattice Attacks¶

https://eprint.iacr.org/2019/023

CVE-2022-21449: Psychic Signatures¶

https://neilmadden.blog/2022/04/19/psychic-signatures-in-java/

Many error happened to make this bug.
1. No error checking if r >= 1 and s >= 1. Also no checking that r < n and s < n
2. No check with fermats therum to create the inverse of s.
3. No check that the point is the infinity point.

When the r = 0 or s = 0 then there is the possibility that the modular inverse will be incorrect.

2 Party Signing (Lindell17)¶

Alice generates a random x_1 and a secret key k_1.
Bob generates a random x_2 and a secret key k_2.
Bob encrypts x_2 to and sends it to Alice
Alice using hobomorphic encryption to interact with Bobs x_2 to generate Enc((k_1^{-1} % l) * (msg + x_1 *x_2))
This is sent to Bob to finish the signature. He decrypts the blob (k_1^{-1} % l) * (msg + x_1 *x_2).
Then finalizes the signature s = k_2^{-1} * (k_1^{-1} % l) * (msg + x_1 *x_2) % l
Check the signature

Attack¶

By setting the k_1 to a custom value the target leaks if k_1 is divisible by x_2. For example if k_1 is 2 then you get the LSB of x_2.

Extracting the ith bit:

\[ k_1 = 2^i offset = (k_1^{-1} \mod{l} - k_1^{-1} \mod N) * (msg + x_1 * partial_x_2) \]

ECDSA

Elliptic Curve Digital Signature Algorithm (ECDSA)¶

Usage¶

Why the signature works¶

Generating a Keypair¶

Signing a Message¶

Implementation¶

Verifying a Message¶

Implementation¶

Getting a Public Key from a message and a Signature¶

Attacks¶

When the random (m) is the same for two different signatures¶

Bad Randomness in Nonces¶

Timing Attacks Leaking the random (k)¶

Signature Malleability¶

Zero Padding¶

Duplicate signatures¶

Invalid Curve Parameters¶

Lattice Attacks¶

CVE-2022-21449: Psychic Signatures¶

2 Party Signing (Lindell17)¶

Attack¶

2+ Party Signing (GG18/GG20)¶