LFSR_Calculation

Posted on Edited on In Word count in article: 3.4k Reading time ≈ 3 mins.

0x01 An extend of my previous blog

上个博客研究了矩阵对递归的实现，本就应该想到与lfsr的联系的，但直到最近做题才想到。参考学习群大佬的博客Canzik's Blog || 关于LFSR的原理以及攻击方式，用矩阵实现了lfsr。

baby lfsr

初始状态s0=0,s1=0,s2=1,变换公式为 则初始向量

变换矩阵 变换公式：

顺便：大佬博客好像有问题，生成的序列不一样？奇怪

0x02 Attack lfsr

以d3ctf的d3bug为例：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from Crypto.Util.number import *
from secret import flag
assert flag.startswith("D3CTF{")
assert flag.endswith("}")
message = bytes_to_long(flag[6:-1])
assert message < 2**64
mask = 0b1010010000001000000010001001010010100100000010000000100010010100

def lfsr_MyCode(R,mask):
    output = (R << 1) & 0xffffffffffffffff #64
    i = (R ^ mask) & 0xffffffffffffffff
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i>>1
    output ^= lastbit
    return (output,lastbit) #lastbit

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

f=open("standardResult","w")
R=message
for i in range(35):
    (R, out) = lfsr_CopiedfromInternet(R,mask)
    f.write(str(out))
f.close()

f=open("myResult","w")
R=message
for i in range(35):
    (R, out) = lfsr_MyCode(R,mask)
    f.write(str(out))
f.close()

#Why are the results always different?!!
#Can you help me debug my code? QAQ

#myresult: 00100110001000110001101010101001001 
#standard: 01111101111010111000010010111001101

说实话这题贼签到，观察到在lfsr_MyCode部分得到的每一位output相当于是前面所有位的异或和。每次移位时最高位会消失，直接把这两次得到的output随意简单异或一下就可以得到这一次消失的高位。

而剩下的低位通过lfsr_CopiedfromInternet的结果可以得到一个模二加方程组（就是异或），解一下方程就可以了

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from Crypto.Util.number import *
my   = [0,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1]
std  = [0,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,0,0,1,1,0,1]
mask = [1,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0]
highbits = []

def calculate_parameter(a, prm, n):
	for i in range(n):
		p = i
		for j in range(i+1, n):
			if a[j][i] > a[p][i]:
				p = j
		for j in range(n+1):
			tmp = a[i][j]
			a[i][j] = a[p][j]
			a[p][j] = tmp
		for j in range(n):
			if not i == j:
				tt = a[j][i] * pow(a[i][i], prm-2, prm)
				for k in range(i, n+1):
					a[j][k] = (a[j][k] - a[i][k] * tt % prm + prm) % prm
	res = []
	for i in range(n):
		res.append(a[i][n] * pow(a[i][i], prm-2, prm) % prm)
	return res

for i in range(1, 34):
	my[i] ^= my[i-1]

for i in range(1, 34):
	highbits.append(my[i]^my[i-1])

basepos = 0

bb = []
for i in range(31):
	res = std[i]
	aa = []
	for j in range(33-basepos):
		if mask[j] == 1:
			res ^= highbits[j+basepos]
	k = 33-basepos
	for j in range(31):
		aa.append(mask[k])
		k += 1
	cnt = 0
	while k < 64:
		if mask[k] == 1:
			res ^= std[cnt]
		cnt += 1
		k += 1
	aa.append(res)
	bb.append(aa)
	basepos += 1

lowbits = calculate_parameter(bb, 2, 31)
flag = 0
for i in range(33):
	flag = (flag << 1) ^ highbits[i]
for i in range(31):
	flag = (flag << 1) ^ lowbits[i]
print(long_to_bytes(flag))
# flag: D3CTF{LF5Rsuk!}

0x03 补充

异或在数学上被称为GF有限域上的加法，对矩阵指定类型，sage自动将该矩阵之后的运算限制为我们规定的域下的运算（指定运算方式）

模运算和多项式也是可以的

说白了就是解一个方程。

0x04 z3 solution

看其他人博客的时候发现，还可用z3solver来解。代码太复杂了，思路是：每参与一次运算，有效位在R中都会向右移动一位（R在向左移，有效位在mask中不变，所以对应着R中的有效位在向右移动）

例如第一次调用函数中：

1

第二次调用中：

以此类推

需要注意的就是，message即R总长64位，当大于64位以后，需要的就是我们补上的lastbit