In this third blog post on security topics, we’ll take a closer look at digital signatures. These are the mechanism by which information, such as a certificate, or the manifest associated with an executable file, can be digitally ‘signed’, and thus rendered tamper-proof.
To understand how digital signatures work, we need to revisit the public key infrastructure (PKI) that we discussed in the first post.

Alice, Bob and Eve, revisited

To refresh your memory, you’ll recall that we had three key players in our scenario, Alice, and Bob, who wished to exchange secret documents, and Eve, the eavesdropper, who was attempting (unsuccessfully) to obtain a copy of these documents.
Now, you’ll also recall that Bob sent Alice a briefcase and a very special padlock, which requires one key to lock it and another one to unlock it. We discussed how the key which locks the padlock corresponds to a public key and the key which unlocks the padlock corresponds to a private key.
In the scenario, Alice locked the padlock using Bob’s public key and then Bob unlocked it using his private key.
This is analogous to Alice encrypting a secret message with Bob’s public key and then sending it to Bob. Since only Bob has access to the private key required to decrypt the message, an eavesdropper such as Eve cannot decrypt the message.

Using public and private keys to create digital signatures

Now it’s possible to use public and private keys in a different way. Suppose Bob encrypts a message with his private key. He then sends this message to Alice. Alice can, of course, decrypt Bob’s message using his public key, as can any other listener, such as Eve.
At first glance, this seems like a rather pointless thing to do. But in fact, there is a good reason why Bob might want to do this. Specifically, only Bob could have created the original message. So if we can decrypt it successfully, and assuming we trust Bob’s public key, we can be quite confident that the message that Bob sent has not been maliciously altered in transit – and, critically, that Bob authored the message.
Eve cannot forge a message purporting to be from Bob because she does not know Bob’s private key. So, although she can most definitely read any such message, she is powerless to alter it.
We exploit this idea to digitally sign a message. Rather than simply encrypt the entire message and send it, there’s no point in Bob requiring the recipient to decrypt it before they can read it. Anyone with his public key can do that. The message may as well be in plain text, so that anyone – or any computer – can read it, even without Bob’s public key.
However, we want to ensure that we don’t allow anyone to alter Bob’s message. To ensure that it is tamperproof, Bob appends a digital signature – a small block of information – to the message text.
The digital signature is essentially a message digest – a unique number that represents the message contents – which Bob then encrypts using his private key.

Verifying a digital signature

Now anyone wishing to verify the authenticity of the message must first acquire Bob’s public key.
They decrypt the message digest with his public key to get the original digest that Bob appended to the message.
They independently compute the message digest for the main message. If this digest matches the decrypted digest Bob supplied, then we know:-

  • That Bob is indeed the author.
  • That the message has not been tampered with in any way since Bob sent it.

Message digests

Now, this talk of message digests might sound a bit mysterious, so let’s go into a little more detail. A message digest is just some ‘summary’ of a message that ought to be unique for any message and be much shorter than the message itself.
For example, if my message was ‘The Quick Brown Fox Jumps Over The Lazy Dog’ then I could perhaps just take the first character of each word in the message to get ‘TQBFJOTLZ’ as my digest. Then for any different message, the digest ought to be different.
This is much too simplistic a solution to be practical, but it shows the idea without introducing any maths.
One problem with the above approach is that the message digest of a long message would also be quite long, and there would be no fixed size for digests. And, of course, other messages could produce the same digest, such as ‘Total Quarterly Biscuit Factory Jam Output Too Large, Decrease’
When this happens, it is known as a ‘collision’. Obviously, we want a message digest that makes collisions very unlikely.

Message digests and hashes

To get around these kinds of issues, an actual message digest is typically a number, computed using something called a ‘hash function’. A hash will typically be at least 128 binary bits.
Here’s what a real hash message digest of the previous message looks like

A65738B5283333387450B2C5D2D426D0

The hash here is represented using a coding scheme called ‘hexadecimal’ because this is quite compact and it represents every 8 binary bits – known as a byte – as a pair of digits and letters.
If I wrote this number out using the decimal system we normally use, it would be REALLY big. To give you an idea, if I convert just the last part of it

5D2D426D0

to decimal, it would be

25,011,955,408

You can see that the full hash would be a very large number indeed. And this is the SMALLEST hash commonly in use – the algorithm for this hash is called ‘MD5’, where the ‘MD’ stands for Message Digest.

Hashes and collisions

The idea of any hash function is that no two messages should ever produce the same hash. Obviously, this is impossible because the hash is shorter than most messages. However, a good hash function is designed so that the possibility of this ever happening, called a ‘collision’ is sufficiently small that you run a significantly higher chance of being kidnapped by aliens while crossing the road than you will of ever seeing one in practice.
[we saw an example of a collision with our simplistic digest function, earlier]

digital signatures

In other words, unless “The X Files” is your favorite program, you can probably assume that for all intents and purposes, you’ll never see two colliding messages.
Now as a side-note, the MD5 hashing algorithm is considered more vulnerable to collisions than newer algorithms. However, these newer algorithms such as SHA-1 or SHA-256 use longer numbers, in some cases, twice as long. So MD5 is still a ‘good enough’ choice for a lot of hashing applications but not where security is critical since it’s a bit too easy to create message collisions using it.
[SHA stands for Secure Hash Algorithm, perhaps not too surprisingly!]

Typical usage scenarios for digital signatures

Digital signatures are obviously very useful. Here are some of the common usages.

Certificates

One key application of digital signatures is in the production of certificates. You recall from our discussion on PKI that it’s important we can trust public keys and that Certification Authorities, or CAs, produce certificates which can be used to verify that a particular person (or company etc), is the actual owner of the public key, and exactly what that public key is.
Obviously, we don’t want Eve to be able to fraudulently alter such a certificate, or issue bogus new ones, so we digitally sign the certificate, as the certification authority, using our private key. Now, since as a CA we are intrinsically trusted, anyone can verify the authenticity of a certificate by verifying it in the same way we discussed above.

Code signing

Because executable files can be a vector for malware, it’s critically important that we can verify that a file is what we expect it to be. We can use digital signatures to ensure that the file’s contents, including information about its publisher, product, and release, are tamper-proof. Before we allow a file to be executed, we can then confirm through its digital signature, that the file is indeed what it represents to be. Additionally, any file lacking a digital signature can simply be rejected, or ‘blacklisted’, thus giving us additional protection.

Identity Assertions

Modern computer systems involve interaction between lots of different computers. We would like to control what individual users can do when they use these computers. Traditionally this problem has been handled by the vendor of whatever operating system runs on those computers. However, this presents a problem when we have different kinds of computers all connected together. For example, we might have traditional Windows systems interacting with Unix/Linux devices, and on top of these Android and iOS-based mobile devices.
To manage the problem of what is known as ‘federated identity management’, we can use digital signatures to create tamper-proof documents which make security assertions about a user.
These assertions are made by associating a user’s identity with a set of claims about the user. In the same way that your passport asserts your identity and visas attached to the passport permit you to visit specific countries, these claims assert that you have certain attributes – such as roles within a set of computer systems.
Because the assertions are made by a trusted authority – that is, some entity whose identity can be independently verified (e.g by using PKI certificates) – it is possible to pass these assertions between computers and then let each device decide independently what it will permit the user to do.

Conclusion

We have seen that digital signatures provide the essential capability of creating tamper-proof documents which can be used for a variety of purposes. In addition, signatures allow us to verify that the author of such a document is indeed who they say they are. These capabilities are core to the design of modern distributed computer systems and indeed the entire internet.