基于分类搜索与快速变换的流密码攻击算法

陆正福， 杨慧慧， 周宪法

(云南大学 数学与统计学院，昆明 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的流密码被成功破译。