3. How Security is Implemented

3.1 What is a cipher?

A cipher is a way to which plaintext (original data) is converted into ciphertext (encrypted data). There are two basic methods, the stream cipher and the block cipher.

3.1.1 Stream Cipher

In a stream cipher a small chunk (usually a bit) of plaintext is exclusive-ored with the next available small chunk of the key. If the end of the keystream is reached, the key can be either regenerated or recursed. The heaviest computation for encryption algorithms is the actual encryption of plaintext by a key. Because stream ciphers skip this encryption step, they can be implemented much faster than any block stream technique.

For a simple stream cipher the plaintext will be encrypted one bit at a time cycling through a constant keystream as many times as needed. This kind of encryption is relatively weak, as an attacker can combine two different cipherstreams made from the same key, combine them, and then mathematically factor out the keystream. The resulting combination of two plaintext messages is much simpler to crack. Once one plaintext message has been cracked, the keystream can be deduced, and all other messages originating from the same keystream can be decoded.

Thus the (re)creation of the keystream is important. If the keystream is generated independantly from the plaintext and ciphertext, the stream is considered a synchronous stream cipher. Otherwise keystreams depending on the message are self-synchronizing. Since synchronizing key streams have no mathematical connection to the message, they are theoretically more secure. Most modern day techniques (such as RC4) use a randomly generated variable length keystream.

3.1.2 Vernam Cipher

A special type of stream cipher that randomly generates the keystream bit by bit is called a one time pad, and is theoretically impossible to crack. Since each individual message is encoded by a completely random keystream matched lengthwise with the plaintext, the plaintext can only be guessed at. However this method only allows each keystream one use, (multiple uses allow the keystream to be factored out of two messages) invoking severe key management problems, making this type of encryption impractical for general use.

Historically Veram ciphers were a different beast altogether. They were originally implemented in the early 20th century to encrypt teletype traffic. Essentially consisting of a circular roll of ticker tape, they operated like a simple recursive stream cipher. As one of the earliest stream cipher techniques I suppose the name got transferred to that of the one-time-pad.

3.1.3 Block Cipher

Block ciphers use a specified sized key on a specified sized block of plaintext to generate a specified sized block of ciphertext. The sizes of all three blocks are implementation dependant. One of the major weaknesses of this algorithm is that two identical blocks will be encrypted identically, and repitition is one of the primary entering wedges, or weak links. Known message content also poses a problem for this method. If the plaintext content of an entire block was known by an attacker, the key would be easily recoverable by factoring out the known plaintext. Therefore a significant amount of attention must be given by algorithms implementing this method to cover this hole.

3.2 Basic Block Cipher Modes

The method of applying a block cipher to plaintext is called a cipher mode. Different cipher modes have different strengths and weaknesses. One may be streamlined for efficiency while another may be for security. Basic cipher modes have been divided into four main catagories, ECB, CBC, CFB, and OFB. PCBC is not officially recognized but its inclusion in kerberos and its intolerance of bit errors makes it worth mentioning. For a single bit error in the cipherstream, none of the four main modes produce an error burst in the decrypted output stream of longer than 128 bits.

3.2.1 Electronic Code Book (ECB)

The most trivial of the methods, ECB can only be as secure as the block cipher is sits upon, often less. ECB simply applies the block cipher to each plaintext block individually. Padding may be required for the last block, but no initialization vector (IV) is needed. ECB is the fastest of the methods and is easily parallelized. It also suffers the most security weaknesses. Identical plaintext blocks will result in identical ciphertext blocks, and it would only take cracking one block to crack the entire message. An attacker that knew the block size could easily cut and paste w/o detection.

3.2.2 Cipher Block Chaining (CBC)


Cipher Block Chaining hides patterns in plaintext, but adds a few performance issues. CBC requires an initialization vector (IV) to begin the encryption, could possibly be two blocks longer after encryption, and is more difficult to parallelize. Padding may be required for the last block.

Each plaintext block is exclusive-ored with the ciphertext of the previous block (or IV for the first block) then encrypted with the key, thus making paralellization difficult for piped plaintext. The IV is generally sent as the first block, and if padding is required there may be up to two blocks extra per message to be transported across a network. The decoder on the opposite end of the network can only begin decoding once the first packet has arrived, causing undue delay if the packets arrive out of order. This method also falls prey to the old cut 'n paste attack, as long as the key for the inserted text is the same. The inserted block will be decrypted as garbage, but will otherwise not affect the message. Truncating at the beginning or end of the message will likewise have little impact on decoding, other than the message will be a bit shorter!

CBC's strong points are that patterns in plaintext are hidden, and it is relatively efficient.

3.2.3 Cipher Feedback (CFB)


In cipher feedback the key encrypts the previous ciphertext block, and this new block is exclusive-ored to the plaintext to create the new ciphertext block. An IV is required to start the process, and must be transferred along with the ciphertext. Because the plaintext is combined with an encrypted data stream, a pseudo stream cipher approach can be taken eliminating block padding. Two identical ciphertexts will of course be encrypted identically, giving attackers an entering wedge. This type of mode is generally as efficient as the block cipher is lies upon.

3.2.4 Output Feedback (OFB)


An output feedback cipher can be compared to a vernam cipher with a not-so- completely-randomized keystream. The key is used to first encrypt an IV, which is combined with the plaintext ala a stream cipher. The encrypted IV is then re-encrypted to create a new encryption stream, and then re-encrypted and so on. Thus the encryption stream used on the plaintext is generated independently from both the plaintext and the ciphertext. This method is referred to as auto-key mode by the military. Extra efficiency can be gained by creating the key before the plaintext is ready to be encrypted, and is a must for efficient parallelization of the algorithm. Due to the independant nature of the encryption stream from the plaintext and ciphertext, re-write attacks of altering the ciphertext during transport are unnoticable if done right. However on the plus side bit errors (altering of ciphertext 'not done right') are very noticeable.

3.2.5 Propagating Cipher Block Chaining (PCBC)

Propagating CBC is not yet an official standard, but is implemented in kerberos and a few other algorithms. PCBC is based on CBC with the exception that any bit error results in complete loss of the rest of the message. This is implemented to throw out messages that may have been tampered with, or whose content has been damaged.

3.3 Special Block Cipher Modes

These ciphers multiply encrypt single plaintext blocks, and can easily be combined with one of the four basic cipher modes.

3.3.1 Iterated Block Cipher

Iterated block ciphers create a group of subkeys from the original key. These subkeys are one by one applied to the encrypted data block, encrypting and re-encrypting for a specified number of rounds. The aim is to increase security by further removing any semblance of patterns in the ciphertext. The extra looping is a definite trade-off between security and computation. This technique is applied to each individual plaintext block, the keys that are used to create the set of subkeys generally come from one of the four basic cipher modes.

3.3.2 Feistel Cipher

Feistel Ciphers are a special case of iterated block ciphers in which the plaintext is halved. One half is transformed by the encryption function f and then exclusive-ored with the other half. This resulting other half is then transformed by f and combined with the first half. This continues until the last round in which the halves are not swapped. This kind of encryption is utilized in algorithms such as LUCIFER, DES, LOKI, and FEAL.