投稿文章：LFSR已知明文攻击
LFSR已知明文攻击
1.流密码
我们知道，OTP(一次一密)是无条件安全的，但是它的缺点使得它不具有实际意义，在实际中流密码使用的密钥都是通过具有某些属性的密钥流生成器产生的。由于密钥流生成器产生的都是伪随机序列，这也就是说序列存在着一定的循环周期，周期的长短是保密性的关键。
实际上的序列密码基本原理如图所示：
从图中可以出密钥流的产生与明文消息流相互独立，即密钥序列产生算法与明文无关。所产生的密钥序列也与明文无关。因此在通信过程中，通信的双方必须保持同步，接收方才可以正确机密。如果传输过程中丢失或增加了一比特信息，则该比特后的数据将全部解密失败。 一种得到长伪随机数的方法就是使用线性反馈移位寄存器。有很多流密码是通过FLSR来实现的，例如GSM中的语音加密标准(A5/1密码)。 2.基于移位寄存器的流密码 构建流密码的方式有很多，本文主要介绍使用线性反馈移位寄存器(LFSR)构建流密码。LFSR产生的序列具有良好的数学统计属性，但是该序列在密码学中却是非常脆弱的，无法抵御已知明文攻击。然而，LFSR组合(Trivium密码)却可以得到安全的序列密码，本文主要介绍LFSR加密原理，加密过程，以及LFSR的已知明文攻击。 简单LFSR 下面我们考虑一个度m=3、拥有3个触发器FF2、FF1和FF0，且反馈路径如图所示：
在每个时钟周期内，内部状态位会向右移动一位。最右边的状态位是当前的输出位。最左边的状态位则是在反馈路径中计算出来的，它是上一时钟周期内某些触发器值的异或结果。我们不妨假设初始状态(s2=1，s1=0，s0=0)，下面列出LFSR的完整状态序列。
所以该LFSR产生的前八位密钥流为 00101110 假设此时明文为字母'n' 使用ASCII编码01101110 对密钥流和明文进行异或：01000000 则发送的密文为：01000000 接收方收到数据后，依旧使用该LFSR产生前八位密钥流00101110 对密钥流和密文进行异或：01101110，使用ASCII解码'n' 不妨使用公式归纳输出位的计算公式：
需要注意的几点是： 度为m的LFSR可以产生的最大序列长度为2^m - 1 如果某个LFSR的状态是全0，它将会永远陷在这个状态中 最大序列长度LFSR拥有本原多项式 LFSR序列属性的数学背景已经超出了本文的讨论范畴 如图所示，这是一个度为16的触发器，有4个反馈位置，并且这些触发器和反馈位置之间通过XOR操作连接。
可以从该动图中看到LFSR生成密钥流的详细过程。 3.针对单个LFSR的已知明文攻击 顾名思义，LFSR是线性的。线性系统是由其输入和输出之间的线性关系来决定的。由于线性依赖易于分析，使得LFSR在诸如通信系统的应用中具有很大优势。但是，如果一个密码体制中的密钥位只呈现线性关系，那么该密钥将会相当不安全。 如果攻击者知道某些明文和密文，他就可能发起攻击，进一步假设攻击者知道LFSR的度m，则攻击将非常高效。但如果攻击者不知道度m，则他可以尝试更多的m值。 假设攻击者已知明文为x0,x1,x2....x2m-1,且对应的密文为y0,y1,y2.....y2m-1,则攻击者可以重构开头的2m个密钥序列位: si = xi +yi mod 2;(将明文和密文按位异或) 则此时密钥序列为：s1,...,s2m,我们可以令： S1 = (a1,...,am) S2 = (a2,...,am+1) .... Sm+1 = (am+1,...,a2m) 那么我们可以构造矩阵： X = (S1,....,Sm) Sn+1 = (cn,...,c1)X 所以 (cn,...,c1) = Sn+1X-1 因此我们可以通过求解该线性系统来精确的构建系数Pi 假设已知密钥流101001100010，且度为6 因此我们可以列出以下等式： 1 = P5 + P2 + P0 0 = P5 + P4 + P1 0 = P4 + P3 + P0 0 = P3 + P2 1 = P2 + P1 0 = P5 + P1 + P0 通过求解该系统，即可精确的构造系数。 4.Z3求解器 像上一小节中需要求解的等式，如果手算的话，怕不是会吐血而亡。 因此我们这里引入新的工具，Z3是微软公司开发的一个优秀的SMT求解器。 简单举例：
from z3 import *
x = Int('x')
y = Int('y')
solve(x > 10, y < 100, y - 4*x == 50)(Z3 在默认情况下，只寻找满足所有条件的一组解) 此处仅列出部分用法：
创建约束求解器
solver = Solver()
添加约束条件（这一步是z3求解的关键）
solver.add(byte_610a0[v10]==i^v4)
判断解是否存在
if solver.check()==sat:
求解
print solver.model()举个栗子,题目如下：
import sys
print ("Please enter a valid serial number from your RoboCorpIntergalactic purchase")
if len(sys.argv) < 2:
print ("Usage: %s [serial number]"%sys.argv[0])
exit()
print ("#>" + sys.argv[1] + "<#")
def check_serial(serial):
if (not set(serial).issubset(set(map(str,range(10))))):
print ("only numbers allowed")
return False
if len(serial) != 20:
return False
if int(serial[15]) + int(serial[4]) != 10:
return False
if int(serial[1]) * int(serial[18]) != 2:
return False
if int(serial[15]) / int(serial[9]) != 1:
return False
if int(serial[17]) - int(serial[0]) != 4:
return False
if int(serial[5]) - int(serial[17]) != -1:
return False
if int(serial[15]) - int(serial[1]) != 5:
return False
if int(serial[1]) * int(serial[10]) != 18:
return False
if int(serial[8]) + int(serial[13]) != 14:
return False
if int(serial[18]) * int(serial[8]) != 5:
return False
if int(serial[4]) * int(serial[11]) != 0:
return False
if int(serial[8]) + int(serial[9]) != 12:
return False
if int(serial[12]) - int(serial[19]) != 1:
return False
if int(serial[9]) % int(serial[17]) != 7:
return False
if int(serial[14]) * int(serial[16]) != 40:
return False
if int(serial[7]) - int(serial[4]) != 1:
return False
if int(serial[6]) + int(serial[0]) != 6:
return False
if int(serial[2]) - int(serial[16]) != 0:
return False
if int(serial[4]) - int(serial[6]) != 1:
return False
if int(serial[0]) % int(serial[5]) != 4:
return False
if int(serial[5]) * int(serial[11]) != 0:
return False
if int(serial[10]) % int(serial[15]) != 2:
return False
if int(serial[11]) / int(serial[3]) != 0:
return False
if int(serial[14]) - int(serial[13]) != -4:
return False
if int(serial[18]) + int(serial[19]) != 3:
return False
return True
if check_serial(sys.argv[1]):
print ("Thank you! Your product has been verified!")
else:
print ("I'm sorry that is incorrect. Please use a valid RoboCorpIntergalactic serial number")使用Z3求解
from z3 import *
s = [Int('serial%d' % i) for i in range(20)]
solver = Solver()
solver.add(s[15] + s[4] == 10)
solver.add(s[1] * s[18] == 2 )
solver.add(s[15] / s[9] == 1)
solver.add(s[17] - s[0] == 4)
solver.add(s[5] - s[17] == -1)
solver.add(s[15] - s[1] == 5)
solver.add(s[1] * s[10] == 18)
solver.add(s[8] + s[13] == 14)
solver.add(s[18] * s[8] == 5)
solver.add(s[4] * s[11] == 0)
solver.add(s[8] + s[9] == 12)
solver.add(s[12] - s[19] == 1)
solver.add(s[9] % s[17] == 7)
solver.add(s[14] * s[16] == 40)
solver.add(s[7] - s[4] == 1)
solver.add(s[6] + s[0] == 6)
solver.add(s[2] - s[16] == 0)
solver.add(s[4] - s[6] == 1)
solver.add(s[0] % s[5] == 4)
solver.add(s[5] * s[11] == 0)
solver.add(s[10] % s[15] == 2)
solver.add(s[11] / s[3] == 0)
solver.add(s[14] - s[13] == -4)
solver.add(s[18] + s[19] == 3)
flag = []
if solver.check()==sat:
m = solver.model()
for i in s:
flag.append(str(m<i>))
print "".join(flag)
print 'ok'5.LFSR已知明文攻击举例 我们得到了一张图片，但是根据扩展名可以发现图片经过了加密，使用二进制查看。
根据图片的名字提示，我们可以知道这个图片是png图片，查找png图片的文件头：
在一个正常的png图片中，前12字节一定是固定的: 89504E470D0A1A0A0000000D 接着，我们取出加密后的png图片前12字节: 43AE212C403363C000E4FD68 对明文和密文进行按位异或，得到LFSR输出的密钥流 脚本如下：
# Name:bintools.py
# Date:2018-07-24
# Time:08:17 GMT
# Author:nianhua
#
hexadecimalcontrast = {
'0':'0000',
'1':'0001',
'2':'0010',
'3':'0011',
'4':'0100',
'5':'0101',
'6':'0110',
'7':'0111',
'8':'1000',
'9':'1001',
'a':'1010',
'b':'1011',
'c':'1100',
'd':'1101',
'e':'1110',
'f':'1111',
}
def Binxor(string1,string2):
"If the length is different, only the short one is returned."
strlen = 0
xorstr = ""
if len(string1) > len(string2):
strlen = len(string2)
else:
strlen = len(string1)
for i in range(strlen):
if string1<i> == string2<i>:
xorstr += '0'
else:
xorstr += '1'
return xorstr
def BinToStr(strbin):
"Turn the binary string to a ASCII string"
strten = ""
for i in range(len(strbin)//8):
num = 0
test = strbin[i*8:i*8+8]
for j in range(8):
num += int(test[j])*(2**(7-j))
strten += chr(num)
return strten
def Textxor(string,num):
"A different or a string and number"
xorstr = ""
if int == type(num):
for i in string:
xorstr += chr(ord(i) ^ num)
return xorstr
else:
return -1
def HexToBin(string):
"Convert sixteen to binary"
Binstring = ""
string = string.lower()
for i in string:
try:
Binstring += hexadecimalcontrast<i>
except:
return -1
return Binstring
def StrToHex(string):
"Converts a string to HEX"
hexStr = ''
for i in string:
tmp = str(hex(ord(i)))
if len(tmp) == 3:
hexStr += tmp.replace('0x','0')
else:
hexStr += tmp.replace('0x','')
return hexStr
def NumToBin(number):
tmp = str(hex(number))
hexStr = ''
tmp = tmp.replace('0x','')
hexStr = '0'*(2-len(tmp)) + tmp
hexStr = HexToBin(hexStr)
hexStr = hexStr[2:]
return hexStr
if "__main__" == __name__:
print(Binxor(HexToBin('89504E470D0A1A0A0000000D'),HexToBin('43AE212C403363C000E4FD68')))我们的到了LFSR输出的密钥流： 110010101111111001101111011010110100110100111001011110011100101000000000111001001111110101100101 但是我们现在并不知道度m为多少，因此我们需要从2开始爆破，一直到已知密钥流长度的1/2位。 脚本如下：
###
### Date:2018-09-11
### Time:08:17 GMT
### Author:nianhua
### Sorry, this progame is python 2.7
###
from z3 import *
outBin = '110010101111111001101111011010110100110100111001011110011100101000000000111001001111110101100101'
def numcc(keytLen):
p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22,p23,p24,p25,p26,p27,p28,p29,p30 = BitVecs('p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p23 p24 p25 p26 p27 p28 p29 p30',1)
s = Solver()
for i in range(keytLen):
ceshi = outBin[i:keytLen+i+1]
print ceshi
ming = ''
for i in range(keytLen):
if ceshi<i> == '1':
ming += 'p' + str(i) + '+'
else:
pass
ming = ming[0:-1] + '==' + str(ceshi[-1])
#print ming
s.add(eval(ming))
s.add()
print s
if s.check() == sat:
print s.model()
#print s.check()
for i in range(2,30):
numcc(i)
#pass
#numcc(6)结果：
[p7 = 1,
p24 = 1,
p28 = 0,
p3 = 0,
p13 = 0,
p19 = 0,
p12 = 0,
p27 = 0,
p2 = 0,
p8 = 1,
p5 = 1,
p0 = 0,
p21 = 0,
p10 = 1,
p14 = 0,
p1 = 1,
p25 = 0,
p17 = 0,
p6 = 1,
p16 = 0,
p26 = 0,
p18 = 0,
p20 = 0,
p22 = 0,
p4 = 0,
p9 = 1,
p11 = 1,
p15 = 0,
p23 = 0]我们一共得到了29组序列，不妨首先使用最后一组(因为前面的我都试过了 不对哈哈哈哈哈啊 )即度为29的序列。 序列如下：01000111111100000000000010000 接下来对图片进行解密： 修改一下刚刚的脚本，直接对图片进行解密
from bintools import *
class LFSR:
def __init__(self,keyt,feedpath):
self.trigger = []
self.feedback = []
self.degree = len(keyt)
self.feed = len(feedpath)
if len(feedpath) != self.degree:
return None
for i in keyt:
self.trigger.append(i)
for i in feedpath:
self.feedback.append(i)
def binxor(self,bin1,bin2):
if bin1 == bin2:
return '0'
else:
return '1'
def getfeed(self):
self.realdback = []
for i in range(self.feed):
if self.feedback<i> == '1':
self.realdback.append(self.trigger<i>)
for i in range(1,len(self.realdback)):
self.realdback[0] = self.binxor(self.realdback[0],self.realdback<i>)
return self.realdback[0]
def tick(self):
outpin = self.trigger[-1]
feedpin = self.getfeed()
for i in range(self.degree-1,0,-1):
self.trigger<i> = self.trigger[i-1]
self.trigger[0] = feedpin
return outpin
def getenbin(thisobj):
tenbin = ''
for i in range(8):
tenbin += thisobj.tick()
print('\t%s'%tenbin,end='')
return ord(BinToStr(tenbin))
if '__main__' == __name__:
newobj = LFSR('10110111101100111111101010011','00001000000000000111111100010')
fr = open('challenge.png.encrypt','rb+')
string = fr.read()
fr.close()
newstring = ''
for i in range(len(string)):
newstring += chr(string<i>^getenbin(newobj))
fw = open('out.png','wb+')
fw.write(newstring.encode(encoding="latin1"))
fw.close()
print ("\nOk......")查看图片
6.后记 其实除了使用这种方法，也可以使用BM算法，脚本如下:
def berlekamp_massey(data):
"""
Implementation of berlekamp-massey algorithm that finds the minimal LFSR and minimal polynomial to generate given
data
:param data: list of 1s and 0s
:type data: list[int]
:return:
"""
n = len(data)
c_x, b_x = np.zeros(n, dtype=np.int), np.zeros(n, dtype=np.int)
c_x[0], b_x[0] = 1, 1
l, m, i = 0, -1, 0
while i < n:
v = data[(i - l):i]
v = v[::-1]
cc = c_x[1:l + 1]
delta = (data<i> + np.dot(v, cc)) % 2
if delta == 1:
temp = copy.copy(c_x)
p = np.zeros(n, dtype=np.int)
for j in range(0, l):
if b_x[j] == 1:
p[j + i - m] = 1
c_x = (c_x + p) % 2
if l <= 0.5 * i:
l = i + 1 - l
m = i
b_x = temp
i += 1
c_x = c_x.tolist()
ind = 0
for x in c_x[::-1]:
if x == 0:
ind += 1
else:
break
c_x = c_x[:-ind]
return len(c_x)-1, c_x请大佬指正！！！！！
关于作者
评论0次