Cryptography - Lecture 9 - Block Cipher Design and Usage

1. Weak Keys

• with many block ciphers there are some keys that should be avoided
• because of reduced cipher complexity
• these keys have the same sub-key generated in more than one round

2. Weak Keys in DES

• the same sub-key is generated for every round
• DES has 4 weak keys

3. Semi-Weak Keys in DES

• only two sub-keys are generated on alternate rounds
• DES has 12 of these (in 6 pairs)

4. Demi-Semi Weak Keys in DES

• have four sub-keys generated in groups

5. Handling Weak Keys

• weak keys dont cause a problem
• since they are a tiny fraction of all available keys
• however they MUST be avoided by any key generation program

6. DES Design Principles

• although the standard for DES is public
• the design criteria used are classified
• a few have since been made public
• have seen reverse engineering to derive others

7. DES S-box Design

• are four substitution functions, one selected by bits 1,6
• map inputs 2,3,4,5 onto output bits
• carefully chosen to provide avalanche & completeness
• also now know designed for max resistance to differential cryptanalysis
• some criteria were released, more have been deduced

8. DES Permutations Design

• 5 permutations: IP and IP^-1, P, E, PC1, PC2
• IP and IP^-1 and PC1 serve no cryptological function when DES is used in ECB or CBC modes
• since they merely rearrange bits in a regular pattern
• hence searches may be constructed with their effect ignored
• E, P, and PC2 act with S-Boxes
• to ensure dependence of the output bits on the input bits and key bits
• ie provide avalanche and completeness effects

9. DES Key Schedule and PC-2 Design

• the rotations are used to present different bits of the key for selection on successive rounds
• PC-2 selects key-bits and distributes them over the S-box inputs

10. Triple DES

• clearly need a replacement for DES given advances in key searching
• Triple DES is a proposal based on the existing DES
• standardised in ANSI X9.17 & ISO 8732 and in PEM for key management
• proposed for general EFT standard by ANSI X9
• backwards compatible with exisitng single DES (K1=K2=K3)
• uses either 2 keys (where K1=K3) or 3 keys:

  C = DESK3 {DES-1K2{DESK1(P)}}
  

11. Security of Triple DES

• no known practical attacks
  • brute force search impossible
  • meet-in-the-middle attacks need 2^(56) plaintext-ciphertext pairs per key
• is a popular current alternative
• major disadvantage is speed (3x slower)

12. Modes of Use

• block ciphers encrypt a fixed size block of information
• eg. DES encrypts 64-bit blocks of data, using a 56-bit key
• need some way of specifying how to use it in practise, given that we usually have an arbitrary amount of information to encrypt
• way a block cipher is used is called its Mode of Use
• four have been defined for DES in ANSI standard ANSI X3.106-1983 Modes of Use
• modes are either:

  Block Modes

  processes message in blocks (ECB, CBC)

  Stream Modes

  processes message as a bit/byte stream (CFB, OFB)

13. Electronic Codebook Book (ECB)

• message is broken into independent blocks which are encrypted
• each block is a value which is substituted, like a codebook, hence name
• each block is independent of all others

  Ci = DESK1 (Pi)
  

  
  Stallings Fig 3.11

14. Advantages and Limitations of ECB

• repetitions in message can be reflected in ciphertext
  • if aligned with message block
  • particularly with data such graphics
  • or with messages that change very little, which become a code-book analysis problem
• weakness due to encrypted message blocks being independent
• hence only really useful when sending a few blocks of data

15. Cipher Block Chaining (CBC)

• message is broken into blocks
• but these are linked together in the encryption operation
• ie cipher blocks are chained with plaintext, hence name
• use a known Initial Vector (IV) to start process

  Ci = DESK1(Pi XOR Ci-1)
  C-1 = IV
  

  
  Stallings Fig 3.12

16. Advantages and Limitations of CBC

• each ciphertext block is dependent on all message blocks before it
• most common mode of use when data available in advance
• thus a change in the message affects the ciphertext block after the change as well as the original block
• to start need an Initial Value (IV) which must be known by both sender and receiver
  • however if IV is sent in the clear, an attacker can change bits of the first block, and change IV to compensate
  • hence either IV must be a fixed value (as in EFTPOS) or it must be sent encrypted in ECB mode before rest of message
• also at the end of the message, have to handle a possible last short block
  • either pad last block (usually with count of pad size)
  • eg. [ b1 b2 b3 0 0 0 0 5] <- 3 data bytes, then 5 bytes pad+count
  • or use some fiddling to double up last two blocks
  • see Davies section 4.2 for examples

17. Cipher FeedBack (CFB)

• the message is treated as a stream of bits
• which are added to the output of the block cipher
• result is feed back for next stage (hence name)
• standard allows any number of bit (1,8 or 64 or whatever) to be feed back
• denoted CFB-1, CFB-8, CFB-64 etc
• in practice it is most efficient to consume all 64 bits
• call this CFB-64

  Ci = Pi XOR DESK1 (Ci-1)
  C-1 = IV
  

  
  Stallings Fig 3.13

18. Advantages and Limitations of CFB

• appropriate when data inherently arrives in bits/bytes
• most common stream mode
• limitation is need to stall while do block encryption after every 64 bits
• block cipher is use in encryption mode at both ends
• errors propogate for several blocks after the error

19. Output FeedBack (OFB)

• the message is treated as a stream of bits
• output of block cipher is added to the message
• and output if then feed back (hence name)
• thus feedback is independent of the message
• can be computed in advance

  Ci = Pi XOR Oi
  Oi = DESK1(Oi-1)
  O-1 = IV
  

  
  Stallings Fig 3.14

20. Advantages and Limitations of OFB

• used where the error feedback is a problem
• or where the encryptions must be done before the message is available
• superficially similar to CFB
• but the feedback is from the output of the block cipher and is independent of the message
• a variation of a Vernam cipher
• hence must never reuse the same sequence (key+IV)
• sender and receiver must remain in sync, and some recovery method is needed to ensure this occurs
• although originally specified with m-bit feedback in the standards
• subsequent research has shown that only 64-bit OFB should ever be used
• and this is the most efficient use anyway

21. Summary

• DES design principles
• triple-DES
• block cipher modes of use: ECB, CBC, CFB, OFB

22. Exercises

1. Consider the avalanche effect in the DES cipher. If a single data input bit is changed, if it becomes a L half bit, roughly how many bits could be changed after round 1? After rounds 2, 3? Hint: if any input bit to an S-box is changed, potentially all that S-boxes output bits can change (given completeness in the S-box design). Now consider the case when a R half data bit is changed. How many bits could change after round 1, 2, 3? When a key bit is changed?
2. For each of the four modes of use for block ciphers, think of an application where that mode would be the most appropriate, and in a few sentences describe the application and why the mode is the best choice