CoCalc Public Fileslinearcryptanalysis.sageOpen with one click!
Author: Marc Stevens
Compute Environment: Ubuntu 18.04 (Deprecated)
1
# load plaintext-ciphertext pair list
2
#ptctlist=load('ptctlist.txt')
3
f=open('ptctlist.txt','r')
4
ptctlist=eval(f.readline())
5
6
# function that sums the bits in state L selected by the 1-bits in list M
7
def 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
13
def 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
16
ptmask=[0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0]
17
r4mask=[0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1]
18
19
# function to test the above linear relation for given plaintext,ciphertext pair and guess for K5
20
def 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|
23
def 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
26
def 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
29
result=[[test(int2K5sub(i),ptmask,r4mask),i] for i in range(256)]
30
31
# sort result on bias
32
result.sort()
33
34
# take the k5guess with highest bias (result[-1] returns the last element)
35
k5guess=int2K5sub(result[-1][1])
36
37
# another linear approximation attack: this assumes 8 bits of K5 are known: [**** 1100 **** 1000]
38
def int2K5sub2(i): return word2bits(i//16)+[1,1,0,0]+word2bits(i%16)+[1,0,0,0]
39
result2=[[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)]
40
result2.sort()
41
k5guess2=int2K5sub2(result2[-1][1])
42
43
# and another linear approximation attack
44
def int2K5sub3(i): return word2bits(i%16)+[1,1,0,0]+word2bits(0)+[1,0,0,0]
45
result3=[[test(int2K5sub3(i)),i] for i in range(16)]
46
result3.sort()
47
k5guess3=int2K5sub3(result3[-1][1])
48