DES (Data Encryption Standard)

 Outline
 Background and History of DES
 Overview of DES
 Double and Triple DES
 Security of DES
1. Background and History of DES (1)

 Early 1970’s - NBS (Nat’l Bureau of Standards) recognized

general public’s need for a secure crypto system
NBS – part of US gov’t / Now: NIST – Nat’l Inst. of Stand’s & Technology

 „Encryption for the masses” [A. Striegel]

 Existing US gov’t crypto systems were not meant to be
made public
 E.g. DoD, State Dept.

 Problems with proliferation of commercial encryption

devices
 Incompatible

 Not extensively tested by independent body

 Background and History of DES (2)
 1972 - NBS calls for proposals for a public crypto system
 Criteria:

 Highly secure / easy to understand / publishable /

available to all / adaptable to diverse app’s /
economical / efficient to use / able to be validated /
exportable
 In truth: Not too strong (for NSA, etc.)

 1974 – IBM proposed its Lucifer

 DES based on it
 Tested by NSA (Nat’l Security Agency) and the general public
 Nov. 1976 – DES adopted as US standard for sensitive but
unclassified data / communication
 Later adopted by ISO (Int’l Standards Organization)
 Official name: DEA - Data Encryption Algorithm / DEA-1 abroad
 2D.2. Overview of DES (1)
 DES - a block cipher
 a product cipher
 16 rounds (iterations) on the input bits (of P)
 substitutions (for confusion) and permutations (for
diffusion)
 Each round with a round key
 Generated from the user-supplied key
 Easy to implement in S/W or H/W
 Overview of DES (2)
Basic Structure
Input
 Input: 64 bits (a block)
Input Permutation
 Li/Ri– left/right half of the input block for
iteration i (32 bits) – subject to substitution S L0 R0
and permutation P (cf. Fig 2-8– text)
S K
 K - user-supplied key
 Ki - round key: P
 56 bits used +8 unused
(unused for E but often used for error checking)
L1 R1
 Output: 64 bits (a block) K1
 Note: Ri becomes L(i+1) L16 R16
K16
 All basic op’s are simple logical ops
 Left shift / XOR Final Permutation

Output
 Overview of DES (3) -
Generation of Round Keys
 key – user-supplied key (input)
 PC-1, PC-2 – permutation tables
key PC-2 also extracts 48 of 56 bits
 K1 – K16 – round keys (outputs)
PC-1
 Length(Ki) = 48
C0 D0  Ci / Di – confusion / diffusion (?)
 LSH –left shift (rotation) tables
LSH LSH
PC-2 K1

C1 D1

LSH LSH
PC-2 K16

[Fig: cf. Barbara Endicott-Popovsky, U. Washington]

 Overview of DES (4) -
Problems with DES
 Diffie, Hellman 1977 prediction: “In a few years,
technology would allow DES to be broken in days.”
 Key length is fixed (= 56)
 256 keys ~ 1015 keys
 „Becoming” too short for faster computers
 1997: 3,500 machines – 4 months
 1998: special „DES cracker” h/w – 4 days

 Design decisions not public

 Suspected of having backdoors
 Speculation: To facilitate government access?
 Overview of DES (4) -
Problems with DES
 Diffie, Hellman 1977 prediction: “In a few years,
technology would allow DES to be broken in days.”
 Key length is fixed (= 56)
 256 keys ~ 1015 keys
 „Becoming” too short for faster computers
 1997: 3,500 machines – 4 months
 1998: special „DES cracker” h/w – 4 days

 Design decisions not public

 Suspected of having backdoors
 Speculation: To facilitate government access?
 2D.3. Double and Triple DES (1)
 Double DES:
 Use double DES encryption
C = E(k2, E(k1, P) )
 Expected to multiply difficulty of breaking the encryption
 Not true!
 In general, 2 encryptions are not better than one
[Merkle, Hellman, 1981]
 Only doubles the attacker’s work
 Double and Triple DES (2)
 Triple DES:
 Is it C = E(k3, E(k2, E(k1, P) ) ?
 Not soooo simple!
 Double and Triple DES (3)
 Triple DES:
 Tricks used:
D not E in the 2nd step, k1 used twice (in steps 1 & 3)
 It is:
C = E(k1, D(k2, E(k1, P) )
and
P = D(k1, E(k2, D(k1, C) )

 Doubles the effective key length

 112-bit key is quite strong
 Even for today’s computers
 For all feasible known attacks
 2D.4. Security of DES
 So, is DES insecure?
 No, not yet
 1997 attack required a lot of coperation
 The 1998 special-purpose machine is still very
expensive
 Triple DES still beyong the reach of these 2 attacks
 But ...
 In 1995, NIST (formerly NBS) began search for
new strong encryption standard
DES – Confusion, Diffusion and Avalanche
Effect
• Confusion and diffusion are two fundamental principles in the design of secure cryptographic
algorithms. These concepts were introduced by Claude Shannon in his seminal work on information
theory and form the basis of many encryption algorithms, including the Data Encryption Standard (DES).
• Confusion refers to making the relationship between the key and the cipher text as complex and as
obscure as possible. This ensures that even if someone knows the cipher text, they cannot easily
deduce the key.
• In DES, confusion is achieved primarily through the use of S-boxes (substitution boxes). The S-boxes take the input
bits and produce output bits that are non-linearly related to the input. This non-linear transformation obscures the
relationship between the plaintext, the cipher text, and the key.
• Diffusion refers to spreading the influence of each plaintext bit over many cipher text bits. This means
that a change in a single bit of the plaintext should result in a significantly different cipher text, thus
making it harder to find patterns that could lead to the key.
• In DES, diffusion is achieved through permutation operations and the Feistel network structure. The permutations
and the repeated mixing of the bits throughout multiple rounds ensure that the plaintext is thoroughly diffused into
the cipher text.
Avalanche Effect in DES
• The avalanche effect is a desirable property of cryptographic algorithms, where a small change in either
the plaintext or the key results in a significant change in the ciphertext. This ensures that the encryption
process is highly sensitive to initial conditions, enhancing security by making it difficult to predict the
output.
• In DES, the avalanche effect is realized through the combined application of confusion and diffusion. A
single bit change in the plaintext or the key should affect approximately half of the bits in the ciphertext,
making it infeasible for attackers to use simple statistical analysis to reverse-engineer the key.
• Examples in DES
• S-boxes: Introduce non-linearity and contribute to confusion. A slight change in input results in a drastically different
output.
• Permutation (P) Boxes: Spread out the bits across the block to ensure diffusion. They help in making the output bits
depend on the input bits in a complex manner.
• Feistel Network: The structure of DES, which involves multiple rounds of processing, ensures both confusion and
diffusion are achieved. Each round uses a different subkey and applies S-box substitutions and permutations,
contributing to the overall avalanche effect.
Avalanche Effect
Applications of DES
• Standardization Requirements: Some standards and regulations might
still list DES as an optional algorithm for compliance, though it is
usually recommended to use more secure algorithms like AES.
• Variants of DES: Triple DES (3DES): This is an enhancement of DES that
applies the DES algorithm three times to each data block. While it is
more secure than single DES, it is also being phased out in favor of
stronger algorithms like AES.
• Payment Card Industry (PCI) Compliance: Some older payment
systems might still support 3DES for encryption, although PCI
standards are pushing towards the use of AES for stronger security.
Activity : Explore PCI compliance and list
down PCI requirements and what are the
consequences of non-compliance.
DES Assignment Questions
• Calculate the total number of bits in a DES key.
• Answer: 56 bits (Note: DES keys are 64 bits long, but 8 bits are used for parity, leaving 56 bits for the actual key.)
• How many subkeys are generated during the DES encryption process?
• Answer: 16 subkeys (One subkey for each of the 16 rounds of encryption.)
• Determine the number of bits in each subkey used in DES.
• Answer: 48 bits
• Calculate the number of possible keys in DES.
• Answer: 2562^{56}256 (Approximately 72 quadrillion or 72×101572 \times 10^{15}72×1015)
• How many times is the initial permutation (IP) applied during the DES encryption and decryption
process?
• Answer: Twice (Once at the beginning of encryption and once at the beginning of decryption.)
• If the plaintext input to DES is 64 bits, how many bits will be processed by each of the 16 Feistel
rounds?
• Answer: 32 bits (Each round processes half of the 64-bit block, so each Feistel function works on 32 bits.)
DES Assignment Questions
• Given that DES uses 16 rounds of Feistel structure, calculate the number of permutations and
substitutions applied to a 64-bit block of data.
• Answer: Each round involves permutations (P-box) and substitutions (S-box). There are 8 S-boxes in each
round, and a permutation function is applied. Thus, there are 16 permutations and 128 substitutions (8
substitutions per round × 16 rounds).
• Calculate the number of bits affected by a single bit change in the plaintext after 3 rounds of
DES, assuming a perfectly random substitution and permutation.
• Answer: This is a complex question involving the avalanche effect. After 3 rounds, due to the diffusion and
confusion properties of DES, it's expected that a single bit change can affect approximately half the bits.
Thus, after 3 rounds, around 642=32\frac{64}{2} = 32264​=32 bits could be affected.
• Estimate the time to brute-force a DES key if a machine can test 1 million keys per second.
• Answer: The total number of keys is 2562^{56}256. Testing 1 million keys per second:
Time=256106 seconds≈7.2×1010 seconds≈2283 years\text{Time} = \frac{2^{56}}{10^6} \text{ seconds} \
approx 7.2 \times 10^{10} \text{ seconds} \approx 2283 \text{ years}Time=106256​
seconds≈7.2×1010 seconds≈2283 years
Numerical on Simplified DES
• [Link]