Introduction: definitions

Encryption Algorithms

Brad McReynolds IFSM430

3 May 2002

Potential Test Questions

1. Q. What is the main difference between block and stream ciphers?

A. Block ciphers encrypt data in fixed block sizes usually 64 or 128-bits at a time. Stream ciphers encrypt data one bit at a time.

2. Q. What is a one-way function?

A. An algorithm that is easy to perform in the forward direction and difficult to perform in the reverse direction.

3. Q. What principle are public-key encryption systems based on?

A. A difficult mathematical problem where the public and private keys are linked.

4. Q. What are hash-functions most frequently used for?

A. Digital signature.

5. Q. What is the most common asymmetric encryption algorithm?

A. RSA

6. Q. What block sizes does DES use?

A. 64-bit for data and 56-bit for key length.

7. Q. Which encryption method is best suited for disk and file encryption?

A. Symmetric (private-key)

8. Q. Which Algorithm includes compression

A. PGP

Introduction

The ability to hide information has been a major concern of governments and business for thousands of years. Ancient generals created simple but effective techniques to hide the meaning of war plans. Recently governments have passed legislation imposing stiff penalties for the theft of company trade secrets. The need to protect data has never been greater than in this age of political instability and electronic business practices. A plethora of computer algorithms exist to keep data hidden whether it’s stored on a hard drive or buried in an e-mail attachment.

Background

Encryption is the process of scrambling or masking the characteristics of data. Although not developed for information hiding, a simple example is Morse code where dot and dash combinations represent letters. For example: …., ., .-.., .-.., ---, .--, ---, .-., .-.., -.. . This works well to hide information but is useless if the data cannot be returned to its original state. Decryption is the process that returns encrypted data back into a usable form. In a simple cryptographic scheme, like Morse code, the decryption would simply require looking at a table of dot/dash combinations corresponding to letters (the key) and determining which letters the dot and dash strings represent; decrypting the above example equates to “hello world”.

Encryption methods are derived from the science of cryptography and are known as ciphers. Two categories of ciphers exist, substitution and transposition. [1]

Substitution ciphers perform a one for one character exchange of the original plain text information without any letter reordering. Caesar used this approach more than 2000 years ago by offsetting letters by three. To illustrate, suppose we want to encode the word attack. Using the caesarian cipher, a + 3 = d, t + 3 = w, c + 3 = f and k + 3 = n so attack now becomes dwwdfn. [2]

Transposition ciphers retain the original message text but change the character order. Cryptographers call this a permutation. One way to permute a string is by using the rail fence approach. [2] For example, to encipher the string ‘do your homework’ first move each alternate letter done a line

d y u h m w r

o o r o e o k

then concatenate the strings into one with the resultant being dyuhmwrooroeok. Modern ciphering algorithms use a combination of substitution and Transposition. [2]

Algorithm Types

The three basic categories of encryption algorithms are:

· Symmetric

· Asymmetric

· Hash functions.

Symmetric (private-key)

Symmetric ciphers are built on a one (private) key philosophy for both encoding and decoding data. These algorithms come in two varieties, block and stream ciphers

Block Ciphers

Block ciphers are the most common form of symmetric algorithm. They manipulate data in 64-bit segments employing a single key that can vary in length from 64 to over 400 bits. The algorithms involve between eight and thirty-two rounds through a feistel network. A feistel networks is a non-linear function that splits the data in two halves and Exclusive Ors (XOR) one half with the other. One pass through the function is considered a round and is usually implemented as a loop. XORing is just a comparison of two bits and only results in a 1 if one of the bits is 1 and the other is 0. For example; 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0. Some common block ciphers are DES, Triple-DES and Blowfish. [3]

DES

One of the first block ciphers in common use was the Data Encryption Standard (DES). This algorithm encrypts 64-bit chucks at a time and uses a 56-bit key length. It performs substitution by means of eight s-boxes and transposition utilizing Feistel networks to mask the data. [4] The s-boxes are nothing more than predefined arrays where the bit values are mapped to individual array indexes. The encryption consists of sixteen rounds of different substitutions and permutations, which are easy to reverse. [1].

Since most block ciphers use DES principles as a foundation, looking at how the DES source code works will hopefully improve your understanding of symmetric algorithms. First a 64-bit key is input to the function and the key schedule is determined. If the key is less than 64-bits it must be padded with ones, zeros or a combination of both. The string is broken up into 8-bytes with the least significant bit of each byte being a parity bit reducing the key to 56 bits. The bits are rearranged into two 28-element arrays in this bit order, remember the parity bits, 8, 16, 24, 32, 40, 48, and 56 aren’t used.

57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36, array1

63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4, array2.

Next the subkeys are calculated by shifting each value in the two arrays to the left then concatenating the arrays into a new 48-element array with the values below representing the indexes from the two arrays.

14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32.

This concatenated string is one key value. Loop fifteen more times to get the other subkeys.

Now get a 64-bit chunk of information to make illegible. If the block is less than 64-bits it needs to be increased using the same key padding procedure. Perform the initial substitution by creating an array placing the bits in this order. 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7. Split the array in two representing the left and right half of the original array.

Next apply the sixteen subkeys to the right half array. Since each key is 48 bits the array has to be expanded from 32 to 48. The array is increased by repeating some of the values in this fashion; 32 1 2 3 4 54 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1.

The next step involves exclusive oring (XOR) the array with the sixteen keys.

Break the XORed table into eight 6-bit arrays and substitute their values into substitution arrays. These are two-dimensional arrays and the most significant and least significant bits of the 6-bit arrays are used to look-up the row and column of the s-box. The array values are predefined but are too lengthy to list here, they are available at the reference cited at the end of this section. Loop until all the s-boxes have been permuted back into a 32-bit array. This mangled 32 bits of data is now XORed with the left half array. Now loop through the array XORing the values with the subkey. The final portion of the substitution phase is one last permutation like this;

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25.

This process is repeated fifteen times to complete the sixteen rounds. After the sixteenth round, the right and left halves are put back together to form a totally encrypted 64-bit slice of data. [5]

To decipher a DES block you just reverse the encryption process. Take the encrypted block and split it in half and left shift the right half. XOR the shifted right half with the left half and then the subkeys. [5] The result should be your original data. DES encryption applications complete with C source code are available for download at the following site. http://www.radiusnet.net/crypto/archive/source/des/

3DES

Since it’s debut twenty-five years ago, many stronger DES variants have been developed. One of these variants is Triple-DES, more commonly written 3DES. As you might image this method uses the DES algorithm but performs it three times. Using an encrypt-decrypt-encrypt sequence with three different, unrelated keys to strengthen the encryption. The major drawback with 3DES is that’s it’s slow compared to other private key techniques. [4]

Blowfish

Another popular DES variant is Blowfish. This algorithm developed by Bruce Schnieder, uses substitution, transposition, 16 Feistel rounds and a variable key length of up to 448 bits. The main difference between Blowfish and DES besides the obvious key length, is the s-box implementation. Instead of eight s-box arrays Blowfish uses four 256-element arrays of 32-bit length with the permutations performed in a random fashion. [3]

Stream Ciphers

The other type of private-key algorithm is the stream ciphers. These programs encode data one character at a time and offer several advantages over block ciphers. They’re usually much faster than the former and can be used in conjunction with compression software adding an additional layer of protection by removing repeated patterns. [10]

RC4

One of the most commonly used stream chippers s RC4 designed by Ron Rivest, Adi Shamir, and Leonard Adleman of RSA Security. Since the RC4 patent has just recently expired, specific details are sketchy, but the code basically works like this. A pseudo random number generator creates a private key known as a keystream. The plain text message is then XORed with the keystream. Decryption is simply the reverse of encryption. [6]

Asymmetric (public-key)

Asymmetric cryptography algorithms are constructed on symmetric encryption techniques but include a private key allowing for secured data and key transmission. Basically the message sender uses a public key to scramble the data, and the receiver uses another key, her private one, to unscramble the text. [8]

According to David Wills, this encryption scheme is better suited for data transmission than symmetric ciphers because it uses a public key that is given freely and private key known only by the information recipient. The encryption is performed using the public key while decryption is accomplished using the secret private key. This concept allows secure message transfer since the decryption key is never exchanged. [11]

All public-key encryption algorithms are designed from a difficult mathematical problem where the public and private keys are linked. [6] To encrypt, the data is converted into an easy instance of the difficult problem then the public key is used to convert the easy problem into a harder one. To restore the data, the private key is used to convert the difficult problem into the simple one and solved changing the cyphertext back to the original clear text.

RSA

The most commonly used asymmetric algorithm is RSA developed in 1978 by RSA Security. [1] In RSA two large prime numbers are multiplied together to produce the keys. Recall that a prime number is an integer that is only divisible by itself and one. This algorithm works because it’s easier to multiply numbers than to divide them as the following illustrates.

“Take two large primes, p and q, and find their product n=pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no common factors except 1. Find another number d, such that (ed-1)

is divisible by (p-1)(q-1). The values e and d are the public and private exponents, respectively. The public key is the pair (n,e); the private key is (n,d).” [10]

To encrypt a message apply the function; t = t^e mod pq, where t is the cleartext and ^ indicates exponentiation. Note that e is the public key component. [1] The Deciphering is the same as the enciphering except, the plaintext is replaced with the ciphertext and the private key component d is used. c = c^d mod pq, where c is the ciphertext and ^ indicates exponentiation. [1]

Pretty Good Privacy

Another type of asymmetric encryption, sort of, is pretty good privacy (PGP). PGP is really a hybrid of encryption technology that utilizes private-key, public-key and compression technologies. [9] When you want to send a secure message, a one-time private key is created based on your keystrokes and mouse movements. This method ensures the key is random, reducing the likelihood that the key can be compromised. The key is called a session key since the value is based on your session. A fast conventional, probably a stream cipher, algorithm is used to encode the message using the session key. Then the session key is encrypted using the recipient’s public key. The cyphertext message and encoded session key are then sent to the recipient. [9]

Simply reverse this process to decrypt the message. The receiver uses their private key to return the session key to clear text. The data is then deciphered using a conventional symmetric decryption technique. [9]

Hash Functions

Hash function are known as one-way functions because they’re easy to perform in one direction and difficult or impractical to perform in the reverse direction. [8] These functions are frequently used in conjunction with symmetric encryption algorithms particularly for securing passwords. UNIX passwords are encrypted in this fashion: “The first 8 characters of the password in 7 bit ASCII form a 56 bit DES key used to encrypt the number 0. DES's output is the hash. To verify a password, this hash is compared to the one stored in the system's password database.” [7]

Another and probably more common use for hash functions is computing digital signatures. The function takes an input in the form of a message and produces an output, the message digest (MD). If two parties share a private key by using a hash function they will be able to: authenticate each other, create a message checksum allowing the recipient to verify it hasn’t been altered and send encrypted messages back and forth. [7]

“Current hash functions produce a MD of fixed length n for a message of arbitrary length. When using a good hash function, in the sense of its output looking random, the only way to break the hash is by trying out a lot of messages. To find a message with a given MD, one will have to try approximately messages, or messages to find two messages with the same MD. It is considered to be possible to search messages with today's technology but not , therefore n=128 is chosen for currently used hash functions.” [7]

MD5 is one such algorithm and basically works like this. The input message padded in multiples of 16-bytes, then a 16-byte checksum of the message is appended. The checksum value is generated by a function based on the digits of . Finally the message digest, a 16- byte block, is produced by scrambling the 16-byte blocks of the message by XOR it with the function based on . [7]

Conclusion

Encryption algorithms can be divided into symmetric, asymmetric and hash functions’, depending on whether the same key is used for encryption and decryption or a message digest is created. Symmetric ciphers use a secret key and serve well for disk and file encryption. Asymmetric methods are based on complex mathematical computations and work by having the receiver provide an encryption key while she maintains a private key for decryption. PGP utilize facets from both types plus adds randomness and compression further strengthening the encryption, which make them ideal for information transmission. Hash functions are one-way algorithms that are effect for securing passwords. Each is a vital component of information security.