Digital signatures

How does one prove that a file (or some buffer) was generated by a well-known entity, and not tampered?
In the physical (human) world, we sign checks and contracts, but those can easily be forged.
In this blogpost, we're going to explore the main ideas behind digital signatures.
At this point, we've had quite a few cryptography blogposts already, I will be heavily relying on my previous RSA and ECC blogposts.

High-level ideas

We refer to the contents of a file or a buffer that we wish to sign as a message.
The idea is to concatenate something to the message - that "something" is called a signature.
In addition, we will be relying on the idea of public and private keys - the concept is explained in my RSA blogpost.
Thus:

• We want to create a procedure that gets a message and a private key and generates a signature, and we call this procedure sign.
• We want to create a procedure that gets a message and a signature, and uses a public key (assumed at this point to be trusted) that validates the signature indeed correctly signs the message. We will call that procedure verify.

In this blogpost, I will be sharing two methods commonly used to sign messages: one with RSA and one with Elliptic Curves.

Digital signatures with RSA

As a reminder, in RSA we have a private key we refer to as d, and a public key we refer to as e.
Those are two numbers that "magically" (mathematically, really) ensure that $(m^d)^e = m (mod n)$ for a message m (within a certain range).
Usually, we use the private key for encryption and public key for decryption, but note we can do it the other way around: $(m^d)^e = (m^e)^d (mod n)$.
Therefore, if we have a message m, we could sign it like this: $m^d (mod n)$, thus creating the message m || sign(m).
The receiver cannot easily derive d from the signature, but there are some issues with that approach:

1. The message m cannot be arbitrarily long - since we treat it as a number, it must be strictly lower than n (commonly 4096 bits).
2. There is a multiplication issue - assuming two messages m1 and m2, an attacker could sign their multiplication: $sign(m_1 \cdot m_2) = m_1^d \cdot m_2^d = sign(m_1) \cdot sign(m_2)$! Note the attacker only needed to collect the signatures, and does not know the private key.

Using Cryptographic hash functions

To deal with those issues (and others), we use a cryptographic hash function, which we will mark as h and is assumed to be a one-way-function:

• The function h is easy to compute for an arbitrary input - calculating $h(x)$ should not be computationally expensive.
• The function h is hard to reverse - given a value y, it's hard to find an x such that $h(x) = y$.
• It's hard to collide function h - given $h(x)$, it's hard to find y different than x such that $h(x) = h(y)$.
• The output of function h has a constant output size for all inputs.

The last point might seem contradictory to the collision requirement - we have infinite numbers of inputs and only a finite set of outputs, which guarantees that collisions exist.
However, the collision requirement discusses complexity rather than impossibility - i.e. practically it'd take a lot of computation power to find a collision.
An example of a hash function used these days is SHA2. I might one day write about the inner workings of the SHA hash function family.

Signing and verifying

Armed with the knowledge of cryptographic hash functions, let us slightly redesign our signing algorithm - instead of signing m, we will sign the hash of m!
The verifier could then use our public key and get the hash of the signature. After that - the verifier cannot undo the hashing (it's supposed to be a hard problem!) but rather than that - hash m and compare.
Let's code that! Note we will have to convert data from bytes to numbers and back. Here's what I coded:

import hashlib

def sign(d, n, m):
    """
        Signs message m with the private key (d, n).
    """

    # Hash the message and convert the hash to a number
    hash_val = hashlib.sha256(m).digest()
    hash_val = int.from_bytes(hash_val, byteorder='little')

    # Create the signature and convert it into bytes
    signature = pow(hash_val, d, n)
    signature = signature.to_bytes(length=n.bit_length() // 8, byteorder='little')

    # Return signature
    return signature

def verify(e, n, m, signature):
    """
        Verifies the message m with the given signature and the public key (e, n).
    """

    # Convert signature to a number
    signature_val = int.from_bytes(signature, byteorder='little')

    # Decrypt the signature with the public key
    alleged_hash_val = pow(signature_val, e, n)

    # Hash the message and convert it into a number
    hashed_message = hashlib.sha256(m).digest()
    hashed_message_val = int.from_bytes(hashed_message, byteorder='little')

    # Compare the two
    return alleged_hash_val == hashed_message_val

Don't believe me? Test it!
You can easily generate an RSA keypair and sign an arbitrary message.

ECDSA

Moving on, we could use Elliptic Curves for digital signatures!
That method is known as ECDSA and relies on the Discrete Logarithm problem on Elliptic Curves.
As a side note, this method is similar to a previous method called DSA which is rarely used today - that's why I jump straight to ECDSA.
In addition, there is a mre "modern" variant called EdDSA which works on something called twisted Edwards curves - sadly, I am not knowledgeable enough to post about them, so I leave the link as a reference and move on.
Unlike the RSA approach - here's things are way more complicated. Let's understand why (hand wavy):

• In RSA, encryption and decryption use the same operation - we work by exponentiation over large numbers in a large finite Field. We say that the exponantiation operation is Commutative - and use that to our advantage.
• In Elliptic Curves, our private key is very different from our public key - our private key is a scalar, but our public key is a point on a curve! We do not have a similar Commutative operation - for example, if our private key is d (with a generator point G), we can create a public key dG but we cannot share a magical $d^{-1}$ without revealing the private key!
• One more reason is that hash values are not points on a curve. We can certainly turn an arbitrary hash value into a point, but it's an extra step.

So, for that, we will need something more sophisticated. The main idea is creating a random epehemral nonce and generate another point with it.
That point will then be combined in some way with the hash function, as well as proving that the way it was used requires for the signer to know the (long-term) private key.
Instead of using further words, let's describe the algorithm and then explain why it's correct.

Signing with ECDSA

Setting the state, we assume the signer has a private key d, as well as a public key Q = dG that is "trusted" by the verifier.
The verifier also knows the curve domain parameters (generator G, modulus n, the curve equation itself and so on).
To sign a message m, we do the following:

1. Use a hash function to get z = hash(m). If z has more bits than the bit length of n - we trim it down, assuming the hash function is still good enough even after truncation.
2. We get a random number k between 1 and n-1 - that will be our epehemeral nonce. It's important it's randomly generated for every signature (more on that - later).
3. We now calculate a corresponding public epehemeral key: R = kG. We mark r as the x coordinate of R and make sure it's not 0 (if it is, we randomize a new k and retry).
4. We calculate: $s = k^{-1}(z + rd)$. Note s is a scalar and $k^{-1}$ is the multiplicative inverse of k (mod n).
5. The signature is (r, s).

Verification wih ECDSA

Similarly to the signing process, we assume the verifier knows the curve domain parameters, as well as the public key Q.
Obviously verifier does not know the private key d or the ephemeral nonce k.
Verfier gets a signature (r, s) and does the following:

1. Verify that r and s from the signature are scalars in the range 1 .. (n-1).
2. Use a hash function to get z = hash(m). If z and truncate if it's too large.
3. Calculate $u_1 = zs^{-1} (mod n)$ (using modular inverse Euclidean Algorithm that I have described in the past).
4. Calculate $u_2 = rs^{-1} (mod n)$ similarly.
5. Calculate a new point: $R = u_1G + u_2Q$, and validate the resulting point R is not the point at infinity $\mathcal{O}$.
6. Check the signature - compare the x coodinate of R to r - if they are equal, we consider the signature valid.

Why is ECDSA "correct"?

Okay, this was quite a lot. There is true beauty in why this works.
We need to prove two things:

1. The signer knows the private key d.
2. Forging a signature (r, s) that satisfy the verification is difficult without knowledge of the private key d.

For simplicity, let's write the verification check in one equation, assuming all previous checks have passed:
$r \stackrel{?}{=} x[zs^{-1}G + rs^{-1}Q]$

Signer knows the private key

Since Q = dG, the point R used as the right hand side of the verification equation could be changed:
$R = zs^{-1}G + rs^{-1}Q = zs^{-1}G + rs^{-1}(dG) = (zs^{-1} + rds^{-1})G = s^{-1}(z + rd)G$

Note $s = k^{-1}(z + rd)$ which means $s^{-1} = k(z + rd)^{-1}$. Plugging that in we get $R = s^{-1}(z + rd)G = kG$.

So, the signer must have known d because they are the only ones who could know $s = k^{-1}(z + rd)$. Signature cannot be created without knowing d or k.

Forgery is difficult

This is a trickier one, but let us assume an attacker tries finding a pair (r, s) that satisfy the equation.
We assume r and s are scalars within range - if r or s are 0 (mod n) then we either disconnect the public key from the equation, or divide by zero...
We also assume bit sizes of r and s are sufficiently large against brute-force attacks. Then, an attacker could, for example, try to fix r and solve for s.
Note Elliptic Curve point operations are not linear, and so, the x coorinate of R behaves like a hash function involving $u_1$, $u_2$, Q and G.
We mark R = kG and note $R = zs^{-1}G + rs^{-1}Q = s^{-1}(z + rd)G = kG$, so the attacker tries to find, for a given r, a value s that satisfies this equation.
However, attacker does not know k or d, so this is difficult. This is also why the point addition is so important - that breaks the linerarity of this potential attack.

Real world implementation

This time I'd like to share the code in OpenSSL that handles ECDSA.
OpenSSL is notoriously full of function pointers and abstraction layers - true ECDSA verification starts with EVP_DigestVerify but eventually goes to a function called ossl_ecdsa_simple_verify_sig. The code is not terribly long, so I'll just paste it here, as it was at the day of writing this blogpost:

int ossl_ecdsa_simple_verify_sig(const unsigned char *dgst, int dgst_len,
                                 const ECDSA_SIG *sig, EC_KEY *eckey)
{
    int ret = -1, i;
    BN_CTX *ctx;
    const BIGNUM *order;
    BIGNUM *u1, *u2, *m, *X;
    EC_POINT *point = NULL;
    const EC_GROUP *group;
    const EC_POINT *pub_key;

    /* check input values */
    if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
        (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
        ERR_raise(ERR_LIB_EC, EC_R_MISSING_PARAMETERS);
        return -1;
    }

    if (!EC_KEY_can_sign(eckey)) {
        ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
        return -1;
    }

    ctx = BN_CTX_new_ex(eckey->libctx);
    if (ctx == NULL) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        return -1;
    }
    BN_CTX_start(ctx);
    u1 = BN_CTX_get(ctx);
    u2 = BN_CTX_get(ctx);
    m = BN_CTX_get(ctx);
    X = BN_CTX_get(ctx);
    if (X == NULL) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }

    order = EC_GROUP_get0_order(group);
    if (order == NULL) {
        ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
        goto err;
    }

    if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
        BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
        BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
        ERR_raise(ERR_LIB_EC, EC_R_BAD_SIGNATURE);
        ret = 0;                /* signature is invalid */
        goto err;
    }
    /* calculate tmp1 = inv(S) mod order */
    if (!ossl_ec_group_do_inverse_ord(group, u2, sig->s, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }
    /* digest -> m */
    i = BN_num_bits(order);
    /*
     * Need to truncate digest if it is too long: first truncate whole bytes.
     */
    if (8 * dgst_len > i)
        dgst_len = (i + 7) / 8;
    if (!BN_bin2bn(dgst, dgst_len, m)) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }
    /* If still too long truncate remaining bits with a shift */
    if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }
    /* u1 = m * tmp mod order */
    if (!BN_mod_mul(u1, m, u2, order, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }
    /* u2 = r * w mod q */
    if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }

    if ((point = EC_POINT_new(group)) == NULL) {
        ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
        goto err;
    }
    if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
        goto err;
    }

    if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
        goto err;
    }

    if (!BN_nnmod(u1, X, order, ctx)) {
        ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
        goto err;
    }
    /*  if the signature is correct u1 is equal to sig->r */
    ret = (BN_ucmp(u1, sig->r) == 0);
 err:
    BN_CTX_end(ctx);
    BN_CTX_free(ctx);
    EC_POINT_free(point);
    return ret;
}

Some interesting notes:

1. OpenSSL works with a module called BIGNUM and is recognizable by the prefix BN_.
2. The beginning of this function has some sanity checks - the key that we got is good for verification and so on.
3. The interesting checks start at BN_is_zero - we check that r is not 0, as well as check for negative values (with BN_is_negative), and finally - validate that r is less than the order of the generator point (in a variable called order here) by calling BN_ucmp. Similar checks are done for s.
4. After calculating $s^{-1}$ (using ossl_ec_group_do_inverse_ord), the algorithm performs the hashing (good for performance as hashing is computationally expensive) as well as truncating the hash if it's too big, as I previously mentioned.
5. Further down, u1 and u2 are calculated, and the addition of $u_1G$ and $u_2Q$ iis assigned to a new point - in the code it's just called point.
6. Lastly, we get the x coordinate of the point by callng EC_POINT_get_affine_coordinates, and finally that coordinate is compared to r.

One thing that is missing from this code is the check that R (or variable point really) is not the point at infinity ($\mathcal{O}$).
I thought I have found a bug that might be quite impactful, but apparently that's not the case - look at EC_POINT_get_affine_coordinates:

int EC_POINT_get_affine_coordinates(const EC_GROUP *group,
                                    const EC_POINT *point, BIGNUM *x, BIGNUM *y,
                                    BN_CTX *ctx)
{
    if (group->meth->point_get_affine_coordinates == NULL) {
        ERR_raise(ERR_LIB_EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
        return 0;
    }
    if (!ec_point_is_compat(point, group)) {
        ERR_raise(ERR_LIB_EC, EC_R_INCOMPATIBLE_OBJECTS);
        return 0;
    }
    if (EC_POINT_is_at_infinity(group, point)) {
        ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
        return 0;
    }
    return group->meth->point_get_affine_coordinates(group, point, x, y, ctx);
}

The EC_POINT_is_at_infinity call exactly solves that problem - indeed there is an implicit check against that case. Phew!

Why repeating the nonce is a bad idea

There are numerous pitfalls when implementing ECDSA - besides all the usual Elliptic Curve attacks we have described in the past.
For instance, if the OpenSSL code I showed wouldn't have checked that r and s are non-negative but simply check that they are less than n and non-zero, an attacker could have set them to be -n, which behaves exactly like zero (mod n), which is quite the bug.
However, I would like to talk about a different issue - the generation of k. We said that k is an ephemeral nonce and it's critical to not repeat it for two different messages.
If k is repeated, an attacker could easily get the private key d!
Imagine two signatures $(r_1, s_1)$ for hash $z_1$ and $(r_2, s_2)$ for hash $z_2$, with a joint nonce k.
Well, remember r is only affected by k, so two signatures using the same k will have the same r values (easy to spot!).
From that point everything becomes scary:
$s_1 - s_2 = k^{-1}(z_1 - z_2)$
Which means the attacker now knows k:
$k = (z_1 - z_2)(s_1 - s_2)^{-1}$

Remembering that $s_1 = k^{-1}(z_1 + r_1d)$, we get $(ks_1 - z_1)r^{-1} = d$ and the attacker knows the entire left-hand side. Ouch!
This is not only theoretical - that attack was exactly used to extract the Playstation 3 signing key!
There is also a variation of ECDSA that generates a deterministic k using a schema called HMAC-DRBG - it basically performs an HMAC calculation on the private key d and the hashed message z. More on that in RFC6979.

Summary

Digital signatures are everywhere, and most notably are applied to files, messages and certficates.
Up until this point I haven't discussed certificates in detail - I will leave that to a future blogpost that discusses PKI.
Because they are quite versatile, I haven't discussed the serialization of them - the binary structure of digital signatures - again, in a future blogpost.
I hope the reader appreciates the mathematical concepts behind digital signatures - they are beautiful and elegant.

Stay tuned!

Jonathan Bar Or (https://jonathanbaror.com)