streamgame124最大的特点在于明文空间很小，例如1，密钥长度是19位二进制数，即有52万个可能的结果，对于现代计算机来说，完全可以在短时间内爆破完成，相比思考问题的解法，直接爆破显得更加经济。

stream3就不一样了，一打开发现密钥是18位十六进制，这时候任何爆破都不能奏效了，就得考虑更合适的解法。

这里用的是correlation attack，当一串密钥流是通过多个lfsr独立生成后再通过代数操作结合在一起的时候就可以用这种攻击方式。本质上是一种分治的操作，即把各个密钥单独算出来，首先得观察三个密钥流的结合操作：

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)
# x1 x2 x3 out
#  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
# out is more related to x1 and x3, but not x2

从下面的表格中可以看出，x1、x3和out更加有关联，表现在x1和out同时相等的频率有6/8，而x2只有4/8，约等于随机的二进制组合。因此，r1和r3可以单独通过correlation attack求出来，最后再用brute force找出r2。

# from flag import flag
# assert flag.startswith("flag{")
# assert flag.endswith("}")
# assert len(flag)==24
def lfsr(R, mask):
    output = (R << 1) & 0xfffff

直接爆破

# 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
def encrypt(R):
    ret = ''
    for i in range(12):
        tmp = 0
        for j in range(8):
            (R, out) = lfsr(R, mask)
            tmp = (tmp << 1) ^ out
        ret += chr(tmp)
    return ret
def brute_force():
    with open('key', 'rb') as r:
        cipher = r.read()
    for i in range(2**20, 2**21):
        print i
        if encrypt(i) == cipher:
            raw_input()

flag{110111100101001101001}

StreamGame4

1.本题给了一个加密脚本和一个加密过后的key。

2.脚本将flag做为二进制读入，做为密钥。然后循环1024*1024次，每次循环8次nlfsr函数，将结果变换写入key中。所以可以进行爆破，每次检测key的一位，从第一位开始，如果正确在检测下一位。脚本如下：

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)
f=open("key","rb").read()
mask=0b110110011011001101110
flag = False
for x in range(0,pow(2,27-6)-1):
    R=x
    for i in range(1024*1024):  #此处可以把1024*1024改成一个较小的数
        tmp=0
        for j in range(8):
            (R,out)=nlfsr(R,mask)
            tmp=(tmp << 1)^out
        if f[i]!=tmp:
            break
        elif i==1024*1024-1:   #此处也要同时更改 
            flag=True
            break
    if x%100000==0:
        print('x =',x)
    if flag==True:
        flag=x
        break
print("flag{"+bin(x)[2:]+"}"