[Crypto] combinelfsr - K1rit0

xp0int Posted on Apr 29 2021

一道lfsr
审计代码可以知道要解出flag只需要还原回R1和R2就行了

题目所给的输出是两个寄存器输出$(X_1,X_2)$的combine, 但是这个combine存在缺陷, 当输出为0的时候, 只有一种情况$X_1 = 0 , X_2 = 1$

再看R1,R2, 都是18位的, 那么要还原回初始的状态也就是R1和R2, 只需要各自的前18位输出就行了
但现在所得到的输出是combine以后的, 可以尝试爆破R1和R2各自的前18位输出来还原R1和R2
但是这样就需要爆破$2^{36}$次 显然不可能(~~说实话后面算出结果发现R1和R2都很小 跑个半天估计真可以~~

而combine的前18位输出里面有7个0, 利用最开始说的缺陷可以得到R1和R2分别的前18位输出的7位

那么爆破的次数变为$2^{36-7-7=22}$大概400万次,十多分钟就行了

## 脚本
```python
from Crypto.Cipher import AES
from hashlib import sha512

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 relfsr(out18,mask):
    i = 17
    R = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    while i >= 0:
        guess = '0'+out18[0:17]
        (_,out) = lfsr(int(guess,2),mask)
        if out == int(out18[17]):
            out18 = '0'+out18
            R[i] = '0'
        else:
            out18 = '1'+out18
            R[i] = '1'
        i -=1
    return int(''.join(R),2)

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

enc_flag = 'b5bc56c17db4a7d898ce63652d3656572e4f5b6757fccef8d8d3a32dc60bfc972d40f061f3a7154f7975d5126b052dad'.decode('hex')
c = '110011001101111010111101100111101111'

guess_R1_out = '{}{}00{}{}00{}{}0{}{}{}{}0{}0'
guess_R2_out = '{}{}11{}{}11{}{}1{}{}{}{}1{}1'

mask1 = 0x30517
mask2 = 0x25b74

# for x in range(0,2049):
#     Sx = bin(x)[2:].zfill(11)
#     guess_R1_out_fill = guess_R1_out.format(Sx[0], Sx[1], Sx[2], Sx[3], Sx[4], Sx[5], Sx[6], Sx[7], Sx[8], Sx[9], Sx[10])
#     # print x
#     for y in range(0,2049):
#         Sy = bin(y)[2:].zfill(11)
#         guess_R2_out_fill = guess_R2_out.format(Sy[0],Sy[1],Sy[2],Sy[3],Sy[4],Sy[5],Sy[6],Sy[7],Sy[8],Sy[9],Sy[10])
#
#         R1 = relfsr(guess_R1_out_fill,mask1)
#         R2 = relfsr(guess_R2_out_fill,mask2)
#
#         tmp = ''
#         _R1 = R1
#         _R2 = R2
#         for i in range(36):
#             R1, R2, out = combine(R1, R2, mask1, mask2)
#             tmp += str(out)
#
#         if tmp == c:
#
#             print _R1,_R2

'''
    上方的爆破得到可能的R1 R2
    67277 18664 x
    13706 69013 x
    13706 90307
    213551 26434
    128326 90307
    128326 63265
    210610 90307
    16663 123756
    194174 90307
'''

R1 = 13706
R2 = 90307
key = sha512(str(R1) + str(R2)).digest()[:16]
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(enc_flag)
print flag

```

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

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