combinelfsr

点击此处获得更好的阅读体验

---

WriteUp来源

官方WP

题目描述

题目考点

• 非线性反馈移位寄存器的相关攻击

解题思路

可以看到题目中使用了两个线性反馈移位寄存器，使用两个寄存器的初始状态生成了密钥对flag进行了加密。

由于每个状态的范围是 0-2**18

对两个状态一起进行爆破的复杂度是 2**36，是比较困难的。

继续往下看，题目对两个线性反馈移位寄存器的输出进行了combine，构成了一个 非线性反馈移位寄存器结构

def combine(r1,r2,mask1,mask2):
  (r11,x1)=lfsr(r1,mask1)
  (r22,x2)=lfsr(r2,mask2)
   return (r11,r22,(x1*x2)^(x2^1))

并且输出了1024*8个bit的结果。显然是要根据给出的结果去计算两个寄存器的初态。

这里就要用到相关攻击的方法。

我们可以枚举x1, x2,和寄存器输出的所有可能取值

x1 x2 F
0 0 1
1 1 1
0 1 0
1 0 1

我们发现 x1 == F 的概率是75%, x2 == F 的概率是25%

所以我们可以对R1单独枚举，并且用单独的lfsr代替非线性反馈移位寄存器的结果，如果和cipher相同的位数接近75%的话就认为枚举正确，而且题目给出的cipher的数据量足够大，足够在这种大量数据的基础下完成攻击。

同样我们也可以对R2进行枚举。

由于我们是对R1和R2单独枚举的，复杂度为 2 * 2**18，是可以接受的。

还原r1

def solver1():
   for r in range(1,2**18):
       R = r
       s = ""
       for i in range(512):
           tmp = 0
           for j in range(8):
              (R, out) = lfsr(R, mask1)
               tmp = (tmp << 1) ^ out
           s += chr(tmp)
       pb = correlation(s, data[:512])
       if pb > 73:
           print r
           print pb
           return r

得到R1是 13706

还原 r2

def solver2():
   for r in range(1,2**18):
       R = r
       s = ""
       for i in range(512):
           tmp = 0
           for j in range(8):
              (R, out) = lfsr(R, mask2)
               tmp = (tmp << 1) ^ out
           s += chr(tmp)
       pb = correlation(s, data[:512])
       if pb < 27:
           print r
           print pb
           return r

得到R2是90307

解密

还原了R1和R2之后按题目要求生成密钥直接解密即可。

R1 = 13706 # solver1()
R2 = 90307 # solver2()
from hashlib import sha512
import random
from Crypto.Cipher import AES
f = open('flag.txt','rb')
flag = f.read().decode('hex')
f.close()
key = sha512(str(R1)+str(R2)).digest()[:16]
aes = AES.new(key,AES.MODE_ECB)
print aes.decrypt(flag)

Flag

flag{d0b570e1-5292-4381-9d71-d6edab490854}