通过三道CTF学习反馈移位寄存器

admin 2022年6月7日23:31:54评论46 views字数 11027阅读36分45秒阅读模式

通过三道CTF学习反馈移位寄存器

前言

流密码的关键在于设计好的伪随机数生成器。一般来说,伪随机数生成器的基本构造模块为反馈移位寄存器。反馈函数或者反馈逻辑F如果是线性函数,那么称其为线性反馈移位寄存器(LFSR)否则为非线性反馈移位寄存器

去年反馈移位寄存器的密码学题目考的比较多,前一阵的tctf又出现了这个考点,于是做了一个对LFSR攻击手法的总结

线性反馈移位寄存器

LFSR是如何实现的呢?先来看看这道题吧

2018 CISCN 初赛 oldstreamgame

flag = "flag{xxxxxxxxxxxxxxxx}"assert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==14def 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)
i=i>>1 #让lastbit依次和i的每一位异或,然后赋值给lastbit
output^=lastbit
return (output,lastbit)R=int(flag[5:-1],16)mask = 0b10100100000010000000100010010100f=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()

单从代码层次来看比较难懂,我画了一个流程图便于理解:

通过三道CTF学习反馈移位寄存器

通过流程图可以简单概括代码的功能为:将mask的二进制位为1的位置对应到种子flag的位置,让他们做异或运算(比如如果mask的二进制位中第2位和第12位为1,其余位置为0,那么就将flag的第2位和第12位的值异或),然后将flag左移一位,最低位加上刚才做异或运算的结果,如此一直循环,此题解法如下:

每一个lastbit输出,是我们已知的,考虑当flag依次左移到只剩下一个二进制位时,剩下的31位全是已知的输出过后的lastbit,那么第32个lastbit(已知)就由第一位flag(未知)和31个lastbit(已知)生成,这样就能知道第一位的flag然后依次得到所有位的flag了,exp如下:

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

if out==key[:]:
flag='0'+flag
else:
flag='1'+flag
first = False

else:
if out==flag+key[:-i]:
flag='0'+flag
else:
flag='1'+flagprint hex(int(flag, 2))

非线性反馈移位寄存器

常见的有三种

  • 非线性组合生成器,对多个 LFSR 的输出使用一个非线性组合函数

  • 非线性滤波生成器,对一个 LFSR 的内容使用一个非线性组合函数

  • 钟控生成器,使用一个(或多个)LFSR 的输出来控制另一个(或多个)LFSR 的时钟

目前遇到最多的是第一种

2018 强网杯 streamgame3

flag='flag{01b9cb05979c16b2f3}'assert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==24def 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:])==17assert len(bin(R2)[2:])==19assert len(bin(R3)[2:])==21R1_mask=0x10020R2_mask=0x4100cR3_mask=0x100002for 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("E:/output/" + str(fi), "ab")
f.write(tmp1mb)
f.close()

题目里的LFSR和第一题一样,但是利用了一个函数将三个LFSR的输出关联起来,来增大解题难度

这里题目告诉了我们R1、R2、R3的2进制长度,虽然直接对flag爆破有难度,但是可以采用关联攻击的思想,对R1、R2、R3分别单独暴破。首先枚举x1, x2, x3和F的所有可能取值

x1 x2 x3 F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

如果把每一种可能视作等概率事件,F和x1、x3相同的概率有75%和x2相同的概率有50%,所以我们可以对R1、R3单独枚举,并且用单独的lfsr代替single round,如果和cipher相同的位数接近75%的话就认为枚举正确,而且题目给出的cipher的数据量足够大,足够在这种大量数据的基础下完成攻击,x1和x3猜测出以后,剩下的x2直接爆破就可以解出了,exp如下:

#! /usr/bin/env python# -*- coding: 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)def correlation(a,b):
assert len(a)==len(b)
count = 0
for i, j in zip(a, b):
ib = '{:08b}'.format(ord(i))
jb = '{:08b}'.format(ord(j))
for m, n in zip(ib, jb):
if m == n:
count+=1
return count / (bytes_size * 8.0) * 100def guess(length, mask):
for n in range(2**(length-1), 2**length):
R = n
s = ''
for i in range(bytes_size):
tmp = 0
for j in range(8):
(R, out) = lfsr(R, mask)
tmp = (tmp << 1) ^ out
s += chr(tmp)
pb = correlation(s, cipher)
#print pb,hex(n)
if 72<=pb<=78:
print pb,hex(n)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))def brute_force(R1, R3, length):
for n in range(2**(length-1), 2**length):
r2 = n
r1 = R1
r3 = R3
s = ''
for i in range(bytes_size):
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
s += chr(tmp)
assert len(s)==len(cipher)
#print hex(n)
if s == cipher:
return str(hex(n))bytes_size = 64with open("E:/output/0") as f:
cipher = f.read(bytes_size)R1_mask=0x10020R2_mask=0x4100cR3_mask=0x100002len1=17len2=19len3=21#guess(len1, R1_mask) #76.5625 0x1b9cbR1 = 0x01b9cb#guess(len3, R3_mask) #73.4375 0x16b2f3R3 = 0x16b2f3print brute_force(R1, R3, len2) #0x5979c

在选择64个字节进行比较的情况下,实测R1和R3的相似度分别为$76.6%$和$73.4%$,故最终flag为flag{01b9cb05979c16b2f3}

TCTF 2019 zer0lfsr

from secret import init1,init2,init3,FLAGimport hashlibassert(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 outputdef 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长度未知,也许和mask的长度可能差不多,所以上面的攻击思路不好利用

这道题的漏洞点在于掩码的选择上,可以发现三个掩码尽管有48bit但是只有两个bit是1,其余的都是0

先从单个lfsr研究:

通过三道CTF学习反馈移位寄存器

那从之前的这张图就可以看到每一轮的运算等价于是对有1的两个bit位做的一个异或,然后贴到R的最低位

由于后面所有的异或的值已知,所以实际上可以通过列线性方程组的方法恢复出每一位,我写了一个demo来模拟500轮变化:

init = []for i in range(48):
init.append(str(i+1))def counter(c, li):
count = 0
for i in li:
if c == i:
count += 1
return countdef clear(string):
new = []
for c in string.split('+'):
if counter(c, string.split('+'))==1:
new.append(c)


return '+'.join(new)for i in range(500):
print init
tmp = init[0]+'+'+init[6]

init = init[1:]
init.append(clear(tmp))

输出结果中使用+代表异或,假设掩码中从高位数起的第1位和第7位为1,输出结果如下:

通过三道CTF学习反馈移位寄存器

追踪初始值1 xor 7可以看到后面还有和1 xor 7单独异或的结果

通过三道CTF学习反馈移位寄存器

也就是说我们知道了43 xor 1 xor 7和1 xor 7的结果,那么我们把这两者异或就能得到第43位的值,而我们所有有关xor的项都是知道的,所以只要数据量够大,就可以通过列出一系列线性方程组来恢复出所有的bit位

但是我们如果想实现这个攻击的话,是比较麻烦的,我们可以用python z3库来帮助我们实现,这里推荐在linux环境下安装z3库:pip install z3-solver

我们只需要为z3的solver添加每一轮的约束断言,z3就能解决这个问题了

#! /usr/bin/env python# -*- coding: utf-8 -*-from libnum import *from z3 import *from os import urandomclass 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 outputdef get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask)-i-1)
return posdef combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)def single_lfsr(cipher, pos, length):
s = Solver() #初始化一个Sovler api
x = BitVec('x', length) #定义一个bit向量
for c in cipher:
x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])#LShR表示二进制位右移
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs
s.add(xs == int(c))#向s添加约束断言

s.check()
return str(s.model())if __name__=="__main__":
mask1 = 0b100000000000000000000000010000000000000000000000
init1 = urandom(48/8)

print 'init:', s2n(init1)

flag1 = lfsr(s2n(init1), mask1, 48)


keystream = ""
for i in range(48):
keystream += str(flag1.next())

res = single_lfsr(keystream, [get_pos(mask1)], 48)
print res

运行结果为:

通过三道CTF学习反馈移位寄存器

注意keystream的大小,如果太小的话可能会得出错误的答案,应该尽可能的让数据量大,但又不至于太大

那么对于3轮来说的话,我们只需要把bit向量的个数扩充到3个,然后依次添加约束就好了,这样的话只是方程组复杂了一点

我们尝试下一个demo,发现z3同样也是可以为我们解出的

#! /usr/bin/env python# -*- coding: utf-8 -*-from libnum import *from z3 import *from os import urandomclass 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 outputdef get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask)-i-1)
return posdef combine(x1,x2,x3):
return (x1*x2)^(x2*x3)^(x1*x3)def break_3_lfsr(cipher, pos, length):
s = Solver()
x = BitVec('x', length)
y = BitVec('y', length)
z = BitVec('z', length)


for c in cipher:

x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs

y_bit1 = LShR(y & (1 << pos[1][0]), pos[1][0])
y_bit2 = LShR(y & (1 << pos[1][1]), pos[1][1])
ys = y_bit1 ^ y_bit2
y = ((y << 1) & (2 ** (length + 1) - 1)) ^ ys

z_bit1 = LShR(z & (1 << pos[2][0]), pos[2][0])
z_bit2 = LShR(z & (1 << pos[2][1]), pos[2][1])
zs = z_bit1 ^ z_bit2
z = ((z << 1) & (2 ** (length + 1) - 1)) ^ zs

s.add(combine(xs, ys, zs) == int(c))

s.check()
return s.model()if __name__=="__main__":
mask1 = 0b100000000000000000000000010000000000000000000000
mask2 = 0b100000000000000000000000000000000010000000000000
mask3 = 0b100000100000000000000000000000000000000000000000


init1 = urandom(48/8)
init2 = urandom(48/8)
init3 = urandom(48/8)
print 'init:', s2n(init1), s2n(init2), s2n(init3)

flag1 = lfsr(s2n(init1), mask1, 48)
flag2 = lfsr(s2n(init2), mask2, 48)
flag3 = lfsr(s2n(init3), mask3, 48)


keystream = ""
for i in range(48*8):
keystream += str(combine(flag1.next(), flag2.next(), flag3.next()))

res = break_3_lfsr(keystream, [get_pos(mask1), get_pos(mask2), get_pos(mask3)], 48)

print res

运行结果为

通过三道CTF学习反馈移位寄存器

这样的结果就足够让人兴奋了,说明有很大的可能是可以将flag直接解出的

先放一下这道题最终的exp:

#! /usr/bin/env python# -*- coding: utf-8 -*-from libnum import *from z3 import *from os import urandomfrom hashlib import sha256def get_pos(mask):
s_mask = bin(mask)[2:]
pos = []
for i in range(len(s_mask)):
if s_mask[i] == '1':
pos.append(len(s_mask) - i - 1)
return posdef combine(x1, x2, x3):
return (x1 * x2) ^ (x2 * x3) ^ (x1 * x3)def break_3_lfsr(cipher, pos, length):
s = Solver()
x = BitVec('x', length)
y = BitVec('y', length)
z = BitVec('z', length)

for c in cipher:
x_bit1 = LShR(x & (1 << pos[0][0]), pos[0][0])
x_bit2 = LShR(x & (1 << pos[0][1]), pos[0][1])
xs = x_bit1 ^ x_bit2
x = ((x << 1) & (2 ** (length + 1) - 1)) ^ xs

y_bit1 = LShR(y & (1 << pos[1][0]), pos[1][0])
y_bit2 = LShR(y & (1 << pos[1][1]), pos[1][1])
ys = y_bit1 ^ y_bit2
y = ((y << 1) & (2 ** (length + 1) - 1)) ^ ys

z_bit1 = LShR(z & (1 << pos[2][0]), pos[2][0])
z_bit2 = LShR(z & (1 << pos[2][1]), pos[2][1])
zs = z_bit1 ^ z_bit2
z = ((z << 1) & (2 ** (length + 1) - 1)) ^ zs

s.add(combine(xs, ys, zs) == int(c))

s.check()
return s.model()if __name__ == "__main__":

mask1 = 0b100000000000000000000000010000000000000000000000
mask2 = 0b100000000000000000000000000000000010000000000000
mask3 = 0b100000100000000000000000000000000000000000000000

with codecs.open('keystream', 'rb', 'utf8') as f:
data = f.read(48)

cipher = ''
for c in data:
cipher += '{:08b}'.format(ord(c))
# print cipher

res = break_3_lfsr(cipher, [get_pos(mask1), get_pos(mask2), get_pos(mask3)], 48*8)
print res

''' [z = 191532558614761, y = 181037482648735, x = 70989122156399] '''
z = 191532558614761
y = 181037482648735
x = 70989122156399
print 'flag{' + sha256(n2s(x) + n2s(y) + n2s(z)).hexdigest() + '}'

其中有一个非常坑的地方,就是题目脚本是用了python3的encode()方法将每个字节用utf-8编码了再写入进去的,所以我们打开文件的时候也必须指定utf-8编码格式打开

思考

那么是不是说明这种的非线性组合生成器存在通用的解法呢?是不是强网杯的那道题也可以用这样的做法呢?毕竟从上面的题看上去并没有对参数有特殊的限制,但是笔者进行了测试,强网杯的题这样做是没有解的,并且这种做法对参数是有比较严格的限制的,笔者利用“控制变量法”对三个mask,F函数,三个初始变量进行了测试,这些参数需满足以下约束条件,否则可能出现无解或多解的情况:

  • F函数的值与x1, x2, x3相同的概率要尽可能大,就像强网杯的那道题一样

  • mask的长度要尽可能地和tctf代码中的lengthmask相同

  • mask的二进制位中为1的个数要尽可能的少

而对三个初始变量的值则没有比较严格的要求

总结:

通过这三道CTF,不仅理解了LFSR的实现过程,还学习到了较多的攻击手法,收获很多

参考文章

https://ctf-wiki.github.io/ctf-wiki/crypto/streamcipher/fsr/intro/

https://github.com/p4-team/ctf/tree/master/2019-03-23-0ctf-quals/crypto_lfsr


源:先知(https://xz.aliyun.com/t/4630#toc-0)

注:如有侵权请联系删除



通过三道CTF学习反馈移位寄存器




通过三道CTF学习反馈移位寄存器

欢迎大家加群一起讨论学习和交流

通过三道CTF学习反馈移位寄存器

快乐要懂得分享,

才能加倍的快乐。


原文始发于微信公众号(衡阳信安):通过三道CTF学习反馈移位寄存器

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年6月7日23:31:54
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   通过三道CTF学习反馈移位寄存器http://cn-sec.com/archives/1093123.html

发表评论

匿名网友 填写信息