MISC

Welcome

使用stegsolve打开，在Analyse->Stereogram Solver 处改变偏移即可。

Crypto

streamgame1

streamgame1.py

 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

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25

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)


R=int(flag[5:-1],2)
mask    =   0b1010011000100011100

f=open("key","ab")
for i in range(12):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def crack(key):
    for k in range(0,2**19):
        R=k
        for i in range(12):
            tmp,flag=0,1
            for j in range(8):
                (R,out)=lfsr(R,mask)
                tmp=(tmp << 1)^out
            if(chr(tmp)!=key[i]):
                flag=0
                break
        if flag:
            print "flag{%s}"%bin(k)[2:]

crack(open('key','rb').read())
# flag{1110101100001101011}

streamgame2

streamgame2.py

 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

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==27

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)

R=int(flag[5:-1],2)
mask=0x100002

f=open("key","ab")
for i in range(12):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def crack(key):
    for k in range(0,2**21):
        R=k
        for i in range(12):
            tmp=0
            flag=1
            for j in range(8):
                (R,out)=lfsr(R,mask)
                tmp=(tmp << 1)^out
            if(chr(tmp)!=key[i]):
                flag=0
                break
        if flag:
            print "flag{%s}"%bin(k)[2:]
crack(open('key','rb').read())
# flag{110111100101001101001}

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
49
50
51
52
53
54
55
56
57

from flag import flag
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(tmp1mb)
    f.close()

solution

如果两个随机二进制串不相关，那么将它们逐位比对，有1/2的概率相等，如果是三进制串，则概率为1/3，以此类推。写个小脚本验证一下：

相反的，如果两个随机二进制串之间的存在关联，那么概率就不会是1/2了。

对于 x1,x2,x3∈{0,1} 考虑逻辑运算 out=(x1*x2)^((x2^1)*x3) ，

若x2=0 ，则out=x3 ，若x2=1 则out=x1 。

那么p(out=x3) = p(out=x3|x2=0) * p(x2=0)+ p(out=x3|x2=1) * p(x2=1)=(1+1/2) * 1/2 = 3/4 != 1/2 ，

对于x1同理有p(out=x1)=3/4 != 1/2 。

这个题目直观的想法和前两题一样，遍历R1，R2，R3三个寄存器所有可能的初始状态，但因为可能性过多在计算上是不可行的。上面提到的这种相关性提供了一种各个击破的思路：遍历R1的所有可能，计算其与out的相关性，逼近3/4的就可能是其初始状态，越逼近可能性越大，对R3同理。

这种基于相关性的攻击称为相关攻击（correlation attack），其分而治之的技巧可以降低爆破复杂度，比相关攻击复杂度更低的都可以称为快速相关攻击（也有一些经典的手法，不过目前还没很理解）。

本题采用相关攻击就可以在可接受时间内得到R1，R3的初始状态。

初始状态的可选空间越大，就需要越长的结果序列来判定。R1，R3分别大概7字节和17字节就足够了。

然后爆破R2就不难了。

全部代码如下：

 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import time
cipher=''.join([bin(ord(i))[2:].zfill(8) for i in open("output/0","rb").read()])
R1_mask=0x10020 ; R2_mask=0x4100c ; R3_mask=0x100002
R1_range=xrange(2**16,2**17)
R2_range=xrange(2**18,2**19)
R3_range=xrange(2**20,2**21)

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

def calcRelation(a,b):
    assert len(a)==len(b)
    cnt=0.0
    for i,j in zip(a,b):
        cnt+=(i==j)
    return cnt/len(a)

def get_most_related(R_range,R_mask,cmp_length):
    real_R,relation=0,0
    for i in R_range:
        R,tmp=i,""
        for j in xrange(cmp_length*8):
            R,out=lfsr(R,R_mask)
            tmp+=str(out)
        r=calcRelation(cipher[:cmp_length*8],tmp)
        if r>relation:
            relation=r 
            real_R=i
    return (real_R,relation)

def bruteR13():
    R1,r=get_most_related(R1_range,R1_mask,7)
    R3,r=get_most_related(R3_range,R3_mask,17)
    return (R1,R3)

def brute():
    R1_,R3_=bruteR13()
    # R1_,R3_=0x1b9cb,0x16b2f3
    print "R1=%s,R3=%s"%(R1_,R3_)
    print time.asctime()
    for i in R2_range:
        R1,R2,R3=R1_,i,R3_
        res=''
        for j in range(40):
            (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
            res+=str(out)
        if cipher[:len(res)]==res:
            print 'flag{'+''.join(map(lambda x:hex(x)[2:],(R1_,i,R3_)))+'}'

print time.asctime()
brute()
print time.asctime()

# Thu May 03 21:56:46 2018
# R1=113099,R3=1487603
# Thu May 03 22:01:41 2018
# flag{1b9cb5979c16b2f3}
# Thu May 03 22:02:41 2018
# [Finished in 357.3s]

参考：http://blog.leanote.com/post/xp0intjnu@gmail.com/66c91498d13b

streamgame4

streamgame4.py

 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

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==27

def nlfsr(R,mask):
    output = (R << 1) & 0xffffff
    i=(R&mask)&0xffffff
    lastbit=0
    changesign=True
    while i!=0:
        if changesign:
            lastbit &= (i & 1)
            changesign=False
        else:
            lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

R=int(flag[5:-1],2)
mask=0b110110011011001101110

f=open("key","ab")
for i in range(1024*1024):
    tmp=0
    for j in range(8):
        (R,out)=nlfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def crack(key):
    for maybe in range(2**21,0,-1):
        flag=0
        R=maybe
        for index in xrange(len(key)):
            tmp=0
            for j in range(8):
                (R,out)=nlfsr(R,mask)
                tmp=(tmp<<1)^out
            if chr(tmp)!=key[index]:
                flag=1
                break
        if not flag:
            print "flag{%s}"%bin(maybe)[2:]

crack(open("key",'r').read())
#flag{100100111010101101011}

nextrsa

nc 39.107.33.90 9999

这是一个RSA相关安全问题的合集，是个很有意思值得一做的题目。

题目源码已公开在GitHub：https://github.com/fpbibi/nextrsa

可参考以下链接：

Web

Web签到

The Fisrt Easy Md5 Challenge

1
2
3

if($_POST['param1']!=$_POST['param2'] && md5($_POST['param1'])==md5($_POST['param2'])){
			die("success!");
		}

可用PHP弱类型或者数组绕过。

post param1=QNKCDZO&param2=240610708 或者 param1[]=&param2[]=0 。

The Second Easy Md5 Challenge

1
2
3

if($_POST['param1']!==$_POST['param2'] && md5($_POST['param1'])===md5($_POST['param2'])){
		die("success!");
	}

可用PHP数组绕过。post param1[]=&param2[]=0 。

Md5 Revenge Now!

1
2
3

if((string)$_POST['param1']!==(string)$_POST['param2'] && md5($_POST['param1'])===md5($_POST['param2'])){
die("success!);
}

绕不过去，但是因为哈希是从无限集到有限集的映射，必然存在两个不同的消息拥有相同的哈希值，而且这种消息对已经可以被构造了。（工具： https://xz.aliyun.com/t/2232 ）

https://crypto.stackexchange.com/questions/1434/are-there-two-known-strings-which-have-the-same-md5-hash-value

1
2
3
4
5

s1="4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2"
s2="4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2"
y=lambda s: "%"+"%".join([s[i*2:i*2+2] for i in range(len(s)/2)])
print y(s1)
print y(s2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

<?php 
$param1=urldecode("%4d%c9%68%ff%0e%e3%5c%20%95%72%d4%77%7b%72%15%87%d3%6f%a7%b2%1b%dc%56%b7%4a%3d%c0%78%3e%7b%95%18%af%bf%a2%00%a8%28%4b%f3%6e%8e%4b%55%b3%5f%42%75%93%d8%49%67%6d%a0%d1%55%5d%83%60%fb%5f%07%fe%a2");
$param2=urldecode("%4d%c9%68%ff%0e%e3%5c%20%95%72%d4%77%7b%72%15%87%d3%6f%a7%b2%1b%dc%56%b7%4a%3d%c0%78%3e%7b%95%18%af%bf%a2%02%a8%28%4b%f3%6e%8e%4b%55%b3%5f%42%75%93%d8%49%67%6d%a0%d1%d5%5d%83%60%fb%5f%07%fe%a2");
print md5($param1)."\n";
print md5($param2)."\n";
print md5($param1)===md5($param2);
print "\n";
 ?>
//008ee33a9d58b51cfeb425b0959121c9
//008ee33a9d58b51cfeb425b0959121c9
//1

附件

题目备份

https://github.com/jas502n/2018-QWB-CTF

stream

奇怪的心路~

streamgame3.py

 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==24
# flag共24个字符，形如 /flag{.{18}}/
# 中间18个字符就是我们想寻找的lfsr初始状态

def lfsr(R,mask):
    """定义了一个lfsr的状态变化规则
    输入是寄存器当前存储的状态信息和一个掩码，
    两者经过一定运算得到寄存器下一个状态并输出
    """
    output = (R << 1) & 0xffffff 
    #将当前值左移一位，并舍弃超出 24bit 的部分
    #这就是线性反馈移位寄存器的 `移位` 部分
    #可以理解为 output = (R * 2) % 0xffffff
    i=(R&mask)&0xffffff
    #将当前值和掩码按位与，只使用某些固定位的信息
    #如对于 R3_mask=0x100002 ，只使用当前值左起第四位和右起第二位
    #对比线性函数的定义，发现0x100002的每一位对应的就是f中的a1,a2,...,a24，
    #其中a4=a23=1,a1=a2=a3=a5=...=a22=a24=0
    #而R的每一位对应的是b1,b2,...b24
    #那么 `R&mask` 就将f中用于异或的每一项都求出来并保存在i的每一位中
    #（我认为 `&0xffffff` 是多余的，R和mask都总在24位以内）
    lastbit=0
    # lastbit实际上是函数中的a0
    while i!=0:
        lastbit^=(i&1) 
        i=i>>1
    # 这个循环用于取出i中的每一位并完成异或操作，i中有奇数个1则lastbit为1，反之为0
    # 得到的lastbit就是【寄存器当前状态的线性函数】f的函数值
    # lastbit就是所谓的 `线性反馈` ，它与寄存器当前状态线性相关，
    # 并作为输入位，用以产生寄存器的下一个状态
    output^=lastbit
    # 产生寄存器的下一个状态
    return (output,lastbit)

def single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask):
    """完成三个线性反馈移位寄存器的一次状态变换
    并将三个反馈进行简单运算（x1x2 ^ x2'x3）后返回
    
    --【我现在明白过来了，我在
    http://findneo.github.io/180325QWBWP/#streamgame3
    中提到的一个失败的尝试为什么会失败，：）
    就是因为最后文件中保存的每个bit都只是这个简单运算的结果
    而这个简单的运算导致了每个single_round中反馈的信息
    从3个bit降到了1个bit】--
    """
    (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(tmp1mb)
    f.close()

solution

因为抽头较少，所以生成序列的每一位都只和初始状态的少数几位有关，如果每一轮分开考虑，再手动合并初始状态，遍历集合会小非常多。折腾了很久才发现自己要写的是递归，写了很多代码但是不work🤔，到比赛最后也没调出来。

赛后总算按我的意愿跑起来了，但是马上发现自己太天真，这代码就是跑到爆栈也没办法得到结果，看来还是要认真理解原理，从算法上突破，暴力 x 不可取。下面是我已被证明不可取的想法（我居然在试图攻破安全高效的伪随机序列发生器，真是naive啊）：

 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
49
50
51
52
53
54
55
56
57
58

#coding:utf8
import itertools
# 因为掩码的原因，大大降低了计算的复杂度。我们可以在每次规约运算时只遍历影响结果的位，而忽略其他将被掩码忽略的位。
# 这样实际上复杂度从每一次规约都有2**（17+19+21）=2**57约10**18种可能降低到了每一位约大概2**8种可能！
# 对我来说，编程实现的难点在于如何控制只遍历影响结果的位，一种是在原来的基础上加一个判断，判断是否该情况已被考虑，这应该不合适。
# 另一种就是用一个list装R的每一位
# 再有就是手动组合三个部分的每次反馈
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)) # lastbit=(R.count(1)%2?1:0)  R*右边加一位lastbit

# R1sm means R1_sub_mask
R1_mask=0x10020;R1sm=[];R1sm.extend([0x10000,0x20])
R2_mask=0x4100c;R2sm=[];R2sm.extend([0x40000,0x1000,0x8,0x4])
R3_mask=0x100002;R3sm=[];R3sm.extend([0x100000,0x2])

def genAll(Rsm):
    # 全组合
    all_iter=[itertools.combinations(Rsm,num) for num in xrange(len(Rsm)+1)]
    return itertools.chain.from_iterable(all_iter)

def genBit(sub_mask,seq,mask):
    ret=0
    for i in sub_mask:
        ret|=i
    done=mask
    if seq==0:done=0
    else:
        for i in range(seq):
            done|=(mask>>i)
    ret&=(done^0xffffff)&(0xffffff<<seq)
    return ret

def digui(level,R1,R2,R3):
    if level==996:
        print hex(R1),hex(R2),hex(R3)
        return 0
    for g,h,n in itertools.product(genAll(R1sm),genAll(R2sm),genAll(R3sm)):
        R1|=genBit(g,level,R1_mask)
        R2|=genBit(h,level,R2_mask)
        R3|=genBit(n,level,R3_mask)
        (R1,R2,R3,out)=single_round(R1,R1_mask,R2,R2_mask,R3,R3_mask)
        if out==((ord(f[level/8])>>(7-(level%8)))&0x1):
            digui(level+1,R1,R2,R3)

f=open("output/0").read()
digui(0,0,0,0)

据说是考察快速相关攻击，与WHCTF一题相似，在 https://www.xctf.org.cn/library/details/whctf-writeup/ 搜索Bornpig即可看到相关信息。

我还找到一些相关信息，但暂时没有时间深入解决。

去了解了一下线性反馈移位寄存器，理解一些概念，对代码做了些注释。

  • In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. flip-flop（触发器）或latch（锁存器）都是某种电路，都根据输入改变存储的状态信息，区别是前者当时钟有效时改变才发生，也就是同步的，后者是时钟无关的，也就是异步的。
  • a shift register is a cascade of flip flops 。 移位寄存器是触发器的级联。
  • In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.
    线性反馈移位寄存器是一个移位寄存器，它的输入位是它先前状态的线性函数。
  • 线性指的是齐次性（f(αx) = αf(x) for all α）和可加性（ f(x + y) = f(x) + f(y)），两者在有理数域是等价的。上述定义中的线性函数实际上指的是布尔代数中的线性函数，形式上这样表述： 对于 ，存在 ，使得 ，那么f 是一个线性函数。（其中的符号分别表示逻辑异或和逻辑与 ，详情如下图）

有一位朋友在这篇文章提到一种基于outbit=(x1*x2)^((x2^1)*x3) 从而当x1==x3 时x1==outbit 来略过R2而只爆破R1和R3的做法，我实现了一下，感觉复杂度仍然不可接受。~~

 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

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)

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

import time
s=''.join([bin(ord(i))[2].zfill(8) for i in open("output/0","rb").read()])
def handle1(start,step):
    for i in xrange(start,start+step):
        for j in xrange(2**20,2**21):
            R1,R3,flag=i,j,1
            for offset in xrange(len(s)):
                R1,out1=lfsr(R1,R1_mask)
                R3,out3=lfsr(R3,R3_mask)
                if out1==out3 and out1!=s[offset]:
                    flag=0
                    break
            if flag:
                print "flag{%s******%s}"%(bin(i)[2:],bin(j)[2:])
                print time.asctime()
                exit(0)
        if (i-start)%10==0:
            print start,time.asctime(),"#"
handle1(2**16,2**16)

受他启发，我有了个基于outbit==(x2==1?x1:x3) 爆破的想法，但看起来也不可操作。

投入太多时间了，还是等官方WP吧：）