Cryptography - Lecture 11 - Block Cipher Cryptanalysis

1. Cryptanalysis of Block Ciphers

• now consider how to attack a block cipher
• a far far harder problem than for classical ciphers
• can always do an exhaustive key search
• has been demonstrated for 56-bit DES keys in s/w & h/w
• real issue is whether other more efficient attacks exist
  • on structure of cipher
  • on implementation of cipher

2. Exhaustive Key Search

• always theoretically possible to simply try every key
• most basic attack, directly proportional to key size
• assume either know or can recognise when plaintext is found
• tabulate for reasonable assumptions about number of operations possible:

  Key Size (bits)	Time (1us/test)	Time (1us/106test)
  32	35.8 mins	2.15 msec
  40	6.4 days	550 msec
  56	1140 years	10.0 hours
  64	~500000 years	107 days
  128	5 x 1024years	5 x 1018 years

3. Structural Attacks

• focus is to utilise some deep structure of the cipher
• so that by gathering information about encryptions
• can eventually recover some/all of the sub-key bits
• if necessary then exhaustively search for the rest
• generally these are statistical attacks:
  • differential cryptanalysis
  • linear cryptanalysis
  • related key attacks

4. Implementation Attacks

• alternatively can attack actual implementation of cipher
• not attacking cipher structure directly
• but use knowledge of consequences of implementation
• to derive knowledge of some/all subkey bits
• generall need physical access to implementation for attacks:
  • timing attacks
  • power attacks
  • differential fault analysis

5. Inventing Attacks

• note once again that each of these attacks involved a new/different perspective on the problem to that expected before
• just as have seen historically
• still have a continuing "arms race" between cryptographers & cryptanalysts
• currently theoretical strength is good, but implementation a concern

6. Differential Cryptanalysis

• one of the most significant recent (public) advances in cryptanalysis
• was known by NSA in 70's when DES was designed
• a powerful technique for analysing block ciphers
• has been used to analyse most current block ciphers with varying degrees of success
• have a break-even point in number of rounds of the cipher used for which differential cryptanalysis is faster than exhaustive key-space search
• if this number is greater than that specified for the cipher, then the cipher is regarded as broken

7. Overview of Differential Cryptanalysis

• a statistical attack against Feistel ciphers
• uses structure in cipher not previously used
• in general the design of S-P networks is such that the output from function f is influenced by both input and key

  Ri = Li-1 XOR f(Ki XOR Ri-1)
  

• hence cannot trace values back through cipher without knowing the values of the key
• Biham & Shamir's key idea is to compare two separate encryptions (using the same key) and look at the XOR of the S-box inputs and outputs

8. Differential Cryptanalysis Compares Pairs of Encryptions

• key concept is to compare a related pair of encryptions
• with a known difference in the input
• searching for a known difference in output

  Rai = f(Ki XOR Rai-1)
  Rbi = f(Ki XOR Rbi-1)
  	hence
  Yi  = Rai XOR Rbi
      = f(Ki XOR Rai-1 XOR Ki XOR Rbi-1)
      = f(Rai-1 XOR Rbi-1)
      = f(Xi)
  

• this is independent of the key being used
• further know that various input XOR - output XOR pairs occur with different probabilities
• hence knowing information on these pairs gives us additional information on the cipher

9. XOR Profiles and Characteristics

• start by compiling a table of input vs output XOR values for each S-box
• called an XOR Profile
• a particular input XOR value and output XOR value pair occurs with some probability
• call such a specified pair, a characteristic
• if find a pair of encryptions matching a characteristic
• knowing input and output XOR values
• can infer information about key value in one round

  

10. Using Characteristics

• can describe 1-round characteristic on function f by:

  f(x')->y',  with Pr(p)
  

• stepping back and considering the feistel structure as a whole:

  (a',b')->(b',a' XOR f(b')) with Pr(p)
  

• here if we start with known input differences (a',b')
• and can trace and see which S-boxes have an input changed
• then can derive what the difference will be after 1 round

11. Useful Charcteristics

• have several variant forms of differential cryptanalysis
• will discuss just the general form used for attacking many rounds (>8) of a cipher
• useful characteristics for this are
  1. f(0')->0', Pr(1) ie always
(x,0)->(0,x) always
  2. f(x')->0', Pr(p0)
(0,x)->(x,0) with probability p0
• these are for a single round
• but can combine them to attack multiple rounds
• when outputs of one matches inputs of next

12. N-round Charcteristics

• used to attack multiple rounds
• combine one round characteristics whose outputs & inputs match
• probability of n-round characteristic is product of the 1-round characteristic probabilities

  

  2-Round Iterative Characteristic

13. Useful N-round Charcteristics

• some common characteristic structures are:
• a 2-round characteristic:

  A.(x,0)->(0,x) always
  B.(0,x)->(x,0) with probability p
  

• a 3-round characteristic:

  A.(x,0)->(0,x) always
  B.(0,x)->(x,x) with probability p1
  C.(x,x)->(x,0) with probability p2
  

14. Using Differential Cryptanalysis

• perform attack by repeatedly encrypting plaintext pairs with known input XOR until obtain expected output XOR matching n-round characteristic being used
• if all intermediate rounds also match required XOR (which is unknown) then have a right pair, if not then have a wrong pair, relative ratio is S/N for attack
• assume know XOR at intermediate rounds (if right pair) then deduce keys values for the rounds - right pairs suggest same key bits, wrong pairs give random values
• for large numbers of rounds, probability is so low that more pairs are required than exist with 64-bit inputs
• optimisations of this attack can be made, trading memory for search time, and number of rounds used
• in their latest paper, Biham and Shamir show how a 13-round iterated characteristic can be used to break the full 16-round DES

15. Linear Cryptanalysis

• another recently developed method for analysing block ciphers
• like differential cryptanalysis it is a statistical method
• again have a break-even point in number of rounds of the cipher used for which linear cryptanalysis is faster than exhaustive key-space search
• if this number is greater than that specified for the cipher, then it is regarded as broken
• developed by Matsui et al in early 90's

16. Linear Cryptanalysis Approach

• want to find a linear approximation which holds with Prob p!=¹/₂

  P[i1,i2,...,ia](+)C[j1,j2,...,jb]=K[k1,k2,...,kc]
  	where ia,jb,kc are bit locations in P,C,K
  

• can determine one bit of key using maximum likelihood algorithm
• using a large number of trial encryptions
• effectiveness of linear cryptanalysis is given by the difference
  |p - 1/2|

17. Linear Cryptanalysis of DES

• DES can be broken by encrypting 2⁴⁷ known plaintexts

  PL[7,18,24] XOR PR[12,16] XOR CL[15] XOR CR[7,18,24,29] XOR F16(CR,K16)[15] =
    K1[19,23] XOR K3[22] XOR K4[44] XOR K5[22] XOR K7[22] XOR K8[44] XOR K9[22]
    XOR K11[22] XOR K12[44] XOR K13[22] XOR K15[22]
  

• this will recover some of the key bits
• the rest must be searched for exhaustively

18. Other Forms of Structural Attacks

• Related Key Attacks
  • uses relations between keys
  • without necessarily knowing either key value
  • to simplify exhaustive keyspace searches
  • or to attack the use of block ciphers as hash functions
  • developed by Biham
• Impossible Cryptanalysis
  • a variant of Differential Cryptanalysis
  • relies on characteristic pairs which should never occur
  • also developed by Biham (98) and applied to Skipjack

19. Current Status of Block Ciphers

• much research is being done analysing block ciphers
• in part due to the Advanced Encryption Standard process
• one source of information on current results is:
  The Block Cipher Lounge - http://www.ii.uib.no/~larsr/bc.html

  Cipher	Data/Key/Rounds	Attack Pairs/Encrypts/Memory (Rounds)
  DES	64/56/16	Known 43/19/13
  Triple-DES	64/168/48	Known 2/112/56
  IDEA	64/128/8.5	Chosen 64/112/32 (4,5)
  LOKI91	64/64/16	Chosen 58/./. (13)
  LOKI91	64/64/16	Known 60/./. (11)

20. Implementation Attacks

• attack the implementation of the cipher, rather than structure directly

21. Timing Attacks

• uses fact that some operations vary in time taken
• eg. multiplying by small vs large number
• or IF's cause varying numbers of instructions to execute
• knowing operations needed in cipher
• infer size of some operands based on time taken for encryption

22. Power Attacks

• similar to timing, but measure power consumption instead
• very effective against smartcards
• where can instrument the reader

23. Differential Fault Analysis

• an attack on h/w implementations
• in which deliberate single bit faults are induced
• and the resulting outputs observed and compared
• and used to infer information about what values must have been used

24. Current State of Play

• have these new classes of attack
• whilst DES threatened in some applications
• other modern block ciphers (IDEA, Rijndael) cannot be attacked structurally
• though always have possibility of a radical new advance (cf differential cryptanalysis in 1990)
• but implementations are of concern, esp in smartcards
• need to engineer systems to resist such threats
• future developments in quantum computation a real "wild-card"

25. Summary

• have discussed:
• attacks on block ciphers
  • exhaustive search
  • structural attacks (differential and linear cryptanalysis)
  • implementation attacks (timing, power, fault analysis)

26. Exercises

1. Consider exhaustively searching the key space of a variable sized block cipher like RC-5. Assuming to can test 1 key in a microsecond (as I did in the notes), and that you can get 10000 computers on the Internet to cooperate in the search (demonstrated possible), tabulate the time it would take to search for keys of length 56, 64, 72 and 80 bits. What do you conclude about the strength of ciphers with this sort of sized key?