未完成的流密码

希望自己对流密码有个初步的认识吧😊，也是在学习的过程中逐渐认识到自己的不足，很多知识需要反复琢磨呀。

LCG

线性同余方法是个用来产生随机数的方法，公式如下：

$$\begin{aligned} N_{k+1}=A*N_k+B \pmod M \end{aligned}$$

乘数A,常数B,模数M在产生过程中都是给定的

一般地，会给出初始seed，也就是[N_0]，然后根据公式产生一系列伪随机数。

这样的随机数并不安全，因为一旦我们知道了其中的某些值，就可以进行攻击。

题型一：已知A,B,M,N_0

根据公式，能求出来所有后面产生的随机数

题型二：已知A,M,N_0,N_1

根据公式先求出B，得到B后转化为题型一

$$\begin{aligned} B=N_{1}-A*N_0 \pmod M \end{aligned}$$

b = (seq[1] - a * seq[0]) % m

题型三：已知M,N_0,N_1,N_2

$$\begin{aligned} N_{1}=A*N_0+B \pmod M (1)式\\ N_{2}=A*N_1+B \pmod M (2)式 \end{aligned}$$

(1)-(2)约去B得到A=(N_1-N_2)(N_0-N_1)^{-1}%M,然后转化成题型二

t = []
    for i in range(1, len(seq)):
        t.append(seq[i] - seq[i-1])
a = inverse(t[0], m) * t[1] % m

题型四：已知N_0,N_1,N_2,N_3,N_4,N_5

A * (N_0-N_1)=(N_1-N_2)%M (1)式

A * (N_1-N_2)=(N_2-N_3)%M (2)式

令t_i=N_i-N_{i+1}

有At_0=t_1%M, A t_1=t_2%M,

A t_0 t_2 =A t_1 t_1%M

两边同时约掉A，得到

t_2 t_0-t_1 t_1=k *M,

t_3 t_1-t_2 t_2=k *M.

上下两式求最大公约数gcd()得到M，然后转化为题型三，

由此我们看出，乘数A,常数B,模数M三数未知率越大，需要的连续随机数就越多，

而题型四中N_0也可以不是最初给出的seed,只要是一系列连续的随机数(至少4个)，我们都可以用这个方法。

前四个题型WP总结：

from Crypto.Util.number import *

def cal_LCG_m(seq):
    t = []
    for i in range(1, len(seq)):
        t.append(seq[i] - seq[i-1])

    T = []
    for i in range(1, len(t) - 1):
        T.append(t[i+1] * t[i-1] - t[i] ** 2)

    m = []
    for i in range(len(T)-1):
        mm = GCD(T[i], T[i+1])
        if isPrime(mm):
            m.append(int(mm))
        else:
            for i in range(1,100):
                if isPrime(mm // i):
                    mm = mm // i
                    m.append(int(mm))
                    break
    return m

def cal_LCG_a_b(seq, m):
    t = []
    for i in range(1, len(seq)):
        t.append(seq[i] - seq[i-1])
    a = inverse(t[0], m) * t[1] % m
    b = (seq[1] - a * seq[0]) % m
    return (a, b)

seq = []
m_poss = cal_LCG_m(seq)
print(m_poss)

m = m_poss[0]
a, b = cal_LCG_a_b(seq, m)

print((a, b, m))

题型五：生成随机数公式的变换

def generate(self):
self.seed = (self.a * self.seed + self.b) % self.m
self.seed = (self.a * self.seed + self.b) % self.m
return self.seed

比如这个，它使用了两次[N_{k+1}=A*N_k+B \pmod M]进行累乘

我们由此能推算出新公式

[N_{k+1}=A*N_k+B \pmod M]

$$\begin{aligned} N_{k+2}=A*N_{k+1}+B \pmod M\\ & =A*(A*N_k+B)+B\\ &=A^2*N_k+B*(A+1)\\ \end{aligned}$$

​ 而output给出了5个随机数，转换成题型四

对于算得的m列表，对它进行遍历看有符合条件的没

for i in m:
    a = gmpy2.invert(t[0],i) * t[1] % i
    b = output[1] - a*output[0] % i
    a_ = gmpy2.invert(a,i)

    seed = a_ * (output[0]-b) % i
    for _ in range(2**16):
        seed = a_ * (seed - b) % i
        flag = long_to_bytes(seed)
        if b'NSSCTF' in flag:
            print(flag)

题型六：给出seed高位

$$\begin{aligned} &N_{k+1}=A*N_k+B \pmod M\\ &将N_k写成高低位相加的形式，有N_k=H_k+L_k\\ &H_{2}+L_{2}=A*(H_1+L_1)+B \pmod M\\ &L_{2}=A*L_1+(A*H_1+B-H_2) \pmod M (1)式 \\ &H_{3}+L_{3}=A*(H_{2}+L_{2})+B \pmod M\\ ​ & =A*(H_{2}+A*L_1+(A*H_1+B-H_2))+B \pmod M\\ & L_3 =A^2*L_1+A*(A*H_1+B-H_2)+A*H_2+B-H_3 \pmod M (2)式\\ &以下规整过程参考Dexterjie师傅\\ &令B_1=A*H_1+B-H_2,B_2=A*B_1+A*H_2+B-H_3\\ &有(1)式变为L_{2}=A*L_1+B_1 \pmod M\\ &有(2)式变为L_{3}=A^2*L_1+B_2 \pmod M\\ &因而有L_i=A^{i-1}*L_1+B_{i-1}\pmod M (3)式\\ &其中B_i=A*B_{i-1}+A*H_2+B-H_{i+1}(i>1,A_i=A^{i-1}(i>1),\\ &将(3)式子转成L_{i+1}=A_{i}*L_1+B_{i}+k_i* M \end{aligned}$$

取系数L_1,1,K_i并构建格子

$$\begin{aligned} \begin{pmatrix} k_1&k_2&...&k_n&L_1&1 \end{pmatrix} * \begin{pmatrix} M&0&...&0&0&0\\ 0&M&...&0&0&0\\ 0&0&...&M&0&0\\ A_1&A_2&...&A_n&1&0\\ B_1&B_2&...&B_n&0&K\\ \end{pmatrix} = \begin{pmatrix} L_2&L_3&...&L_{n+1}&L_1&K \end{pmatrix} \end{aligned}$$ $$\begin{aligned} 然后调整K值，算一下规约到格里的向量的长度\\ 与\sqrt {n+2}*delta(L)^{1/(n+2)}值进行比较,直到符合条件。 \end{aligned}$$

抄下Dexterjie的脚本

from Crypto.Cipher import AES
from Crypto.Util.number import *

a =  731111971045863129770849213414583830513204814328949766909151
b =  456671883153709362919394459405008275757410555181682705944711
m =  666147691257100304060287710111266554526660232037647662561651
c =  [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]

h = [0] + c

length = len(h)
for i in range(length):
    h[i] <<= 64

A = [1]
B = [0]

for i in range(1, len(h)-1):
	A.append(a*A[i-1] % m)
	B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)

A = A[1:]
B = B[1:]



Ge = Matrix(ZZ,length,length)

for i in range(len(A)):
    Ge[i,i] = m
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]

K = 2**64
Ge[-2,-2] = 1
Ge[-1,-1] = K

for line in Ge.LLL():
    if abs(line[-1]) == K:
        L1 = line[-2]
        seed1 = h[1] + L1
        seed = (seed1 - b) * inverse(a,m) % m
        print(f"seed = {seed}")
        print(long_to_bytes(seed))

Many-Time-Pad攻击

加密时使用简单的异或操作，对不同的明文，取相同长度的key进行异或，得到密文，

$$M_1 \oplus key_1=C_1\\ M_2 \oplus key_2=C_2\\ ...\\ M_n \oplus key_n=C_n$$

上述加密过程被称为一次一密(One-Time-Pad),这样产生的一次性密码本是完全安全的。

但是在现实中，几乎没有人使用一次性密码本，因为它是一种非常不实用的密码，

最大的问题在于密钥的分发，接受者Bob收到了Alice发来的密文，Bob要想进行解密，就必须使用和Alice进行加密时相同的密钥，因此Alice也必须将密钥发送给Bob，且两者长度相等，然而这就产生了一个矛盾—如果有一种方法能将密钥安全地发送出去，那么岂不是也可以用同样的方法来安全地发送密文了吗？

而多次一密(Many-Time-Pad)描述的则是—Alice造一个比较长的密钥，然后非常秘密地告诉Bob。Alice 每次向 Bob 发送信息，都把明文异或上这个约定好的字符串；Bob 收到信息之后，把密文异或上 key, 于是就可以拿到明文。整个过程多次使用了同一个密钥。

MTP是非常不安全的，由于异或运算具有良好的性质：结合律、交换律、逆元为其自身。

因为

$$C_1\oplus C_2=(M_1 \oplus key)\oplus (M_2 \oplus key)=(M_1\oplus M_2)\oplus key \oplus key=M_1\oplus M_1$$

当得到多个明文C_i的异或同时，我们实际上也得到了多个密文M_i的异或

看题

25030206463d3d393131555f7f1d061d4052111a19544e2e5d54
0f020606150f203f307f5c0a7f24070747130e16545000035d54
1203075429152a7020365c167f390f1013170b1006481e13144e
0f4610170e1e2235787f7853372c0f065752111b15454e0e0901
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a1855
0909075412132e247436425332281a1c561f04071d520f0b1158
4116111b101e2170203011113a69001b47520601155205021901
041006064612297020375453342c17545a01451811411a470e44
021311114a5b0335207f7c167f22001b44520c15544801125d40
06140611460c26243c7f5c167f3d015446010053005907145d44
0f05110d160f263f3a7f4210372c03111313090415481d49530f

首先可以看看C_1异或上其它C_i会得到什么

....S....N.U.....A..M.N...
...Ro..I...I....SE....P.I.
.E..H...IN..H...........TU
..A.H.R.....E....P......E.
...RT...E...M....M....A.L.
d...V..I..DNEt........K.DU
.......I....K..I.ST...TiS.
.....f...N.I........M.O...
.........N.I...I.S.I..I...
....P....N.OH...SA....Sg..

观察发现有很多字母是大写英文字母

由于ASCII码表有重要的性质

1. 0x20 是空格。 低于 0x20 的，全部是起特殊用途的字符； 0x20~0x7E 的，是可打印字符

2. 0x41~0x5A 是大写字母 A-Z； 0x61~0x7A 是小写字母 a-z

发现一个规律为：小写字母 xor 空格，会得到对应的大写字母；大写字母 xor 空格，会得到小写字母

所得到异或后英文字符在异或前的M_1，M_i中二者有一很有可能是空格，

假设此英文字符出现在异或后字符串的第m列,那么M_1的第m个字符可能是空格

$$M_m=M_1 \oplus M_m\oplus M_1=M_1\oplus M_m\oplus0x20$$

因而得到密文的第m列的所有字符。

最后要求得到key，利用异或的性质,就得到

$$M_1 \oplus C_1=key$$

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False


def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)


dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

* Lazzaro @ https://lazzzaro.github.io**LFSR**

LFSR

定义：

线性反馈移位寄存器是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。

FSR是流密码产生密钥流的一个重要组成部分，在GF(2)上的一个n级FSR通常由n个二元(只有0和1)存储器和一个反馈函数组成。

反馈函数如下：

$$a_{i+n}=\sum_{j=1}^{n} c_j*a_{i+n-j}=c_1a_{i+n-1}+c_2a_{i+n-2}+....+c_{n-1}a_{i+1}+c_na_{i+0}$$

​

此时反馈函数f(a1,a2…..an)=[c_1a_n⊕c_2a_{n−1}⊕⋯⊕c_na_1]为线性函数

运动过程：

初始状态 a1,a2,………an

将其投入线性函数[a_{n+1}=c_1a_n+c_2a_{n−1}+⋯+c_na_1]后输出[a_{n+1}]

寄存器储存内容依次向右移位，

此时状态变为a2,a3……[a_{n+1}]，并且输出序列输出a1

依次类推，

对于n级线性反馈移位寄存器，存在最长周期为[2^n-1](排除全0)，达到最长周期的序列一般称为m序列

同时经过投入线性函数过程的输出序列满足

​

e.g.

对于5级线性反馈移位寄存器，其最长周期为[2^5-1]

如果我们知道反馈函数f(a1,a2…..a5)=a1⊕a4

即下一个输出a6=a1⊕a4,

我们可以推出[a_n=a_{n-5}⊕a_{n-2}]

因而推出后面的输出。

根据已知长度为2n的序列推出LFSR的反馈表达式：

假设已知的序列为a1,a2,….[a_{2n}]

令S1=(a1,…,an)

​ S2=(a2,…,[a_{n+1}])

​ ……..

​ [S_{n+1}]=([a_{n+1}],…,[a_{2n}])

构造矩阵X=([S1^T,…Sn^T])

[S_{n+1}]=(cn,…,c1)*X

(cn,…,c1)=[S_{n+1}*X^{-1}]

(c1,…cn就是反馈函数的系数)

就能求出反馈表达式

(如果给出序列长度不是2n，可以尝试猜测未给出的几个值)

求初始种子：

由于LFSR是一个线性变换，我们就可以的值这个线性变换是

补：i+1的由来：

(从i+n-1到i+n经历（i+n-(i+n-1)=1)次转换，那么从n-1到n+i就经历（n+i-(n-1)=i+1)次转换）

而我们上面已经求得（c1,c2,…cn)，就能求出初始种子了。

题目：[CISCN 2018]oldstreamgame

flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    #output为R左移一位并且初始化了lastbit=0
    i=(R&mask)&0xffffffff
    #i为R和mask进行按位与操作：只有同时为1才输出1，其他输出为0
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        #i&1用来提取i的不等于0的有效最低位
        #从i的最低位到最高位依次做异或操作然后赋值给lastbit
        i=i>>1
    output^=lastbit 
    #将output变量的最后一位设置为lastbit变量的值
    return (output,lastbit)

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

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

分析LFSR

i=(R&mask)&0xffffffff
lastbit^=(i&1)

R与mask进行按位与运算的到i,mask从右往左数只有第3、5、8、12、20、27、30、32这几位为1，其余位均为0，当且仅当R的第3、5、8、12、20、27、30、32这几位也出现1的时候i会出现1，否则i全都是0；

最新一位lastbit的值是由i的最低位到最高位依次异或运算得到的，（相当于经过f(a1,a2…..an)=[c_1a_n⊕c_2a_{n−1}⊕⋯⊕c_na_1]这个函数）

所以lastbit的值只和i中1的个数有关，也就是与mask中1的个数有关，若mask中由奇数个1，按位异或后的结果为1，如果有偶数个1，那么结果为0，(也就是说只和第3、5、8、12、20、27、30、32位异或后的结果有关)

那就得出：

倒推R:

当R左移31位时（最高位即第32位为R的第一位），根据上式可以得出[lastbit_{32}=lastbit_3+lastbit_5+lastbit_8+lastbit_{12}+lastbit_{20}+lastbit_{27}+lastbit_{30}+R_1]

上式中+为⊕

依次类推得到R的值

mask = '10100100000010000000100010010100'
key = '00100000111111011110111011111000'

tmp=key

R = ''
for i in range(32):
    output = '?' + key[:31]
    ans = int(key2[-1-i])^int(output[-3])^int(output[-5])^int(output[-8])^int(output[-12])^int(output[-20])^int(output[-27])^int(output[-30])
    R += str(ans)
    key = str(ans) + key[:31]

R = format(int(R[::-1],2),'x')
flag = "flag{" + R + "}"
print flag

题目：2018 强网杯 streamgame1

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

为了加深印象再来分析一遍。

第一步：

首先给出output为初始R左移一位并将最低位初始化为0，然后对R和mask进行按位与操作，根据给出的mask值，推测当且仅当R的第3,4,5,9,13,14,17,19位出现1的时候i才出现1.

第二步：

下面的while循环给出latbit和i的从低到高位异或的结果，每次循环后i向右移动一位，即改变它的最低位，然后将lastbit与这个有效最低位(最低位是1的时候参与循环)依次进行异或，所以lastbit的值取决于i中1的个数即R中1的个数，当R中1的个数是奇数的时候，lastbit异或后为1；当为偶数时，lastbit异或后为0，总之,lastbit的值与R的第3,4,5,9,13,14,17,19位异或后的结果有关。

第三步：

那么我们就能得到这个LFSR反馈机制，有关系式

[lastbit=R_3⊕R_4⊕R_5⊕R_9⊕R_{13}⊕R_{14}⊕R_{17}⊕R_{19}]

我们假设此时R已经左移了31位，根据已知的key中[lastbit_{32}-lastbit_{32}]和上式能得到每一个R，进而恢复flag

LCG | DexterJie’Blog

流密码 | Lazzaro

Many-Time-Pad 攻击

反馈移位寄存器 - CTF Wiki

​