Encryption Algorithms

Many different encryption algorithms have been created. They were often designed as replacements for earlier algorithms that were found to have weaknesses. The following sections explore the various types of encryption algorithms that have been used or are still used today. These include:

• Asymmetric algorithms

• Symmetric algorithms

• Hashing functions

Asymmetric Encryption Algorithms

Asymmetric encryption is also called public key encryption, but it actually relies on a key pair. Two mathematically related keys, one called the public key and another called the private key, are generated to be used together. The private key is never shared; it is kept secret and used only by its owner. The public key is made available to anyone who wants it. Because of the time and amount of computer processing power required, it is considered "mathematically unfeasible" for anyone to be able to use the public key to recreate the private key, so this form of encryption is considered very secure.

Diffie-Hellman Algorithm

Whitfield Diffie and Martin Hellman published the Diffie-Hellman algorithm for key exchange in 1976. This was the first published use of public key cryptography, and arguably one of the cryptography field's greatest advances ever. Because of the inherent slowness of asymmetric cryptography, the Diffie-Hellman algorithm was not intended for use as a general encryption scheme—rather, its purpose was to transmit a private key for Data Encryption Standard (DES) (or some similar symmetric algorithm) across an insecure medium. In most cases, Diffie-Hellman is not used for encrypting a complete message because it is 10 to 1,000 times slower than DES, depending on implementation.

Prior to publication of the Diffie-Hellman algorithm, it was difficult to share encrypted information with others because of the inherent key storage and transmission problems (as discussed later in this chapter). Most wire transmissions were insecure, since a message could travel between dozens of systems before reaching the intended recipient and any number of snoops along the way could uncover the key. With the Diffie-Hellman algorithm, the DES secret key (sent along with a DES-encrypted payload message) could be encrypted by one party and decrypted only by the intended recipient.

In practice, this is how a key exchange using Diffie-Hellman works:

• The two parties agree on two numbers; one is a large prime number, the other is an integer smaller than the prime. This can be done in the open and does not affect security.

• Each of the two parties separately generates another number, which they keep secret. This number is equivalent to a private key. A calculation is made involving the private key and the previous two public numbers. The result is sent to the other party. This result is effectively a public key.

• The two parties exchange their public keys. They then privately perform a calculation involving their own private key and the other party's public key. The resulting number is the session key. Each party will arrive at the same number.

• The session key can be used as a secret key for another cipher, such as DES. No third party monitoring the exchange can arrive at the same session key without knowing one of the private keys.

The most difficult part of the Diffie-Hellman key exchange to understand is that there are actually two separate and independent encryption cycles happening. As far as Diffie-Hellman is concerned, only a small message is being transferred between the sender and the recipient. It just so happens that this small message is the secret key needed to unlock the larger message.

Diffie-Hellman's greatest strength is that anyone can know either or both of the sender and recipient's public keys without compromising the security of the message. Both the public and private keys are actually just very large integers. The Diffie-Hellman algorithm takes advantage of complex mathematical functions known as discrete logarithms, which are easy to perform forwards but extremely difficult to find inverses for. Even though the patent on Diffie-Hellman has been expired for several years, the algorithm is still widely used, most notably in the IPSec protocol. IPSec uses the Diffie-Hellman algorithm in conjunction with RSA authentication to exchange a session key that is used for encrypting all traffic that crosses the IPSec tunnel.

Test Day Tip 

Do not despair if you cannot follow all of the math behind the encryption algorithms and cryptosystems discussed. The important things to know are the theory and the practical application. Keep your mind fresh with an overview of the different crypto methods on the morning of the test—there is no need to cram for binary math and assembly language product-of-two-primes factoring equations.

RSA Algorithim

In the year following the Diffie-Hellman proposal, Ron Rivest, Adi Shamir, and Leonard Adleman proposed another public key encryption system. Their proposal is now known as the RSA algorithm, named for the last initials of the researchers. The RSA algorithm shares many similarities with the Diffie-Hellman algorithm in that it is also based on multiplying and factoring large integers. However, RSA is significantly faster than Diffie-Hellman, leading to a split in the asymmetric cryptography field that refers to Diffie-Hellman and similar algorithms as Public Key Distribution Systems (PKDS), and to RSA and similar algorithms as Public Key Encryption (PKE). PKDS systems are used as session key exchange mechanisms, while PKE systems are generally considered fast enough to encrypt reasonably small messages. However, PKE systems like RSA are not considered fast enough to encrypt large amounts of data like entire filesystems or high-speed communications lines.

Because of the former patent restrictions on RSA, the algorithm saw only limited deployment, primarily only from products by RSA Security, until the mid-1990s. Now you are likely to encounter many programs making extensive use of RSA, such as Pretty Good Privacy (PGP) and Secure Shell (SSH). The RSA algorithm has been in the public domain since RSA Security placed it there two weeks before the patent expired in September 2000. Thus the RSA algorithm is now freely available for use by anyone, for any purpose.

Digital Signature Algorithm

Digital Signature Algorithm (DSA) is a public key encryption algorithm. This name was granted by the National Institute of Standards and Technology (NIST) for the digital signature method defined by NIST's Digital Signature Standard (DSS). The defined goal was the creation of a standard for substitution of handwritten signatures with binary ones. The algorithm utilizes public and private key pairs. Only the private key of a key pair is capable of creating a signature. This permits verification of the sender's identity as well as assurance of the integrity of the message data that has been signed. The hash function used in the creation and verification process is defined in the Secure Hash Standard (SHS).

To create a signature, the message is processed by the SHS hashing algorithm, thereby creating a message digest. The private key and the digest are then used as inputs to the DSA, which generates the signature. For message and sender verification, the recipient uses the hash function to create a message digest, and then the sender's public key is used to verify the signature. Allowed key sizes range from 512 to 1,024 bits. DSA is much slower than RSA for signature verification.

Symmetric Encryption Algorithms

Symmetric encryption is also called secret key encryption, and uses just one key, called a shared secret, for both encrypting and decrypting. This is a simple, easy-to-use method of encryption, but there is one problem with it: The key must be shared between the sender and the recipient of the data, so a secure method of key exchange must be devised. Otherwise, if a third party intercepts the key during the exchange, they can easily decrypt the data.

Data Encryption Standard Algorithm

Among the oldest and most famous encryption algorithms is the DES, which was developed by IBM and was the U.S. government standard from 1976 until 2001. DES was based significantly on the Lucifer algorithm invented by Horst Feistel, which never saw widespread use. Essentially, DES uses a single 64-bit key—56 bits of data and 8 bits of parity—and operates on data in 64-bit chunks. This key is broken into 16 separate 48-bit subkeys, one for each round, which are called Feistel cycles. Figure 6.1 gives a schematic of how the DES encryption algorithm operates.

Figure 6.1: Diagram of the DES Encryption Algorithm

Important elements of the DES algorithm include the "S-boxes," the key schedule, permutations "P," and the "E operator." Each round consists of a substitution phase, wherein the data is substituted with pieces of the key, and a permutation phase, wherein the substituted data is scrambled (re-ordered). Substitution operations, sometimes referred to as confusion operations, are said to occur within S-boxes. Similarly, permutation operations, sometimes called diffusion operations, are said to occur in P-boxes. Both of these operations occur in the "F Module" of the diagram.

Triple DES Algorithm

Triple DES (3DES) encryption is based on the DES algorithm; however, to improve security, the encryption is performed three times (hence the name) using three different keys. The multiple encryptions result in a ciphertext that has an "effective" key size as large as the sum of the sizes of the three keys. The keys can all be different numbers, all the same number, or two can be the same. In some common implementations the same key is used for the first and third stage of processing, somewhat reducing the strength of the encryption. If all three 64-bit keys have the same value, the algorithm is no stronger than DES.

Advanced Encryption Standard Algorithm

The Advanced Encryption Standard (AES) defined a new algorithm to use in place of DES and its derivatives, 3DES and DES eXclusive (DESX). NIST accepted proposals for review in 1997. Once the search began, most of the big-name cryptography players submitted their own AES candidates. Among the requirements of AES candidates were:

• AES would be a private key symmetric block cipher (similar to DES).

• AES needed to be stronger and faster then 3DES.

• AES required a life expectancy of at least 20 to 30 years.

• AES would support key sizes of 128 bits, 192 bits, and 256 bits.

• AES would be available to all—royalty free, non-proprietary, and unpatented.

Within months, NIST had a total of 15 different entries, six of which were rejected almost immediately on grounds that they were considered incomplete. By 1999, NIST had narrowed the candidates down to five finalists including MARS, RC6, Rijndael, Serpent, and Twofish.

Selecting the winner took approximately another year, as each of the candidates needed to be tested to determine how well they performed in a variety of environments. After all, applications of AES would range anywhere from portable Smart Cards to standard 32-bit desktop computers to high-end optimized 64-bit computers. Since all of the finalists were highly secure, the primary deciding factors were speed and ease of implementation (which in this case meant memory footprint).

Rijndael was ultimately announced the winner in October 2000 because of its high performance in both hardware and software implementations and its small memory requirement. The Rijndael algorithm, developed by Belgian cryptographers Dr. Joan Daemen and Dr. Vincent Rijmen, also seems resistant to power- and timing-based attacks.

So how does AES/Rijndael work? Instead of using Feistel cycles in each round like DES, it uses iterative rounds like International Data Encryption Algorithm (IDEA) (discussed in the next section). Data is operated on in 128-bit chunks, which are grouped into four groups of 4 bytes each. The number of rounds is also dependent on the key size, such that 128-bit keys have 9 rounds, 192-bit keys have 11 rounds, and 256-bit keys have 13 rounds. Each round consists of a substitution step of one S-box per data bit followed by a pseudo-permutation step in which bits are shuffled between groups. Then, each group is multiplied out in a matrix fashion and the results are added to the subkey for that round.

How much faster is AES than 3DES? It is difficult to say, because implementation speed varies widely depending on the type of processor performing the encryption and whether or not the encryption is being performed in software or running on hardware specifically designed for encryption. However, in similar implementations, AES is always faster than its 3DES counterpart. One test, performed by Brian Gladman, shows that on a Pentium Pro 200 with optimized code written in C, AES (Rijndael) can encrypt and decrypt at an average speed of 70.2 Mbps, versus the DESs speed of only 28 Mbps. You can read his other results at fp.gladman.plus.com/cryptography_technology/aes.

Exam Warning 

With the continued deployment of IPSec solutions and rapid adoption of the standard by hardware and software vendors, an understanding of the AES, its details, and its purpose, is very important.

International Data Encryption Algorithm

Ascom Systems, Ltd. holds a patent on the International Data Encryption Algorithm (IDEA). The algorithm supports both Electronic Code Book (ECB) and Cipher Block Chaining (CBC) with eight initial vectors (CBC64). A 128-bit key is used to enhance security. Not only is IDEA newer than DES, but IDEA is also considerably faster and more secure. IDEA's enhanced speed is due to the fact that each round consists of much simpler operations than the Fiestel cycle in DES. These operations (XOR, addition, and multiplication) are much simpler to implement in software than the substitution and permutation operations of DES.

Test Day Tip 

You may find it helpful to create a chart detailing the various algorithms and the bit sizes for their keys on the scrap paper provided to you during the exam. If you take your time and compare questions with the correct information you put in your chart, you might find it easy to spot incorrect answers that "look right" at a first or casual glance.

SkipJack

SkipJack is intended only for use embedded in electronic encryption devices. This makes it unique since the other algorithms might be implemented in either hardware or software, while SkipJack is intended for hardware only. SkipJack operates in a manner similar to DES, but uses an 80-bit key and 32 rounds, rather than 56-bit keys and 16 rounds (DES).

Hashing Algorithm Functions

Hashing is a technique in which an algorithm (also called a hash function) is applied to a portion of data to create a unique digital "fingerprint" that is a fixed-size variable. If anyone changes the data by so much as one binary digit, the hash function will produce a different output (called the hash value) and the recipient will know that the data has been changed. Hashing can ensure integrity and provide authentication. The hash function cannot be "reverse-engineered"; that is, you cannot use the hash value to discover the original data that was hashed. Thus, hashing algorithms are referred to as one-way hashes. A good hash function will not return the same result from two different inputs (called a collision); each result should be unique.

There are several different types of hashing, including division-remainder, digit rearrangement, folding, and radix transformation. These classifications refer to the mathematical process used to obtain the hash value. Standard hashing algorithms include:

• MD2

• MD4

• MD5

• Secure Hash Algorithm (SHA)

Message Digest 4

Message Digest 4 (MD4) is a one-way hash function. A message digest is a small digital signature, generally intended for use with e-mail or other electronic communication. The MD4 hash function produces a hash 128 bits in size from a plaintext message of any size. Ronald Rivest, of RSA fame, created MD4 in 1990. It was discovered that MD4 was vulnerable to several types of attack as well as collisions. Therefore MD4 is now considered obsolete and has been replaced by MD5. Details and sample code for the algorithm are available in RFC 1320 (www.ietf.org/rfc/rfc1320.txt).

A message hashed with MD4 has bits added so that the total message length (in bits) plus an additional 64 bits is divisible by 512. MD4 then appends a 64-bit "snapshot" of the message length. Next, the message is encrypted in 512-bit blocks. Each block is manipulated three times in production of the final hash.

Message Digest 5

Rivest responded to the critiques of MD4 with the creation of Message Digest 5 (MD5) in 1991. MD5, like MD4, creates a 128-bit hash, pads the message to a length divisible by 512, and processes the message in 512-bit blocks. MD5 is different from MD4 in its use of four rounds of processing rather than three. MD5 is slower than MD4 but much more secure.

Details of the algorithm are published in RFC 1321 (www.ietf.org/rfc/rfc1321.txt).

In the RFC summary, the authors propose "…that the difficulty of coming up with two messages having the same message digest is on the order of 2^64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2^128 operations."

SHA-1 (160-bit)

SHA-1 is a replacement for SHA, described by the SHS. SHA and SHA-1 were developed by NIST. SHA-1 is similar to the MDx hash functions, although slightly slower. This performance loss is due to the creation of a 160-bit message digest rather than a 128-bit one. The greater number of bits in the digest makes the algorithm stronger against collisions and other attacks.

Exercise 6.01: Cracking an NT Password Hash

In this exercise, you will use a well-known utility from the NT security community to examine the reconstruction of plaintext password data from the one-way hashes stored on NT systems. This tool was originally published as L0phtCrack by L0pht Heavy Industries, but is now provided for research and historical purposes by the company @Stake, founded by the creator.

1. Download the file lcsrc.zip found at: www.atstake.com/research/lc/dist/lcsrc.zip.

2. Unzip the file into a directory such as C:\LC.

3. Change into that directory and run the lc_cli.exe command to view the program options. They are:

   Usage: lc_cli.exe -p <pwfile> -w <wordlist> -o <ofile> -b [-l || n]     -p <pwfile>   The password file to read from in pwdump format     -P <pwfile>   The password file to read from in sniffer format     -w <wordlist> The dictionary of words to try     -o <ofile>    File to write results to - if not specified defaults                   to stdout     -b            Brute force through the entire keyspace <A-Z takes                   26 hours on PPRO 200>     -l            Only go after the LANMAN password     -n            Only go after the NT Dialect password [dumb!] without                   the -l or -n it goes after both which is still much                    faster than going after the NT Dialect password only!                   Note: Both -p and -w are required, unless -b is specified in which case -w                   must be ommited                   [e-mail]

Also included in the extracted files are sample password extract files: pwfile.txt, pwfile2.txt, and so on. A dictionary file, wfile.txt, is also present. This is enough to begin the demonstration.

Before running the program, examine the format of the extracted password hashes in the pwfile.txt file. A utility is included called pwdump.exe that can extract the password hashes from a system if you already have administrator access to the system. The extracted password hashes appear like this in the file:

BillG:1010:5ECD9236D21095CE7584248B8D2C9F9E:C04EB42B9F5B 114C86921C4163AEB5B1::: Administrator:500:73CC402BD3E791756C3D3B817E02809D:C7E26 22D76D3F001CF08B0753646BBCC: Built-in account for administering the computer/domain:: fredc:1011:3466C2B0487FE39A417EAF50CFAC29C3:80030E356D15 FB1942772DCFD7DD3234::: twoa:1000:89D42A44E77140AAAAD3B435B51404EE:C5663434F963B E79C8FD99F535E7AAD8::: william:1012:DBC5E5CBA8028091B79AE2610DD89D4C:6B6E0FB2ED 246885B98586C73B5BFB77::: threea:1001:1C3A2B6D939A1021AAD3B435B51404EE:E24106942BF 38BCF57A6A4B29016EFF6::: foura:1002:DCF9CAA6DBC2F2DFAAD3B435B51404EE:FA5664875FFA DF0AF61ABF9B097FA46F:::

Appearing on each line are the NT account name, the numerical user ID, the LANMAN hash, and the NT MD4 password hash. Colons separate all of the entries. Note that this file format is the same as a Samba password file.

At the command prompt, enter the command lc_cli.exe -p pwfile.txt -w wfile.txt and then press Enter. This produces the following:

User: [threea] Lanman PW: [AAA] NT dialect PW: [aaa] User: [BillG] Lanman PW: [YOKOHAMA] NT dialect PW: [YokoHama] User: [fredc] Lanman PW: [CRACKPOT] NT dialect PW: [crackpot] User: [william] Lanman PW: [IMPUNITY] NT dialect PW: [impunity] User: [Administrator] Lanman PW: [SCLEROSIS] NT dialect PW: [ScleROSIS] 

As can be seen, choosing short, weak passwords can make cracking them quite simple. If an attacker uses a sniffer and captures the hash challenge-response exchange over the network, L0phtCrack can decrypt it. Source code for the command line, graphical user interface (GUI) version, and the pwdump.exe program is also provided in the zip file.

Exam Warning 

A thorough understanding of encryption key use, management, weaknesses, strengths, and functions is very important. Ensure that you understand which algorithms use what type and size of keys and why.

Damage & Defense…
LANMAN Weaknesses…

Older Windows-based clients store passwords in a format known as LAN Manager (LANMAN) hashes, which is a horribly insecure authentication scheme. However, since this chapter is about cryptography, we will limit the discussion of LANMAN authentication to the broken cryptography used for password storage.

As with UNIX password storage systems, LANMAN passwords are never stored on a system in cleartext format—they are always stored in a hash format. The problem is that the hashed format is implemented in such a way that even though DES is used to encrypt the password, the password can still be broken with relative ease. Each LANMAN password can contain up to 14 characters, and all passwords less than 14 characters are padded to bring the total password length up to 14 characters. During encryption the password is split into a pair of seven-character passwords, and each of these seven-character passwords is encrypted with DES. The final password hash consists of the two concatenated DES-encrypted password halves.

Since DES is known to be a reasonably secure algorithm, why is this implementation flawed? Shouldn't DES be uncrackable without significant effort? Not exactly. Recall that there are roughly 100 different characters that can be used in a password. Using the maximum possible password length of 14 characters, there should be about 10014 or 1.0×1028 possible password combinations. LANMAN passwords are further simplified because there is no distinction between upper- and lowercase letters—all letters appear as uppercase. Furthermore, if the password is less than eight characters, the second half of the password hash is always identical and never needs to be cracked. If only letters are used (no numbers or punctuation), then there are only be 267 (roughly eight billion) password combinations. While this may seem like a large number of passwords to attack via brute force, remember that these are only theoretical maximums and that since most user passwords are quite weak, dictionary-based attacks will uncover them quickly. The bottom line here is that dictionary-based attacks on a pair of seven-character passwords (or even just one) are much faster than those on single 14-character passwords.

Suppose strong passwords that use two or more symbols and numbers are used with the LANMAN hashing routine. The problem is that most users tend to just tack on the extra characters at the end of the password. For example, if a user uses his birthplace along with a string of numbers and symbols such as "MONTANA45%," the password is still insecure. LANMAN will break this password into the strings "MONTANA" and "45%." The former will probably be caught quickly in a dictionary-based attack, and the latter will be discovered quickly in a brute force attack because it is only three characters. For newer business-oriented Microsoft operating systems such as Windows NT and Windows 2000, LANMAN hashing can and should be disabled in the registry, if possible, though this will make it impossible for Win9x clients to authenticate to those machines.

Microsoft addressed the weaknesses of the LANMAN authentication with the introduction of a new standard for Windows NT known as NT LAN Manager (NTLM), followed by NTLM2. NTLM supports mixed-case passwords as well as eliminating the splitting of passwords into two separate units. NTLMv2 supports 128-bit encryption, although the default is 56 bits. NTLMv2 also provides additional security features including unique session keys and other improvements. Windows 2000 introduced an entirely different authentication model based on the Kerberos authentication standard.