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

前言

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

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

线性反馈移位寄存器

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

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 #将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 = 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()

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

通过流程图可以简单概括代码的功能为:将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 = True
for 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'+flag

print hex(int(flag, 2))

非线性反馈移位寄存器

常见的有三种

  • 非线性组合生成器,对多个 LFSR 的输出使用一个非线性组合函数
  • 非线性滤波生成器,对一个 LFSR 的内容使用一个非线性组合函数
  • 钟控生成器,使用一个(或多个)LFSR 的输出来控制另一个(或多个)LFSR 的时钟

目前遇到最多的是第一种

2018 强网杯 streamgame3

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("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) * 100

def 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 = 64
with open("E:/output/0") as f:
    cipher = f.read(bytes_size)


R1_mask=0x10020
R2_mask=0x4100c
R3_mask=0x100002

len1=17
len2=19
len3=21

#guess(len1, R1_mask) #76.5625 0x1b9cb
R1 = 0x01b9cb
#guess(len3, R3_mask) #73.4375 0x16b2f3
R3 = 0x16b2f3

print 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,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长度未知,也许和mask的长度可能差不多,所以上面的攻击思路不好利用

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

先从单个lfsr研究:

那从之前的这张图就可以看到每一轮的运算等价于是对有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 count

def 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,输出结果如下:

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

也就是说我们知道了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 urandom


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 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 pos

def 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

运行结果为:

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

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

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

#! /usr/bin/env python
# -*- coding: utf-8 -*-

from libnum import *
from z3 import *
from os import urandom


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 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 pos

def 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

运行结果为

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

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

#! /usr/bin/env python
# -*- coding: utf-8 -*-

from libnum import *
from z3 import *
from os import urandom
from hashlib import sha256



def 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 pos


def 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

点击收藏 | 1 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖