I 248 H2001

3. forelesning 4.9.2001

Crash Course on cryptography (continued) : Chapters 3 &4

• Block or stream ciphers
  
• Assume (in the following)  that message is
• a sequence of bits or
• a sequence of bytes
• divided into blocks if convenient
  (block: for example, 64 bits)
  
• (Shannon: "Communication theory of secrecy systems", Bell Syst. Tech. J.,vol 28, pp. 656-715, 1949):
• Unconditional security
• Practical security.
• Principles:
• Confusion:
• Use security transformations that complicate the determination of how the
  statistics of the ciphertext depend on the statistics of the plaintext
  (statistics:
• single-letter statistics
• higher order statistics...)
• hilde local patterns in the language
• Small-alphabet monoalphabetic cipher: Fails (doubled letters "ee" still occurs)
• Vigenere: better (destroys some local statistics)
• Transposition: Fails; No local mapping at all
  
• Diffusion:
• Spread the influence of a single plaintext digit over many digits of ciphertext
• Purpose: Even out letter distribution,
  Frustrate piecemeal attack, hide statistical structure of plaintext
• Two almost equal plaintexts will look very different after encryption
• Small-alphabet monoalphabetic cipher: Fails
• Vigenere : Fails  (does not move anything around)
• Transposition: excellent
• The avalanche effect:
• A small change in either plaintext or key results in many bits of ciphertext change
  
• Simple legitimate encryption and decryption
• Product cipher: A succession of simpler "building block" ciphers,
  each adding to an overall large amount of diffusion and confusion
• "Building blocks:"
• Substitution
• Poor when used alone on a small alphabet
• Strong when the alphabet is extremely large and each plaintext "letter" is used
  with very small probability
  
• Transposition 
• Alters the higher order statistics of the plaintext

• Product cipher
• Reversible(Invertible/nonsingular) mapping of n-bit value into another n-bit value
  (i. e., 2ⁿ! different mappings)
• Block substitution (Fig. 3.4)
• represents one particular of the 2ⁿ! different mappings
• key: table of mapping key; key size is n*2ⁿ bits
  
• n=4...simple to describe mapping, key size is n*2ⁿ = 64 bits but insecure (vulnerable to statistical analysis)
• n=64...secure(?!) but key size is is n*2ⁿ = a horrible number of bits
• Feistel: Figure 3.5.
• L_i=R_i-1
• R_i= L_i-1 + F(R_i-1 ,K) 
• Key issues: 
  
  • Block size
  • Key size
  • Number of rounds
  • Subkey (K_i) generation
  • Round function F
  • Fast software implementation?
  • easy analysis? (if so, simpler to avoid or assess vulnerability)
  • Decryption: Reverse process (Fig. 3.6)
    

  
  

• Standard since 1977
• Fig 3.7
• Details Fig 3.8
• F: Consists of
• Expansion 32-48 bits (Linear)
• XOR with subkey (Linear)
• 8 S-boxes (Nonlinear mappings from (DES:) 6 to 4 bits)
• Permutation (Linear)
  
• Avalanche effect: Strong (Table 3.5)
• Weaknesses:
• Suspicion about design
• Recent trends in cryptanalysis:
• Differential cryptanalysis
• Biham & Shamir, 1991
• start with pairs m, m' of chosen plaintexts with known difference
• track differences through the rounds
• this technique can suggest (with high probability) correct parts of the key
• Requires 2⁴⁷ chosen plaintexts with corresponding ciphertexts to break full DES
  
• Linear cryptanalysis
• Matsui 1994
• Requires 2⁴⁷ known plaintext-ciphertext pairs to break full DES
  
• Key size...56 bits allow brute force design, by specially designed machines or large-scale parallel attacks
• will be followed now by AES (Advanced ES)

• Number of rounds:
• More rounds: stronger but slower, differential cryptanalysis more difficult
• at least...make  differential cryptanalysis more difficult than brute force
  (DES: 16, just OK)
  
• Design of F
• Nonlinear...F(a+b) != F(a)+F(b)
• Diffusion: Strict avalanche criterion...when one inputbit changes,
  any output bit should change with probability 1/2
• Bit independence criterion...the above change should be independent in two arbitrary output bits
  
• Design of S-Box
• Large: better resistance to diff/lin cryptanalysis, more difficult to design
• nonlinear!  (bent functions)
• avalanche criterions (GA 1-g)
  
• Random/random with testing/man-made/math-made
  
• Key schedule
• No general principles...key/ciphertext SAC/BIC?
  
• Characteristics
• Weakness of DES: short key -------------- better: variable key length (AES: 128/192/256)
• Mixed operators in S-boxes (arithmetic/boolean/other)----nonlinearity
• Data- and/or  key-dependent  rotation of data block, as an alternative or addition to S-boxes
• Key-dependent S-boxes
• Complex key generation
• Different F's
• variable plaintext length
• optional number of rounds
• operations on both halves of data
  

• Table 3.6; Figs 3.11-14
• Electronic Codebook
• Cipher Block Chaining
• secret and intergrity-checked IV!
  otherwise, if opponent made receiver used a different IV',
  this would change the bits in the difference IV-IV'
• Cipher Feedback Mode
• stream cipher (for example character-based, fig 3.13)
• Output feedback mode
• similar to CFB
• no bit error propagation
• vulnerable to message modification
  

• Triple DES
• Why not double DES?
• Meet in the middle attack
  
• IDEA,Blowfish,RC5,CAST-128,RC2
• AES (Rijndael )
• http://csrc.nist.gov/encryption/aes/rijndael/