How to Verify Digital Signatures

Digital Signatures

Digital signatures provide two features we absolutely need in order to communicate on-line in meaningful and trustworthy ways. They let you verify that something is true, or at least that it's precisely what someone sent or otherwise made available. Consider the situations of sending e-mail messages and providing files to be downloaded. In both cases, the person who receives the message or downloads the file needs to have very high confidence in two things:

First, the integrity of the data. Is this really the original data, or has it been modified, replaced, or even inserted into the communications channel by an attacker? The message might be a business agreement, or the data file might be a software patch. Or, possibly, a malicious replacement.

Second, the identity of the sender. Is the data really from who it claims to be? Or is it from an attacker trying to masquerade as a legitimate source of information?

You can answer those questions with high confidence if you very carefully use digital signatures.

So, what is a Signature?

A digital signature is a small data file. The sender or source of the data creates it with software that does a two-stage cryptographic operation on the message or file. The receiver needs to have both the digital signature and the message or file, and verifies it with cryptography.

Maybe the message is the content or body of an e-mail message, and the digital signature is an attachment. Or maybe the data and its signature are two files to be downloaded from the same server.

The important thing to realize is that digital signatures are cryptographic operations. They're not simply clicking a box on-line. The U.S. Social Security Administration uses the term "electronic signature" for clicking a box on a web page.

However, this is not a digital signature:

Neither are point-of-sale terminals, where the old-school versions had you scribble something with a stylus. What about the new ones that require a PIN, which appeared in the U.S. over a decade after the rest of the world? (Although the ones in the U.S. don't require a PIN) They aren't really doing digital signatures either.

Still not a digital signature:

So, What Is A Digital Signature?

It's a small piece of data, the result of a two-stage cryptographic operation. Here are the mechanics of how a digital signature is created and verified.

Alice wants to send a message to Bob, and have Bob believe that what he received is exactly what his friend Alice sent.

She starts with the message. It could be a short piece of text. Or, it might be an enormous archive file containing many component files, like a tar or zip archive. If she is concerned about confidentiality, keeping its contents secret, she should have already encrypted it. So, the box labeled "message" below might be either plaintext or ciphertext. It doesn't matter, it's just data for what follows.

She calculates the hash of the message, let's say she uses the SHA-256 function. Then she encrypts that, using an asymmetric cipher like ECC, RSA, or the special-purpose DSA or ECDSA, using her private key. The result is the digital signature. I said that Alice does all that, but she simply asks a program, maybe her e-mail tool, to do it for her. It should ask her to type her passphrase so it can decrypt and extract her private key from the database called her keyring. She could tell it to cache her passphrase after the first use each day, but that would significantly increase her risk and Alice is too cautious to do that.

Then she transmits the message and digital signature to Bob.

Bob gets the two pieces somehow. Maybe the message was the body of an e-mail message and the digital signature was another component of the message. Or maybe both the message and the signature were attachments to a message. E-mail tools are aware of the OpenPGP standard and so there's no need for Alice or Bob to worry about what tool the other one is using.

If the message was large, Alice might have put it and the digital signature on a web server or FTP server as a pair of files. Or, she could have put the large message somewhere and e-mailed the digital signature to Bob, telling him where to go to download the file, and then use the digital signature to verify it.

He doesn't yet know if the message is legitimate. His software looks at the OpenPGP metadata in the signature to see the hash function, cipher, and sender identity. It says that it came from his friend Alice, and he has a copy of her public key in his keyring.

His software calculates the hash of what was received. Then it decrypts the digital signature using Alice's public key.

If those two results are equal, he knows that this message is exactly what Alice sent.

If an attacker in the middle had modified the message, that would make Bob's hash calculation completely different. The hash verifies the message content.

If an attacker wanted to make fake signatures as Alice, he couldn't, because he wouldn't have Alice's private key. You have to encrypt with Alice's private key if you're going to decrypt with Alice's public key. The asymmetric encryption verifies the sender identity.

The combination of message integrity and sender identity provides non-repudiation. Let's say that the message was an archive with two components: a contract, and a short note saying "I agree to this."

Non-repudiation is a power that Bob, the receiver, now has over Alice, the sender. As long as he keeps the message and digital signature, Alice cannot deny having sent it. She is committed to her digitally signed messages.

What Does A Practical Digital Signature Look Like?

I have downloaded archives of the source code for the Linux kernel and the Nginx web server, plus their digital signatures. The Linux kernel project signs the original archive, the Nginx project signs their compressed version. So, I have already uncompressed the kernel source.

The archives may be quite large, the Linux kernel source is over 800 MB. But the signatures are fairly small, less than 1,000 bytes. Let's see what they look like, and how they verify.

$ ls -l nginx-1.15.8.tar.gz* linux-*
-rw-rw-r-- 1 cromwell cromwell 854876160 Feb  9 12:30 linux-4.20.7.tar
-rw-rw-r-- 1 cromwell cromwell       989 Feb  9 12:30 linux-4.20.7.tar.bin
-rw-rw-r-- 1 cromwell cromwell   1027862 Dec 25 09:58 nginx-1.15.8.tar.gz
-rw-rw-r-- 1 cromwell cromwell       455 Dec 25 09:58 nginx-1.15.8.tar.gz.asc
$ more linux-4.20.7.tar.bin 
-----BEGIN PGP SIGNATURE-----
Comment: This signature is for the .tar version of the archive
Comment: git archive --format tar --prefix=linux-4.20.7/ v4.20.7
Comment: git version 2.20.1

iQIzBAABCAAdFiEEZH8oZUiU471FcZm+ONu9yGCSaT4FAlxbC4kACgkQONu9yGCS
aT6YMBAAuv6Gxz+jkPVklukBF9+4AWFQs8gfuSVpS1ah1CBScp1psa7Fp9iITCQL
55mIQa6C587bt0V7VKevHbsSVvDhn+ADTjtqLMMDVOB9tVhZa6DKIhX0h7s4w/xc
1/QQyrsDw8Hu9QKpIGOQeMiG2vtu86YYWZ2Uuq7DSoPghn97B6re53lWTaTy0kU0
B1+B93nhguvotmKcCL+FES5zVYXtX4tiO1VVzw/XP8C9xSZa7EYjbMQbfMYJc2rZ
eCHQjJslUX/NTRXiv2w6btceR3/sOZctmDzgcDYuK8B1yUSPcE6dremTUvzdjn44
fjpMmpSl8vmaKdszg2LWv7OJgzCSniOvY8SBqU/l+81kpUFdw9yg6Cyv6bbN1+/h
5UVRa6MFgg/rwPJae1f8ShhcRqXzm2RHtTKhw65T5MdXpTwekzirDe7v4mgSW7aw
cvbHllyWnTeRaxpqktb+pWFeVoGK+PXiszxStU0GmYkX0lb9mi0LypW2XP6oqQmV
kD+1cqFUs9R3o0Lnw0Bxxibb8sBkuRZMldJi40Uv0wlT9vwTQfsR25bJVavXgcWX
OjbhZ9HhUJrUbMEBkPz0bu+RS32Jau15x9cHbNfTMUxrc7tmZVuWupMXaFpDUyYG
G8xO22g8/l3Xp9ZL73GFpuVMUcBQBSumyrILIJC7Njz8jHDQis0=
=hEKO
-----END PGP SIGNATURE-----
$ more nginx-1.15.8.tar.gz.asc 
-----BEGIN PGP SIGNATURE-----

iQEcBAABAgAGBQJcIkUXAAoJEFIKmZOhwFL4pCYIAJkz+Qdwvc3xQA/RCCyZcmwl
BOfTvZEFj+SM/YlR3PHjt5+xVAAqjPJag0Lb5CTrXCPReb/9RJXQB2XLcCpOXFjA
b63l7nJ1aEnuwsEGxsteHzfVWrTftpbWtwQVy6JYX1axwETOaLsBLyz4BbFij2Do
U9IOpWspnF1BfIjlbbKaoGygenQy04s4febvI67GhkuxkkvMYsyiRPTnF5ecPvnG
ateFJnHGN5/n21CLn5iJUYt8BJsdTUB2iSm/zR2h5DHS5k2CbKPZFRvXvRjVpGez
PYleYJRIMaQgRRGjFhEjKxxhQeTC5NG7J7kiOMfF58PRZnouOTD+UK0kfBVF65g=
=qScf
-----END PGP SIGNATURE-----
$ gpg2 -v --verify linux-4.20.7.tar.bin linux-4.20.7.tar
gpg: armor header: Comment: This signature is for the .tar version of the archive
gpg: armor header: Comment: git archive --format tar --prefix=linux-4.20.7/ v4.20.7
gpg: armor header: Comment: git version 2.20.1
gpg: Signature made Wed Feb  6 11:30:01 2019 EST
gpg:                using RSA key 647F28654894E3BD457199BE38DBBDC86092693E
gpg: using classic trust model
gpg: Good signature from "Greg Kroah-Hartman <gregkh@linuxfoundation.org<" [unknown]
gpg:                 aka "Greg Kroah-Hartman (Linux kernel stable release signing key) <greg@kroah.com<" [full]
gpg:                 aka "Greg Kroah-Hartman <gregkh@kernel.org<" [unknown]
gpg: binary signature, digest algorithm SHA256, key algorithm rsa4096
$ gpg2 -v --verify nginx-1.15.8.tar.gz.asc nginx-1.15.8.tar.gz
gpg: Signature made Tue Dec 25 09:56:23 2018 EST
gpg:                using RSA key 520A9993A1C052F8
gpg: using classic trust model
gpg: Good signature from "Maxim Dounin <mdounin@mdounin.ru<" [full]
gpg: binary signature, digest algorithm SHA1, key algorithm rsa2048

I used the -v option to make the tool more verbose. That caused it to display the comments inside the Linux kernel signature, and the hash functions and ciphers. The Linux kernel source is signed with SHA-2-256 and 4096-bit RSA, while the Nginx web server is signed with SHA-1 and 2048-bit RSA.

I used the gpg2 command, part of GNU Privacy Guard or GnuPG.

The difficult part that remains is getting the sender's public key. It sounds like it should be easy to get a public key, but it can be difficult to do this correctly.

Validity and Trust

You collect the public keys of other people and organizations on what is called your "public keyring." There are two important concepts associated with those public keys on your keyring — validity and trust.

Validity is your confidence that the public key that claims to be Bob's public key really belongs to this Bob fellow. You ran this command and saw the following output:

$ gpg2 --list-key bob
pub   4096R/41E1A929 2015-04-12
uid                  Bob Cromwell <bob.cromwe11@comcast.net>
sub   4096R/C6E07606 2015-04-12

However, anyone can use PGP software to generate a public key with any claimed identity! By the way, that looks like my e-mail address but it isn't — I have replaced the L's with the digit "1" so spammers don't scrape my address off this page. But otherwise that's the actual command and output copied and pasted into this page.

An example of validity from the physical world would be what a border guard does with your passport when you try to enter a country. They can validate your claimed identity credential by first being familiar with the passports of various countries. Is that small leatherette booklet you presented really a valid passport issued by the nation of Freedonia? If they are not familiar with Freedonian passports, they should have some sort of reference available. Then, does the physical description and photograph seem to be of you? It is a Freedonian passport, but is it your Freedonian passport?

Trust is your confidence that a given person or organization is a careful issuer of credentials. In the physical world, does the Freedonian Foreign Ministry carefully check the identity of applicants for passports? Is a Freedonian passport easier or harder to get than a driver's license or a library card?

Trust in a person or organization means that you are willing to use them as an introducer. You are not going to verify the person's identity, probably it is not practical or even possible for you to really do so. You effectively say, "Good enough for the introducer is good enough for me."

Verifying Key Validity

Let's say that you have downloaded my public key and imported it into your public keyring. The following commands will do this if you have installed GnuPG, you can just copy and paste them into the command line:

$ cd /tmp
$ wget https://cromwell-intl.com/security/public-key.html
$ gpg2 --import public-key.html

You can verify that you really have what claims to be my public key:

$ gpg2 --list-key bob
pub   4096R/41E1A929 2015-04-12
uid                  Bob Cromwell <bob.cromwe11@comcast.net>
sub   4096R/C6E07606 2015-04-12

You have added some key, but is it really mine? You could check the fingerprint of the key, a SHA hash of the public key itself:

$ gpg2 --fingerprint 41E1A929
pub   rsa4096/41E1A929 2015-04-12 [SC]
      Key fingerprint = 6E6E 1DF0 C381 9172 55B4  AC00 8344 6EEA 41E1 A929
uid         [ultimate] Bob Cromwell <bob.cromwe11@comcast.net>
sub   rsa4096/C6E07606 2015-04-12 [E]

Now I could tell you that you should expect to see the following fingerprint of my public key:
6E6E 1DF0 C381 9172 55B4  AC00 8344 6EEA 41E1 A929
However, careful hackers could have modified this page as part of a complex scheme to mislead you about my identity and possibly about the Linux kernel organization's public key.

So what can you do? Since I am a private individual, this is difficult to solve. I could give you my business card if we met in person. My card includes my PGP public key fingerprint. You could ask other people if they knew the true fingerprint of my public key, but chances are next to zero that you will ever meet anyone who can accurately answer that question. You could search for me at public key servers, but all you find is some public key that claims to be mine. It could have been generated and uploaded by anyone.

We need another mechanism....

Using Trust

Let's say that we have done enough work to make you believe the validity of your copy of my public key. We actually met somewhere. Or you tracked me down on the telephone to ask me for my key fingerprint, and you believe that the telephone company is not part of some vast conspiracy to mislead you. Put simply, you believe that you really have my key.

What you do is digitally sign that key on your public keyring. That tells your PGP software "That key is valid." The second command here will show you that my key now has at least two signatures — mine (PGP public keys are X.509 self-signed certificates) and yours.

$ gpg2 --sign-key 41E1A929
....answer the question....
$ gpg2 --check-sigs 41E1A929

Sometimes --check-sigs produces a very minor warning of the form:
7 signatures not checked due to missing keys

Don't panic! That just means that the key you received has also been signed by other people. You don't have their public keys so you can't verify their signatures. There's nothing at all bad or ominous about that. Imagine that you have asked someone for their identity papers, wanting to see their national passport. They might respond, "Here is my passport, and my driver's license, and my work ID, and my library card, and my Ralph's supermarket loyalty card, and ..." None of those should count against them! You check the passport, for which you understand the issues of validity and trust, and can safely ignore the rest.

This is my only form of ID.

Amazon
ASIN: B000A7DVR2

Amazon
ASIN: 1569759766

Furthermore, let's say that you have decided to trust me in the way defined above. You are willing to use me as an introducer, to accept what I say about which public keys belong to which people and organizations.

"Good enough for Bob is good enough for me", you say.

If you decide to do that, you edit the settings on my key to change the trust:

$ gpg2 --edit-key 41E1A929
....use the "trust" command,
	answer the questions,
	save the changes....
$ gpg2 --check-sigs 41E1A929

What If You Can't Easily Verify Validity?

Here's an extremely ad-hoc way of getting "close enough". I wanted to verify the Nginx source code because I was going to build the latest version for a project.

The Nginx download page allowed me to download the source archive and signature file, as I showed you above. The problem was that I got this:

$ gpg2 --verify nginx-1.15.8.tar.gz.asc nginx-1.15.8.tar.gz
gpg: Signature made Tue Dec 25 09:56:23 2018 EST
gpg:                using RSA key 520A9993A1C052F8
gpg: Can't check signature: No public key 

OK, let's import it from the on-line keyserver, if that's possible. Yes, it is. Maxim created his key pair some time ago, and more recently uploaded his key wrapped in signatures done by people with newer keys. Don't worry about those "newer than the signature" reports.

$ gpg2 --keyserver sks-keyservers.net --recv-keys 520A9993A1C052F8
gpg: key 520A9993A1C052F8: public key "Maxim Dounin <mdounin@mdounin.ru>" imported
gpg: public key 662C9D02F54C3035 is 271 days newer than the signature
gpg: public key 7BE65B698FAF3E32 is 1461 days newer than the signature
gpg: public key 13A085FCD77B2094 is 1888 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 1479 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 1479 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key D3E0C24F3EEEDCE1 is 63 days newer than the signature
gpg: public key D3E0C24F3EEEDCE1 is 63 days newer than the signature
gpg: public key 1F13F36F19EDE474 is 110 seconds newer than the signature
gpg: marginals needed: 3  completes needed: 1  trust model: classic
gpg: depth: 0  valid:   2  signed: 268  trust: 0-, 0q, 0n, 0m, 0f, 2u
gpg: depth: 1  valid: 268  signed:  36  trust: 254-, 5q, 0n, 1m, 8f, 0u
gpg: depth: 2  valid:   1  signed:   1  trust: 1-, 0q, 0n, 0m, 0f, 0u
gpg: next trustdb check due at 2020-05-08
gpg: Total number processed: 1
gpg:               imported: 1 

So, now I have what appears to be Maxim's key, but I'm not sure. I now notice that there's a public key page at the Nginx project where I could download keys. I right-click on the links, select "Copy link address", and paste them into a command line to download them with the wget tool. It will ask the server for the modification times on the files, and set my copies to agree.

$ wget https://nginx.org/keys/mdounin.key
--2019-02-09 14:39:36--  http://nginx.org/keys/mdounin.key
Resolving nginx.org... 2001:1af8:4060:a004:21::e3, 62.210.92.35, 95.211.80.227
Connecting to nginx.org|2001:1af8:4060:a004:21::e3|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1912 (1.9K) [text/plain]
Saving to: 'mdounin.key'

mdounin.key         100%[===================>]   1.87K  --.-KB/s    in 0.001s  

2019-02-09 14:39:36 (2.73 MB/s) - 'mdounin.key' saved [1912/1912]
$ ls -l mdounin.key
-rw-rw-r-- 1 cromwell cromwell 1912 Dec 16  2011 mdounin.key 

We see at the end of the first command's output that I did this in early February of 2019. But the public key file dates from a little over seven years ago. There is simply no way that a prominent project like Nginx would be hacked for seven years with no one noticing.

But, you object, it could have been hacked 10 minutes ago by someone who set the replacement file timestamps in the past!

Yes, I know. So I'll wait a day or two. A hack of that project would be big news. If I don't hear anything, I'll conclude that I really have a valid copy of that key. Then I'll sign my copy.

I will go ahead and delete the key I downloaded a few minutes ago, and then I will import the 7-year-old key.

$ gpg2 --delete-keys mdounin@mdounin.ru
gpg (GnuPG) 2.1.21-3.1.mga6; Copyright (C) 2017 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

pub  rsa2048/520A9993A1C052F8 2011-11-27 Maxim Dounin <mdounin@mdounin.ru>

Delete this key from the keyring? (y/N) y
$ gpg2 --import mdounin.key
gpg: key 520A9993A1C052F8: public key "Maxim Dounin <mdounin@mdounin.ru>" imported
gpg: Total number processed: 1
gpg:               imported: 1
gpg: public key 662C9D02F54C3035 is 271 days newer than the signature
gpg: public key 7BE65B698FAF3E32 is 1461 days newer than the signature
gpg: public key 13A085FCD77B2094 is 1888 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 1479 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 1479 days newer than the signature
gpg: public key ACBB164BCF73EC4C is 326 days newer than the signature
gpg: public key D3E0C24F3EEEDCE1 is 63 days newer than the signature
gpg: public key D3E0C24F3EEEDCE1 is 63 days newer than the signature
gpg: public key 1F13F36F19EDE474 is 110 seconds newer than the signature
gpg: marginals needed: 3  completes needed: 1  trust model: classic
gpg: depth: 0  valid:   2  signed: 268  trust: 0-, 0q, 0n, 0m, 0f, 2u
gpg: depth: 1  valid: 268  signed:  36  trust: 254-, 5q, 0n, 1m, 8f, 0u
gpg: depth: 2  valid:   1  signed:   1  trust: 1-, 0q, 0n, 0m, 0f, 0u
gpg: next trustdb check due at 2020-05-08

Then, after a few days with no alarming news of nginx.org being hacked, I will sign my copy, effectively telling my software "I believe that this is a valid copy of Maxim's key."

$ gpg2 --sign-key mdounin@mdounin.ru

pub  rsa2048/520A9993A1C052F8
     created: 2011-11-27  expires: never       usage: SC  
     trust: unknown       validity: unknown
sub  rsa2048/57A82F1DD345AB09
     created: 2011-11-27  expires: never       usage: E   
[ unknown] (1). Maxim Dounin <mdounin@mdounin.ru>

gpg: using "41E1A929" as default secret key for signing

pub  rsa2048/520A9993A1C052F8
     created: 2011-11-27  expires: never       usage: SC  
     trust: unknown       validity: unknown
 Primary key fingerprint: B0F4 2533 73F8 F6F5 10D4  2178 520A 9993 A1C0 52F8

     Maxim Dounin <mdounin@mdounin.ru>

Are you sure that you want to sign this key with your
key "Bob Cromwell <bob.cromwell@comcast.net>" (83446EEA41E1A929)

Really sign? (y/N) y 

A passphrase entry tool pops up, I enter my passphrase, and my keyring is updated.

This is why PKI is important. If I was in the same organization as the people in that project, we could rely on our shared public-key infrastructure for valid keys. They would arrive as trusted digital certificates, wrapped in valid signatures from a trusted signer.