Encryption Algorithms
Encryption algorithms, or ciphers, are core components of any cryptosystem. These are the mathematical functions that combine plain text and a secret key to produce cipher text.
This section describes some of the common encryption algorithms publicly in use today. Keep in mind that this is not a complete list, but rather a sampling of some popular ciphers. Recall the two different encryption systems: symmetric and public key (or asymmetric). Each uses a different set of algorithms to do its job.
Symmetric key encryption algorithms can operate in one of two modes: block ciphers and stream ciphers. Block ciphers apply encryption to a certain block of data, measured in bits. For example, a typical block cipher like Digital Encryption Standard (DES) encrypts data in 64-bit blocks. What do you do with data that cannot be evenly broken down into 64-bit blocks? In this case, the extra bits needed to fill up a block are added to the plain text. This process is called padding, and it involves adding random data to the plain text to achieve a 64-bit block.
Consider the following sentence:
This sentence does not add up.
Your computer sees this sentence as a string of 30 bytes. Because a byte has 8 bits, this sentence contains 240 bits. 240 bits are not evenly divisible by 64, so the DES algorithm needs to pad an extra 16 bits of random data to this string, making it a total of 256 bits, which can be divided into four blocks of 64 bits. A block cipher might then apply encryption to each block separately, using a different seed for each, or the same, depending on the implementation.
Stream ciphers are the other major mode of symmetric key algorithms. In this case, the data can be encrypted byte by byte. The stream cipher is obtained from a pseudo- random number generator (PRNG) to produce a pseudo-random stream of bits. This bit stream is combined with the plain text to create the cipher text. Notice that the stream ciphers do not work on blocks of data as the block ciphers do. The stream cipher is considered faster, working on a bit by bit or byte by byte stream of data, depending on the implementation.
The concept of a stream cipher can be hard to understand. Let's try to illustrate. Remember invisible ink pens? As you wrote, each word was hidden, invisible to prying eyes. This is nearly the same thing as stream cipher encryption. Imagine that as your data is sent across the network, it is being encrypted one word at a time.
The AES Project
In 1997, the U.S. National Institute of Standards and Technology (NIST) opened a worldwide competition aimed at deciding a replacement algorithm for DES. Known as the Advanced Encryption Standard (AES), the project decided its winner in November of 2000: the Rijndael cipher. This was an important event for NIST because DES had become outdated, and a new encryption standard was needed for government use. The contest also helped to raise encryption awareness globally, and it brought together developers worldwide.
Symmetric Key Algorithms: Block Ciphers
Listed here are some popular block ciphers. DES is mentioned because it is still widely used today, even though it has been proven insecure by the power of modern hardware to crack it. Each block cipher is unique, using different algorithms, key lengths, and block sizes to do its job. The important thing to note is that these are each widely used, and primarily considered secure with the exception of DES.
DES
The Digital Encryption Standard was developed at IBM Thomas J. Watson Labs in the 1970s. It was soon after adopted by NIST as the standard encryption algorithm to be used for unclassified, low-security files. DES encrypts in 64-bit blocks by using a 56-bit key for encryption. DES was a good solution for many years, but with the power of technology increasing with Moore's Law (computing power doubles every 12–18 months), the DES encryption algorithm has been proven insecure, cracked by Distributed.Net and Electronic Frontier Foundation in a record 22 hours in January of 1999. It is believed that DES can be cracked even more quickly today. Refer to http://www.eff.org/Privacy/Crypto_misc/DESCracker/HTML/19990119_deschallenge3.html for full details.
3DES (Triple DES)
3DES is DES three times over. Created by IBM and the National Security Agency (NSA), it makes three passes on the plain text, encrypting each pass with a new 56-bit key, making for a total of 168-bit key encryption. It, like DES, applies encryption in 64-bit blocks. This algorithm has proved highly secure, with no publicly known compromises to date. Although it is three times DES, the end result is only about twice as secure as DES.
Blowfish
Bruce Schneier and the team at Counterpane Labs invented this popular encryption algorithm. It allows for a variable length key of up to 448 bits. This algorithm is unpatented and available for public use. Blowfish is considered a highly secure and highly optimized algorithm, with no major attacks against it to date.
CAST
Designed by Carlisle Adams and Stafford Taveres, CAST is also confidently considered highly secure. The CAST algorithm is patented by Entrust Technologies, but released to the public for free use. This cipher has 128- and 256-bit versions.
IDEA
Another block algorithm that is considered highly secure is IDEA, developed in Zurich, Switzerland by Xuejia Lai and James Massey. IDEA uses a 128-bit key and is designed to be resistant to certain popular attacks (differential cryptanalysis) on symmetric key encryption systems.
RC2, RC5, and RC6
RC2 is a block cipher that was originally created by Ronald Rivest of RSA Data Security. RC5 was the successor to RC2, attempting to overcome the discovered security weaknesses of the algorithm. David Wagner, John Kelsey, and Bruce Schneier found weaknesses in both RC2 and RC5. RC6 is the latest from Ronald Rivest. It was an AES submission, and it works on 128-bit blocks.
Rijndael
Two Belgium cryptographers, Joan Daemen and Vincent Rijmen, developed Rijndael. The creators have graciously decided to never patent this algorithm. It uses a variable length block and key length. When people refer to the current AES algorithm, they are referring to Rijndael.
Twofish
Also designed by the team at Counterpane Labs, Twofish was originally an AES submission. A 256-bit block cipher, it is considered highly secure, and is being considered by the NIST as a replacement for the current AES.
These are just some of the choices you have for block ciphers. The one you should choose depends on your needs. If you have a high security concern, you should not choose DES because it only suffices for low security. CAST and Blowfish are great choices. Both are considered relatively fast and extremely secure. Block ciphers are important because these are what you will use most often when encrypting files on your computer.
Symmetric Key Algorithms: Stream Ciphers
Stream ciphers are popular in Web browsers and SSL connections. They are commonly used to help set up secure channels between a Web browser and an online shopping site. Stream ciphers are considered faster than block ciphers. They encrypt data byte by byte, as opposed to a block cipher, which encrypts data in chunks of multiple bytes.
RC4
Another breed of algorithm from Ronald Rivest, RC4 can be found in popular Web browser implementations including Internet Explorer and Netscape Navigator. RC4 is a variable key length stream cipher operating in bytes.
SEAL
The Software optimized Encryption Algorithm was originally designed by Rogaway and Coppersmith in 1993. It is a fast stream cipher for 32-bit machines. Operating systems such as Windows 95, 98, Me, 2000, and XP are considered 32-bit operating systems because they are capable of processing data 32 bits at a time.
Public Key Algorithms
Public key algorithms are largely used for sending secure e-mail messages with programs such as PGP. Web browsers and Web sites can also use them to set up secure SSL channels. Public key systems operate using two keys. They can serve two purposes: 1) encryption of information; and 2) digital signatures. For encryption, the public key is used to encrypt the information, whereas the private key is used to decrypt it. For digital signatures, the owner uses his private key to encrypt a portion of text, whereas the recipient uses the owner's public key to decrypt and verify the signature.
Diffie-Hellman Key Exchange
The Diffie-Hellman key exchange is a popular method for exchanging secret keys over an insecure medium such as the Internet. It was developed by W. Diffie and M.E. Hellman around 1976. These pioneers of public key cryptography knew that it would be essential for two people to securely exchange a secret key over an insecure network. The Diffie-Hellman key exchange is not perfect because it is vulnerable to a man-in-the-middle attack; however, it is widely agreed to be a good method for secret key exchange.
RSA
RSA can be used for both encrypting data and as the foundation of a digital signature. Originally developed by Ronald Rivest, Adi Shamir, and Leonard Adleman, RSA is well known worldwide. Public experts in mathematics and cryptography have tested RSA, and it has proven secure. However, attacks have been proposed against it, and certain implementations were found to be weak. RSA key sizes can be any length, although 1024 bits is common. RSA can be computationally slow on a small PC.
DSS
The NSA created the Digital Signature Standard, and NIST adopted it. It is based on the Digital Signature Algorithm (DSA), which allows for keys of any length. As specified by NIST, DSS should use keys of either 521-bit or 1024-bit sizes. Although DSA can be used for encryption, the standard calls for DSS to be used only for digital signatures.
Hashing Algorithms
We have not mentioned the hashing algorithms up until this point because they do not provide encryption in and of themselves; rather, they aid the encryption process. These are known as message digest functions. They can have several purposes:
Create encryption keys for use with symmetric key ciphers
Provide proof that files are authentic and unaltered
Aid in the creation of digital signatures
Basically, a message digest function looks at a file bit by bit and equates it to a single large number of 128 or 256 bits in length, which basically serves as an ID for the file. Technically, this single large number is called a message digest, hash, or fingerprint. If you run the same message digest against the same file at any point in time, you will get the same digest. If a single bit in the file changes, the entire digest changes. In this way, you can detect when a file has been modified or tampered with.
Why should anybody do this? Using hashing algorithms to create a message digest is beneficial in several instances:
To give Web site visitors a way to determine if downloaded files are authentic
To ID personal files and later determine whether they have been modified
To create a semi-random number used by an encryption algorithm
For example, consider that Bob shares a computer at work with Alice. Bob is going on vacation for two weeks. He has some important client files stored on the computer. Upon return, Bob wants to be able to determine whether Alice has modified any of his client files. By creating a message digest for these files before he leaves for vacation, he creates a file fingerprint. When he returns from vacation, he can create a message digest again. If the files have not been modified, the file fingerprint will be the same as when he left. If the fingerprint is different, he will know that somebody modified the file.
The following sections detail a few message digest functions that are in use today.
MD5
Message Digest 5 (MD5) was created by Ronald Rivest. It produces a 128-bit message digest. Although attacks have been proposed against MD5, it is still widely used and generally considered secure. It is not quite as secure as SHA-1 because of its smaller digest size, but its size actually makes it faster to use.
SHA-1
The Secure Hash Algorithm (SHA) is a standard developed by NIST. SHA-1, a 1994 revision to SHA, is used today to produce a 160-bit message digest. SHA-1 is slower to use than MD5, but it is stronger because of the larger digest size.
HMAC
Hash function-based Message Authentication Code (HMAC) is actually something applied to one of the functions such as MD5 or SHA-1. HMAC is a protection mechanism that takes the digest one step further by actually protecting the integrity of the digest. If an attacker tries to modify your message digest, HMAC knows that the digest has been tampered with. HMAC is a technique that uses the message digest function (MD5 or SHA-1) in conjunction with a secret key to produce a checksum on the message digest.
MD5SUM.EXE Walkthrough
It is good to get your feet wet with hashing algorithms, so we will go through an example. As stated, hashing algorithms provide a great way to get the fingerprints of a file. Using these fingerprints, you can easily tell if the file has been tampered with or modified. MD5SUM.EXE is a Windows program for generating the fingerprint. You first run MD5SUM.EXE with any file as input, and the fingerprint of the file is output to you. You can also feed the file fingerprint to MD5SUM.EXE as input, and get output that tells you if the file has been modified.
Why would you want to use MD5SUM.EXE? Here's why:
It can create a baseline of fingerprints for important files on your computer.
Several Web sites are offering their MD5 fingerprints for files that you download. By running MD5SUM.EXE against their file and fingerprint, you can determine whether the file has been hacked or modified.
It is important to realize that these hashing algorithms are used to create an ID or fingerprint for a file. They do not contain data from the original file or alter the original file. Let's stop and run some MD5 digests of our own to see how this works:
1. |
Download MD5SUM.EXE for Windows and save it to C:md5sum.exe. The program is openly licensed under the GNU license agreement, so different versions exist all over the place. One place you can get it is http://unxutils.sourceforge.net/, but you will have to load the UnxUtils.zip and extract it from there. |
2. | |
3. |
Save the file as C:md5test.txt. |
4. |
Open a command prompt (select Start, Run and type command or cmd). |
5. |
At the command prompt, type md5sum.exe md5test.txt > md5test.md5. After you press Enter, a new file named md5test.md5 is created, containing the message digest and a reference to the original filename. |
6. |
Now verify the file integrity by typing the following command at the prompt: md5sum.exe -cv md5test.md5. md5sum.exe returns with a message saying that the file is okay, as in Figure 12.24. Figure 12.24. Using md5sum.exe to verify a file's integrity.
|
7. |
Now open md5test.txt in Notepad again, and delete the word is so that you only have the following: This a test of MD5 message digests. |
8. |
Repeat step 6 to see how the modified file will fail the fingerprint check, as shown in Figure 12.25. Figure 12.25. Using md5sum on a modified file returns a failure.
Success! In essence, you have succeeded in using md5sum.exe to verify a file's integrity. The next time you download a file from the Internet, grab its MD5 message digest if it is provided, and check its integrity. |
9. |
If you want, go ahead and add the word is back to the sentence. Run the check again, and you will see that your MD5 sum returns OK. |
Today, many sites are using message digest to protect you from downloading the wrong version of a file. Because the fingerprint IDs the file, you can determine whether the file you downloaded is the original. This protects you against such things as forgeries, viruses, or transmission errors.
Let's look at the message digest. The message digest, or fingerprint, is a string of letters and numbers. It appears as unreadable gibberish, but serves to identify the file. You might think of it as a serial number, which also often appears as a string of unreadable text. Tables 12.5 and 12.6 demonstrate the input to the MD5 function and the digest or fingerprint of those results. Each row of text in the column on the left was typed into a separate text file using Windows Notepad. The text in the second column shows the corresponding message digest produced from the original text. These tables show how different the message digest is for each text file.
| MD5 Function Applied to the Following Text | Message Digest |
|---|---|
| This is a test of the MD5 function. | 162135972a0371739a6e33e820ef0971 |
| This is another test of the MD5 function. | d288caebe9951d53e06a4ea08b6aa82a |
| This is a third test of the MD5 function. | 7f1979a409067cdb62b951bac57bf91c |
| MD5 Function Applied to the Following Text | Message Digest |
|---|---|
| This is a test of the MD5 function. | 162135972a0371739a6e33e820ef0971 |
| This is the last test. | 0749f091848d6f995bd368e068624f12 |
Take a look at the first example in Table 12.6. Notice that the same text file produces the same message digest. This is a natural outcome of the message digest function. What is important is that two different text files (or any files for that matter!) do not produce the same digest. If they do, you have a collision of digests. Collisions do happen, but for a message digest function to be secure, it must be computationally improbable for a collision to occur.
For example, if you produce the same message digest for your Microsoft Money financial file as you do for your top secret business plan file written in Microsoft Word, you have a collision. When this happens, you no longer have a unique fingerprint for each file, so the message digest is more or less invalid. This is a rare occurrence, but it's possible.