Data Encryption Standard

History of LUCIFER, DES, triple DES

• 1971: IBM project, led by Horst Feistel, develops LUCIFER algorithm: A Feistel block cipher with 64-bit blocks and 128-bit key. Sold to Lloyd’s of London for use in a cash-dispensing system, also developed by IBM. Refined version (effort lead by Walter Tuchman and Carl Meyer of IBM, with support of National Security Agency NSA): more resistant to cryptanalysis but 56-bit key in order to fit on a single chip.
• 1973: National Bureau of Standards (NBS) issues a request for proposals for a national cipher standard. IBM’s refined version of LUCIFER by far best algorithm proposed.
• 1977: adopted as Data Encryption Standard (Federal Information Processing Standard 46 (FIPS PUB 46)) by National Bureau of Standards (now National Institute of Standards and Technology NIST).
• 1994: NIST reaffirms DES for federal use for another 5 years, recommends use for applications other than protection of classified info.
• 1999: NIST issues a new version (FIPS PUB 46-3), indicates DES should be used only for legacy systems and triple DES be used.

Data Encryption Standard

Data Encryption Standard is a symmetric key encryption algorithm.

Although DES standard is public, there was controversy over its design:

• in choice of 56-bit key over 128-bit key Subsequent research showed design was in fact appropriate. DES is still standard for legacy application use. Extensions such as triple DES were created to overcome short key length.
• design criteria was classified

Link to original

DES Encryption Scheme

• Block size of $64$ bits.
• Plaintext and ciphertext space is $\mathcal{M}=\mathcal{C}=\{0,1{\}}^{64}$
• The input is $64$ bits of plaintext with a $56$-bit key. (note: $64$-bit key used as input but only $56$ bits are used)
• The output is $64$ bits.

DES keys are all bitstrings of length $64$ with a checksum property.

If a $64$-bit DES key is divided into eight bytes, then the sum of the eight bits of each byte is odd. This means that $7$ out of the $8$ bits determine the value of the $8^{th}$ bit so that transmission errors of one bit can be spotted.

Therefore the key space is:

$$\mathcal{K}=\{(b_1,\dots ,b_{64})\in \{0,1{\}}^{64}|\sum _{i=1}^8{b}_{8k+1}\equiv 1\text{ mod }2,0\le k\le 7\}$$

When we throw away the last bit of each byte, we are left with $56$ bits.

Explanation of scheme

The plaintext is processed in 3 phases:

1. Initial permutation ($\text{IP}$): rearranges bits to produce permuted input
2. 16 rounds of both permutation and substitution functions
   • Output of $16^{th}$ round: $64$ bits, function of input plaintext and keys
   • Left and right halves of output swapped to produce preoutput
3. Preoutput is passed through ${\text{IP}}^{-1}$ to finally produce $64$-bit ciphertext.

Except for initial and final permutations, DES has the exact structure of a Feistel cipher.

$\text{IP}$ and ${\text{IP}}^{-1}$ have no cryptographic significance but included to facilitate loading blocks in and out of mid-1970s 8-bit based hardware.

Use of $56$-bit key:

• Initially, key is passed through a permutation function.
• For each of $16$ rounds, a subkey $K_i$ is produced by a combination of left circular shift and permutation. The permutation function is the same for each round but a different subkey is produced because of repeated shifts of key bits.

$\text{IP}$ and ${\text{IP}}^{-1}$ are defined by tables:

• Input to a table consists of $64$ bits numbered from $1$ to $64$.
• The $64$ entries in permutation table contain a permutation of numbers from $1$ to $64$.
• Even bits to LH half, odd bits to RH half.
• ${\text{IP}}^{-1}(\text{IP}(M))$ restores the original ordering of bits

Example: consider $64$-bit input $M$ and permutation $\text{IP}(M)$

Details of Single Round

• $L$ and $R$ halves of each $64$-bit intermediate value treated as separate $32$-bit quantities.
• As in any Feistel cipher, overall processing at each round is: $$\begin{array}{rl}{L}_i& =R_{i-1}\\ R_i& =L_{i-1}\oplus F(R_{i-1},K_i)\end{array}$$
• The round key $K_i$ is $48$ bits.

Encryption

• $R_{i-1}$ is $32$ bits and is expanded to $48$ bits by using Expansion Permutation (E) table which defines a permutation plus an expansion that involves a duplication of $16$ bits of $R_{i-1}$. Resulting $48$ bits are XORed with $K_i$.

• $48$ bit result of XOR passes through substitution function (S-box) that produces a $32$-bit output.

  Substitution consists of a set of $8$ S-boxes, each of which accepts $6$ bits as input and produces $4$ bits as output.

  The transformations are defined by the following table:

  • The first and last bits of the input to box $S_i$ form a $2$-bit binary number to select $1$ of $4$ substitutions defined by four rows in the table for $S_i$.
  • Middle $4$ bits select one of the $16$ columns.
  • Decimal value in the cell selected by the row and column is then converted to its $4$-bit representation to produce output.
  • Each row of an S-box defines a general reversible substitution.

  
  Example: in $S_1$ for input $011001$, the row is $01$ (row $1$) and the column is $1100$ (column $12$). The value in row $1$, column $12$ is $9$, so the output is $1001$.

• The $32$-bit output is permuted by using a table (Permutation Function P).

Key Generation

• $64$-bit key is used as an input
• Every eighth bit is ignored:
• Key first subjected to a permutation using table Permuted Choice One
• Resulting $56$-bit key is treated as two $28$-bit quantities $C_0$ and $D_0$.
• At each round, $C_{i-1}$ and $D_{i-1}$ are separately subjected to a circular shift (rotation) of $1$ or $2$ bits as governed by the Schedule of Left Shifts table.
• Shifted values are input to:
  • next round
  • Permuted Choice Two which produces a $48$-bit output that serves as input to function $F(R_{i-1},K_i)$

Decryption

As with any Feistel cipher, decryption uses the same algorithm as encryption, except that the application of the subkeys is reversed.

Example

Security of DES and Triple DES

Strength of DES (and Triple DES)

Since its invention, security of DES has been studied intensively. Special techniques such as differential cryptanalysis and linear cryptanalysis have been invented to attack DES (e.g. reducing key space from $2^{56}$ to $2^{43}$).

Most successful attack is an exhaustive search of the key space.

• Special hardware or large networks of workstations can decrypt DES ciphertexts in a few days or even a few hours. $7$ hours with $1$ million dollar computer in 1993.
• DES will be breakable on a single PC.

Link to original

Double DES

Double DES

To increase DES security, a proposal was made to perform two DES encryptions which supposedly was equivalent to using $112$ bit keys (i.e. $K_1$ and $K_2$, but this is not true):

Link to original

Strength of Double DES

However, this is susceptible to a Meet-in-the-Middle attack:

• For $C=E(K_2,E(K_1,P))$, let $X=E(K_1,P)=D(K_2,C)$.
• Given known $P$ and $C$, encrypt $P$ for all possible $2^{56}$ possible $K_1$.
• Store in table, sorted by $X$.
• Decrypt $C$ with all $2^{56}$ possible $K_2$ and look for a match.
• Each hit is a candidate solution, validated with additional plain/cipher-text pair.
• A known plaintext attack against double DES will succeed with effort on the order of $2^{56}$ operations.

Link to original

Triple DES

Triple DES

Use 3 stages of encryption instead of 2, with 2 keys $K_1$ and $K_2$:

• Compatible with standard DES ($K_2=K_1$) if needed.
• There is no known practical attack but a brute-force attack search with $2^{112}$ operations.

Variant of Triple DES exists with $3$ different keys $K_1,K_2,K_3$.

This has an effective key length of $168$ bits. This is also adopted by some internet applications such as PGP and S/MIME.

Link to original

Advanced Encryption Standard

Advanced Encryption Standard (AES)

A symmetric block cipher intended to replace DES for commercial applications.

• Uses $128$-bit block size and a key size of $128$, $192$, or $256$ bits.
• Does not use Feistel structure.
• Each full round consists of $4$ separate functions:
  • byte substitution
  • permutation
  • arithmetic operations over a finite field
  • XOR with a key

Link to original

History of AES

• 1997: NIST initiated selection process for the successor of DES. One of the submissions was the Rijndael cipher (named after its inventors Rijmen and Daemen).
• 2001: this encryption scheme standardized as the Advanced Encryption Standard. AES special case of Rijndael, which admits more different block lengths and ciphertext spaces.

AES Encryption

• Key length can be $16$, $24$, or $32$ bytes ($128,192,$ or $256$ bits).

• Cipher consists of $N$ rounds depending on key length:

  • $10$ rounds for $16$-byte key
  • $12$ rounds for $24$-byte key
  • $14$ rounds for $32$-byte key

Simplified DES (S-DES)

[skipped this, TODO later i guess for practice] [PDF included in this folder]