Link to this headingElliptic Curve Digital Signature Algorithm (ECDSA)

  • Biased on the [ElGamal](/Crypto/Asymmetric Encryption/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.

Link to this headingUsage

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")

Link to this headingWhy 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

Link to this headingGenerating 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)

Link to this headingSigning a Message


    

  1. Calculate the Hash of the message h
    2. 

  2. Generate a random number range [1..n-1] and store it as the private key
    3. 

  3. Generate k

      

    • Deterministic-ECDSA, k = HMAC(h + private_key)
      • 

    • Non Deterministic-ECDSA, k = message_key
      • 

    

    4. 

  4. Calculate the random point R = k * G

      

    • Set r = R.x
      • 

    

    5. 

  5. Calculate the signature s = k^{-1} * (h + r * private_key) \pmod{N}

      

    • k^{-1} is where (k * k^{-1}) mod N = 1
      • 

    

    6. 

  6. Return the signature {r, s}.
    7. 



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.


Link to this headingImplementation


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


Link to this headingVerifying a Message


    

  1. Calculate the Hash of the message
    2. 

  2. Calculate the modular inverse of the signature proof s^{-1}.

      

    • s^{-1} is where (s * s^{-1}) mod N = 1
      • 

    

    3. 

  3. Generate the random point used during signing R = (h * s^{-1}) * G + (r * s^{-1}) * pubKey

      

    • Set r_1 = R.x
      • 

    

    4. 

  4. 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.
    5. 



Link to this headingImplementation


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

Link to this headingGetting 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


Link to this headingAttacks


    

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



Link to this headingWhen 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)

Link to this headingBad Randomness in Nonces


Papers:



Link to this headingTiming 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.


Link to this headingSignature 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


Link to this headingZero 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
"""

Link to this headingDuplicate 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


Link to this headingInvalid Curve Parameters


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


Link to this headingLattice Attacks


Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

CTF Describing the Attack

Lattice ECDSA Attack PoC


    

  • Needs atleast 4 LSB or MSB bits set
    • 



Link to this headingCVE-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. 

  2. No check with fermats therum to create the inverse of s.
    3. 

  3. No check that the point is the infinity point.
    4. 



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


Link to this heading2 Party Signing (Lindell17)


    

  1. Alice generates a random x_1 and a secret key k_1.
    2. 

  2. Bob generates a random x_2 and a secret key k_2.
    3. 

  3. Bob encrypts x_2 to and sends it to Alice
    4. 

  4. Alice using hobomorphic encryption to interact with Bobs x_2 to generate Enc((k_1^{-1} % l) * (msg + x_1 *x_2))
    5. 

  5. This is sent to Bob to finish the signature. He decrypts the blob (k_1^{-1} % l) * (msg + x_1 *x_2).
    6. 

  6. Then finalizes the signature s = k_2^{-1} * (k_1^{-1} % l) * (msg + x_1 *x_2) % l
    7. 

  7. Check the signature
    8. 



Link to this headingImplementation


Link to this headingAttack


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)


Link to this heading2+ Party Signing (GG18/GG20)