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

陸正福， 楊慧慧， 周憲法

(云南大學 數學與統計學院，昆明 650500)

0 引 言

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

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

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

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

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

1 問題與模型轉化

1.1 問題描述

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

1.2 模型轉化

假設某一個LFSR的輸出序列：

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

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

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

圖1 快速相關攻擊譯碼模型

2 FCA-MLD-CS-FWT算法

2.1 FCA-MLD算法

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

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

(1)

2.2 FCA-MLD-CS-FWT算法

2.2.1 分類搜索策略

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

(1) 分類策略。考慮G中每一列的最后k(0

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

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

(2)

通過該步驟可大幅降低譯碼階段時間復雜度。其中對校驗方程分組階段共需m次計算，對f(i)做快速Walsh變換階段共需2BB次計算，改進后時間復雜度為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變換構造流密碼的攻擊算法FCA-MLD-CS-FWT，分為預處理和譯碼兩個階段。預處理階段是通過二元域上的本原特征多項式g(x)生成矩陣G：

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

(3)

滿足遞歸關系式：

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 [系數不為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 實驗及分析

根據算法FCA-MLD-CS-FWT對流密碼進行已知明文攻擊實驗并分析。以2017年全國高校密碼數學挑戰賽賽題二的數據[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次。

實驗結果表明：

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

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

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

表2 譯碼時間對比

4 結 語

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