Cryptography (2024)

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

Cryptography is a tool thathelps build protocols that address:

Confidentiality:

Hiding the contents of a message.

Authentication

Showing that the user really is that user.

Integrity:

Validating that the message has not been modified.

Nonrepudiation:

Binding the origin of a message to a user so that she cannot deny creating it.

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.

Monoalphabetic substitution ciphers

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 ciphersare vulnerable to frequency analysis attacks, in which an analystanalyzes letter frequencies in ciphertext and substitutes characterswith those that occur with the same frequency in natural languagetext (e.g., if “x” occurs 12% of the time, it’s likely to reallybe an “e” since “e” occurs in English text approximately 12% of thetime while “x” occurs only 0.1% of the time).

Polyalphabetic substitution ciphers

Polyalphabetic substitution ciphers were designed to increase resiliency againstfrequency analysis attacks. Instead of using a singleplaintext to ciphertext mapping for the entire message, the substitution alphabetmay 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 charactersas 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 characterof the key determines which Caesar cipher (which row of the grid)will be used for the next character of plaintext. The position ofthe plaintext character identifies the column of the grid.

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

One-time Pads

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

The position in the key (pad) must bysynchronized at all times. Error recovery from unsynchronized keysis not possible. For the cipher to be secure, a key mustbe composed of truly random characters, not ones derived by analgorithmic pseudorandom number generator. Also, the key cannever 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 ofsending a message securely is now replaced with the challenge ofsending 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 tocreate 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 thegenerator spits out.

The keystream generator is fully deterministic: the samekey 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 strengthrests on the strength of the key. A keystream generator will, at some point,will reach an internal state that is identical to some previous internalstate and produce output that is a repetition of previous output. This alsolimits the security of a stream cipher. Since key repetition may not occur fora long time, stream ciphers can still be useful for in some applications.

Rotor machines

A rotor machine is an electromechanical device that implementsa 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 acomplete 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 beemployed before they start repeating when the rotors all reach theirstarting position. The number of alphabets is c^r, wherec is the number of characters in the alphabet and r isthe 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.

Block ciphers

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 keyis 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 rounduses a subkey, which is a key generated from the main key viaa specific set of bit replications, inversions, and transpositions. Thesubkey 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 extremelydifficult to find any correlation between a bit of the ciphertext withany part of the key or the plaintext.

Diffusion meansthat any changes to the plaintext are distributed (diffused) throughout theciphertext so that, on average, half of the bits of the ciphertext wouldchange 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 (L₀) and a right part (R₀). 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 (L₀ ⊕ R₀). This result then becomes the new right part while the original right part becomes the left part for the new round:

R₁ = L₀ ⊕ R₀
L₁ = R₀

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

Substitution-Permutation Network (SPN)

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 cipherbased 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 2⁴⁷ chosen plaintexts or 2⁴³ 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 2⁵⁵ 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 K₁
2. C'' = Decrypt C' with key K₂
3. C = Encrypt C'' with key K₃

If K₁, K₂, and K₃ are identical, we have the original DES algorithmsince the decryption in the second step cancels out the encryption in the first step.If K₁ and K₃ are the same, we effectively have a 112-bit key and if all threekeys are different, we have a 168-bit key.

Cryptanalysis is not effective against 3DES: the three layers of encryptionuse 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 DESand 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 blocksand each block is encrypted separately. This leads to two problems.

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

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

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

Cipher Block Chaining (CBC)

Cipher blockchaining (CBC) addresses these problems. Every block of datais still encrypted with the same key. However, prior to beingencrypted, the data block is exclusive-ORed with the previousblock of ciphertext. The receiver does the process in reverse: a blockof received data is decrypted and then exclusive-ored with thepreviously-received block of ciphertext to obtain the original data. The veryfirst block is exclusive-ored with a random initialization vector,which must be transmitted to the remote side.

Note that CBC doesnot make the encryption more secure; it simply makes the result ofeach block of data dependent on all previous previous blocks so that datacannot be meaningfully inserted or deleted inthe message stream.

Counter mode (CTR)

Counter mode (CTR) also addresses these problemsbut in a different way. The ciphertext of each block is a functionof its position in the message. Encryption starts with amessage counter. The counter is incremented for each blockof input. Only the counter is encrypted. The resulting ciphertext isthen exclusive-ORed with the corresponding block of plaintext, producinga block of message ciphertext. To decrypt, the receiver doesthe same thing and needs to know the starting value of the counteras well as the key.

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

Cryptanalysis

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

Differential cryptanalysisseeks to identify non-random behavior byexamining how changes in plaintext input affect changes in the output ciphertext.It tries to find whether certain bit patterns are unlikely for certain keysor whether the change in plaintext results in likely changes in the output.

Linear cryptanalysistries to create equations that attempt to predict the relationships betweenciphertext, plaintext, and the key. An equation will never be equivalent toa cipher but any correlation of bit patterns give the analyst an advantage.

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

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.