This post is a basic explanation of the concepts behind sending/receiving messages with PGP. This is the basic information I want someone to understand before I start communicating with them. These explanations are fairly simplified.

Infeasible means it is very, very difficult to do something. In cryptology, this usually equates to something along the lines of, “It’s possible with known algorithms and the expected advancements in hardware, but it will take thousands/millions of years.”

What is PGP

PGP stands for Pretty Good Privacy, and is a program originally developed in the 90s to send and received encrypted emails. It is not an encryption algorithm. It provides a basic format for using various algorithms and best-practices in cryptology to send messages between people. PGP has now become the colloquial word used for a variety of concepts used with this format. A PGP Key is a key that can be used with PGP to encrypt/decrypt emails. A PGP encrypted email is an email that could be decrypted with PGP, given a PGP key. Again, PGP is not a cryptographic algorithm.

I personally use GnuPG along with enigmail to communicate using PGP formatted messages.

The three basic types of encryption

PGP uses all three of these. We will hit them briefly now, and then again at the end.

Symmetric Encryption

Symmetric encryption is used to exchange information between two parties with one key. This key is shared, a “shared secret”, and the security of symmetric encryption relies on the safe-guarding of this shared secret (the key). Relative to asymmetric encryption, symmetric encryption is fast. AES stands for the Advanced Encryption Standard, comes in 128 and 256 bit flavors (128 is considered secure/unbreakable, but 256 is available to comply with requirements but forth by NIST when they were evaluating candidates for AES), and replaces 3DES, which was three consecutive rounds of DES and was the previous encryption standard.

• Key: Both parties have same, shared key
• Example Algorithms: AES, Blowfish, Twofish, 3DES
• Speed: Fast
• Security Relies On: Safe-guarding shared key

Asymmetric Encryption

Asymmetric encryption is used to exchange information between two parties where one party has a known “public” key, and uses this known “public” key to encrypt information for another party. This information can only be decrypted with the “private” key which is kept secret. Asymmetric encryption is based on mathematical problems that are infeasible to solve. Relative to symmetric encryption, asymmetric encryption is slow. RSA and the Diffie-Hellman Key Exchange are two basic methods (based on two different infeasible-to-solve problems) for implementing asymmetric encryption.

There are TWO KEYS in asymmetric encryption, the “private” key and the “public” key. Ok, technically there are four keys, one pair for signing and one pair for encrypting, but we will pretend there are two keys and abstract some details for quick understanding. If I want to send you a message, I use your public key to encrypt your message. Only you, with your private key, can decrypt that message. If you send me a message, you can use your private key to sign that message. I can then use your public key to verify the signature, and mathematically prove that the message comes from you.

• Key: You have a secret, private key, and you share a public key with EVERYONE
• Example Algorithms: RSA, Diffie-Hellman Key Exchange
• Speed: Slow
• Security Relies On: Safe-guarding private key and verifying public key

We will return to security relies on.

Cryptographic Hash

A cryptographic hash is a “one-way” cryptographic operation where we input data of arbitrary length and end up with a unique number. Hash is used colloquially to refer to both the algorithm, and the resulting “sum” of the hashing algorithm. We will use “sum” to mean the result of the hashing operation. A cryptographic has two very special properties by definition.

• Preimage Resistance:Given the sum of a hash, it is infeasible to create or find any input that will hash to that same sum.
• Collision Resistance: It is infeasible to find any two inputs that will hash to the same sum.

Preimage resistance means you do not get to pick the sum. Collision resistance means you can pick the sum. Collision attacks are easier to implement than preimage attacks. Some implementations of cryptographic hashing algorithms are still valid if the hash can withstand preimage attacks but falls prone to collision attacks. Anything that deals with PGP (key fingerprints, signing emails) requires both strong preimage and collision resistance.

• Key: There is no key
• Example Algorithms: OLD_DO_NOT_USE(MD4, MD5, SHA1) USE(SHA256/SHA512 (these are both sha2 with different block sizes))
• Speed: fast
• Security Relies On: The strength of the hashing algorithm

Understanding Asymmetric Encryption Security Concerns

Fingerprint: A cryptographic hash (sum) of a public key. Usually when I say, “verify public key,” I mean the fingerprint. PGP/GnuPG will generate these fingerprints for you.

Symmetric security is pretty easy to understand. Cryptographic encryption is also pretty easy to understand. Asymmetric encryption, however, has a few special implications we will need to cover. These come from the second security requirement of asymmetric encryption: verifying the public key.

Imagine a scenario where I post my public key to a website and then tell you to go download my public key (exactly like my key available on rainbowsandpwnies.com). Unbeknownst to either you or me, someone has:

• Hacked into rainbowsandpwnies.com and modified the key stored there.
• Is sitting between you and rainbowsandpwnies.com and giving you fake information.
• Modifying the key you will end up receiving by some other means.

This third party instead gives you their public key. You send a message to me, encrypting it with the public key of the third party. They then decrypt this message, read it, re-encrypt it with my real public key, and then send the message to me. The third party can even sign the message with their private key and send me their public key. You and I will now communicate, believing we are speaking secretly, but our messages are being read by third parties.

In order to know we are speaking secretly, we must be sure that our messages are coming directly from one another. To do this, two things need to happen:

• You must know, with certainty, that you have my real public key. I must know, with certainty, that I have your public key.
• If I receive a message from you, it must be signed with your public key (that I know belongs to you). Vice-versa for messages you receive from me.

There are multiple models for establishing trust. One popular model involves what is called a Certificate Authority. In this model, everyone has the public key of a trusted entity known as the Certificate Authority. You send your public key to the Certificate Authority in what is known as Certificate Signing Request. The Certificate Authority then verifies your identity (by some other means) and then signs your certificate. When you send me your public key, you also send you certificate signed by the Certificate Authority. I can use the Certificate Authority’s public key (that I already have and trust) to verify his signature on your certificate, and because your public key is in that certificate, I transfer my trust of the Certificate Authority, through the certificate, to that public key. I now know that public key belongs to you, and can trust that public key with equal trust as I trust the Certificate Authority. This model is referred to as Public Key Infrastructure (PKI). You can have your PGP key signed by a CA, if you want, for a fee.

There is another model for trust, known as the Web of Trust. The easiest way to imagine the Web of Trust is to think of each user as a Certificate Authority. In the Web of Trust, users “sign” the public keys of other users whom they verify. We can now base our trust of a public key equally to the amount of trust we place in the users who signed that public key. We place trust in the signers based on our confidence in them to both safeguard their private keys, and properly verify the public keys they sign. That’s a two part trust there, and it’s important to understand both of them.

• If I trust Mark to both safeguard his private key and to only sign public keys he properly verifies, and Mark has signed your key, then I can transfer that trust to your key.
• If I trust Mark to safeguard his private key but I don’t believe Mark uses proper methods to verify other public keys, I will not trust his signature of your key.
• If I trust Mark to use proper methods to verify other public keys but do not think Mark properly safeguards his key, I will not trust his signature of your key.

The “Web” part of the Web of Trust comes from the “filtering” down of this trust. Imagine I trust Mark fully, and Mark trusts Steve fully. If Steve signs Katie’s key, then I will trust Katie’s key. There is more to the Web of Trust, but if you just understand the concepts discussed above then you (and I) will be OK.

Verifying/Signing Public Keys

There are two very important parts to verifying a public key before you sign/trust it.

• You must be certain the other person is who they say they are.
• You must be certain the method in which they are giving you their public key is one that can not be intercepted and modified.

The easiest way to do this is to meet the person face-to-face, exchange multiple forms of identification (a passport and driver’s license, for example), and then exchange fingerprints of public keys. You can make it into a party.

If you already know the person well enough to be certain of their identity, then any method which can not be intercepted and modified will suffice. IE: you could meet them face-to-face (this is always preferred). Another method I sometimes use is a webcam chat with someone I know where I simultaneously write out, in view of the camera, and vocally speak each letter of the fingerprint.

Safeguarding your Key

In addition to verifying the keys of others, you must also safeguard your own private key. Losing your private key can have severe consequences relative to the amount of trust other people have placed in your ability to safeguard it. In this context, “losing,” your private key means someone else has a copy of your private key. You may (and most likely will) still have your private key. You must maintain control of your private key at all times. Do not use your private key on insecure machines. Other people are counting on you to maintain your key.

Here is a list of acceptable places to use/store your private key to decrypt and sign emails:

• On a computer that you, and you alone, control, that other people do not and will not tamper with, and that you keep patched and secure.
• On an encrypted piece of removable storage

Here is a list of unacceptable places to use/store your private key to decrypt and sign emails, REGARDLESS OF HOW BADLY YOU NEED/WANT TO SIGN AND/OR DECRYPT AN EMAIL:

• A computer that is owned by your university/employer/government/friend/parents.
• That computer, that you own, in your living room, that your Aunt Susie uses to read emails and play bejeweled on when she visits every other Tuesday.
• Your smartphone (especially iPhone/Android). (CEO, Here is a bunch of details of our company’s intellectual property that we would be ruined if our competitors discovered. Don’t worry, this email is encrypted. Sincerely, Employee — sent from iPhone).
• On an unencrypted thumbdrive (or any other unencrypted removable media). Ever.

A quick understanding of how PGP encrypts/signs your messages

First, there are a lot of considerations when implementing a cryptographically secure solution like PGP. The quality of random numbers, side-channel attacks, padding and many other considerations are all taken into account. Don’t try a homebrew solution.

To encrypt a message, PGP will first encrypt the message with a symmetric encryption algorithm such as AES and a random key. This is because symmetric encryption is fast. PGP will then encrypt the random key with your public key. It will send the symmetrically encrypted text, along with the asymmetrically encrypted key, to you. You decrypt the key, and then decrypt the text.

To sign a message, PGP will cryptographically hash your entire message. This is because cryptographic hashes are fast. Now, remember when we said you really had four keys instead of two? Well, you have a separate pair of signing keys. With your signing keys, your “encryption” or signing key is kept secret, and your “decryption” or verifying key is public. You use your private signing key to encrypt the cryptographic hash of the message. You send the encryption of the cryptographic hash with the message. Whomever receives your message can hash it, and then use your public verifying key to decrypt your signature. If the decrypted hash from the signature matches the hash the recipient generated of your message, then message is valid. In this case, valid means the recipient knows the message came from you and was not modified in any way.