Linux Security: Public Key and Symmetric Key Encryption

This is an excerpt from “A Practical Guide to Red Hat Linux 8“. An interview with the author is available here.

Public Key Encryption

In order to use public key encryption, you must generate two keys: a public key and a private key. You keep the private key for yourself and give the public key to the world. In a similar manner your friends will generate a pair of keys and give you their public keys. Public key encryption is marked by two distinct features.
1. When you encrypt data with someone’s public key, only that person’s private key can decrypt it.
2. When you encrypt data with your private key, anyone else can decrypt it with your public key.

You may wonder why the second point is useful at all: Why would you want everybody else to be able to decrypt something you just encrypted? The answer lies in the purpose of the encryption. Although encryption changes the original message into unreadable ciphertext, the purpose of this encryption is to provide a digital signature. If the message decrypts properly with your public key, only you could have encrypted it with your private key, proving that the message is authentic. Combining these two modes of operation yields privacy and authenticity. You can sign something with your private key so that it is verified as authentic, and then you can encrypt it with your friend’s public key so that only your friend can decrypt it.

Public key encryption has three major shortcomings.

1. Public key encryption algorithms are generally much slower than symmetric key algorithms and usually require a much larger key size and a way to generate large prime numbers to use as components of the key, making them more resource intensive.
2. The private key must be stored securely and its integrity safeguarded. If a person’s private key is obtained by another party, that party can encrypt, decrypt, and sign messages impersonating the original owner of the key. If the private key is lost or becomes corrupted, any messages previously encrypted with it are also lost, and a new keypair must be generated.
3. It is difficult to authenticate the origin of a key, that is, to prove who it originally came from. This is known as the key-distribution problem and is the raison d’etre for such companies as VeriSign.

Algorithms such as RSA, Diffie-Hellman, and El-Gamal implement public key encryption methodology. Today a 512-bit key is considered barely adequate for RSA encryption and offers marginal protection; 1,024-bit keys are expected to withhold determined attackers for several more years. Keys that are 2,048 bits long are now becoming commonplace and rated as espionage strength. A mathematical paper published in late 2001 and reexamined in the spring of 2002 describes how a machine can be built-for a very large sum of money-that could break 1,024-bit RSA encryption in seconds to minutes (www.counterpane.com/crypto-gram-0203.html#6). Although the cost of such a machine is beyond the reach of most individuals and smaller corporations, it is well within the reach of large corporations and governments.

Symmetric Key Encryption

Symmetric key encryption is generally fast and simple to deploy. First, you and your friend agree on which algorithm to use and a key that you will share. Then either of you can decrypt or encrypt a file with the same key. Behind the scenes, symmetric key encryption algorithms are most often implemented as a network of black boxes, which can involve hardware components, software, or a combination of the two. Each box imposes a reversible transformation on the plaintext and passes it on to the next box, where another reversible transformation further alters the data. The security of a symmetric key algorithm relies on the difficulty of determining which boxes were used and the number of times the data was fed through the set of boxes. A good algorithm will cycle the plaintext through a given set of boxes many times before yielding the result, and there will be no obvious mapping from plaintext to ciphertext.

The disadvantage of symmetric key encryption is that it depends heavily on a secure channel to send the key to your friend. For example, you would not use e-mail to send your key; if your e-mail is intercepted, a third party is in possession of your secret key, and your encryption is useless. You could relay the key over the phone, but your call could be intercepted if your phone were tapped or someone overheard your conversation.

Common implementations of symmetric key algorithms are DES (Data Encryption Standard), 3-DES (triple DES), IDEA, RC5, Blowfish, and AES (Advanced Encryption Standard). AES is the new Federal Information Processing Standard (FIPS-197) algorithm endorsed for governmental use and chosen to replace DES as the de facto encryption algorithm. AES uses the Rijndael algorithm, chosen after a thorough evaluation of 15 candidate algorithms by the cryptographic research community.

None of the aforementioned algorithms has undergone more scrutiny than DES, which has been in use since the late 1970s. However, the use of DES has drawbacks, and it is no longer considered secure, as the weakness of its 56-bit key makes it unreasonably easy to break. With advances in computing power and speed since DES was developed, the small size of its key renders it inadequate for operations requiring more than basic security for a relatively short period of time. For a few thousand U.S. dollars, you can link off-the-shelf computer systems so that they can crack DES keys in a few hours.

The 3-DES application of DES is intended to combat its degenerating resilience by running the encryption three times; it is projected to be secure for years to come. DES is probably sufficient for such tasks as sending e-mail to a friend when you need it to be confidential, or secure, for only a few days (for example, to send a notice of a meeting that will take place in a few hours). It is unlikely that anyone is sufficiently interested in your e-mail to invest the time and money to decrypt it. Because of 3-DES’s wide availability and ease of use, it is advisable to use it instead of DES.

Encryption Implementation

In practice, most commercial software packages use both public and symmetric key encryption algorithms, taking advantage of the strengths of each and avoiding the weaknesses. The public key algorithm is used first, as a means of negotiating a randomly generated secret key and providing for message authenticity. Then a secret key algorithm, such as 3-DES, IDEA, AES, or Blowfish, encrypts and decrypts the data on both ends for speed. Finally, a hash algorithm, such as DSA (Digital Signature Algorithm), generates a message digest that provides a signature that can alert you to tampering. The digest is digitally signed with the sender’s private key.

GnuPG/PGP

The most popular personal encryption packages available today are GnuPG and PGP. GNU Privacy Guard was designed as a free replacement for PGP, a security tool that made its debut during the early 1990s. Phil Zimmerman developed PGP as a Public Key Infrastructure (PKI) featuring a convenient interface, ease of use and management, and the security of digital certificates. One critical characteristic set PGP apart from the majority of cryptosystems then available: PGP functions entirely without certification authorities (CA). Until the introduction of PGP, PKI implementations were built around the concept of CAs and centralized key management controls.

PGP and GnuPG use the notion of a ring of trust:(2) If you trust someone and that person trusts someone else, the person you trust can provide an introduction to the third party. When you trust someone, you perform an operation called key signing. By signing someone else’s key, you are verifying that that person’s public key is authentic and safe for you to use to send e-mail. When you sign a key, you are asked whether you trust this person to introduce other keys to you. It is common practice to assign this trust based on several criteria, including your knowledge of a person’s character or a lasting professional relationship with the person. The best practice is to sign someone’s key only after you have met face to face to avert any chance of a person-in-the-middle(3) scenario. The disadvantage of this scheme is the lack of a central registry for associating with people you do not already know.

PGP is available without cost for personal use, but its deployment in a commercial environment requires you to purchase a license. This was not always the case: Soon after its introduction, PGP was available on many bulletin board systems, and users could implement it in any manner they chose. PGP rapidly gained popularity in the networking community, which capitalized on its encryption and key management capabilities for secure transmission of e-mail.

After a time, attention turned to the two robust cryptographic algorithms RSA and IDEA, which are an integral part of PGP’s code. These algorithms are privately owned. The wide distribution and growing user base of PGP sparked battles over patent violation and licenses, resulting in the eventual restriction of PGP’s use.

Enter GnuPG, which supports most of the features and implementations made available by PGP and complies with the OpenPGP Message Format standard. Because GnuPG does not use the patented IDEA algorithm but uses BUGS instead, you can use it almost without restriction: It is released under the GNU GPL. The two tools are considered to be interchangeable and interoperable. The command sequences for and internal workings of PGP and GnuPG are very similar.

The GnuPG System Includes the gpg Program

GnuPG is frequently referred to as gpg, but gpg is actually the main program for the GnuPG system.

GNU has a good introduction to privacy, The GNU Privacy Handbook, available in several languages listed at www.gnupg.org/docs.html. Listed on the same Web page is the Gnu Privacy Guard (GnuPG) Mini Howto, which steps through the setup and use of gpg. And, of course, there is a gpg info page.

(2) For more information, see the section of The GNU Privacy Handbook titled Validating Other Keys on Your Public Keyring.

(3) Person in the middle: If Alex and Jenny try to carry on a secure e-mail exchange over a network, Alex first sends Jenny his public key. However, suppose that Mr. X sits between Alex and Jenny on the network and intercepts Alex’s public key. Mr. X then sends his own public key to Jenny. Jenny then sends her public key to Alex, but once again Mr. X intercepts it and substitutes his public key and sends that to Alex. Without some kind of active protection (a piece of shared information), Mr. X, the person in the middle, can decrypt all traffic between Alex and Jenny, reencrypt it, and send it on to the other party.

Don't miss