反馈移位寄存器

admin
admin
admin
118591
文章
95
评论
2024年8月18日01:28:24评论5 views字数 6065阅读20分13秒阅读模式

前言

这篇博客其实在xman培训的时候就应该出的，但当时还有一些没学通，所以拖到现在

简介

这个其实是硬件实现的一个过程，但是被人搬去了密码学上使用，于是就有了这个知识点啦
这其实是一种流密码，整个过程可以简单的理解成一串数据放去进行一系列随机化操作以后获得加密后的数据，这中间的操作，也就是反馈函数如果是线性的，那就是线性反馈移位寄存器，如果是非线性的，那就是非线性反馈移位寄存器，emmm，这么说很难理解，放几个例题就能懂了

线性反馈移位寄存器LFSR

2018 ciscn oldstream

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  #R左移一位然后保留低32位，记录该值到output
    i=(R&mask)&0xffffffff  #将R和mask进行与运算，保留低32位并赋值给i
    lastbit=0
    while i!=0:
        lastbit^=(i&1)  #将lastbin和i的每一位异或，然后赋值给lastbin
        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()

这是国赛的一道题，也是一道比较简单的LSRF的题目，先读代码，简单的可以理解成：将mask的二进制为1的地方跟flag对应起来，然后记录到I上，然后将1的个数记录到output上，一直循环进行运算，再简单一点的理解就是循环将高位的值异或到低位上，信息并没有丢失，所以我们要解密逆推回去就行了

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
 
import libnum
from Crypto.Util.number import bytes_to_long
# coding=utf-8

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)

def lfsr_inv(R, mask):
    str = bin(R)[2:].zfill(32)
    new = str[-1:] + str[:-1]  #最后一个 + 前面31个
    new = int(new, 2)
    i = (new & mask) & 0xffffffff
    lastbin = 0
    while i!=0:
        lastbin ^= (i & 1)
        i = i >> 1
    return R>>1 | lastbin<<31

# flag = 14-5-1 = 8
mask = 0b10100100000010000000100010010100
data = open("key").read()
data = data[:4]
c = bytes_to_long(data)
for k in range(32):
    c = lfsr_inv(c, mask)
print hex(c)
#flag: 0x926201d7L

这题还有另一种使用矩阵变幻的做法

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
 
mask = 0b10100100000010000000100010010100

N = 32
F = GF(2)

b = ''
with open('key', 'rb') as f:
    b = f.read()

R = [vector(F, N) for i in range(N)]
for i in range(N):
    R[i][N - 1] = mask >> (31 - i) & 1
for i in range(N - 1):
    R[i + 1][i] = 1
M = Matrix(F, R)
M = M ^ N

vec = vector(F, N)
row = 0
for i in range(N / 8):
    t = ord(b[i])
    for j in xrange(7, -1, -1):
        vec[row] = t >> j & 1
        row += 1
print rank(M)
num = int(''.join(map(str, list(M.solve_left(vec)))), 2)
print hex(num)

2019 de1ctf babylfsr

前面的做法只能适用于flag长度比较小的时候，当flag长度比较长的时候，直接爆破显然是不现实的，算力支撑不了，因此只能进行矩阵变换进行求解

非线性反馈移位寄存器NFSR

非线性的反馈移位寄存器一般有三种

1
2
3
 
非线性组合生成器，对多个LFSR的输出内容使用一个非线性的组合函数
非线性滤波生成器，对一个LSRF的输出内容使用一个非线性的组合函数
钟控生成器，使用一个或多个LFSR的输出来控制另一个或多个LFSR的时钟

2018 ciscn streamgame3

源码在这里

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
 
flag='flag{01b9cb05979c16b2f3}'
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==24

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)


def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    (R1_NEW,x1)=lfsr(R1,R1_mask)
    (R2_NEW,x2)=lfsr(R2,R2_mask)
    (R3_NEW,x3)=lfsr(R3,R3_mask)
    return (R1_NEW,R2_NEW,R3_NEW,(x1*x2)^((x2^1)*x3))

R1=int(flag[5:11],16)
R2=int(flag[11:17],16)
R3=int(flag[17:23],16)
assert len(bin(R1)[2:])==17
assert len(bin(R2)[2:])==19
assert len(bin(R3)[2:])==21
R1_mask=0x10020
R2_mask=0x4100c
R3_mask=0x100002


for fi in range(1024):
    print (fi)
    tmp1mb=""
    for i in range(1024):
        tmp1kb=""
        for j in range(1024):
            tmp=0
            for k in range(8):
                (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
                tmp = (tmp << 1) ^ out
            tmp1kb+=chr(tmp)
        tmp1mb+=tmp1kb
    f = open("./output/" + str(fi), "ab")
    f.write((bytes)(tmp1mb.encode()))
    f.close()

2019 TCTF zer0lfsr

这题跟上一题差不多，也是先求三个lfsr，然后再联合获得结果，源码如下

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
 
from secret import init1,init2,init3,FLAG
import hashlib
assert(FLAG=="flag{"+hashlib.sha256(init1+init2+init3).hexdigest()+"}")

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

def combine(x1,x2,x3):
    return (x1*x2)^(x2*x3)^(x1*x3)

if __name__=="__main__":
    l1 = lfsr(int.from_bytes(init1,"big"),0b100000000000000000000000010000000000000000000000,48)
    l2 = lfsr(int.from_bytes(init2,"big"),0b100000000000000000000000000000000010000000000000,48)
    l3 = lfsr(int.from_bytes(init3,"big"),0b100000100000000000000000000000000000000000000000,48)

    with open("keystream","wb") as f:
        for i in range(8192):
            b = 0
            for j in range(8):
                b = (b<<1)+combine(l1.next(),l2.next(),l3.next())
            f.write(chr(b).encode())

这题没有把l1、l2、l3的长度给出来，也没有更多的信息，所以不能直接用相关攻击，但是我们可以仔细观察，虽然有掩码位数很长，但是只有两位是1，其他位都是0，所以我们可以先思考一下，next处理的部分，对他进行影响的，只是init中位数为1的部分，而且处理后的信息储存到了最低位，没有丢失，因此可以逆推回去获得原值，而其中combine的三个值因为输入为单位，所以实际上可以变换为

1
2
 
def combine(x1, x2, x3):
    return (x1&x2) ^ (x2&x3) ^ (x3&x1)

因此结合一起的三个lfsr就可以轻易的分解为单个lfsr了，剩下的求解可以直接用z3去跑

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
 
# -*- coding:utf8 -*-
from z3 import *
from Crypto.Util.number import long_to_bytes
import hashlib

def combine(x1, x2, x3):
    return (x1 * x2) ^ (x2 * x3) ^ (x1 * x3)

def solve_3_lfsr(keystream, relevant_bit_indices, length, mask_length):
    len_mask = (2 ** (mask_length + 1) - 1)
    result_bits = map(long, "".join([bin(ord(c))[2:].zfill(8) for c in keystream]))
    s = Solver()
    x = BitVec('x', length)  # z3中只有BitVec类型支持异或操作
    y = BitVec('y', length)  # BitVec表示无符号数
    z = BitVec('z', length)
    inits = [x, y, z]
    for result in result_bits:
        combs = []
        new_inits = []
        for index in range(3):  # 无符号数的移位需要使用LShR，表示逻辑移位
            relevant_bit1 = (inits[index] & (1 << relevant_bit_indices[index][0]))
            bit1_value = LShR(relevant_bit1, relevant_bit_indices[index][0])
            relevant_bit2 = inits[index] & (1 << relevant_bit_indices[index][1])
            bit2_value = LShR(relevant_bit2, relevant_bit_indices[index][1])
            single_lfsr_result = bit1_value ^ bit2_value
            combs.append(single_lfsr_result)
            new_init = ((inits[index] << 1) & len_mask) ^ single_lfsr_result
            new_inits.append(new_init)
        s.add(combine(combs[0], combs[1], combs[2]) == result)  # 约束条件
        inits = new_inits
    s.check()
    model = s.model()
    x_res = int(str(model[x]))
    y_res = int(str(model[y]))
    z_res = int(str(model[z]))
    return x_res, y_res, z_res

with codecs.open("keystream", 'rb', 'utf8') as input_file:
    data = input_file.read()
    mask1 = (47, 22)
    mask2 = (47, 13)
    mask3 = (47, 41)
    keystream = data[:24]
    x, y, z = solve_3_lfsr(data[:24], [mask1, mask2, mask3], 48, 48)
    init1, init2, init3 = map(long_to_bytes, [x, y, z])
    print "flag{" + hashlib.sha256(init1 + init2 + init3).hexdigest() + "}"

#flag{b527e2621131134ec22250cfbca75e8c9f5ae4f40370871fd55910927f66a1b4}

后记

看来还得继续拖着了……生成函数啥的没学懂，做题到后面地动山摇Orz

FROM:Xi4or0uji

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年8月18日01:28:24
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   反馈移位寄存器https://cn-sec.com/archives/3074479.html

发表评论

匿名网友 填写信息