Automne's Shadow.

LFSR in Crypto Conclusion

lfsr z3
2019/05/19 Share

Crypto

LFSR-线性反馈移位寄存器是一种比较简单的PRNG（伪随机数生成器），属于流密码里的概念。LFSR主要用于生成一串随机的比特流，比特流可用做加密明文的密钥流。

参考https://zhuanlan.zhihu.com/p/33920501

看一下LFSR的基本操作。

automne

automne

automne

已知明文攻击

LFSR存在已知明文攻击，可以通过比特流，枚举度数，然后还原随机的抽头序列。

举个例子：

1
假设某lfsr输出的比特流为：101011001101，比特流长度为12，优先考虑12/2=6的度，也就是将比特流6位一组：101011 001101，现在要求解该lfsr接下来12bit的内容。

根据lfsr的特点，该时刻的初始状态为101011，那么001101里的最左边一位0就是初始状态产生的last bit，现在要确定其抽头序列P，取其索引值从左到右依次为P0,P1,…P5。

可以列出下面的方程组，注意异或操作：

101011 001101 0 = P0P2P4^P5

1 010110 01101 0 = P1P3P4

10 101100 1101 1 = P0P2P3

101 011001 101 1 = P1P2P5

1010 110011 01 0 = P0P1P4^P5

10101 100110 1 1 = P0P3P4

使用z3-solver来求解这个方程。

python脚本如下图：

automne

求解得到该抽头序列P为[1,0,0,0,0,1]

automne

使用下面的脚本（python3）就可以每6位一次计算接下来的比特流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#encoding=utf-8

instr = input("Please input last 6 bits: ")
lens = len(instr)
rig = list(int(i) for i in instr)
res = [0]*lens

print("Reading First 6 bits: " + str(rig))

for i in range(6):
	res[i] = (1*rig[0]+1*rig[5])%2
	print(res[i])
	rig2 = rig.pop(0)
	rig = rig + [res[i]]

print("The Next 6 bits is: " + str(res))

运行效果：

automne

使用python的lfsr典型实现代码如下：

1
2
3
4
5
6
7
8
9
def lfsr(R,mask):
    output = (R << 1) & 0xffffff
    i=(R&mask)&0xffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

其中R表示某时刻的初始状态，mask表示抽头序列。

举个例子，使用下面的代码就可以一次性地求出上面的lfsr接下来的12bit数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#encoding=utf-8

def lfsr(R,mask):
    output = (R << 1) & 0xffffff
    i=(R&mask)&0xffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

#R = 0b101011
R = 0b001101 #初始状态
mask = 0b100001 #抽头序列

stream = []

for _ in range(12):
	(R,lastbit) = lfsr(R,mask)
	stream.append(str(lastbit))
	print lastbit

print "".join(stream)

运行后发现和上面的输出内容是一样的

automne

逆向LFSR数据

上面的例子，101011 001101输出的比特流为110110 100100，现在如果知道了抽头序列，那么尝试从110110的输出求解其前6位的比特流（初始状态），这就是逆向lfsr的过程。

python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#encoding=utf-8

def lfsr_inv(R,mask):
	str=bin(R)[2:].zfill(6)
	#print str
	new=str[-1:]+str[:-1]
	#print new
	new=int(new,2)                    #R循环右移一位得到new
	i = (new & mask) & 0xffffffff
	lastbit = 0
	while i != 0:
		lastbit ^= (i & 1)
		i = i >> 1
	return R>>1 | lastbit<<5         #最高位用lastbit填充

mask = 0b100001 #抽头序列
c = 0b110110 #输出比特流

for _ in range(6):
	c = lfsr_inv(c,mask)

print bin(c)[2:].zfill(6)

运行后，就可以得到前一状态的比特流

automne

基于此，看一下2018年的oldstreamgame赛题。

题目源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

f=open("key","w")
for i in range(100):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

从代码里可以看到，将lfsr生成的lastbit每8位一组组成一个byte，然后生成100个byte输出到key文件里，根据上面的逆向函数，可以写出下面的脚本，由抽头序列的32位构造响应的脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#encoding=utf-8

import libnum

def lfsr_inv(R,mask):
	str=bin(R)[2:].zfill(32)
	#print str
	new=str[-1:]+str[:-1]
	#print new
	new=int(new,2)                    #R循环右移一位得到new
	i = (new & mask) & 0xffffffff
	lastbit = 0
	while i != 0:
		lastbit ^= (i & 1)
		i = i >> 1
	return R>>1 | lastbit<<31         #最高位用lastbit填充

mask = 0b10100100000010000000100010010100
#c = 0b00100000111111011110111011111000

data = open('key').read()
data = data[:4] #取4bytes对应32bits
c = libnum.s2n(data)
#print c
print bin(c)[2:].zfill(32)

for _ in range(32):
	c = lfsr_inv(c,mask)

print bin(c)[2:].zfill(32)
print hex(c)

运行可得到初始状态（flag）：

automne

可以看到单个的LFSR是不安全的，但是在实际应用中，一般是多个LFSR之间基于某种非线性运算，从而使得破解变得非常复杂。

原文作者: Automne

原文链接: https://ce-automne.github.io/2019/05/19/LFSR-in-Crypto-Conclusion/

发表日期: May 19th 2019, 5:30:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 已知明文攻击
  2. 2. 逆向LFSR数据
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc