基于分類搜索與快速變換的流密碼攻擊算法

陸正福， 楊慧慧， 周憲法

(云南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，昆明 650500)

0 引 言

流密碼是對稱密碼的重要分支，其核心思想是依賴密鑰流生成器產(chǎn)生偽隨機(jī)序列作為密鑰流進(jìn)行實時的加解密。根據(jù)密鑰流生成器的基本組件，對已有常見的基于移位寄存器的流密碼作如下分類：①基于線性反饋移位寄存器(LFSR)的流密碼[1-4]等；②基于非線性反饋移位寄存器(NFSR)的流密碼[5-7]算法等；③基于帶進(jìn)位的反饋移位寄存器(FCSR)的流密碼[8]；④基于LFSR、NFSR、FCSR組合的流密碼。其中，LFSR因結(jié)構(gòu)簡單易實現(xiàn)，僅用簡單異或就可達(dá)到較高安全性的特點，使得以其為基礎(chǔ)的流密碼得到普遍應(yīng)用。此類流密碼的設(shè)計通?；诜蔷€性組合生成器：一般由n個LFSR和1個非線性布爾函數(shù)組成，其中，LFSR用于產(chǎn)生統(tǒng)計特性良好的偽隨機(jī)序列；非線性布爾函數(shù)則用于提高密鑰流的線性復(fù)雜度，保證密碼的安全性。但基于LFSR的流密碼因LFSR的輸出序列與密鑰流之間的統(tǒng)計相關(guān)性使其易遭受已知明文攻擊,即通過截獲的序列對其密鑰進(jìn)行分析，破譯出LFSR的初態(tài)。

常見的攻擊方法中，(快速)相關(guān)攻擊[9-10]利用流密碼體制中LFSR的輸出序列與密鑰流序列之間的統(tǒng)計相關(guān)性實施攻擊，是基于LFSR的流密碼的重要攻擊方法。2000年，Chepyzhov等[11]提出一種簡單有效的快速相關(guān)攻擊，該方法基于最大似然譯碼(MLD)，預(yù)處理階段操作簡單，且不受反饋多項式抽頭數(shù)的限制，譯碼階段采用一步譯碼，窮搜索部分比特位的LFSR初態(tài)，相對于基于卷積碼的快速相關(guān)攻擊算法有更低的空間復(fù)雜度；2003年，Molland等[12]針對該算法提出一種改進(jìn)算法，提出一種快速尋找重量w>2的部分校驗方程的方法；2009年，伍文君等[13]針對基于最大似然譯碼的快速相關(guān)攻擊提出一種改進(jìn)算法，通過采用快速Walsh變換，降低了譯碼階段的時間復(fù)雜度；2017年，劉好莉等[14]對CJS算法提出一種優(yōu)化算法，通過建立數(shù)組縮短校驗方程的尋找時間；2017年，全國高校密碼數(shù)學(xué)挑戰(zhàn)賽賽題二以相關(guān)攻擊中的數(shù)學(xué)問題為主題，給出了相關(guān)數(shù)據(jù)，一批參賽選手在算法改進(jìn)和破譯實踐方面付出了巨大努力，并取得了很好的破譯進(jìn)展。

本文將LFSR的初態(tài)破譯問題轉(zhuǎn)化為(N,L)線性分組碼譯碼問題，并做如下研究工作：

(1) 構(gòu)造FCA-MLD-CS-FWT算法。①尋找校驗方程過程中首次引入分類搜索(CS)策略；②對校驗方程引用快速Walsh變換(FWT)，在譯碼階段對LFSR的狀態(tài)分割，并分別采用最大似然譯碼(MLD)進(jìn)行LFSR初態(tài)的破譯。

(2) 以2017年全國高校密碼數(shù)學(xué)挑戰(zhàn)賽賽題二[15]的數(shù)據(jù)為例對算法進(jìn)行實驗驗證。結(jié)果表明，該算法：①通過靜態(tài)字典的建立可實現(xiàn)重量w=2，窮搜索比特數(shù)B不同的校驗方程的快速搜索；②可大幅降低譯碼階段時間復(fù)雜度；③在單核計算平臺上可實質(zhì)性縮短破譯時間。

1 問題與模型轉(zhuǎn)化

1.1 問題描述

流密碼源自于“一次一密”思想，設(shè)計目的是產(chǎn)生隨機(jī)性較強(qiáng)的密鑰流序列(z0,z1,…,zN-1)以抵抗已知明文攻擊，即通過截獲的密鑰流序列(z0,z1,…,zN-1)破譯出產(chǎn)生該序列的原始密鑰SK。在基于LFSR的流密碼設(shè)計中，SK即LFSR的初態(tài)aI。對基于LFSR的流密碼進(jìn)行已知明文攻擊，即根據(jù)截獲的密鑰流序列破譯出LFSR的初態(tài)。

1.2 模型轉(zhuǎn)化

假設(shè)某一個LFSR的輸出序列：

aI=(a0,a1,…,aL-1)

p=P(ai=zi),i=0,1,…,N

定義(線性分組碼[16])是對L長信息位以一定的規(guī)則增加r=N-L長校驗位組成長為N的序列(碼字)。在二元域中，信息組共2L個，相應(yīng)的碼字也有2L個，所有碼字的集合稱為(N,L)線性分組碼。

圖1 快速相關(guān)攻擊譯碼模型

2 FCA-MLD-CS-FWT算法

2.1 FCA-MLD算法

定理[17]對于無記憶二元對稱信道，最大似然譯碼準(zhǔn)則等價于最小漢明距離準(zhǔn)則。

基于最大似然譯碼的快速相關(guān)攻擊[18]是一種基于部分比特窮舉搜索的新算法。通過模型轉(zhuǎn)化把流密碼的破譯問題轉(zhuǎn)化為線性分組碼的譯碼問題，并將破譯工作分為預(yù)處理和譯碼兩個階段。預(yù)處理階段需根據(jù)截獲的密鑰流序列和LFSR的反饋多項式構(gòu)造相應(yīng)(N,L)線性分組碼的生成矩陣G，并通過G尋找足夠多的校驗方程(由重量w和窮搜索比特數(shù)B決定，包括初態(tài)的B的信息)，由校驗方程的系數(shù)得到校驗矩陣H，此階段操作簡單，且不受反饋多項式抽頭數(shù)的限制。譯碼階段采用無記憶一步譯碼策略，通過窮舉搜索比特數(shù)B實現(xiàn)對LFSR狀態(tài)的分割，構(gòu)造出一個維數(shù)更小的(N2,B)線性分組碼，其中：

(1)

2.2 FCA-MLD-CS-FWT算法

2.2.1 分類搜索策略

采用“分類搜索”策略尋找校驗方程，實現(xiàn)對基于最大似然譯碼的快速相關(guān)攻擊算法預(yù)處理階段的改進(jìn)。即利用映射結(jié)構(gòu)——字典對生成矩陣G中的列向量進(jìn)行分類和存儲以縮小尋找范圍，該算法的時間復(fù)雜度為O(n+nlgn)。為方便后續(xù)計算，將校驗方程的系數(shù)存儲到校驗矩陣H中。具體策略如下：

(1) 分類策略?？紤]G中每一列的最后k(0

(2) 搜索策略。利用字典找到滿足k項均相等的列向量，找出字典中“值”的集合元素個數(shù)≥2的“鍵—值”對，每一次搜索時間復(fù)雜度為O(1)，且生成矩陣G的列數(shù)為N，故最多可分為N類，因此搜索部分總的時間復(fù)雜度為O(n)。

類Python偽代碼如下：

import numpy

def dictionary(G,k)

dic={}

for a in xrange(2):

if a==0:

A=np.where(G[l-k]==0)[0]

else:

A=np.where(G[l-k]==1)[0]

for b in xrange(2):

if b==0:

B=A[np.where(G[l-k+1][A]==0)[0]]

else:

B=A[np.where(G[l-k+1][A]==1)[0]]

…

for w in xrange(2):

if w==0:

W=V[np.where(G[l-k+19][V]==0)[0]]

else:

W=V[np.where(G[l-k+19][V]==1)[0]]

s=‘[‘+str(a)+’‘+str(b)+’‘+str(c)+’‘+str(d)+’‘+str(e)+’‘+str(f)+’‘+str(h)+’‘+str(i)+’‘+str(j)+’‘+str(k)+’‘+str(m)+’‘+str(n)+’‘+str(o)+’‘+str(p)+’‘+str(q)+’‘+str(r)+’‘+str(t)+’‘+str(u)+’‘+str(v)+’‘+str(w)+’]’

dic[s]=W

def Array(G,B)

array1=[]

array2=[]

for i in xrange(60,N):

x= dic[str(G[i,L-B-k:L-B])]

y=np.where((G[i]==G[x]).all(1))[0]

if len(y)>1:

array1.append(tuple(x[y]))

array1=list(set(array1))

array1=np.array(array1)

for x in array1:

if len(x)>2:

for i in xrange(len(x)-1):

for j in xrange(i+1,len(x)):

array2.append([x[i],x[j]])

else:

array2.append(list(x))

array2=np.array(array2)

2.2.2 快速Walsh變換

在譯碼階段對每一個初態(tài)進(jìn)行估計需計算m個校驗方程，而窮搜索比特數(shù)B決定了需要估計的所有初態(tài)共2B種，故譯碼階段時間復(fù)雜度為O(2Bm)。借鑒文獻(xiàn)[27]通過采用Walsh變換降低譯碼階段時間復(fù)雜度的思想，對由分類搜索策略得到的校驗方程采用快速Walsh變換，得到長度為2B的數(shù)組：

(2)

通過該步驟可大幅降低譯碼階段時間復(fù)雜度。其中對校驗方程分組階段共需m次計算，對f(i)做快速Walsh變換階段共需2BB次計算，改進(jìn)后時間復(fù)雜度為O(2BB+m)。類Python偽代碼如下：

import sys

import gc

import numpy

from sage.all import *

from sage.crypto.boolean_function import BooleanFunction

def Fx( )

f=np.random.randint(0,2,2**30,dtype=int).tolist()

F = BooleanFunction(f)

F.walsh_hadamard_transform()

2.2.3 FCA-MLD-CS-FWT算法描述

通過分類搜索策略和快速Walsh變換構(gòu)造流密碼的攻擊算法FCA-MLD-CS-FWT，分為預(yù)處理和譯碼兩個階段。預(yù)處理階段是通過二元域上的本原特征多項式g(x)生成矩陣G：

g(x)=1+cL-1x+cL-2x2+…+c1xL-1+xL

(3)

滿足遞歸關(guān)系式：

aL=c1aL-1+c2aL-2+…+cL-1a+1

(4)

import sys

import gc

import numpy

from sage.all import *

from sage.crypto.boolean_function import BooleanFunction

A=np.eye(L,h=1,dtype=int)

C=np.zeros((L,),dtype=int)

for i in [系數(shù)不為0的項]:

C[i]=1

E=np.eye(L, dtype=int)

G=np.zeros((N,L),dtype=int)

for i in range(0,L):

G[i,]=E[i,]

G[L]=C

for i in range(L+1,N):

if(G[i-1][L-1]==1):

G[i]=G[i-1].dot(A)+C

else:

G[i]=G[i-1].dot(A)

G[i]=np.mod(G[i],2)

G=np.transpose(G)

dictionary(G,k)

def Array(G,B)

def Fx( )

3 實驗及分析

根據(jù)算法FCA-MLD-CS-FWT對流密碼進(jìn)行已知明文攻擊實驗并分析。以2017年全國高校密碼數(shù)學(xué)挑戰(zhàn)賽賽題二的數(shù)據(jù)[21]為例，已知信息如下：

ai+60=ai+57⊕ai+51⊕ai+44⊕ai+25⊕

ai+23⊕ai+13⊕ai+4⊕ai

(5)

其中，ai∈{0,1},i≥0。

(6)

計算上述實例的生成矩陣G，耗時約40 s，空間占用約915 MB，該矩陣僅需計算1次。

實驗結(jié)果表明：

(1) 當(dāng)校驗方程重量w=2時，采用不同搜索策略尋找校驗方程的實驗耗時如表1所示。從中可以看出，采用分類搜索策略可降低預(yù)處理階段時間復(fù)雜度，縮短實驗耗時。

表1 不同搜索策略時間對比

(2) 當(dāng)參數(shù)取w=2,B=30時，對12組實例分別采用文獻(xiàn)[11]和本文FCA-MLD-CS-FWT算法(算法5)進(jìn)行譯碼，每組實例平均譯碼耗時見表2。從表中可以，看出對校驗方程引用快速Walsh變換可有效減少譯碼階段耗時，降低時間復(fù)雜度。

表2 譯碼時間對比

4 結(jié) 語

將基于線性反饋移位寄存器的流密碼分析問題轉(zhuǎn)化為線性分組碼的譯碼問題并提出算法 FCA-MLD-CS-FWT，進(jìn)行實驗驗證分析。首次引入分類搜索策略尋找校驗方程；并對校驗方程引用快速Walsh變換，大幅降低了譯碼階段的時間復(fù)雜度。實驗表明：當(dāng)截獲序列長度N≥3 680 605，相關(guān)概率p=P(ai=zi)≥0.63時，通過調(diào)整參數(shù)B、w，算法FCA-MLD-CS-FWT可于單核計算平臺上在1 h左右破譯出階(原始密鑰長度)L=60的LFSR的初態(tài)，即基于該LFSR的流密碼被成功破譯。