Deterministic Digital Signature Algorithms

In practice we see a need for caution and care around the commitment part of a signature. If the commitment secret is duplicated for different messages, then the signing key secret for that key can be recovered. When an attacker holds the key, they may impersonate the honest key holder and defeat the security of the scheme that relies upon that authenticity.

If you are unfamiliar with some of the vocabulary in this section, see Elliptic Curve Digital Signature Algorithms. When I mention "recovered", consider it equal to "leaked" or "stolen."

The security of a signature scheme requires that all commitment secrets be unique (at least as far as distinct messages go). One way to do this is to record information that changes over time, called state. It could be a counter or a collection of all previously issued commitments. Unfortunately, state in this scenario requires consistency for any application that holds the private key. Also, maintaining a set of all commitments that can be efficiently searched is difficult at scale. An alternative is to partition counters such that each signer has a reserved counter space, so other signers will not accidentally duplicate commitment secrets that will collide.

If this is starting to sound over engineered, that is because it is.

Instead, we have a cryptographic tool which is collision-resistant. Cryptographic hashes or message digests exist to fill the role of what is called a "random oracle." In computer science theory, an oracle is something that gives an answer, and a random oracle gives a random answer which has never been seen before. Replying with a pre-existing signature does not reveal more information about the secret key. By definition something that has never been seen before cannot collide with previous answers.

We deem a hash function as broken when a collision is found. MD5 is easily broken, and SHA-1 (see shattered) can be broken with sufficient money and server time.

One more computer science thing to mention: we generally do not care if a message is verified twice. The verifier will not be able to determine if a signer had signed the same message again or replied with a saved signature when the message is the same. Because of that, it is safe to use deterministic signatures which use deterministic commitments.

To create a deterministic commitment secret with a hash function, we need to maintain one important requirement: the hash digest used to create the commitment secret must be unguessable. Also, the public form of the commitment which goes into the signature should not reveal the commitment secret.

If you see that the commitment for any signature repeat for a different message or key: that is a strong sign that something is wrong! Examples of this are on the blockchain.

Ed25519 uses the message and part of a SHA-512 hash of the signing secret key to create a deterministic commitment secret and then the commitment is made from that commitment secret. Because secret bits of sufficient entropy were added to the hash of the message, it is too difficult to guess or reverse what the commitment secret is.

Deterministic ECDSA (RFC6979) uses a unique approach to probe for safe commitment secrets using HMACs. The message and signing secret key are mixed together with HMACs to create a possible commitment secret. If the commitment secret is unsatisfactory, it probes for another value with a deterministic algorithm. For example, a commitment secret of all 0’s is unsatisfactory.

A deterministic commitment secret protects the secret signing key from being recovered. This protection relies on the collision resistance property we get from cryptographic hashes. Besides key generation, the commitment secret generation part of digital signatures is the only probabilistic part of creating a signature. By replacing the commitment secret probabilistic process with a deterministic process, the complete signature process for a pre-existing key becomes deterministic.

Deterministic signatures remove the risk of exposing a secret signing key when commitment secrets could be misused. This provides a defense against application developer ignorance (like Sony) and poor randomness from the environment (like some transactions on the blockchain).

An interesting consequence of Ed25519’s design: since the secret scalar is derived from the first 256 bits of the SHA-512 hash and the secret commitments are made from the other 256 bits, if the secret scalar were leaked but not the private key then signatures made with a stolen secret scalar must be different from honest signatures for messages that have not been honestly signed before.

However, a verifier cannot tell the difference between the impersonator and the honest signer since the commitment is made from secret information.