Crypto

6 Aug 2019

反馈移位寄存器

反馈移位寄存器

$a_i$表示二值存储单元，个数n称为反馈移位寄存器的级。在某一时刻，这些级构成该反馈移位寄存器的一个状态，共有$2^n$个可能状态，每一个状态对应于域$GF(2)$上的一个n维向量，用$(a_0,a_1,a_2,…a_{n-1})$表示

F 为反馈函数或者反馈逻辑。如果 F 为线性函数，那么我们称其为线性反馈移位寄存器（LFSR），否则我们称其为非线性反馈移位寄存器（NFSR）

在主时钟周期的周期区间上，每一级存储器$a_i$都将内容向下一级$a_{i-1}$传递，并根据寄存器的当前状态$f(a_0,a_1,a_2,…a_{n-1})$作为$a_{n-1}$的下一时间内容，即从一个状态转移到下一个状态。

$a_{i+n}=F(a_i,a_{i+1},…,a_{i+n-1})$

$(a_i,a_{i+1},…,a_{i+n-1}) \rightarrow (a_{i+1},…,a_{i+n-1},a_{i+n})$

线性反馈移位寄存器(LFSR)

反馈函数：$a_{i+n}=\sum\limits_{j=1}^{n}c_ja_{i+n-j}$ ，其中，$c_j$ 均在某个有限域 $F_q$ 中。

$(a_i,a_{i+1},…,a_{i+n-1}) \rightarrow (a_{i+1},…,a_{i+n-1},a_{i+n})$

这个线性变换为

特征多项式：$f(x)=x^n-\sum\limits_{i=1}^{n}c_ix^{n-i}$

互反多项式：$\overline f(x)=x^nf(\frac{1}{x})=1-\sum\limits_{i=1}^{n}c_ix^{i}$

基本操作
1. 初始化。以给定的密钥初始化寄存器
2. 抽头。从这些比特位中随机选取一些，并计算这些抽头的异或
3. 位移、输出。输出抽头异或的结果。寄存器左移一位，把抽头异或的结果与寄存器最后一位异或，当前寄存器状态作为新的密钥。
```
def lfsr(R,mask):
    output = (R << 1) & lengthmask
    i = (R & mask) & lengthmask 
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    output ^= lastbit 
    return(output,lastbit)
```

2018 CISCN 初赛 oldstreamgame

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()
#key  = '00100000111111011110111011111000'

flag左移到只剩一位时，剩下的31反馈移位位寄存器全是已知的输出过后的lastbit

第32个lastbit由flag的第一位和31位已输出lastbit生成，可以推出flag第一位，然后推出flag所有位

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
     
mask = '10100100000010000000100010010100'
key  = '00100000111111011110111011111000'
flag = ''
for i in range(32):
    r = key[:-i-1]
    l = '0'+flag
    R = int(l+r, 2)
    out = lfsr(R, int(mask, 2))
    out = '{:032b}'.format(out)
    if out == flag+key[:-i]:
        flag = '0' + flag
    else:
        flag = '1' + flag
print(flag)
#0x926201d7

线性变换解法

from sage.all_cmdline import *
mask = 0b10100100000010000000100010010100
key = '00100000111111011110111011111000'
N = 32
GF2 = GF(2)
R = [vector(GF2, N) for i in range(N)]
for i in range(N):
    R[i][N - 1] = mask >> (N-1 - i) & 1
for i in range(N - 1):
    R[i + 1][i] = 1
M = Matrix(GF2, R)
M = M ** N
    
first = [int(op) for op in key]
first = vector(GF2, first)
flag = int(''.join(map(str, list(M.solve_left(first)))), 2)
print(hex(flag))
#0x926201d7

爆破解法

略

已知 2n 序列求初始化种子

$a_1,…,a_{2n}$，令

$S_1=(a_1,…,a_n)$

$S_2=(a_2,…,a_{n+1})$

….

$S_{n+1}=(a_{n+1},…,a_{2n})$

构造矩阵 $A=(S_1,…,S_n)^T$

$A(c_n,…,c_1)^{T}=S_{n+1}$

所以

$(c_n,…,c_1)^{T}=S_{n+1}A^{-1}$

得到LFSR反馈表达式，可以推出初始化种子

De1ctf-babylsfr

import hashlib
from secret import KEY,FLAG,MASK
#assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
#assert(FLAG[7:11]=='1224')
LENGTH = 256
#assert(KEY.bit_length()==LENGTH)
#assert(MASK.bit_length()==LENGTH)
      
def pad(m):
    pad_length = 8 - len(m)
    return pad_length*'0'+m
      
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
      
      
if __name__=="__main__":
    l = lfsr(KEY,MASK,LENGTH)
    r = ''
    for i in range(63):
        b = 0
        for j in range(8):
            b = (b<<1)+l.next()
        r += pad(bin(b)[2:])
    with open('output','w') as f:
        f.write(r)

mask和key是256位，给出504位的输出，爆破8位补足512位，求出LFSR反馈表达式，还原key，sha256(key)前四位为1224

爆破时检查矩阵的秩，不满秩无解。

from sage.all_cmdline import *
import hashlib
GF2 = GF(2)
N = 256
for x in range(2 ** 8):
	a ='001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'
	a = a + bin(x)[2:].zfill(8)
	A = []
	for i in range(256):
		A.append([int(op) for op in a[i:i+256]])
	A = matrix(GF2,A)
	if A.rank() != 256:
		continue
	last = [int(op) for op in a[256:]]
	last = vector(GF2, last)
	mask = A.solve_right(last)#(c_n,...,c_1)
	mask = int(''.join(map(str, list(mask))),2)
      
	R = [vector(GF2, N) for i in range(N)]
	for i in range(N):
		R[i][N - 1] = mask >> (N-1 - i) & 1
	for i in range(N - 1):
		R[i + 1][i] = 1
	M = Matrix(GF2, R)#线性变换矩阵
	M = M ** N
      
	first = [int(op) for op in a[0:256]]
	first = vector(GF2, first)
	if M.rank() != 256:
		continue
	res = M.solve_left(first)
	KEY = int(''.join(map(str, list(res))),2)
	FLAG = "de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}"
	if FLAG[7:11]=='1224':
		print FLAG
		break
#de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}

非线性反馈移位寄存器

为了使得密钥流输出的序列尽可能复杂，会使用非线性反馈移位寄存器，常见的有三种
1. 非线性组合生成器，对多个 LFSR 的输出使用一个非线性组合函数
2. 非线性滤波生成器，对一个 LFSR 的内容使用一个非线性组合函数
3. 钟控生成器，使用一个（或多个）LFSR 的输出来控制另一个（或多个）LFSR 的时钟

Tags:

0 comments

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议（CC BY-NC-ND 4.0）进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).

反馈移位寄存器

反馈移位寄存器