Still using ECDSA? Think again, and consider EdDSA

Still using ECDSA? Think again, and consider EdDSA

One major change within the time of our pandemic is the usage of electronic signatures on documents. Increasingly the usage of our wet-signature methods is receding. But, the alternatives are often DocuSign and pasting images of your signature in a document. These methods have very little credibility and can be seen as “fake digital”, and where it would be almost impossible for someone to actually prove that someone else actually digitally sign something. The highest level of security that DocSign brings is that someone has received an email, but, as we all know, email is not exactly the most trustworthy method of proving anything.

So what’s the alternative? Well, Bitcoin uses ECDSA (Elliptic Curve Digital Signature Algorithm), and where a Bitcoin owner signs a transaction with their private key. Satoshi possibly chose it to avoid the existing patents around the Schnorr signature method. But it is a well-known that sloppy implementation of ECDSA [here] can lead to many digital signing problems. Along with this, many experts just do not trust NIST in defining curves that are free from flaws. Finally, Curve 25519 is seen to be a more secure curve than the NIST-defined P-256 curve.

At the core of security of ECDSA is the usage of a strong random number generator. Any weaknesses in this can lead to the private key being leaked. Along with this, there have been many side-channel attacks on ECDSA. Within the Sony Playstation 3, a flaw allowed for the recovery of the private key from a signature and allowed others to sign updates with Sony’s private key. There have also been weaknesses in Java for the generation of random numbers, and which led to the leakage of Bitcoin private keys on some Android apps. Other problems include nonce reuse [here] and when a nonce value is revealed [here].

To overcome the problems of ECDSA, we can use EdDSA, and which uses SHA-512 and Curve 25519 (created by Daniel J Bernstein) to give the Ed25519 method.

Key generation

Alice generates a random 32-byte secret key (sk) and then creates a public key of:

pk=sk⋅G

and where G is the base point of the curve.

Signing

Alice creates a SHA-512 hash of her private key:

h=HASH(sk)

Create r from the upper 32 bytes of hash and the message:

r=HASH(h[32:]||m))

And where “||” represents a concatenation of the byte array values. Next, she matches r onto curve with:

R=r⋅G

Next Alice compute s with:

s=r+(HASH(R||pk||m))⋅sk

The signature is (R,s). The values of R and s are 32 bytes long, and thus the signature is 64 bytes long.

Verifying

Bob creates S using R, pk and m:

S=HASH(R||pk||m)

And next creates two verification values:

v1=s⋅G

v2=R+pk⋅S

If v1==v2 the signature checks. This is because:

v1=sG=(r+(HASH(R||pk||m))⋅sk)⋅G=rG+sk⋅G⋅(HASH(R||pk||m))=R+pk⋅S

Overall, we just need point multiplication and point addition. The following is an outline of the code [here]:

from basic import (clamp,bytes_to_scalar, scalar_to_bytes,bytes_to_element, Base,B)
import hashlib, binascii
import os
import sys

def HashIt(m):
    return hashlib.sha512(m).digest()

def publickey(sk):
    # turn first half of SHA512(seed)
    a = clamp(HashIt(sk)[:32])
    A = Base.scalarmult(a)
    return A.to_bytes()

def HashToInt(m):
    h = HashIt(m)
    return int(binascii.hexlify(h[::-1]), 16)

def signature(m,sk,pk):
    h = HashIt(sk[:32])
    a_bytes, inter = h[:32], h[32:]
    a = clamp(a_bytes)
    r = HashToInt(inter + m)
    R = Base.scalarmult(r)
    R_bytes = R.to_bytes()
    S = r + HashToInt(R_bytes + pk + m) * a
    return R_bytes , scalar_to_bytes(S)

def verify(pk, sig, msg):
  R = bytes_to_element(sig[:32])
  A = bytes_to_element(pk)
  S = bytes_to_scalar(sig[32:])
  h = HashToInt(sig[:32] + pk + m)
  v1 = Base.scalarmult(S)
  v2 = R.add(A.scalarmult(h))
  if (v1==v2): return (True)
  return False

print (f"Base point: {B[0]},{B[1]}")

sk=os.urandom(32)
pk=publickey(sk)
print (f"\nPrivate key: {binascii.hexlify(sk)}\nPublic key: {binascii.hexlify(pk)}")

m="Hello"

if (len(sys.argv)>1):
  m=str(sys.argv[1])

m=m.encode()

print(f"\nMessage: {m.decode()}\n")

R,s=signature(m,sk,pk)
print (f"\nSignature\nR: {binascii.hexlify(R)}\ns:{binascii.hexlify(s)}")

sig=R+s
ver=verify(pk,sig,m)
print ("\nVerified: ",ver)

A sample run is [here]:

Base point: 15112221349535400772501151409588531511454012693041857206046113283949847762202,46316835694926478169428394003475163141307993866256225615783033603165251855960

Private key: 53b7ba00b4eb1b9ef4b160f80aeb75b300b709e15eb5aba5079e362a1a39e39e
Public key: 7ec476332a76d264f6553a2881b04a3f8b685542b3bf2e25213856166dc70c1f

Message: Hello

Signature
R: f46add9cfc1dce483548deeb3d533d0531dfcc17d292cfe2d90acd9380767e0b
s: f557d36cb3484d0dd2fbaec886560cb2983225299e80929d442042be74a84305

Verified:  True

And the full code is here:

Conclusions

Well, the advice is … for new digital signing applications you should use EdDSA instead of ECDSA.

Here are some tests on EdDSA: