Cryptography - Lecture 11 - Block Cipher Cryptanalysis

Objectives

Preliminary Reading

Lecture Content

Cryptanalysis of Block Ciphers

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

     Comment here that its pretty obvious you can just try every key, but it is necessary to be able to recognise when you've cracked the message, either by knowing explicitly the message you want, or being able to recognise it (ie English text for example). Some forms of data (graphics, machine code) can be much much harder to recognise.

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

Differential Cryptanalysis

1. 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
2. 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
3. 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

     Called Differential Cryptanalysis because the analysis compares differences between two related, encryptions - and looking for known difference in leading to a known difference out.

4. 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

     

     XOR profile shows the statistical characteristics of a single S-box, what is likely to happen if you feed a known difference into it. *** show XOR profile of DES S-box 1 ***

5. 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

     Start with the difference we want to use into an S-box, then have to account for the affect of the Permutation of how the ouput(s) are permuted to inputs in the next round. With DES, the best we can do is to use a difference affecting 3 bits & 2 S-boxes.

6. 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

     These are the nicest characteristics to use - the obvious one of no difference in MUST give no difference out (or the universe has suddenly gotton very strange), and one where a difference in leads to no difference out. Then arrange for the data input difference to match this (with the affect of permutation P taken into account).

7. 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

     Note assumption of independence here in the way the probabilities are combined - not actually true, but it works well enough in practise to use it.

8. 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
     

9. 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

     Can follow with Biham & Shamir TR Dec 91, Fig 1 p5, Table 2 p9.

Linear Cryptanalysis

1. 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

     Again, this attack uses structure not seen before. This time, it works on single encryptions, collecting stats over many encryptions.

2. 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|

     Whilst the S-boxes were designed to be non-linear, it turns out that some of the inputs/outputs can be approximated by linear functions with varying success. Use this to attack the cipher.

3. 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

Other Forms of Structural Attacks

1. 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
2. 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)

Implementation Attacks

1. Implementation Attacks
   • attack the implementation of the cipher, rather than structure directly

     These attacks are applicable to virtually all ciphers, since just about all of them have operations that potential take a varying amount of time/ power to compute, depending on the values being used.

2. 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

     Idea is to monitor the time taken to perform encryptions, and hence infer something about the number of instructions executed, or possibly the values used in time dependent instructions

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

     As part of the AES evaluation, this attack was implemented against a 6502 smartcard version of Twofish, needing 50-100 encryptions to be monitored to recover the 128-bit key (plaintext is not needed, it works by monitoring just the start of the encryption process where keying info is used). The authors believe most of the candidates would be vulnerable.

4. 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

     Another Biham/Shamir attack - it uses deliberately induced errors, typically due to ionising radiation, to introduce single bit errors in the code or subkeys during an encryption computation. When the erroneous output is compared to the correct output, information can be derived about the key. The attack its believed, can be applied to many types of ciphers (incl public key).

Summary

1. 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"
2. Summary
   • have discussed:
   • attacks on block ciphers
     • exhaustive search
     • structural attacks (differential and linear cryptanalysis)
     • implementation attacks (timing, power, fault analysis)

Exercises

1. 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?

Additional References