经由过程三道CTF进修反应移位寄存器 | 申博官网
登录
  • 欢迎进入申博官网!
  • 如果您觉得申博官网对你有帮助,那么赶紧使用Ctrl+D 收藏申博官网并分享出去吧
  • 这里是申博官方网!
  • 申博官网是菲律宾sunbet官网品牌平台!
  • 申博开户专业品牌平台!

经由过程三道CTF进修反应移位寄存器

申博_安全防护 申博 208次浏览 已收录 0个评论

AFL源码剖析条记(一)

0x00 前言 总结师傅们笔记,主要源码分析。 0x01 代码覆盖率 代码覆盖率是fuzz中基本概念,先了解清这个概念后面的插装编译等概念才好理解。 代码覆盖率是一种度量代码的覆盖程度的方式,也就是指源代码中的某行代码是否已执行;对二进制

经由历程三道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()

单从代码条理来看对照难明,我画了一个流程图便于明白:

经由过程三道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' #注重key的高位和低位递次
flag = ''

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 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研讨:

经由过程三道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 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,输出效果以下:

————————————-

申博网络安全巴士站

申博-网络安全巴士站是一个专注于网络安全、系统安全、互联网安全、信息安全,全新视界的互联网安全新媒体。

————————————-

经由过程三道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 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

运转效果为:

经由过程三道CTF进修反应移位寄存器

注重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

运转效果为

经由过程三道CTF进修反应移位寄存器

如许的效果就充足让人高兴了,申明有很大的多是能够将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的完成历程,还进修到了较多的进击手段,收成许多

AFL源码剖析条记(一)

0x00 前言 总结师傅们笔记,主要源码分析。 0x01 代码覆盖率 代码覆盖率是fuzz中基本概念,先了解清这个概念后面的插装编译等概念才好理解。 代码覆盖率是一种度量代码的覆盖程度的方式,也就是指源代码中的某行代码是否已执行;对二进制


申博|网络安全巴士站声明:该文看法仅代表作者自己,与本平台无关。版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明经由过程三道CTF进修反应移位寄存器
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址