CoCalc Public Fileslinearcryptanalysis.sage
Author: Marc Stevens
Compute Environment: Ubuntu 18.04 (Deprecated)
1# load plaintext-ciphertext pair list
3f=open('ptctlist.txt','r')
5
6# function that sums the bits in state L selected by the 1-bits in list M
7def sumstate(L,M): return sum([(L[i]&M[i]) for i in range(16)],0)
8# function to test linear relation given plaintext PT, ciphertext CT, guess for roundkey K5
9#    and the linear relation specified by PTM (over the bits of PT) and R4M (over the bits of the input of round 4)
10#    Using K5 it decrypts the final round key-mixing and the last substitutions of CT to obtain the input of round 4
11#    (we can ignore K4 here as showed in class: it only affects the sign of the bias)
12#    it returns the sum of the selected bits PTM of PT and of the selected bits R4M of the round 4 input
13def testlinrel(PT,CT,K5,PTM,R4M): return ((sumstate(PTM,PT)+sumstate(R4M,substbitsinv(xor(CT,K5)))+1)%2)
14
15# the plaintext mask and round 4 input mask for the linear relation covered in class
18
19# function to test the above linear relation for given plaintext,ciphertext pair and guess for K5
20def testsub(PTCT,K5,PTM,R4M): return testlinrel(int2state(PTCT[0]), int2state(PTCT[1]), K5, PTM, R4M)
21
22# function to test guess for K5 over entire plaintext-ciphertext pair list and return |bias|=|#(testsub=1) - 4096|
23def test(K5,PTM,R4M): return abs(sum([testsub(ptctlist[i],K5,PTM,R4M) for i in range(len(ptctlist))],0)-(len(ptctlist)//2))
24
25# function that maps an 8-bit integer to a guess for K5 over bits 5,6,7,8 and 13,14,15,16
26def int2K5sub(i): return word2bits(0)+word2bits(i//16)+word2bits(0)+word2bits(i%16)
27
28# try all possible guesses for K5: result is list of [bias,k5guess]-pairs
30
31# sort result on bias
32result.sort()
33
34# take the k5guess with highest bias (result[-1] returns the last element)
35k5guess=int2K5sub(result[-1][1])
36
37# another linear approximation attack: this assumes 8 bits of K5 are known: [**** 1100 **** 1000]
38def int2K5sub2(i): return word2bits(i//16)+[1,1,0,0]+word2bits(i%16)+[1,0,0,0]
39result2=[[test(int2K5sub2(i),[0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0]),i] for i in range(256)]
40result2.sort()
41k5guess2=int2K5sub2(result2[-1][1])
42
43# and another linear approximation attack
44def int2K5sub3(i): return word2bits(i%16)+[1,1,0,0]+word2bits(0)+[1,0,0,0]
45result3=[[test(int2K5sub3(i)),i] for i in range(16)]
46result3.sort()
47k5guess3=int2K5sub3(result3[-1][1])
48