Ethereum Digital Signatures
- Digital Signatures
- Details of ECDSA Signatures
- ECRecover and Signature Verification in Ethereum
- ECDSA Malleability
If you are a cryptographer, the concept of Digital Signature will be as familiar to you as wooden blocks are to a toddler.
If you are a developer, and you’ve done any work requiring some sort of authentication, chances are you have at least heard the term. You may even glance over them and not give a second thought.
And yet, like any other crypto technique, we can easily fall into a trap when implementing them in a real piece of software, and especially in blockchain.
Today, I start a new series on Digital Signatures, how they are used in Ethereum and Bitcoin, and why.
What is a Digital Signature?
Digital signatures are one of the basic building blocks of modern cryptography, on par with encryption schemes and hash functions. You can think as each of these blocks as providing very specific services.
Encryption is like putting a letter inside an opaque envelope. It provides confidentiality of messages, which intuitively means only the intended recipient can read an encrypted message.
Hashing is like sealing the envelope after you put the letter in. A Hash functions provide integrity, evidence that no one tampered with a document.
You can associate a plain text (eg a mail message, a written document, any digital file, etc) with a hash that is distributed separately. You can now use the hash to detect accidental corruptions of the original text, by hashing your version and checking if that matches the published hash.
But you can’t use hashes to protect against an attacker. There is no secret in the computation of a hash, so a hacker who wants to change a document, for example infecting it with a virus, would try to change the hash protecting it as well.
The Purpose of Digital Signatures
This is where digital signatures come in. A digital signature is like a hash, in that it provides integrity: protection against unintentional change. But it gives more than that.
Digitally signing is like adding a signature to your letter before (or after, but let’s not quibble over details) you put it in the envelope.
Mathematically, a signature is a function of the document you want to sign, plus some private information, a signing key. And because this key is required and secret to the signing key owner, the digital signature provides also authenticity.
It goes even beyond this. The other side of the medal is that when you sign something, you are the only person who could have done it, and so you can’t claim that signature is forged. This is non-deniability (or non-repudiation), and ensures that a party cannot walk away from a bad contract they signed in bad faith.
Of course, in the real world there are complications to this ideal model, mainly around how you bind a public key to a real world identity. But that is not a matter for this post and neither this blog. I leave you with some references here. For now, let us just understand how digital signatures work and then see the particular one used by Ethereum.
How Do Digital Signatures Work?
Digital signatures are public-key schemes composed of 3 main algorithms described below. When a signature scheme is deployed in practice, it is common to have some public parameters generally known and fixed in stone.
The structure of these parameters vary with each scheme. For example, they could be a specific elliptic curve. Or a prime indicating the order of a group.
In a specific deployment, these will be known by everyone and assumed as inputs to every algortihm below.
Key Generation (KEYGEN)
This generates a public-key pair, composed of:
- a signing key SK, that is given to the signer and must be kept secret from everyone else. This is also called the private key.
- a verification key VK, that is public and widely distributed, in a way that it uniquely links the key itself to the identity of the signer. This is also called the public key.
Signature Generation (SIGN)
Signature generation requires as inputs a signing key SK and a message m. Typically the message can be any binary string, of any unbounded length (or in other words, any sequence of bytes).
The signing key has a very definite structure, dictated by the particular signature scheme. It may not be just any sequence of bytes.
The result of the signature is another message (sig), also with a definite structure and usually of fixed size, that is determined by the scheme definition.
Signature Verification (VERIFY)
Similarly to the real world, we want to verify if a digital signature attached to a document was created by a specific entity.
This is done by the verification algorithm, which takes three arguments: the signature sig, the purported message m that was signed, and the identity of the signer, or rather, its verification key VK. The result is either YES or NO (or more usually, 1 or 0).
Properties of a Digital Signature Scheme
Any digital signature scheme to be used in practice must have two properties. The first one is basic, and it ensures the scheme works.
The second one is an aspiration, and it simply says the scheme must be secure.
Correctness
This is the simple one, it just says that the scheme must be correctly implemented.
By definition, if a message is signed by a certain secret key SK, the verification with the corresponding verification key VK always returns YES:
KEYGEN() --> (SK, VK)
VERIFY ( SIGN ( m, SK ), VK ) = YES
If the verifying key does not match the one used to produce the signature, or if indeed the signature corresponds to a different message, then the verification will return NO.
Security
The security property of a digital signature is broadly an aspirational one. In practice we only want to use “secure things”, but this must be made somehow concrete.
It’s not enough to claim “it is secure because it’s quite complex, and I don’t understand it” or “it is secure because it was created by the government, Microsoft or some very good hackers”.
We must first define a security model, which typically specifies what we believe the scheme is secure against. The most widely-used definition in academia states that no one is able to produce a valid signature sig for a message m under signing key SK if they don’t know this key.
This should be the case even when the attacker has access to an arbitrary list of pairs (m’, sig’) that are valid for the same signing key. This is a very powerful adversary!
Once you have this target in place, there are only two ways I know of convincing yourself something is secure:
- let it be attacked or analysed by competent, determined and well-funded attackers
- provide a formal proof of security showing that if an attacker can forge a signature, then it can also create some major breakthrough in maths or computer science.
Parting Thoughts
This is enough for today. But before you go, remember a couple of main points.
A digital signature only has any power as long as the signing key is kept private. The signing algorithm is such that any change in the key or the input data will unpredictably change the output (the signature).
For each signing key there is exactly one valid verification key. Said another way, if a signature is valid under some verification key, it must have been produced by the corresponding signing key, and therefore by its owner.
In the next post, I’ll dive into the ECDSA algorithm that is used to provide signatures in Bitcoin and Ethereum.
See you then.