These are my complete notes for Block Ciphers in Symmetric Cryptography.
I color-coded my notes according to their meaning - for a complete reference for each type of note, see here (also available in the sidebar). All of the knowledge present in these notes has been filtered through my personal explanations for them, the result of my attempts to understand and study them from my classes and online courses. In the unlikely event there are any egregious errors, contact me at jdlacabe@gmail.com.
Summary of Block Ciphers (Symmetric Cryptography)
Table Of Contents
IV. Block Ciphers.
IV.I Historical Background.
A cipher that encrypts a block of 'b' plaintext bits all at the same time, where b is greater than one (since one bit would be a stream cipher). Thus, the encryption of any plaintext bit in the block depends on the nature of every other plaintext bit in the block, like the positions of celestial bodies in a galaxy.
Most block ciphers have a block length of 128 bits (16 bytes), such as the AES (see Rule [[[[[), or 64 bits (8 bytes), such as the DES and 3DES (see Rules 43 & [[[[, respectively). For each input, a block cipher will produce an equivalent amount of output data: in the case of DES, this will be another 64 bits.
Block Ciphers are more commonly used than Stream Ciphers in modern computer encryption schemes, due to the stream cipher mass extinction event caused by relentless attacks by cryptanalysts in the '90s, and the mass adoption of block ciphers that followed.
# Look-up Table: A Substitution table - an algorithm in which every input is paired with a particular value/address, and has that value outputted. It is not a requirement that the number of output bits match the number of inputted bits - in the DES Feistel cipher, for example, table S1 produces 4 output bits from 6 input bits.
# Product Cipher: A generic term used to describe any cipher that utilizes/concatenates the methods of permutation and repeated encryption (in "rounds") to create the element of "diffusion" (see Rule 41) necessary for any block cipher.
# C. Rule 41. Confusion & Diffusion:
During the postwar Cryptographic research boom, stemming from the rush of funding for military science, it was postulated in a classified paper that there were two atomic operations that all good block ciphers should perform:
- Confusion:
The relationship between the plaintext and ciphertext must be obscured. Any cipher that scrambles its characters thoroughly enough that the plaintext and ciphertext bare no resemblance to one another, passes this requirement.
However, the sole utilization of this requirement and the abandonment of the second, as was done with the Substitution and Shift Ciphers, will produce a very unsecure cipher. - Diffusion:
The influence of each plaintext bit is spread over many ciphertext bits. In systems making good use of diffusion, changing one bit of plaintext results in an average change of half of the total output bits, known as the Avalanche effect and akin to chaos theory. Example: Permutations of an encryption method to make a cryptosystem more secure.
This element is impossible under stream ciphers, since each bit is processed and encrypted individually.
IV.II Feistel Networks.
Mathematical Definition:
i ∈ {1, ..., 16}
Li = Ri-1
Ri = (Li-1 + f(Ri-1, ki)) mod 2
i = The particular round, minus 1, that the left and right tranches of the data are at. L0, for example, would be in the first round of the cipher. Since i has a minimum value of 1, the first round that can have the equations utilized on is round 2, since there is no past round data to feed into round 1.
Li = The left tranche as it is in round i-1. If not in the first round, it will inherit the unencrypted form of the previous right tranche as its starting value in the round.
Ri = The right tranche as it is in round i-1. If not in the first round, it will inherit the XOR-ing of the left tranche of the previous round with the encrypted right tranche of the previous round as its starting position.
Ri-1 = The right tranche of the round prior to the current one, used by the f function (see below).
f = The mysterious encryption function, the central part of the entire Feistel scheme. Uses the right tranche and the subkey of a particular round to make an encryption. Explained in Rule 46.
ki = The specific subkey used in the round. Each subkey is derived from the main key, explained (for DES) in Rule [[[[[.
mod 2 = The modulus/remainder operator with respect to 2. Numbers can only be 0 or 1 in this reality.
Explanation:
A Feistel Cipher/Feistel Network/Feistel Structure is a round-based algorithm used to encrypt data. Widely used among block ciphers (though not in the AES), several ciphers developed more optimized versions of the network, such as the DES. The original, standard, unadorned version of the Feistel Network is depicted below, while the DES-enhanced version can be seen in Rule 43.
The bulk of the modern ciphers currently in use were built using feistel ciphers and their varients. A particular advantage of the Feistel Network is that decryption and encryption are almost the same operation, simply using a reversed key schedule (see Rule [[[[[[[[). In terms of importance/usage in the cipher structure, Feistel Networks are the block cipher equivalent of the LFSR, although it actually encrypts the data and requires a key, instead of merely producing the key (like the LFSR).
Devoid of the more specialized characteristics (particular those relating to DES, described in section IV.III), the system by which the "standard", unadorned Feistel Cipher encrypts data is simple:
- The data path will be split into two parts: a Left and a Right tranche, L0 and R0 respectively. For a 64 bit cipher (like DES), each part will have 32 bits.
- The Right tranche will have its bits fed into the f function, which is the actual encryption function of the entire operation.
Additionally, a subkey will also be fed into the f function: In each round of encryption, a new subkey derived from the main key is used, thus keeping the process deterministic and replicable, but complicating the process so much that discovery of the plaintext from knowledge of the ciphertext is made (most likely) impossible.
In the DES cipher, which differs from the more generalized standard feistel network described here and shown in the graphic, the subkey is created using a key schedule. See Rule [[[[[ for an explanation of how this is carried out.
The length of the subkey does not have to be exactly as long as tranche - in the DES, the subkey is 48 bits long, the purpose of which is explained in Rule [[[[[[[. - The output of the encryption of the right tranche will then be XOR'd with the left tranche (which had gone untouched until now).
- For each round, the output of the previous round is fed in as input to the next round. The trick at this juncture is that the tranches will switch their positions in the new round: the right tranche will become the new left tranche (L1), and the left tranche will become the new right tranche (R1).
IMPORTANT NOTE: The Right tranche is sent to the left tranche of the next round in its unencrypted form. The Right tranche passes through unaltered to the left tranche; since the Left tranche of the first round got XOR'd with the encrypted version of the Right tranche, IT is the one being "encrypted" or simply changed in any meaningful way, not the right tranche.
IV.III Data Encryption Standard.
# C. Rule 43. Data Encryption Standard (DES):
Mathematical Definition:
Explanation:
The Data Encryption Standard is a block cipher that encrypts 64 bits at a time, outputting 64 bits of ciphertext in return, through bijective mapping (see definition). As a product cipher, DES uses 16 encryption rounds of an optimized form of the Feistel Network (depicted below) to thoroughly obfuscate and diffuse the impact of each bit, under the known elements of best-practice block ciphers (Rule 41).
The keysize of DES is 56 bits (and thus has a keyspace of only 2^56), highly crackable, and so it is not in popular use today - it has been largely replaced by other ciphers with longer keys, such as 3DES ([[[[[) and AES ([[[[[). Still, it remains useful and neccesary to study the design of DES, which is modern cryptography in its embryonic state. The subkeys used in DES for the Feistel Network are only 48 bits - see Rule [[[[ for why that is.
# C. Rule 44. History of the Data Encryption Standard (DES):
Proposed in 1974 by IBM (in coordination with the NSA), DES was the cryptographic standard for the U.S. government between 1977 and 1998, making it the most studied cipher in the world.
The DES was the first ever "secure" cryptosystem made public by a national government under the postulate of Kerckhoffs's principle (Rule 3).
Today, there are still some varients of DES that see application: notably, 3DES, which was used in Firefox until 2021. While the original DES, as developed in 1974, is unsecure from Brute-Force attacks due to the short length of its key (56 bits), 3DES has a very long key, and as such is immune to such attacks.
# C. Rule 45. DES Internals #1 - Bit Permutation:
The first characteristic one may note about the DES Feistel Cipher (as depicted in the graphic of Rule 43) is that the operation undergone by data travelling through the cipher is IP(x), the Initial Permutation function. Undepicted is the very last operation in the encryption process, at the bottom of the cipher (which is 16 rounds deep), where the IP(x)⁻¹, the Final Permutation, would be located.
IP(x) and IP(x)⁻¹ are simple bit permutations, or bitwise permutations: the bits are scrambled and assigned to different placements in the data than they were before. This just the algorithmic term for a crosswiring. IP(x)⁻¹, being the inverse of IP(x), perfectly undoes the scrambling of IP(x), cancelling eachother out.
The purpose of the DES bit permutation functions is simple: while serving no cryptographic purpose (since the attacker can simply take the permutation into account, and because it is undone anyway), when DES was designed in 1974, the application of the cipher into hardcare necessitated cross-wiring (physical bit permutation) just to allow the data to enter the chip. The specific bit permutations used for the initial and final permutations (both depicted below) are done in order to, according to leading experts on the issue, "arrange the plaintext and ciphertext bits in a bytewise manner to make data fetches easier for 8-bit data buses", widely used in the '70s.
Thus, the bit permutations were merely placed in the DES for practical, electrical engineering purposes, devoid of cryptographic meaning. DES was initially designed purely for hardware, and the electrical engineering-devised permutation (no gates or special operations) made it very easy to be fabricated in hardware form, but somewhat tedious and more time-consuming in software.
# C. Rule 46. DES Internals #2 - The 'f' Function:
The f function, the heart of the Feistel Network (and thus the DES), acts similarly to the a PRNG, using the two input parameters Ri-1 (32 bits) and ki (48 bits) to "encrypt" the right tranche. Below are the complete contents of the f function:
-
The first operation that will be performed will solely involve the first parameter: Ri-1. In order to account for the differences in length between the right tranche and the subkey, the right tranche will be expanded from 32 bits to 48 bits, using the special "Expansion function" or "Expansion box", also referred to as simply the "E-box". Notably, this function will provide diffusion to the cipher, as its effects (as described below) will increase the significance & influence of each individual bit of the plaintext with every additional round of encryption.
While the E-box also performs a basic permutation on the inputted bits, it differs from a standard bit permutation in that some of the inputted bits are connected to two bit positions, creating values for an expanded table. With the initial 32-bit string of the right tranche, 16 bits of data will be connected only once, while the other 16 bits will be connected twice. An example of how this can be done is seen below.
The complete F function of the DES-specific Feistel Network.
- With the newly 48-bit right tranche, an XOR operation can be performed between the tranche and the subkey (which has its own special means of derivation, explained in Rule [[[[[[). This produces a 48-bit string that incorporates data from both parameters, and now all that is left to be done is to shrink the string back down to 32 bits so that it can be XOR'd later on with the data from the left tranche (outside of the f function).
-
After the XOR, the most important part, the heart of the f function, is performed: the S boxes. Complementary to the diffusion of the E-box, the S-box will provide the confusion.
The pattern the S-box follows is simple, and is shown in the complete diagram above: The newly-created 48-bit string will be split into 8 tranches of 6 bits. Each tranche will be sent to a Substitution Table, S1 through S8.
These tables will be akin to compression functions/compression boxes, as they will produce less output than input: Each table will output 4 bits from an input of 6, thus resulting in a net total of 32 bits, exactly what is needed.
The Compression Algorithm works as follows: Since each table accepts 6 bits, which are read in their combined, binary form, the table is simply taking the given, 6-bit value (0-63) and replacing it with a 4-bit value (0-15). The chosen 4-bit replacement value for each possible 6-bit value is assigned according to a set, predetermined substitution table, the purposeful and exact design of which was done to ensure protection against Differential Cryptanalysis ([[[[[[[[), which researchers at IBM discovered decades before the academics of the late '80s. For information as to what exact criteria the S-boxes were designed with in mind, see the relevant blue section below.
Note that EACH Substitution Table, S1 through S8, has its own, individual, substitution table. [[[[[[ The S1 table is shown below; the rest of the tables can be found on page 3 of this here document.
The specific, exact table used in the first S-Box to replace the 6 bit string with a (max) 4 bit one. Chosen by IBM & the NSA to be differential cryptanalysis-proof.
In order to read the table, you must take the 6-bit value and examine it as follows:
For the Column Select, take the middle 4 values (the internal, non-edge values) and find their individual value in binary, separate from the rest of the string. This will give you a value 0-15.
For the Row Select, simply combine the left and right edge values of the 6-bit value in a single binary number, 0-3. This will serve as the row value.
All that needs to be done to find the 4-bit output (represented in decimal in the given table image, and all others) is to locate it on the table using the known column and row values. The value returned from properly finding the value from the specific column and row values. - All that remains within the f function is a simple bit permutation, in the same fashion (though different permutation patterns) as the one at the top and bottom of the DES cipher (described in Rule [[[[[).
# Most Significant Bit (MSB): The leftmost bit in a binary number - the largest value representation in the binary place value system. This varies from system to system.
# Least Significant Bit (LSB): The rightmost bit in a binary number (1, from 2^0) - the smallest value representation in the binary place value system.
# Design of DES S-Boxes:
The design of the S-boxes in the DES cipher, both the mechanism for determining the output and the tables of outputs themselves, was done by the NSA and IBM under the following specific criteria, ranging from the obvious to the esoteric:
- Each S-box must have six input bits and four output bits, as to have an end total of 32 bits (to allow for XOR-ing with the left tranche).
- No single output bit should be too close to a linear combination (Linear Algebra - [[[[[[) of the input bits.
- If the lowest and the highest bits of the input are "fixed" (e.g., constant while the four middle values cycle through all possible incarnations) and the four middle bits are varied, each of the possible 4-bit output values must occur exactly once.
- "For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output difference."
If you know what the above words mean, since they seem (atleast to me) to be complete and utter nonsense, please contact me at jdlacabe@gmail.com. You will be credited (if you wish) on this page. - A collision (identical output values, known as a "Zero Difference" (since XOR-ing the values = 0)) of the outputs of the eight S-boxes must only be possible for a maximum of three adjacent S-boxes. Two adjacent colliding S-boxes would thus be fair game.
If it were possible for all 8 boxes to have a zero difference, then the S-box design would have a highly predictable structure. - DIFFUSION: If two inputs to an S-box differ by exactly one bit, their outputs must differ by atleast two bits.
- DIFFUSION: If two inputs to an S-box differ in two middle bits, their outputs must differ by atleast two bits.
- DIFFUSION: If two inputs to an S-box differ in their first two bits, but are identical in their last two bits, the two outputs must be different.
Diffusion Requirements:
