ghost423543

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")
  125. datain=fin.read()
  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))
  131. ## Password is LSFRNGAG
  132. fout.write(dataout.encode("Latin-1"))
  133. fout.close()
  134. fin.close()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×