[Crypto] Streamgame3 - CirQ

xp0int Posted on Mar 27 2018

? crypto ? ? Burteforce ?

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

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

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

```python
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。

```python
# 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)
# 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

# R1 = int(flag[5:11], 16)    # bin len 17
# R2 = int(flag[11:17], 16)   # bin len 19
# R3 = int(flag[17:23], 16)   # bin len 21
R1_mask = 0x10020 # masks are the connection polynomial
R2_mask = 0x4100c
R3_mask = 0x100002
intercept = 64

def encrypt(R1, R2, R3):
    ret = ''
    for i in range(intercept):
        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
        ret += chr(tmp)
    return ret

with open('output/0', 'rb') as r:
    cipher = r.read(intercept)

def single_lfsr(R, mask):
    ret = ''
    for i in range(intercept):
        tmp = 0
        for j in range(8):
            (R, out) = lfsr(R, mask)
            tmp = (tmp << 1) ^ out
        ret += chr(tmp)
    return ret

def correlation(A, B):
    assert len(A) == len(B)
    N = intercept * 8
    d = 0
    for a, b in zip(A, B):
        for i in range(8):
            mask = 1 << i
            if ord(a)&mask == b&mask:
                d += 1
    return d / N

def guess1():
    possible, max_p = 0, 0.0
    for r1 in range(2**16, 2**17):
        u1 = single_lfsr(r1, R1_mask)
        p = correlation(u1, cipher)
        if p > max_p:
            possible, max_p = r1, p
        print(r1, p)
    print(hex(possible), max_p, intercept) # 0x1b9cb 0.7529296875 128bytes

# this function not work, since x2 is less related to out
def guess2():
    possible, max_p = 0, 0.0
    for r2 in range(2**18, 2**19):
        u2 = single_lfsr(r2, R2_mask)
        p = correlation(u2, cipher)
        if p > max_p:
            possible, max_p = r2, p
        print(r2, p)
    print(hex(possible), max_p, intercept)

def guess3():
    possible, max_p = 0, 0.0
    for r3 in range(2**20, 2**21):
        u3 = single_lfsr(r3, R3_mask)
        p = correlation(u3, cipher)
        if p > max_p:
            possible, max_p = r3, p
        print(r3, p)
    print(hex(possible), max_p, intercept) # 0x16b2f3 0.734375 64bytes

def brute_force():
    for r2 in range(2**18, 2**19):
        g = encrypt(0x1b9cb, r2, 0x16b2f3)
        print r2
        if g == cipher:
            raw_input() # 0x5979c
guess1()
guess3()
brute_force()
```
**flag{01b9cb05979c16b2f3}**

打赏还是打残，这是个问题