When a change in one bit of the plaintext or one bit of the key produced a change in many bits of the ciphertext such is called?

Paul Krzyzanowski

February 26, 2022

Cryptography deals with encrypting plaintext using a cipher, also known as an encryption algorithm, to create ciphertext, which is unintelligible to anyone unless they can decrypt the ciphertext.

Cryptography is a tool that helps build protocols that address:

A restricted algorithm is one where the workings of the cipher must be kept secret. There is no reliance on any key and the secrecy of the cipher is crucial to the value of the algorithm. This has obvious flaws: people in the know leaking the secret, designers coming up with a poor algorithm, and reverse engineering.

For any serious use of encryption, we use well-tested, non-secret algorithms that rely on secret keys. A key is a parameter to a cipher that alters the resulting ciphertext. Knowledge of the key is needed to decrypt the ciphertext. Kerckhoffs’s Principle states that a cryptosystem should be secure even if everything about the system, except the key, is public knowledge. We expect algorithms to be publicly known and all security to rest entirely on the secrecy of the key.

A symmetric encryption algorithm uses the same secret key for encryption and decryption.

Properties of good ciphers

For a cipher to be considered good:

1. Ciphertext should be indistinguishable from random values.
2. Given ciphertext, there should be no way to extract the original plaintext or the key that was used to create it except by of enumerating over all possible keys. This is called a brute-force attack.
3. The keys used for encryption should be large enough that a brute force attack is not feasible. Each additional bit in a key doubles the number of possible keys and hence doubles the search time.

Classic cryptography

The earliest practical; form of cryptography was the monoalphabetic substitution cipher. In this cipher, each character of plaintext is substituted with a character of ciphertext based on a substitution alphabet (a lookup table). The simplest of these is the Caesar cipher, known as a shift cipher, in which a plaintext character is replaced with a character that is n positions away in the alphabet. The key is the simply the the shift value: the number n. In the general case of the monoalphabetic substitution cipher, a randomly-scrambled substitution alphabet is used but this makes sharing knowledge of the substitution alphabet more difficult.

Substitution ciphers are vulnerable to frequency analysis attacks, in which an analyst analyzes letter frequencies in ciphertext and substitutes characters with those that occur with the same frequency in natural language text (e.g., if “x” occurs 12% of the time, it’s likely to really be an “e” since “e” occurs in English text approximately 12% of the time while “x” occurs only 0.1% of the time).

Polyalphabetic substitution ciphers were designed to increase resiliency against frequency analysis attacks. Instead of using a single plaintext to ciphertext mapping for the entire message, the substitution alphabet may change periodically.

Leon Battista Alberti is credited with creating the first polyalphabetic substitution cipher. In the Alberti cipher (essentially a secret decoder ring), the substitution alphabet changes every n characters as the ring is rotated one position every n characters.

The Vigenère cipher is a grid of Caesar ciphers that uses a repeating key. A repeating key is created by taking a key and repeating to make a string that is as long as the message. Each character of the key determines which Caesar cipher (which row of the grid) will be used for the next character of plaintext. The position of the plaintext character identifies the column of the grid.

These algorithms are still vulnerable to frequency analysis attacks but require substantially more plaintext since one needs to deduce the key length (or the frequency at which the substitution alphabet changes) and then effectively decode multiple monoalphabetic substitution ciphers.

One-time Pads

The one-time pad is the only provably secure cipher. It uses a random key that is as long as the plaintext. Each character of plaintext is permuted by a character of ciphertext (e.g., add the characters modulo the size of the alphabet or, in the case of binary data, exclusive-or the next byte of the text with the next byte of the key).

The position in the key (pad) must by synchronized at all times. Error recovery from unsynchronized keys is not possible. For the cipher to be secure, a key must be composed of truly random characters, not ones derived by an algorithmic pseudorandom number generator. Also, the key can never be reused (hence, the name “one-time”).

The one-time pad provides perfect secrecy (not to be confused with forward secrecy, also called perfect forward secrecy, which will be discussed in the next lecture). Perfect secrecy has these properties:

1. The ciphertext conveys no information about the content of the plaintext or the key. Of course, it does not hide the fact that a message exists.
2. Given several plaintexts, you will have no way of determining which one created the cipher text (this is the property of indistinguishability).
3. You can always create some key that will convert any ciphertext to any possible plaintext.

Perfect secrecy can be achieved only if there are as many possible keys as the plaintext, meaning the key has to be as long as the message. For this reason, it is not particularly useful in practice since transporting the key securely becomes a problem. The challenge of sending a message securely is now replaced with the challenge of sending the key securely.

See this video for an explanation of perfect secrecy.

Stream ciphers

A stream cipher simulates a one-time pad by using a keystream generator to create a set of key bytes that is as long as the message. A keystream generator is a pseudorandom number generator that is seeded, or initialized, with a key that drives the output of all the bytes that the generator spits out.

The keystream generator is fully deterministic: the same key will produce the same stream of output bytes each time. Because of this, receivers only need to have the key to be able to decipher a message. With that, they can generate the same key stream. However, because the keystream generator does not generate true random numbers, the stream cipher is not a true substitute for a one-time pad. Its strength rests on the strength of the key. A keystream generator will, at some point, will reach an internal state that is identical to some previous internal state and produce output that is a repetition of previous output. This also limits the security of a stream cipher. Since key repetition may not occur for a long time, stream ciphers can still be useful for in some applications.

Rotor machines

A rotor machine is an electromechanical device that implements a polyalphabetic substitution cipher. It uses a set of disks (rotors), each of which implements a substitution cipher. A rotor rotate one position with each character. After a complete rotation of one rotor, the next rotor advances one position. Each successive character gets a new substitution alphabet applied to it. The multi-rotor mechanism allows for a huge number of substitution alphabets to be employed before they start repeating when the rotors all reach their starting position. The number of alphabets is cr, where c is the number of characters in the alphabet and r is the number of rotors.

Transposition ciphers

Instead of substituting one character of plaintext for a character of ciphertext, a transposition cipher scrambles the position of the plaintext characters. Decryption is the knowledge of how to unscramble them.

A scytale (rhymes with Italy), also known as a staff cipher, is an ancient implementation of a transposition cipher where text written along a narrow strip of paper is wrapped around a rod and the resulting sequences of text are read horizontally. This is equivalent to entering characters in a two-dimensional matrix horizontally and reading them vertically. Because the number of characters might not be a multiple of the width of the matrix, extra characters might need to be added at the end. This is called padding and is essential for block ciphers, which encrypt chunks of data at a time.

Computer cryptography

With the exception of stream ciphers, modern ciphers are block ciphers, meaning that they encrypt a chunk of bytes, or a block, of plaintext at a time. The same key is used to encrypt each successive block of plaintext. AES and DES are two of the most popular symmetric block ciphers. Common block sizes are 64 bits (8 bytes, used by DES) and 128 bits (16 bytes, used by AES).

Symmetric block ciphers are usually implemented as iterative ciphers. he encryption of each block of plaintext iterates over several rounds. Each round uses a subkey, which is a key generated from the main key via a specific set of bit replications, inversions, and transpositions. The subkey is also known as a round key since it is applied to only one round, or iteration. This subkey determines what encryption takes place in each round. The result of that encryption is fed into the next round. The final round produces the output ciphertext.

The iteration through multiple rounds creates confusion and diffusion. Claude Shannon, the father of information theory, who also did fundamental work on cryptography and cryptanalysis, described these as two properties that will make the use of statistical analysis ineffective in cracking codes.

Confusion means that it is extremely difficult to find any correlation between a bit of the ciphertext with any part of the key or the plaintext.

Diffusion means that any changes to the plaintext are distributed (diffused) throughout the ciphertext so that, on average, half of the bits of the ciphertext would change if even one bit of plaintext is changed. No single bit of the plaintext is responsible for the value of a bit in the cipher text.

The iterations of encrypting a block of data can take one of two forms: a Feistel Network (Feistel cipher) or an Substitution-Permutation Network (SPN).

Feistel Network

Encryption must be an invertible operation. That is, you must be able to decrypt what you encrypted (providing you have the key, of course). The Feistel network was designed to provide a mechanism that can use any function, even a non-invertible one, within a round and still create an invertible cipher.

In a cipher that uses a Feistel Network, the plaintext block is split into two equal parts: a left part (L0) and a right part (R0). Each round produces a new left and right block that is fed into the next round.

In each round, only half of the data block is encrypted by a round function, which takes as input the subkey for that round and the right part of the block. The result is then XORed with the left half of the data (L0 ⊕ R0). This result then becomes the new right part while the original right part becomes the left part for the new round:

R1 = L0 ⊕ R0
L1 = R0

The part that wasn’t encrypted in the previous round gets encrypted in the next round.

An SP Network encrypts a block of plaintext through several rounds (iterations). Each round passes the bits through a substitution box (s-box) and a permutation box (p-box).

An s-box is an invertible operation that replaces (substitutes) one set of bits to another set. It usually applies to a small set of bits (e.g., four bits is common) and can be implemented by a lookup table. The translation of bits is not a permutation but has the property that a change of one input bit will affect, on average, half of the output bits and that every output bit depends on every input bit.

The p-box takes all the bits in the block and scrambles, or permutes, them. The output of this is fed into the next round of substitutions and permutations.

Each substitution and permutation is guided by a subway that is derived from the main key. That means that the set of substitutions and permutations will differ within each round as determined by that round’s subway.

DES

DES, the Data Encryption Standard was adopted as a U.S. federal encryption standard in 1976 and is a block cipher based on the Feistel cipher that encrypts 64-bit blocks using a 56-bit key.

It differs from a pure Feistel network by the addition of an initial permutation that scrambles the 64 bits of the block before going through 16 rounds of the Feistel network. At the end, another permutation, that is the inverse of the initial permutation, is applied to the block.

Within each round, the encryption function on each half block does the following:

1. The right half of the block goes through an expansion permutation where 32 bits of data are permuted and expanded into 48 bits.
2. 48 bits are generated from the key through permutation, inversion, and selection
3. These two values are XORed together
4. Each set of 6 bits passes through an s-box that converts 6 bits of input to 4 bits of output. Normally, this would imply that data would be lost but note that in the end the eight s-boxes produce 32 bits of data, the same as the input.
5. The resulting 32 bits of data go through a permutation and are XORed with the left half of the block (which was untouched this round).

The permutations and substitutions are guided by the subkey for that round. A core component of security of DES is its design of the s-box, which converts the 6 input bits to 4 output bits and adds confusion by altering the relationship between the input and output bits.

DES has been shown to have some minor weaknesses against cryptanalysis. Key can be recovered using 247 chosen plaintexts or 243 known plaintexts. Note that this is not a practical amount of data to get for a real attack. The real weakness of DES is not the algorithm but its 56-bit key. An exhaustive search requires 255 iterations on average (we assume that, on average, the plaintext is recovered halfway through the search). This was a lot for computers in the 1970s but is not much for today. Custom hardware (FPGA-based DES crackers) or distributed efforts can do an exhaustive search to crack a DES key within a day.

Triple-DES

Triple-DES (3DES) solves the key size problem of DES and allows DES to use keys up to 168 bits. It does this by applying three layers of encryption:

1. C' = Encrypt M with key K1
2. C'' = Decrypt C' with key K2
3. C = Encrypt C'' with key K3

If K1, K2, and K3 are identical, we have the original DES algorithm since the decryption in the second step cancels out the encryption in the first step. If K1 and K3 are the same, we effectively have a 112-bit key and if all three keys are different, we have a 168-bit key.

Cryptanalysis is not effective against 3DES: the three layers of encryption use 48 rounds instead of 16 making it infeasible to reconstruct the substitutions and permutations that take place. DES is relatively slow compared with other symmetric ciphers, such as AES. It was designed with hardware encryption in mind. Moreover, 3DES is, of course, three times slower than DES.

AES

AES, the Advanced Encryption Standard, was chosen as a successor to DES and became a federal government standard in 2002.

The AES cipher is based on an SP-network with 10–14 rounds per block. It uses a larger block size than DES: 128 bits (16 bytes) versus DES’s 64 bits (8 bytes) and supports larger key sizes: 128, 192, and 256 bits. Note that even 128 bits is long enough to prevent brute-force searches.

Each round uses a subkey derived from the encryption key. The block passes through s-boxes that substitute one set of bits for another via a table lookup, with the table selected by the subkey for the round. The resulting block is scrambled via a permutation that is also guided by the subkey.

No significant academic attacks against AES have been discovered thus far beyond brute force search. AES is also typically 5–10 times faster in software than 3DES.

Block cipher modes

Electronic Code Book (ECB)

When data is encrypted with a block cipher, it is broken into blocks and each block is encrypted separately. This leads to two problems.

1. If different encrypted messages contain the same substrings and use the same key, an intruder can deduce that it is the same data.

2. Secondly, a malicious party can delete, add, or replace blocks (perhaps with blocks that were captured from previous messages).

This basic form of a block cipher is called an electronic code book (ECB). Think of the code book as a database of encrypted content. You can look up a block of plaintext and find the corresponding ciphertext. This is not feasible to implement for arbitrary messages but refers to the historic use of codebooks to convert plaintext messages to ciphertext.

Cipher Block Chaining (CBC)

Cipher block chaining (CBC) addresses these problems. Every block of data is still encrypted with the same key. However, prior to being encrypted, the data block is exclusive-ORed with the previous block of ciphertext. The receiver does the process in reverse: a block of received data is decrypted and then exclusive-ored with the previously-received block of ciphertext to obtain the original data. The very first block is exclusive-ored with a random initialization vector, which must be transmitted to the remote side.

Note that CBC does not make the encryption more secure; it simply makes the result of each block of data dependent on all previous previous blocks so that data cannot be meaningfully inserted or deleted in the message stream.

Counter mode (CTR)

Counter mode (CTR) also addresses these problems but in a different way. The ciphertext of each block is a function of its position in the message. Encryption starts with a message counter. The counter is incremented for each block of input. Only the counter is encrypted. The resulting ciphertext is then exclusive-ORed with the corresponding block of plaintext, producing a block of message ciphertext. To decrypt, the receiver does the same thing and needs to know the starting value of the counter as well as the key.

An advantage of CTR mode is that each block has no dependance on other blocks and encryption on multiple blocks can be done in parallel.

Cryptanalysis

The goal of cryptanalysis is break codes. Most often, it is to identify some non-random behavior of an algorithm that will give the analyst an advantage over an exhaustive search of the key space.

Differential cryptanalysis seeks to identify non-random behavior by examining how changes in plaintext input affect changes in the output ciphertext. It tries to find whether certain bit patterns are unlikely for certain keys or whether the change in plaintext results in likely changes in the output.

Linear cryptanalysis tries to create equations that attempt to predict the relationships between ciphertext, plaintext, and the key. An equation will never be equivalent to a cipher but any correlation of bit patterns give the analyst an advantage.

Neither of these methods will break a code directly but may help find keys or data that are more likely are that are unlikely. It reduces the keys that need to be searched.

References

Fred Cohen, 2.1 - A Short History of Cryptography, 1995.

Alberti Cipher Disk, Wikipedia.

Daniel Rodriguez-Clark, Caesar Shift Cipher, Crypto Corner, 2019. - **includes interactive examples **

Simon Singh, Cracking the Vigenère Cipher, The Black Chamber, 2000. Daniel Rodriguez-Clark, Vigenère Cipher, Crypto Corner, 2019. - **includes interactive examples **

One-time Pad

Wikipedia, One-time Pad

Data Encryption Standard, Wikipedia.

Sanchita Mal-Sarkar and Chansu Yu, Data Encryption Standard, Hands-on Experience on Computer System Security.

Advanced Encryption Standard process, Wikipedia.

Josh Lake, What is AES Encryption and how does it work?, Comparitech, 2020.