Just Enough Cryptography

Digital Signatures, Digital Certificates, and Hashed Message Authentication Codes

Digital Signatures

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), K_private )

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:
                                            +---------+
                                          { | Message |
           +----------------------------> { |  body   |
           |                              { |         |
           |   +---+   +---+                +---------+
  Message -+-->| H |-->| E |--> Digital --> |Signature|
               +---+   +---+   signature    +---------+
                         ^
                         |
                         kpriv

Verifying a digitally signed message:

    +---------+      +---+
    | Message | }--->| H |------------+
    |  body   | }    +---+            |
    |         | }                     |
    +---------+      +---+            v
    |Signature| }--->| D |----> Are they the same?
    +---------+      +---+    If so, the message is valid
                       ^      and the sender is legitimate!
                       |
                      kpub

	Firefox users may find that "monospace" isn't really a constant-width
	font, and Courier works much better for ASCII art.

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. And it can be used 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:

• The message was signed with a trusted key, and the signature could be verified.
  • This is what you want to see!
• 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 that 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
    or:
    $ 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 a validity of a key — this is the hardest problem to solve in the area of digital signatures and public-key cryptography.
• 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. 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 the case immediately above this one...
• 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). Sender transmits message and HMAC. Receiver performs same hash(received+key) to verify message integrity and sender authentication.

Generating HMAC:

    +----------+
    |          | }
    | Message  | }    +---+
    |          | }--->| H |---> HMAC
    +----------+ }    +---+
    |Secret Key| }
    +----------+

Transmit only the message and HMAC to the receiver.

       Sender                  Receiver
    +----------+
    |          |
    | Message  | =================>
    |          |
    +----------+

    +----------+
    |   HMAC   | =================>
    +----------+

Verifying HMAC:
    +----------+
    | Received | }
    | Message  | }    +---+
    |          | }--->| H |---> hash
    +----------+ }    +---+      ^
    |Secret Key| }               |
    +----------+                 |
                                 |
    +----------+                 |
    | Received |  <--------------Compare these.
    |   HMAC   |                 If equal, then this was a valid
    +----------+                 message from the authentic sender.

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 an electronic mail message, but use HMAC within IPsec to verify all IP datagrams.

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, Thawt, 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 bogus-and-dishonest-bank.com domain, set up a web server, and get you to tell it your credit card numbers over an SSL/TLS connection.

I have a page explaining how to create and install keys and X.509v3 certificates for a secure Apache web server.

All the way back to the start Terminology Symmetric and Asymmetric Ciphers One-Time Pads Cipher Strength and Key Length Diffie-Hellman Key Negotiation and Secret Sharing Cryptographic Hash Functions Digital Signatures and Certificates Next — Cultural Cryptography Further Reading

Back to the Security Index

Home Unix/Linux Networking Cybersecurity Travel Technical Radio Site Map Contact

Tweet