# Cracking_LFSR_with_know_plain_text_attack

Apr 23rd, 2021 (edited)
989
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ## https://www.root-me.org/en/Challenges/Cryptanalysis/LFSR-Known-plaintext?action_solution=voir#ancre_solution
2. import os
3. from collections import deque
4. import numpy as np
5. import copy
6.
7. DIR = os.path.dirname(os.path.realpath(__file__))
8. key1=[]
9. def berlekamp_massey(data):
10.     """
11.   Implementation of berlekamp-massey algorithm that finds the minimal LFSR and minimal polynomial to generate given
12.   data
13.   :param data: list of 1s and 0s
14.   :type data: list[int]
15.   :return:
16.   """
17.     n = len(data)
18.     c_x, b_x = np.zeros(n, dtype=np.int), np.zeros(n, dtype=np.int)
19.     c_x[0], b_x[0] = 1, 1
20.     l, m, i = 0, -1, 0
21.     while i < n:
22.         v = data[(i - l):i]
23.         v = v[::-1]
24.         cc = c_x[1:l + 1]
25.         delta = (data[i] + np.dot(v, cc)) % 2
26.         if delta == 1:
27.             temp = copy.copy(c_x)
28.             p = np.zeros(n, dtype=np.int)
29.             for j in range(0, l):
30.                 if b_x[j] == 1:
31.                     p[j + i - m] = 1
32.             c_x = (c_x + p) % 2
33.             if l <= 0.5 * i:
34.                 l = i + 1 - l
35.                 m = i
36.                 b_x = temp
37.         i += 1
38.     c_x = c_x.tolist()
39.     ind = 0
40.     for x in c_x[::-1]:
41.         if x == 0:
42.             ind += 1
43.         else:
44.             break
45.     c_x = c_x[:-ind]
46.     return len(c_x)-1, c_x
47.
48. def generate_key(polynomial, init_state=None):
49.     """
50.   Create key using given polynomial and determine whether the polynomial by counting number of states generated
51.   :param polynomial: Binary string representing the connection polynomial
52.   :type polynomial: str
53.   :param init_state: binary string representing initial state of the key generation
54.   :type init_state: str
55.   :raises ValueError if init_state doesn't match polynomial degree or any of the strings are not binary
56.   :return:
57.   """
58.     degree = len(polynomial) - 1
59.
60.     ini = init_state if init_state is not None else '0' * (degree - 1) + '1'
61.     ini = [int(x) for x in ini]
62.     if len(ini) != degree:
63.         raise ValueError("Degrees don't match")
64.
65.     xor_indices = []
66.     for i, n in enumerate(polynomial[1:]):
67.         if n == '1':
68.             xor_indices.append(i)
69.
70.     key = []
71.     ini_deque = deque(ini)
72.     cur_state = deque(ini)
73.     while True:
74.         el = sum(cur_state[x] for x in xor_indices) % 2  # xor the elements in the indices determined by the polynomial
75.
76.         key.append(cur_state.pop())
77.         cur_state.appendleft(el)
78.         if ini_deque == cur_state:  # full cycle completed
79.             break
80.     return key
81.
82. def break_partially_known(cipher, ends_with):
83.     """
84.   Extract plain text, connection polynomial and initial state from partially known cipher text
85.   :param cipher: integer array of 1s and 0s representing message
86.   :type cipher: list[int]
87.   :param ends_with: string that is known to be end of message
88.   :type ends_with: str
89.   :return:
90.   """
91.     binary_str = ''.join(format(ord(x), 'b').zfill(8) for x in ends_with)
92.     len_of_known = len(binary_str)
93.     partial_cipher = cipher[-len_of_known:]
94.     partial_key = [(partial_cipher[i] + int(binary_str[i])) % 2 for i in range(len(partial_cipher))]
95.     print (partial_key)
96.     l, c_x = berlekamp_massey(partial_key)
97.     key = deque(generate_key(''.join(str(x) for x in c_x), ''.join(str(x) for x in partial_key[l-1::-1])))
98.
99.     key.rotate(-len_of_known)
100.     key1=list(key)
101.     key = list(key)[-len(cipher):]
102.
103.     extracted_plain_binary = ''.join([str((cipher[i] + key[i]) % 2) for i in range(len(cipher))])
104.     print (extracted_plain_binary)
105.     return key1,''.join(str(x) for x in c_x), key,''.join(chr(int(extracted_plain_binary[i:i+8], 2)) for i in range(0, len(extracted_plain_binary), 8))
106.
107. def show_image(input__):
108.     try :
109.         image = Image.open(io.BytesIO(input__))
110.         image.show()
111.         return 1
112.     except :
113.         return 0
114.
115. cipher=[0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,
116.         0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1,1,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,0,0,0,1,1,1,0,1,0,0,0,0,1,0,1,0,0]
117.
118. ends_with = 'IHDR'
119. key1,con_pol, key, plain_text = break_partially_known(cipher, ends_with)
120.
121. pos=len(key1)-len(cipher)
122. lenkey=len(key1)
123. print("start pos:=",pos)
124. fin=open(f"{DIR}/challenge.png.encrypt","rb")
126. print(len(datain))
127. # fout=open("challenge.png","wb")
128. inbinary_str = ''.join(format(datain[x], 'b').zfill(8) for x in range(len(datain)))
129. plain_binary = ''.join([str((int(inbinary_str[i]) + key1[(i+pos)%lenkey]) % 2) for i in range(len(inbinary_str))])
130. dataout=''.join(chr(int(plain_binary[i:i+8], 2)) for i in range(0, len(plain_binary), 8))
132. fout.write(dataout.encode("Latin-1"))
133. fout.close()
134. fin.close()
RAW Paste Data