A commitment scheme can protect the integrity of transmitted data, but it does not attest to its authenticity. Put another way, we need a mechanism to allow the sender to endorse the transferred data and for the receiver to verify this is indeed the case. The solution is to use digital signatures.

Brief recap on digital signatures

As mentioned in our previous article, digital signatures rely on public key cryptography and every user is responsible for generating their own key pair:

• Public key P
• Private key d

As the names suggest, the public key can be shared with others and the private key should be kept secret.

Digital signature interface. There are two interfaces that are implemented by a digital signature scheme:

σ = SignMessage(d, m) // m is the message, and σ is the signature
bool = VerifySignature(σ, P, m) // returns TRUE or FALSE

Both signing and verification is a straight-forward process. The signer generates a signature σ for message m, using their private key d. Both the signature σ and message m is sent to the receiver and the private key is not sent. The receiver can verify the message was indeed signed by the public key P.

Authenticating the public key

There is a classical bootstrapping issue. The receiver needs to retrieve a copy of the signer’s public key and link it to an identity. For example, the receiver may want to verify a signature from a website’s domain or identify a customer’s payment if they pay an invoice using Bitcoin.

There a few ways to solve the authentication issue:

• Physical exchange of public keys. All parties can meet each other in real-world to swap public keys.
• Public key infrastructure certificate. Each client has a certificate and it is endorsed/signed by a trusted authority. This forms a hierarchical tree of certificates.
• Password-authenticated exchange. A public key is associated with the counter-party if they can prove knowledge of a password.
• Unique address per sender. Some cryptocurrency exchanges generate a unique receiving key (Bitcoin address or Ethereum account) for every customer on their website. If a customer sends funds to the address, then the exchange can link the payment to their account on the service.

The ability to connect meat-space to digital space will always remain difficulty and authentication is one field that may always rely on some form of trust to make it work.

There is some interesting work that started with NameCoin and continued with the Ethereum name service. A smart contract can be used as a registrar to link public keys to a human readable name and we can rely on informal processes like a twitter account to authenticate it. The classical example is to look up vitalik.eth which belongs to Vitalik Buterin.

Goals and security properties

The security goal for a digital signature is to fend against forgeries:

• Security against existential forgery under an adaptive chosen message attack

This is the strongest security property possible for a digital signature scheme. It assumes the adversary lacks access to the signer’s private key, but they can force the signer to:

• Sign any message,
• Sign at any time,
• Repeat signatures millions of times,

Assuming the property holds up, the adversary cannot extract the signer’s private key nor can they forge a single signature, even if it the forgery is attempted on an arbitrary and gobbledygook message. Of course, real-world written signatures cannot fend against such an attack.

In layman terms, there are also other properties that a signature scheme should provide:

• Authentication. Anyone can verify the associated public key has indeed digitally signed the message.
• Integrity of message. No one can tamper with the message that was signed, especially during transit.
• Non-repudiation. The signer cannot deny their private key has signed the message.

If you would like to learn more, I recommend the wikipedia article as a great place to start.

Randomness is the Achille’s heel

The Elliptic Curve Digital Signature Algorithm (ECDSA) remains the most popular digital signature scheme used by cryptocurrencies. We do not plan to dive into the mathematics, but there are some gotchas for developers to consider. We will not dive into the mathematics, it is relatively simple and the linked articles do a better job.

Every digital signature relies on a fresh source of cryptographic randomness to protect it against attackers. For example, an ECDSA signature has two components:

σ = (r,s), where “r” is the random nonce and “s” is the signature.

The random nonce r is publicly visible to all. If the signer re-uses the same r for more than one signature, then it is trivial to break the signature and derive the private key. I recommend checking slide 51 for how to break it.

There are several examples of attackers extracting the private key from a signature (especially for EDSA) because the signer relied on a poor random number generator:

• PS3 digital signature. The signer always used the same random number and has led to the meme “return 4” meme.
• Bitcoin wallets on Android. In 2013, the random number generator on Android was broken. Bots found vulnerable signatures on the blockchain and extracted the private key to steal the bitcoins.
• Brain wallets. Some people used human-readable words like “bitcoin” as opposed to cryptographic randomness.

Even if the random number is not the same, it is still possible to extract the private key and forge signatures if a relationship between the random nonces used by the signer can be found.

The solution implemented by most wallets is to rely on:

• Cryptographic randomness to generate the private keys for the wallet (BIP32),
• Produce a random nonce for signing in a deterministic manner using hash functions in RFC6979.

Essentially, it assumes the signer can have access to a single random source for generating the private keys. This single random source can be used with a hash function to continuously extract unpredictable and cryptographic randomness. To work, it relies on the pre-image resistance property of a hash function.

Key point: If you rely on Math.random() to generate randomness, then do not tell people you took this class!!!