Rotors of M-209 cipher machine.

Digital Signatures, Digital Certificates,
and Hashed Message Authentication Codes

Digital Signatures

We need to be able to verify both the integrity and origin of data. That is, for an e-mail message or a data archive or program stored on a server, we need to prove to a high level of confidence that the data is precisely in its original form and that it came from the claimed source. In other words, that precisely that message came from that sender or source. This combination provides non-repudiation, in which the sender cannot convincingly deny having sent that message. The technique is called a digital signature as it provides a much more trustworthy signature method than examining ink scrawls, and it is performed by a digital computer program combining two cryptographic components.

If you send a message and its hash, all you prove is that you know how to calculate a hash!

Instead, send the message and the result of encrypting its hash with your private key. That result is called a digital signature. The digital signature is:
E( H(message), Kprivate )

Anyone can calculate the hash of the received message. They can also use your public key to decrypt the digital signature. Then they compare those two results. If the two are the same, you are the sender, and the message wasn't altered.

Digitally signing a message and verifying that digital signature.

For an application of this technology, see my page explaining how to use this to verify downloaded software and operating systems.

For a less technical explanation of how this can be used with e-mail messages, see my page referenced in my .signature file, explaining it to people puzzled by their clueless mail tool's report of "unknown attachment".

Verifying Digital Signatures With PGP Tools

I use the GNU Privacy Guard, or GnuPG. It can be used from the command line, where the gpg command does pretty much everything. (Note that the command itself is gpg2 in many Linux distributions.) And, the GnuPG package functions as a plug-in for mail tools.

One of four things must happen when you attempt to verify a digitally signed message or data file:

1: The message was signed with a trusted key, and the signature could be verified. This is what you want to see!

2: The signature could be verified, but the key is not trusted. You have the signer's public key on your key ring, but you have not yet decided to trust the validity of that key, in the sense of being able to say, "I am quite certain that this key belongs to that person or group."

You need to fix this. The problem is, how do you decide if that key really belongs to that person or organization? If you got the key from shrink-wrapped media that you purchased (for example, a set of Red Hat Enterprise Linux install media), it would make sense to believe that the keys on the media really belong to he people who sent you the media.

However, these days companies want to save money by having you download data instead of shipping media. So, you could check the fingerprint (a hash) of the key you have:
$ gpg --fingerprint keyID
$ gpg --fingerprint SignersNameHere
Then call them on the telephone and read that fingerprint to them so they can verify that what you have is really their key.

Or, you could ask some trusted third party. If you're looking at Linux software, you could ask me as I might happen to have a copy of that key. Then it's up to you to decide if you should believe me.

It is hard to decide on the validity of a key — this is the hardest problem to solve in the area of digital signatures and public-key cryptography.

3: The signature could not be verified because you do not have the needed public key. You have no idea whether the data might be valid or not, because you do not have the public key needed to answer that question. It's time to go look at public key servers, and if that doesn't work, maybe ask Google.

Once you import that public key in your keyring, your problem becomes case #3 immediately above this one...

4: The signature is invalid! This is the worst possible result!

Something bad has happened! Maybe it was malicious. Maybe it was innocent (for example, you are looking at an e-mail message that passed through a Lotus Notes gateway that decided to add extra blank spaces to the ends of lines and otherwise reformat the message). Whatever the cause, something has modified the data after the digital signature was created.

Hashed Message Authentication Code (HMAC)

The sender and receiver share a secret key. HMAC is formed as hash(message+key).

The sender transmits message and HMAC.

The receiver performs a corresponding hash(received+key) operation to verify the message integrity and sender authentication.

Generating and transmitting a hash message authentication code or HMAC.
Verifying a hash message authentication code or HMAC.

Note that a digital signature requires a hash of the entire message followed by an encryption of the hash. If you are only sending one large message, the work required for the hash overwhelms that for the encryption, and there is no real computational advantage to an HMAC.

An HMAC requires only a hash. If you are sending a large number of small messages, an HMAC has a computational advantage.

So, digitally sign electronic mail messages and archives to be downloaded from web servers, as you only send or create them every once in a while. But use HMAC within IPsec to verify all IP datagrams in a rapid stream of network traffic.

X.509v3 Digital Certificates

None of this makes much sense if you cannot be absolutely certain who you are talking to!

A digital certificate is a message that says, "The public key of so-and-so is such-and-such", with that message digitally signed by an entity called a Certificate Authority (CA). Attributes of a CA:

You are absolutely certain the CA will tell the truth.

You are absolutely certain you know the CA's public key.

For instance, Verisign, Comodo, and others are CAs whose public keys have been coded into your web browsers by the software developers (and so you must absolutely trust your software providers, too).

When you download a secure page via HTTPS:

1: The server sends your browser a digital certificate signed by some CA you trust.

2: Your browser verifies the digital certificate and thus is certain that it really has the public key for some claimed identity.

3: However, anyone could send you the well-known digital certificate, we must verify that the server really is who it claims....

4: Your browser generates a random number and encrypts it with that public key. It then sends the result to the server, asking the server to decrypt it with the corresponding private key and send it back. [OK, I have simplified this somewhat for the sake of this explanation, go read the SSL/TLS specifications for the whole story if you care.]

X.509v3 is simply the format of digital certificate that everyone uses.

Also be aware that a digital certificate is proof of identity, but not proof of intent or good will! Anyone could get a digital certificate for the domain, set up a web server, and get you to tell it your credit card numbers over an SSL/TLS connection.

I have some pages with applications of digital certificates:

Next in this series ❯ Cultural Cryptography