xXxYOLOxXx

xXxYOLOxXx

Crypto-LFSR

Posted on In

Stream Cipher

LFSR

[2018强网杯]Streamgame1

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
from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25

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=int(flag[5:-1],2)
mask    =   0b1010011000100011100

f=open("key","ab")
for i in range(12):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()
1
2
3
4
hexdump -C key 

00000000  55 38 f7 42 c1 0d b2 c7  ed e0 24 3a              |U8.B......$:|
0000000c

加密流程

  1. 序列左移一位
  2. 与反馈系数进行且运算
  3. 运算结果进行异或得到结果
  4. 结果作为序列的结尾

result=cn&an⊕...⊕c2&a2⊕c1&a1result = c_n\&a_n \oplus ... \oplus c_2\&a_2 \oplus c_1\&a_1
反馈系数为 mask = 0b1010011000100011100
即 c19,c17,c14,c13,c9,c5,c4,c3=1c_{19}, c_{17}, c_{14}, c_{13}, c_9, c_5, c_4, c_3 = 1 (从右到左)
那么反馈运算为
result=a19⊕a17⊕a14⊕a13⊕a9⊕a5⊕a4⊕a3result = a_{19} \oplus a_{17} \oplus a_{14} \oplus a_{13} \oplus a_9 \oplus a_5 \oplus a_4 \oplus a_3

而且我们已知a1-a18以及产生的result
那么就可以根据这些条件来得出a19
a19=result⊕a17⊕a14⊕a13⊕a9⊕a5⊕a4⊕a3a_{19} = result \oplus a_{17} \oplus a_{14} \oplus a_{13} \oplus a_9 \oplus a_5 \oplus a_4 \oplus a_3
以此类推，来恢复flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
f = open("key", "rb")
bytes = f.read(3)
f.close()
key = ""
for i in bytes:
	if len(bin(i)[2:]) != 8:
		key += (8 - len(bin(i)[2:])) * "0" + bin(i)[2:]
	else:
		key += bin(i)[2:]
key = key[:19]
print(key)
flag = ""
for i in range(19):
	res = key[-1]
	key = key[:18]
	awns = chr(int(res) ^ int(key[-3]) ^ int(key[-4]) ^ int(key[-5]) ^ int(key[-9]) ^ int(key[-13]) ^ int(key[-14]) ^ int(key[-17]) + 48)
	key = awns + key
print("flag{" + key + "}")

[2018强网杯]Streamgame2

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
from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==27

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=int(flag[5:-1],2)
mask=0x100002

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

跟上一题一个思路，而且更简单（移位寄存器更少）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python3
#coding:utf-8

f = open("key", "rb")
bytes = f.read(3)
f.close()
key = ""
for i in bytes:
	if len(bin(i)[2:]) != 8:
		key += (8 - len(bin(i)[2:])) * "0" + bin(i)[2:]
	else:
		key += bin(i)[2:]
key = key[:21]
flag = ""
for i in range(21):
	res = key[-1]
	key = key[:20]
	awns = chr(int(res) ^ int(key[-2]) + 48)
	key = awns + key
print("flag{" + key + "}")

[CISCN2018]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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3
#coding:utf-8

f = open("key", "rb")
bytes = f.read(4)
f.close()
key = ""
for i in bytes:
	if len(bin(i)[2:]) != 8:
		key += (8 - len(bin(i)[2:])) * "0" + bin(i)[2:]
	else:
		key += bin(i)[2:]
print(key)
for i in range(32):
	res = key[-1]
	key = key[:31]
	awns = chr(int(res) ^ int(key[-30]) ^ int(key[-27]) ^ int(key[-20]) ^ int(key[-12]) ^ int(key[-8]) ^ int(key[-5]) ^ int(key[-3]) + 48)
	key = awns + key
print("flag{" + hex(int(key,2)) + "}")

TBC