Part 1: Symmetric Ciphers

Chapter 2. Classical Encryption Techniques

Definitions of Terms *

The many schemes used for encryption constitute the area of study known as cryptography. Such a scheme is known as a cryptographic system (cryptosystem) or a cipher. Techniques used for deciphering a message without any knowledge of the enciphering details fall into the area of cryptanalysis. Cryptanalysis is what the layperson calls "breaking the code". The areas of cryptography and cryptanalysis together are called cryptology.

Symmetric Cipher Model

A symmetric encryption scheme has five ingredients (as shown in the following figure):

Figure 2.1 Simplified Model of Symmetric Encryption

Encryption Requirements *

There are two requirements for secure use of conventional encryption:

  1. The encryption algorithm must be strong.
    • At a minimum, an opponent who knows the algorithm and has access to one or more ciphertexts would be unable to decipher the ciphertext or figure out the key.
    • In a stronger form, the opponent should be unable to decrypt ciphertexts or discover the key even if he or she has a number of ciphertexts together with the plaintext for each ciphertext.
  2. Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable.

Why not keep the encryption algorithm secret? *

We assume that it is impractical to decrypt a message on the basis of the ciphertext plus knowledge of the encryption/decryption algorithm. This means we do not need to keep the algorithm secret; we need to keep only the key secret. This feature of symmetric encryption makes low-cost chip implementations of data encryption algorithms widely available and incorporated into a number of products. With the use of symmetric encryption, the principal security problem is maintaining the secrecy of the key.

Model of Symmetric Cryptosystem *

The essential elements of a symmetric encryption scheme is described in the following figure:

Figure 2.2 Model of Symmetric Cryptosystem

The encryption process is:

This notation indicates that Y is produced by using encryption algorithm E as a function of the plaintext X, with the specific function determined by the value of the key K.

The intended receiver with the key is able to invert the transformation:

An opponent, observing Y but not having access to K or X, may attempt to recover X or K or both. It is assumed that the opponent knows the encryption (E) and decryption (D) algorithms. The opponent may do one of the following:

Cryptography

Cryptographic systems are characterized along three independent dimensions:

  1. Type of operations for transforming plaintext to ciphertext. All encryption algorithms are based on two general principles:

    • Substitution: each element in the plaintext (bit, letter, group of bits or letters) is mapped into another element,
    • Transposition: elements in the plaintext are rearranged.

    The fundamental requirement is that no information be lost (all operations are reversible). Product systems involve multiple stages of substitutions and transpositions.

  2. Number of keys used.

    • If both sender and receiver use the same key, the system is referred to as symmetric, single-key, secret-key, or conventional encryption.
    • If the sender and receiver use different keys, the system is referred to as asymmetric, two-key, or public-key encryption.
  3. How the plaintext is processed.
    • A block cipher processes the input one block of elements at a time, producing an output block for each input block.
    • A stream cipher processes the input elements continuously, producing output one element at a time, as it goes along.

Cryptanalysis and Brute-Force Attack

The objective of attacking an encryption system is to recover the key in use rather than simply to recover the plaintext of a single ciphertext. There are two general approaches to attacking a conventional encryption scheme:

If either type of attack succeeds in deducing the key, then future and past messages encrypted with that key are compromised.

Cryptanalytic attacks *

The following table summarizes the various types of cryptanalytic attacks based on the amount of information known to the cryptanalyst.

Type of Attack Known to Cryptanalyst
Ciphertext Only
  • Encryption algorithm
  • Ciphertext
Known Plaintext
  • Encryption algorithm
  • Ciphertext
  • One or more plaintext–ciphertext pairs formed with the secret key
Chosen Plaintext
  • Encryption algorithm
  • Ciphertext
  • Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key
Chosen Ciphertext
  • Encryption algorithm
  • Ciphertext
  • Ciphertext chosen by cryptanalyst, together with its corresponding decrypted plaintext generated with the secret key
Chosen Text Combination of "Chosen Plaintext" and "Chosen Ciphertext"

[p32]

In general, we can assume that the opponent does know the algorithm used for encryption. If the key space is very large, the brute-force approach of trying all possible keys, which is one possible attack, becomes impractical. Thus, the opponent must anaylyze the ciphertext itself, applying various statistical tests to it. To use this approach, the opponent must have some general idea of the type of plaintext that is concealed.

Ciphertext-only attack *

The ciphertext-only attack is the easiest to defend against because the opponent has the least amount of information to work with.

Known-plaintext attack *

In many cases, the analyst has more information than ciphertext only:

For example, a file that is encoded in the Postscript format always begins with the same pattern, or there may be a standardized header or banner to an electronic funds transfer message. All these are examples of known plaintext. With this knowledge, the analyst may be able to deduce the key on the basis of the way in which the known plaintext is transformed. This is known as the known-plaintext attack.

Probable-word attack *

The probable-word attack is closely related to the known-plaintext attack. If the opponent is working with the encryption of some general prose message, he or she may have little knowledge of what is in the message. However, if the opponent is after some very specific information, then parts of the message may be known.

For example:

Chosen-plaintext attack *

If the analyst is able to get the source system to insert into the system a message chosen by the analyst, then a chosen-plaintext attack is possible. An example of this strategy is differential cryptanalysis, explored in Chapter 3. In general, if the analyst is able to choose the messages to encrypt, the analyst may deliberately pick patterns that can be expected to reveal the structure of the key.

The other two types of attack: chosen ciphertext and chosen text, are less commonly employed as cryptanalytic techniques but are nevertheless possible avenues of attack.

Generally, an encryption algorithm is designed to withstand a known-plaintext attack; only weak algorithms fail to withstand a ciphertext-only attack.

Unconditionally secure and computationally secure *

An encryption scheme is unconditionally secure if the ciphertext generated by the scheme does not contain enough information to determine uniquely the corresponding plaintext, no matter how much ciphertext is available. That is, no matter how much time an opponent has, it is impossible for him or her to decrypt the ciphertext simply because the required information is not there.

With the exception of a scheme known as the one-time pad (described later in this chapter), there is no encryption algorithm that is unconditionally secure. Therefore, an encryption algorithm should meet one or both of the following criteria:

An encryption scheme is said to be computationally secure if either of the foregoing two criteria are met. Unfortunately, it is very difficult to estimate the amount of effort required to cryptanalyze ciphertext successfully.

All forms of cryptanalysis for symmetric encryption schemes are designed to exploit the fact that traces of structure or pattern in the plaintext may survive encryption and be discernible in the ciphertext. Cryptanalysis for public-key schemes proceeds from a fundamentally different premise: the mathematical properties of the pair of keys may make it possible for one of the two keys to be deduced from the other.

Brute-force attack *

A brute-force attack involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained.

On average, half of all possible keys must be tried to achieve success. A brute-force attack is more than simply running through all possible keys. Unless known plaintext is provided, the analyst must be able to recognize plaintext as plaintext:

Thus, to supplement the brute-force approach, some degree of knowledge about the expected plaintext is needed, and some means of automatically distinguishing plaintext from garble is also needed.