# C. Rule . Block Ciphers:

A cipher that encrypts a block of 'b' plaintext bits all at the same time, where b is greater than one (since one bit at a time would be a stream cipher). These ciphers are both deterministic and hyper-unpredictable: the encryption of any plaintext bit in a block depends on the value of every other plaintext bit in the block, like the positions of celestial bodies in a galaxy. A one bit difference between two blocks of plaintext will produce two completely different ciphertexts.

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 Rule 48 & Rule [[[[, 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.

# C. Rule . 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:

1. 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. An example of this is the substitution table, which maps one input bit to a particular output bit the bears no relation to it (see definition).



2. 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 which works akin to chaos theory. Example: Permutations of an encryption method to make a cryptosystem more secure (see Rule 49).
   
   This element is impossible under stream ciphers, since each bit is processed and encrypted individually.

The sole utilization of Confusion and the abandonment of Diffusion, as was done with the Substitution and Shift Ciphers, will produce a very unsecure cipher. In order to make a truly "secure" cryptosystem using block ciphers, you need to combine both confusion & diffusion elements into the algorithm many times over, in the form of a product cipher.

# C. Rule . Feistel Ciphers:

Mathematical Definition:

i ∈ {1, ..., 16}

L_i = R_i-1
R_i = (L_i-1 + f(R_i-1, k_i)) mod 2


i = The particular round that the left and right tranches of the data were created in. The first round produces the tranches L₁ & R₁, for example.

L_i = The left tranche as it is in round i. It will inherit the unencrypted form of the previous right tranche as its starting value in the round.

L_i-1 = The left tranche of the round prior to the current one, used by the f function (see below). If i is 1, then it will be L₀, the left tranche of the initial input (32 bits of plaintext).

R_i = The right tranche as it is in round i. 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.

R_i-1 = The right tranche of the round prior to the current one, used by the f function (see below). If i is 1, then it will be R₀, the right tranche of the initial input (32 bits of plaintext).

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 50.

k_i = 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 - see Rule 24 for a full treatise.


Explanation:

A Feistel Cipher/Feistel Network/Feistel Structure is a round-based algorithm used to encrypt data. The original, standard, unadorned version of the Feistel Network is depicted below, while the DES-enhanced version can be seen in Rule 48.

A diagram of an individual round of the Feistel Network, totally unadorned of any additional characteristics specific to the DES system - see Rule 48 for that. The given values and lengths, such as the 48-bit subkey, are all specific to the DES varient.

Widely used among block ciphers (though not in the AES, see Rule [[[), several ciphers like DES developed their own, more optimized versions of the network. The bulk of all 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 (i.e. going about the rounds in reverse; 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). It is just at the same level of ubiquity in block ciphers that LFSRs have for stream ciphers.

Devoid of the more specialized characteristics (particularly those relating to DES, described in Subsection IV.III), the process by which a standard Feistel Cipher encrypts data is simple:

1. The data path will be split into two parts: a Left and a Right tranche, L₀ and R₀ respectively. For a 64 bit cipher (like DES), each tranche will have 32 bits.


2. 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 either tranche - in the DES, the subkey is 48 bits long, the purpose of which is explained in Rule [[[[[[[.


3. The output of the encryption of the right tranche will then be XOR'd bit-by-bit with the left tranche (which had gone untouched until now).


4. 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 (L₁), and the left tranche will become the new right tranche (R₁).
   
   IMPORTANT NOTE: The Right tranche is sent to the left tranche of the next round in its unencrypted form, while the right tranche of the next round is sent the encrypted output of steps 2-3. Since the Left tranche of the first round got XOR'd with the encrypted version of the Right tranche, the LEFT tranche is the one being "encrypted" during any particular round, not the right tranche. Although an encrypted version of the Right tranche is used to encrypt the Left tranche, the encrypted version of the right tranche is not used for any other purpose than to change the left tranche, since it is the unaltered version of the right tranche that gets sent to the next round.

Each round takes in the tranches produced by the previous round (or, in the case of round 1, the inputted plaintext tranches) and converts them algorithmically into new tranches. Thus, each encryption round extends from the tranches above the encryption algorithm to the end-result tranches below it: round 1 takes in tranches L₀ and R₀ and outputs L₁ and R₁.

# C. Rule . 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 "secure" cryptosystem ever made public by a national government under the postulate of Kerckhoffs's principle (see 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 its short key-length (56 bits), 3DES has a very long key, and as such is immune to such attacks. For information on 3DES, see Rule [[[.

# C. Rule . Data Encryption Standard (DES):

Mathematical Definition:

[[[[[

Explanation:

The Data Encryption Standard is a 56-bit 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, following the known elements of best-practice block ciphers (see Rule 45).

A diagram of an individual round of the DES-specific optimized version of the Feistel Network, complete with a representation of how the subkey is formed from a transform of the main key. On the right hand side is the key schedule, described in Rule [[[.

The key-length of DES is 56 bits (and thus has a keyspace of only 2^56 under the relation given in Rule 6) and 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 each round of the DES Feistel Network are only 48 bits each - see Rule [[[[ for why that is.

# C. Rule . DES Internals #1 - Bit Permutation:

The first characteristic one may note about the DES Feistel Cipher (as depicted in the graphic of Rule 48) is that the first operation undergone by data being processed by the cipher, even before it is split into tranches, 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, detailed in the definition above. Essentially, IP(x) just scrambles the bits and places them in different parts of the 64-bit sequence. IP(x)⁻¹, being the inverse of IP(x), perfectly undoes the scrambling of IP(x) at the end of the cipher (after all the bits have been fully encrypted), 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 in the illustration 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 the 8-bit data buses [widely used in the '70s]."

Below are the specific bit permutation tables hand-selected for the DES cipher. For any value in either box, look for the value in the other box whose position-value is the first value - this will determine what the first value maps to. For example, the value '58' in the IP box maps to '1' in the IP⁻¹ box, since 1 is in the 58th position in IP⁻¹. Likewise, '1' in the IP⁻¹ box maps to 58 in the IP box since 58 is in the 1st position. Note that these values represent the bits at these positions in the 64-bit sequence being mapped to other bits.

The Initial and Final Permutations in the DES cipher.

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 . DES Internals #2 - The 'f' Function:

The f function, the heart of the Feistel Network (and thus the DES), acts similarly to a PRNG, using the two input parameters R_i-1 (32 bits) and k_i (48 bits) to "encrypt" the right tranche (encrypt in quotations because this encrypted version will only be used to XOR the left tranche, while the unencrypted right tranche will move on to the next round, as detailed in Rule 46).

R_i-1 is the tranche created in the previous round (since each round creates its tranches using the tranches of the previous round; see Rule 46), while k_i is the subkey for that particular round (see step 2). Below are the complete contents of the f function, with each step labeled (and each individually described at length further below):

The complete f function of the DES-specific Feistel Network, with each step labeled.

1. The first operation that will be performed will solely involve the first parameter: R_i-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".
   
   The E-box is a non-bijective variation of the standard bit permutation (see definition), 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 in the illustration below.
   
   Notably, this function will provide diffusion to the cipher, as its effects will increase the significance & influence of each individual bit of the plaintext with every additional round of encryption.
   
   
   
   The permutation performed by the Expansion box.



2. 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 successfully alters the data using a key.



3. After the XOR, the string must be shrunk 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). This requires the uses of the S boxes, arguably the most important part of the f function. Complementary to the diffusion of the E-box, the S-box will provide the confusion element of the cipher (as well as more diffusion - see the "Design of DES S-Boxes" blue section).
   
   The pattern the S-box follows is simple, and is shown in the complete f function diagram further above: The newly-created 48-bit string will be split into 8 sub-tranches of 6 bits. Each sub-tranche will be sent to a Substitution Table (see definition), S₁ through S₈. These tables will work akin to compression functions/compression boxes in the exact opposite manner to the E-box, as they 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 predetermined substitution table. For information as to what exact criteria the S-boxes were designed with in mind, see the relevant "Design of DES S-Boxes" blue section below.
   
   Note that EACH S-box, S₁ through S₈, has its own, individual, substitution table. While the S₁ table is shown below, the rest of the tables can be found on page 3 of this document here.
   
   
   
   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 and in all others) is to locate it on the table using the known column and row values. The binary representation of the located value is then concatenated with the results from all the S-boxes, forming a 32-bit string that passes onto the final step.



4. All that is left to be done within the f function after the compression from the S-boxes of step 3 is a simple bit permutation, which works in a different fashion to the IP(x) and IP(x)⁻¹ described in the Rule 49.
   
   This permutation has a legitimate cryptographic purpose: the collective output bits of the S-boxes from step 3 are scrambled in such a way that the individual bits are positioned to affect more S-boxes in the following round. If even a single bit is flipped in the input, it will progressively affect more S-boxes each round and will eventually change the entire output. Thus, this permutation hastens the avalanche effect and contributes further diffusion to the cipher.
   
   Each round uses the same permutation table, seen below. Of course, as before in Rule 49, it must be read in terms of both position and value - the 1st bit is moved to position 16, while the 2nd is moved to position 7, and so on.
   
   
   
   The permutation table/substitution table used in each round of the f function to move the bits around the sequence.

# C. Rule . DES Internals #3 - Key Schedule:

The Key Schedule is the algorithm used to generate the subkey for every round of DES, working almost like a mini-DES using its own permutations and round system to supply the subkeys. Using a series of fairly simple operations, the key schedule is able to shrink the inputted key from 64-bits to 56-bits, and then from there into sixteen 48-bit subkeys. The reason that DES doesn't just use 64-bit subkeys (adjusting the E-box and S-box's appropriately) is because [REDACTED].

A 64-bit key is inputted into the key schedule and goes through a series of operations before 16 subkeys (k₁ through k₁₆) are derived from it to supply each of the 16 encryption rounds, each subkey consisting of 48 bits. Each operation in this process is described in the paragraphs, in the order that the bits travel from entry into the key schedule to the creation of the final subkey. The illustrations below depict the placement of the Key Schedule in relation to the rest of the DES cipher, as well as the internal details of the Key Schedule and their steps.

The DES Feistel network, with the Key Schedule circled in red so you don't miss it.


A closeup of the Key Schedule, with the finer details of the Transforms shown. Each step is described in detail in the paragraphs below.