Leanpub: Publish Early, Publish Often

Chapter 5: Digital signatures

Another use for asymmetric algorithms is in digitally signing messages; it is based on the assumptions that only the holder can produce the signature for a given message (i.e. signatures are unforgeable), and that a signature is valid for only a single message. In this chapter, we’ll talk about digital signatures with Ed25519, which we’ll use with Curve25519 encryption keys; ECDSA, which we’ll use with the NIST curves; and RSA. In the algorithms we’ll use here, the message isn’t signed directly; rather, the hash of the message is signed. Sometimes we’ll have to provide the hash of the message ourselves, other times it will be computer for us.

Cryptographic hashing algorithms

We’ve seen hash functions already: SHA-256 was used as part of the HMAC in the symmetric security chapter, and SHA-512 was used as part of the NIST ECDH. We haven’t talked about what they do yet, or when they should be used.

A hash function maps some arbitrary input to a fixed size output. For example, no matter what m is, SHA-256(m) always produces a 32-byte output. In non-cryptographic uses, this is sometimes called a checksum. In cryptography, there are stricter requirements for hash functions, and we only use cryptographic hash functions that satisfy these requirements. In this book, the term “hash function” implies a cryptographic hash function.

The most basic property is collision resistance: for any two messages m¹ and m² where m¹ does not equal m², the hash of m¹ should not equal m². We don’t want two inputs to collide and produce the same hash if they’re not the same.

We also want our hash functions to have preimage resistance. This means that if we have some hash function output x, we shouldn’t be able to find some m that hashes to x. A hash function should be one-way: easy to compute the hash from a message, but infeasible to compute the message from a hash.

Another property is that changing m should result in a change in h(m). h(m) should be indistiguishable from random, which means that an attacker who sees h(m) and h(m') (where m' is any modification, even a single-bit, of m) shouldn’t be able to determine that they came from related messages.

Considering that a hash function outputs a fixed-size output and accepts arbitrary input, there will be some collisions; we accept computationally infeasible as a requirement. A successful attack must occur in time to exploit that attack. On the other hand, a hash function must be computationally efficient and quickly produce a hash from its input.

The hash functions we use in this book are in the SHA-2 family of hash functions, which are named according to the size of the output they produce: SHA-256 produces 32-byte (256-bit) hashes, SHA-384 produces 48-byte (384-bit) hashes, and so forth. The SHA-1 hash is sometimes specified, but there have been attacks on it that make it unsuitable for security purposes. Note that the attacks on SHA-1 do not extend to HMAC-SHA-1; this construction is still thought to be secure. We’ll use the SHA-2 family for consistency, not due to security concerns.

Hashes are often misused; they’ve been used in an attempt to secure passwords or for authentication. What we’ll use them for is to remove structure from some data or to produce an ID from some arbitrary input. In the symmetric security chapter, we used SHA-256 with the HMAC construction to produce an authenticated message ID. In the key exchange chapter, we used SHA-512 to remove some of the structure from the numbers that were produced to make them better suited to use as keys.

The problem with using hashes to secure passwords comes back to the requirement that hashes be efficient. An attacker with a set of hashed passwords can quickly mount attacks aimed at recovering those passwords. In authentication, the way the SHA-2 hashes are constructed leaves them vulnerable to a length extension attack (for an example, see [Duong09]).

Another misuse of hashes is for integrity checks, such as the SHA-256 digest of a file on a download page. This doesn’t provide any authenticity, and an attacker who can replace the download file is likely able to replace the digest: there’s no guarantee that the digest was provided by a legitimate party. HMACs aren’t the right choice either, as anyone with the HMAC key to verify it could produce their own. This is a case where digital signatures are quite useful, so long as the public key is well known. If the public key is just served on the download page and the attacker can swap files on the page, they can swap out the public key.

Forward secrecy

The ECDH key exchange presented us with a problem: how do we trust the public keys we’re receiving? Assuming that we’ve chosen the asymmetric route and have a key distribution and trust mechanism, we have a set of tools for establishing this trust. Our trust mechanism won’t be employed for session keys; these last only the lifetime of a session. Instead, we employ long-term identity keys that are then used to sign session keys. At the start of a session, the session keys are signed and the other side verifies the signature.

A key feature of this arrangement is that the session key and the identity key, are unrelated and will always be separate keys in the systems that we build. In the case of NaCl, they’ll even be different curves. This follows the security principle of using separate keys for authentication and secrecy. If an attacker is able to compromise the identity key, they won’t be able to decrypt any previous sessions using that key. They can use the identity key to sign any future sessions, however.

Identity keys are, by themselves, just numbers. They carry no innate information about the bearer. Using identity keys relies on a well-defined key distribtion plan that maps public keys to identities and provides a mechanism for participants to obtain the appropriate public keys (and, usually, any associated identity metadata). They also need some way to determine how much a key has been trusted. We’ll talk about this problem more in a future chapter, and we’ll see how some real world systems approach the problem. It is a decidedly unsexy problem, but it is critical to a successful secure system.

Let’s consider the scenario where a session encryption key is compromised, and the scenario where an identity key is compromised. In the first case, keys are only in scope for a single session. A compromise here breaks the security of that session, and warrants examining the failure to determine countermeasures and appropriate action. However, the key damage is limited to affected sessions. If an identity key is compromised, the same attention has to be paid. However, there’s usually additional overhead in communicating the compromise to other peers, and getting them to mark the compromised key as untrusted. Depending on the key distribution mechanism, replacing this key may be difficult and/or expensive.

Ed25519

Adam Langley has an implementation of Ed25519 on Github, which is the implementation we’ll use in this book. Ed25519 private keys and signatures are 64 bytes in length, while public keys are 32 bytes. This implementation uses SHA-512 internally to hash the message, and so we pass messages directly to it.

Generating keys is done as with curve25519 keys:

1 pub, priv, err := ed25519.GenerateKey(rand.Reader)n

Signatures are made using the Sign function and verified with the Verify function:

sig, err := ed25519.Sign(priv, message)

if !ed25519.Verify(pub, message) {
       // Perform signature verification failure handling.
}

We’ll prefer Ed25519 signatures in this book: the interface is simple, keys are small, and the algorithm is efficient. Signatures are also deterministic and don’t rely on randomness for signatures; this means they do not compromise security in the case of a PRNG failure, which we’ll talk about more in the section on ECDSA. This property was one of the key motivators for the development of this algorithm.

ECDSA

The elliptic curve digital signature algorithm, or ECDSA, is a signature algorithm that we’ll use with the previously mentioned NIST curves. Just as ECDH is the elliptic curve variant of DH, ECDSA is the elliptic curve variant of the original DSA.

There is a serious weakness in DSA (which extends to ECDSA) that has been exploited in several real world systems (including Android Bitcoin wallets and the PS3); the signature algorithm relies on quality randomness (bits that are indistinguishable from random); once the PRNG enters a predictable state, signatures may leak private keys. Systems that use ECDSA must be aware of this issue, and pay particular attention to their PRNG.

ECDSA signatures usually provide a pair of numbers in the signature called r and s. The most common way to serialise these two numbers is using ASN.1 as defined in [SEC1], and we’ll use this when signing with ECDSA.

type ECDSASignature struct {
       R, S *big.Int
}

func SignMessage(priv *ecdsa.PrivateKey, message []byte) {
       hashed := sha256.Sum256(message)
       r, s, err := ecdsa.Sign(rand.Reader, priv, hashed[:])
       if err != nil {
               return nil, err
       }

       return asn1.Marshal(ECDSASignature{r, s})
}

func VerifyMessage(pub *ecdsa.PublicKey, message []byte, signature []byte) bool {
       var rs ECDSASignature

       if _, err := asn.Unmarshal(signature, &rs); err != nil {
               return false
       }

       hashed := sha256.Sum256(message)
       return ecdsa.Verify(pub, hashed[:], rs.R, rs.S)
}

RSA

RSA is a different type of asymmetric algorithm than the ones we’ve seen so far; it isn’t based on elliptic curves and it is has historically been more weidely used than elliptic curve cryptography. Notably, TLS and PGP both make heavy use of RSA, although elliptic curve cryptography is increasingly used more.

There are two signature schemes for RSA defined in the PKCS #1 standard ([PKCS1]): PKCS #1 v1.5 and the Probabilistic Signature Scheme. These are both signature schemes with appendix, where the signature and message are separate; typically, the signature is appended to the message. In contrast, there are some signature schemes (though not defined for RSA) with message recovery, where the signature verification step produces the original message as a byproduct of the verification.

There have been many vulnerabilities found in various implementations of RSA signatures; the most recent of which is BERserk. Even if the Go implementation is well-written, the libraries used in other components may not be. Go also makes some other proper choices, such as picking an acceptable public exponent. The RSA encryption situation is even bleaker. We’ll prefer to avoid RSA where we can; there’s a lot that can go wrong with it, and it’s difficult to get right. It will be something we use when we need compatibility (like with TLS); in this case, we’ll be following a specification. We’ll also prefer PSS in applications that are written entirely in Go for its stronger security proof ([Lind06], [Jons01]).

RSA signatures with PKCS #1 v1.5 are done using the SignPKCS1v15 function. Likewise, PSS signatures are performed using SignPSS. In both cases, the message must be hashed before sending it to the function. The SignPSS function also takes an rsa/PSSOptions value; this should be defined in your programs as

1 var opts = &rsa.PSSOptions{}

You shouldn’t change any of the opts values unless specifically told to do so by a specification.

The following are example functions that sign using SHA-256 as the hash function.

func SignPKCS1v15(priv *rsa.PrivateKey, message []byte) ([]byte, error) {
       hashed := sha256.Sum256(message)
       return rsa.SignPKCS1v15(rand.Reader, priv, crypto.SHA256, hashed[:])
}

func SignPSS(priv *rsa.PrivateKey, message []byte) ([]byte, error) {
       hash := sha256.Sum256(message)
       return rsa.SignPSS(rand.Reader, priv, crypto.SHA256, hashed[:], opts)
}

Conclusions

Digital signatures provide a useful mechanism in certain scenarios for providing authenticity and integrity, but their use should be weighed against the resulting requirement for public key infrastructure. We’ll prefer Ed25519 as part of the NaCl suite for its robustness against PRNG failures, its simplicity, security, and efficiency. The quality of any libraries used in other languages that are used to build components of the system should also be checked, as they are difficult to get right.

Practical: Sessions with identities

Extend the session example from the previous example to sign the session keys. Keep in mind the need to consider the mechanism for distributing and verifying signature keys. Before writing the code, you should write a security model describing the signature key distribution and verification.