Stream and Block Ciphers

Stream Cipher Basics

• Encrypts digital data streams one bit or byte at a time.
• Examples include Autokeyed Vigenère cipher and Vernam cipher

Ideal Stream Cipher

• The keystream should be as long as the plaintext bitstream, as in a one-time pad version of the Vernam cipher
• If the cryptographic keystream is random, the cipher is unbreakable except by acquiring the keystream
• Keystream must be provided to both users in advance via an independent, secure channel.
• Introducing logistical problems if the intended data traffic is large

Practical Stream Cipher

• Bit-stream generator must be implemented as an algorithmic procedure to produce the cryptographic bit stream
• Computationally impractical to predict future portions of the bit stream based on previous portions of the bit stream
• Two users need only share the generating key; each can produce the keystream

Block Cipher Basics

• Treats a block of plaintext as a whole and uses it to produce a ciphertext block of equal length.
• Typically uses a block size of 64 or 128 bits.
• Like stream ciphers, the two users share a symmetric encryption key
• Most symmetric cryptographic applications that are network-based use block ciphers

Feistel Cipher Key Points

• Proposed by Feistel
• Use of a cipher that alternates substitutions and permutations
• Is a practical application of Claude Shannon's proposal for a product cipher, alternating confusion and diffusion functions
• Used by many significant symmetric block ciphers

Substitution

• Each plaintext element or group of elements is uniquely replaced by a corresponding ciphertext element or group of elements

Permutation

• No elements are added or deleted or replaced in the sequence; rather, the order in which the elements appear in the sequence is changed

Diffusion

• Introduced by Claude Shannon
• Dissipates the statistical structure of the plaintext into long-range statistics of the ciphertext
• Achieved by having each plaintext digit affect the value of many ciphertext digits

Confusion

• Seeks to make the relationship between the statistics of the ciphertext and the value of the encryption key as complex as possible
• Complex enough that even if the attacker can infer stats of the ciphertext the attacker still unable to deduce the key

Feistel Cipher Design Features: Block Size

• Larger block sizes offer greater security
• Block size decreases encryption/decryption speed for a given algorithm

Feistel Cipher Design Features: Key Size

• Larger key sizes provide greater security
• larger key size may decrease encryption/decryption speeds

Feistel Cipher Design Features: Number of Rounds

• Minimum security can be achieved in a single round
• Multiple rounds offer increasing security

Feistel Cipher Design Features: Subkey Generation Algorithm

• Greater complexity in this algorithm leads to greater difficulty of cryptanalysis
• More complex algorithms for generating the subkeys will be more resilient to cryptanalysis

Feistel Cipher Design Features: Round Function F

• Greater complexity generally means greater resistance to cryptanalysis of the round function

Feistel Cipher Design Features: Fast Software Encryption/Decryption

• Encryption is embedded in applications/utility functions in a way that precludes hardware implementation, execution speed of the algorithm becomes a concern therefore the speed must be fast
• Should be easy to implement in software for fast encryption

Feistel Cipher Design Features: Ease of Analysis

• If the algorithm can be explained concisely and clearly, easier to analyze for cryptanalytic vulnerabilities
• Allows for a higher level of assurance as to its strength

Data Encryption Standard (DES)

• Issued in 1977 by the National Bureau of Standards (now NIST) as Federal Information Processing Standard 46
• Most widely used encryption scheme until the introduction of AES in 2001
• The algorithm is referred to as the Data Encryption Algorithm (DEA)

Data Encryption Standard (DES) Encryption Details

• 64-bit blocks are encrypted using a 56-bit key
• The algorithm transforms 64-bit input in a series of steps into a 64-bit output
• The same steps, with the same key, are used to reverse the encryption

Initial Permutation IP

• The first step of the data computation.
• Reorders the input data bits.
• Even bits go to the left hand side and the odd bits go to the right hand side
• Structure is quite regular, making it easy to implement in hardware

Feistel Cipher Round Details:

• Uses 2 32-bit L & R halves
• The left half L₁ = R(i-1)
• The right half R₁ = L(i-1) XOR F(R(i-1, K₁)
• F takes 32-bit R half and 48-bit subkey
• Expands R to 48-bits using perm E
• Adds to subkey using XOR
• Passes through 8 S-boxes to get 32-bit result
• Finally permutes using 32-bit perm P
• F is NOT a permutation

Substitution Boxes S

• Each S-box maps 6 to 4 bits.
• Each S-box is actually 4 little 4-bit boxes
• Outer bits are used to select the row of 4 possible 4 bit permutations
• The row selection depends on both data and key, known as autoclaving (autokeying)
• Inner bits are substituted
• 8 lots of 4 bits are returned, or 32 bits overall

Avalanche Effect

• Key desirable property of encryption alg is observed
• A change of one input or key bit results in changing approximately half of the output bits
• Makes efforts to "home-in/reverse engineer" impossible
• DES exhibits strong avalanche

DES Table 4.5 Summary

• Key size of 56 bits, exhaustive key search time required is 1.125 years
• Key size of 128 bits, exhaustive key search time required is 5.3 x 10^21 years
• Key size of 168 bits, exhaustive key search time required is 5.8 x 10^33 years
• Key size of 192 bits, exhaustive key search time required is 9.8 x 10^40 years
• Key size of 256 bits, exhaustive key search time required is 1.8 x 10^60 years
• 26 char permutation, exhaustive key search time required is 6.3 x 10^6 years