基于GPU的密文分组随机链接加密模式的研究*

2015-03-27 07:06吴伟民李坚锐林志毅
计算机工程与科学 2015年1期
关键词:明文密文密钥

吴伟民, 李坚锐,林志毅

(广东工业大学计算机学院,广东 广州 510006)

基于GPU的密文分组随机链接加密模式的研究*

吴伟民, 李坚锐,林志毅

(广东工业大学计算机学院,广东 广州 510006)

大部分传统的分组加密模式不能有效应用于GPU上。分析传统加密工作模式,结合GPU并行计算的要求提出一种满足GPU执行要求的、高效的、安全的分组加密模式——密文分组随机链接加密模式(RCBC)。该模式不但执行效率高,并且增加了破解难度。实验结果表明,在CPU_GPU上采用RCBC的密码算法在处理数据时,呈现出高效的处理能力。

GPU;数据加密;工作模式

1 引言

自1999年NVIDIA发布第一款GPU(Graphic Processing Unit)以来,GPU的发展一直保持很高的速度,随着以CUDA(Compute Unified Device Architecture)为代表的GPU通用计算API(Application Programming Interface)的普及,GPU在计算机中的作用将更为重要,GPU的含义已经从图形处理器扩展为通用处理器(General Purpose Unit)。利用GPU的强大计算能力,能为大数据的处理提供新的解决方案[1]。

随着信息时代的发展,数据安全也越显重要,其中对数据进行保护的重要手段是进行加密,但是在明文与密文的转换过程中,需要大量的运算。当对大量数据加解密时,对CPU提出较高的要求。因此,将加密解密过程中最耗时间的部分交给GPU完成,能有效提高加密的效率。国内外对运用GPU加速密码算法做了大量研究,朱兴锋[2]提出基于GPU的高效IDEA加密算法的实现,Addison W[3]提出AES在GPU上的实现,随后叶剑等人[4]也提出基于GPU的AES快速实现,以上研究都表明GPU能对密码算法进行有效加速。但是,它们都是针对具体的分组密码算法而言的,缺少对CPU_GPU协处理下分组密码工作模式的深入描述。

分组密码工作模式是利用分组密码解决实际问题的密码方案,好的模式可以弥补分组密码的缺陷,不好的工作模式可能带来隐患。大部分传统分组加密模式不能有效应用于GPU上。虽然电子密码本ECB(Electronic Codebook)模式能在保持密码学特征的同时易于并行实现,但众所周知,ECB对分组重放等攻击缺乏高强度的抵御能力[5],所以对于大数据量的加密更适合采用其它模式,其中密码分组链拉CBC(Cipher-Block Chaining)是最为常用的工作模式,但由于其串行的特性,无法有效应用于并行体制上。殷新春[6,7]在CBC基础上提出并行的PCBC(Parallel CBC)模式,通过模运算实现块间的并行,但其安全性依赖于对n的保密,并且缺乏灵活性,运用该模式难以发挥GPU与CPU协处理的优势。而关于CPU_GPU下的分组密码模型研究少之又少。因此,本文在CBC的基础上,根据CPU_GPU协处理下的各自特征提出分组随机链接模式RCBC(RandomCipher-BlockChaining)。

2 相关知识

2.1 GPU编程

现代的图像处理器(GPU)把数据并行计算引入到几乎每台计算机中。这些处理器有能力加速很多应用程序,而不仅仅局限于实时渲染。其中,GPU的编程模型与CPU的编程模型完全不同,GPU使用的是SIMT模型,该编程模型的主要目标之一是高效计算。SIMT的好处是无需开发者费力把数据凑成合适的矢量长度,同时SIMT允许每个线程有不同的分支。在这种编程模型中,对数据流的连续操作便是程序,当对一个处理器编程时,将以更加结构化的方式访问存储器。而由于在一个流元素上的计算不会影响其他元素的计算,所以保证了这种数据的并行性。模型所给予的数据并行性使得GPU的处理速度能比串行处理器快很多。文献[1]给出了GPU编程的参考内容。

2.2 分组密码模式

(1)分组密码(BlockCipher)是一种对称密钥密码[8],它的特点是将明文分为多个等长的组,并用相同的密钥对每组分别进行加密与解密,其中典型的加密算法有DES和AES等,不同的分组密码算法又可以配合不同的工作模式。

(2)电子密码本(ECB)是使用分组密码的最简单方式,加密方式为:yt=Ekey(xi),对应解密过程为:xi=Dkey(yi)。各组可以独立进行加解密而不相互干涉。ECB可以在GPU上完美地执行,但是ECB过于简单,不能很好地隐藏明文的模式,所以夏春林等人[9]在GPU上实现AES时,采用改进的ECB模式,在进行密码运算前采用序列消除明文中相同的数据区域。

(3)密码分组链接(CBC)是一种基于反馈机制的分组模式。前一个分组的加密结果被反馈到当前分组的加密中。具体如下,从一个初始加密参数项IV开始,定义y0=IV,然后使用下式构造y1~yt:

yi=Ekey(xi⊕yi-1),i≥1

(1)

解密过程:

y0=IV,xi=Dkey(yi)⊕yi-1,i≥1

(2)

简单地来说,每一组被用来修改下一组的加密,每组的密文不仅依赖于产生它的明文组,而且依赖于前面所有的明文分组。虽然CBC增加了密文复杂程度,使得攻击难以实施,但是由于该模式中组与组间存在数据相关性,导致无法并行处理各组。因此,将应用CBC模式的密码算法运行于GPU环境下,其效率极低,本文实验章节将给出相关数据。

(4)其他模式。输出反馈OFB(Output Feed Back)以及密码反馈CFB(Cipher Feed Back)与CBC类似,这些模式为了增加密码的安全性均在组与组之间形成依赖关系,从而无法在并行机制下实现,文献[10]给出了相关描述及近年来的研究现状。

3 密文分组随机链接加密模式设计与实现

RCBC是在CBC加密模式的基础上,针对CPU_GPU协处理的特征,在CPU上运用伪随机算法产生随机的链接表(Tr)及向量表(TIV),再将大量需处理的数据传入GPU中进行快速加密,发挥CPU与GPU的各自优势。

3.1 拆分

与传统的分组加密模式相同,明文以及密文进行加解密前都需要进行分组,每组大小为64位或者128位。设想把每组当作是单独的节点,那么CBC可以看作成链式结构的模型,其特性是后一个节点依赖于前一个节点。前后节点的依赖性决定了CBC只能串行地处理,因此对链式结构进行拆分至关重要。规律性地切断原节点间的关系,生成多个分链,并且各个分链使用独立的VI加密参数项作为新的输入,使分链间相互独立,从而分链能被并行处理。

若拆分后分链的长度均为K,则称该种拆分方式为等长拆分。当K=1时,拆分的CBC模式与ECB模式的差异在于VI加密参数项的输入。如图1所示,是将原来的链式等长地拆分成三个节点为一个分链的例子。

Figure 1 Isometric splitting

通过拆分,使得CBC满足了并行计算的要求,同时有效地防止了错误的扩散和传播。需注意的是,使用过短的等长拆分方式,明文中重复的内容在密文中会有所体现,仍难以抵抗相关攻击[11]。因此,本文采用非等长及随机的拆分方式,并用以下方式实现。

3.2 随机链接

RCBC采用非等长的拆分,即拆分后的分链长短各异,避免等长拆分所产生的规律性。但是,这会导致各分链计算规模大小不一致的问题,为了保证并行时任务完成时间相近,避免短板效应带来的影响,分链中节点数目必须得到有效限制。设分链的最大链接节点数为Kmax(Kmax> 0),通过设定分链中的节点数必须小于或等于Kmax来限制分链中拥有的节点,解决由于并行计算粒度粗细差异而产生的效益问题。由定义可知,当Kmax越小,分链的平均长度也越小,利于整体的并行计算。

为了增加该方案的复杂性,组成分链的节点成员是随机产生的,分链中的节点在原链式中可以是连续的或者是间隔的,这取决于具体采用的链接规则。本文采用随机链接表(Tr)实现具体的链接规则,根据随机链接表决定节点间链接关系,并约定采用连续的节点作为分链成员。具体如下,从多组初始加密参数项IV开始,定义y0=IV0,…,yk=IVk(k为未知量),然后使用下式构造y1~yt:

yi=Ekey(xi⊕R),i≥1

(3)

R=Tr(i)=yi-1orIVk

(4)

解密过程:

y0=IV0,xi=Dkey(yi)⊕R,i≥1

(5)

R=Tr(i)=yi-1orIVk

(6)

随机链接表与链接规则的对应关系如图2所示,设定Kmax=3。随机链接表中第一个1表示明文第1组为单独一个分链,接下来的2表示明文第2、3组为第二个分链成员。根据随机链接表对拆分出分链,如此类推下去,直到将i组成员分到各分链中。

Figure 2 Rules for random grouping

对于随机链接表的产生,本文选取混沌映射来实现。其中,Logistic[12]映射生成混沌序列已广泛应用于密码学中,其安全性及效率已得到许多研究的证实。如图3所示,将密钥及附加参数作为输入,结合Logistic映射在CPU上生成随机链接表(Tr)及分链初始向量表(TIV)。

Figure 3 Generate Tr and TIV

其中对于Tr及TIV的大小,将通过分组总数i、Kmax及阈值L计算出来。设定分组密码每组m位,当i≦2L时,则所需Tr及TIV的大小设定为:sizeof(Tr)=(i/Kmax/m)* 2Kmax;sizeof(TIV)=i/(Kmax/2),其中以m位为一单位。当i>2L,则设定所需Tr及TIV的大小为:sizeof(Tr)=(2L/Kmax/m)* 2Kmax;sizeof(TIV)=2L/(Kmax/2),通过阀值L控制Tr及TIV的大小,避免处理大数据块时过度膨胀。同时,周期性变换使用TIV及Tr,从而满足RCBC的输入要求。

3.3 CPU_GPU上的实现

在CPU_GPU上实现应用RCBC的密码算法,其具体步骤如下:

(1)程序初始阶段,通过主机(CPU)读入明文、附加参数以及密钥,明文进行划分补齐,密钥进行位数检测。密钥及附加参数结合Logistic映射,生成所需随机链接表(Tr)及初始向量表(TIV)。

(2)主机(CPU)计算明文、Tr及TIV所需空间,向设备(GPU)申请内存。将数据从主机(CPU)内存复制到设备(GPU)内存。

(3)根据Tr以及组数(i)计算产生分链数M。再根据分链数M分配所需的线程块以及线程块中的线程数,其中需满足:

M≤线程块 × 线程块中的线程

(7)

(4)配置核函数(kernel)参数,执行核函数。将产生大于或等于M个线程副本,对数据进行并行加密处理。其中每个线程对应一个拆分后的分链。

(5)并行计算过程中,各个线程在TIV读取独立的IV,再对Tr进行查询,计算出分链首地址,以及对应分链的节点数,得到待处理的数据,将数据交给密码算法Ekey(x)完成具体加密工作。

(6)等待GPU完成所有分链的处理,将处理后的结果传回主机(CPU)中,完成RCBC模式下CPU_GPU协处理的加密过程。

对于分组加密算法而言,解密的过程与加密的过程是相对应的,此处的关键在于保证Tr及TIV在加解密算法前后的一致性。

4 安全性分析

对RCBC可能的攻击方法大致有四种:

(1)Vaudenay S[13]对CBC实施的填补攻击;

(2)逐组破解分组密码得到明文;

(3)通过攻击分组密码找出分链的链接规则;

(4)对密钥及附加参数进行穷举,直到找到有意义的明文或与得到的密文相符合。

对上面的攻击方法进行可行性分析。

对于第(1)种攻击,其依据在于 CBC模式需填补位数使加密长度为分组长度的倍数。利用该弱点,攻击者尝试填补数据,并向语言机询问结果,从而对CBC进行破解[13]。但是,对于RCBC而言,由于各分链间是相互独立的,并且各分链的IV均不同,所以对于攻击者而言,最多只能分析出拥有末端分组的分链内容,不可能通过该方式获得整个明文内容。

对于第(2)种攻击,攻击者只能够使用穷举密钥的方法进行破译,对于ECB而言,攻击者只需要找到一个密钥,使得它对每一组密文解密后的结果有意义,即可破解该密码。但是,对于RCBC而言,由于每个分链使用了不同的初始向量,而分链内采用CBC,使得每组明文并不单单依赖于密钥,所以对一组密文的破译不能对整个RCBC构成威胁,这种攻击等同于猜想明文,显然毫无意义。

对于第(3)种攻击,由于链接规则的产生依赖于混沌映射,使其具有很强的随机性。同时,攻击者无法获取更多由同一IV输入所加密的明文/密文对,攻击者只能用穷举的方法找出链接规则。当链长为N,Kmax=k时,链接的方式达k×N!种,N>256时,其数量级已达到2256。以1 Mb大小的文件为例,64位为一组,其链长为1.25×105,假设Kmax=4,即便攻击者得到了密钥,而在不知链接规则的情况下,对信息进行强力攻击,至少需要2128的计算量,按照每微秒加密一百万次的运算能力,需要用时5.9×1030年,而随着N的变大,可选择的链接规则也随之膨胀。因此,在链接规则保密的情况下,攻击者对较大数据进行攻击显得无力。

对于第(4)种攻击,假设攻击者已得知伪随机函数来生成链接规则,则在总链长足够长及Kmax够大的情况下,可以通过增大混沌映射输入参数(P)的位数来保障其安全性。具体做法是将P作为附加的伪密钥与原密钥结合,假设P的位数为 512位,密钥key的位数为64位,将其结合,使得密钥空间达2576。以目前的计算水平来看,已经完全能够抵抗穷举攻击了。而随着计算技术的进步,P的位数也能随之增大,使得计算水平的发展不对RCBC构成过大的威胁,因此对于RCBC来说,即使攻击者拥有计算能力很强的计算机,仍难以快速地进行暴力破解。

5 性能分析

5.1 测试环境

硬件:CPU 为Intel Core(TM) i3 3.30 GHz,4 GB内存,GPU为GTX250 650 MHz 516 MB显存,128个流处理器。

软件:Windows7系统,Visual Studio 2010,CUDA Toolkit 4.0。

5.2 测试结果

本文进行了两个性能对比实验,一个是在CPU环境下,CBC及RCBC的对比实验。另一个是RCBC在CPU环境及CPU_GPU环境上的对比实验。实验结果如表1~表2所示,其中,加密算法采用AES,Kmax取值为3,阈值L取值为18。表2中GPU的计算时间包括数据从CPU到GPU所花的时间。

Table 1 Comparison of CBC and RCBC on CPU

Table 2 Implementation of RCBC on CPU and CPU_GPU

通过观察表1可以看出,进行数据量较小的加密时,AES_RCBC的吞吐量显然低于AES_CBC,这是由于RCBC需要产生Tr及TIV导致的,但随着数据的增大,AES_RCBC的吞吐量与AES_CBC的吞吐量相差无几。说明了RCBC应用于大数据量处理时,其随机性的增加及随机的处理方式并不会对性能造成影响。

通过观察表2可以看出,在处理大量数据时,RCBC在CPU及CPU_GPU上有着明显的差异,运用RCBC的AES算法在CPU_GPU上的执行时间更快,当输入加密文件的大小为512 MB时,速度达到了85.3 M/s,这时AES_RCBC_CPU_GPU上的处理速度是AES_RCBC_CPU上的4.2倍。在CPU_GPU下,密码算法有明显的加速。

本文还测量了应用CBC的AES算法在GPU上的性能,其吞吐量维持在0.8 M/s左右,与采用RCBC的AES在CPU_GPU的性能相差甚远。另外,将AES替换成其他主流分组密码算法重复以上实验,实验数据表明,采用RCBC的DES、Camellia及IDEA均能达到4倍左右的加速。

以上实验表明了应用RCBC的密码算法能在GPU上有效运行,且根据 Amdahl 定律可知,当数据量不大时,加速效果并不明显;而随着数据量的增大,产生Tr、TIV所需时间与数据在CPU_CPU之间的传输时间所占用的比例越来越小,从而加速效果越来越明显。

6 结束语

本文对现有分组加密模式进行研究分析,在CBC的基础上,结合CPU_GPU各自特征需要,提出了新的密文分组工作模式。通过非等长拆分及增加随机性,使CBC能应用于GPU上,同时数据相关性的切断有效地防止了错误的扩散,并能抵御CBC所不能抵御的填补攻击。最后,在CUDA环境下实现了RCBC,结果表明该模式拥有良好的性能,特别是在处理大数据时,表现出了较强的处理能力。

[1] Zhang Shu,Chu Yan-li.GPU performance computing-CUDA[M].Beijing:China Water Power Press,2009.(in Chinese)

[2] Zhu Xing-feng. Design and implementation of efficient IDEA encryption algorithm based on CUDA[J]. Computer and Modernization, 2011(12):48-52.(in Chinese)

[3] Addison W.AES encryption and decryption on the GPU [M].GPU Gems 3 GPU Computing, NY:Microsoft Research,2007.

[4] Ye Jian,Li Li-xin.Fast implementation of AES based on GPU [J]. Computer Engineering and Design, 2010,31(2):256-259.(in Chinese)

[5] Zhang Ji-li, Dong Xi-wei, Xu Shao-wen. Security defect of block cipher mode—ECB mode[J]. Science& Technology Information, 2007(28):341:343.(in Chinese)

[6] Yin Xin-chun,Chen Wei-he,Xie Li.Parallel processing model of the block cipher[J].MINI-MICRO SYSTEMS, 2005,26(4):601-603. (in Chinese)

[7] Yin Xin-chun.Research on parallel cipher[D]. Nanjing:Nanjing University, 2003.(in Chinese)

[8] Fen Deng-guo. Status quo and trend of cryptography[J]. Journal of China Institute of Communications,2002,23(5):18-25. (in Chinese)

[9] Xia Chun-lin, Zhou De-yun, Zhang Kun. CUDA based high-efficiency implementation of AES algorithm[J]. Application Research of Computers, 2013,30(6):1097-1910. (in Chinese)

[10] Wu Wen-ling, Feng Deng-guo. The state-of-art of research on block cipher mode of operation[J].Chinese Journal of Computers,2006,29(1):21-34.(in Chinese)

[11] Li Chao, Sun Bing, Li Rui-lin. Attack method and examples analysis of block cipher[M]. Beijing:Science Press, 2010.(in Chinese)

[12] Wang Yong, Li Sheng-zhu. Block encryption algorithm based on multiple logistic maps[J]. Computer Engineering, 2007,33(22):162-164.(in Chinese)

[13] Vaudenay S.Security flaws induced by CBC padding—applications to SSL,IPSEC,WTLS[C]∥Proc of the International Conference on the Theory and Applications of Cryptographic Techniques,2002:534-545.

附中文参考文献:

[1] 张舒,褚艳利. GPU高性能运算之CUDA [M].北京:中国水力水电出版社,2009.

[2] 朱兴锋.基于CUDA的高效IDEA加密算法设计与实现[J].计算机与现代化,2011,(12):48-52.

[4] 叶剑,李立新.基于GPU的AES快速实现[J].计算机工程与设计,2010,31(2):256-259.

[5] 张吉力,董西伟,徐少文.浅谈分组密码算法模式—ECB 模式的安全缺陷[J].科技信息,2007(28):341-343.

[6] 殷新春,陈伟鹤,谢立.分组密码的并行工作模式[J].小型微型计算机系统,2005,26(4):601-603.

[7] 殷新春.密码算法并行化研究[D].南京:南京大学,2003.

[8] 冯登国.国内外密码学研究现状及发展趋势[J].通信学报,

2002,23(5):18-25.

[9] 夏春林,周德云,张堃.AES算法的CUDA高效实现方法[J].计算机应用研究,2013,30(6):1907-1910.

[10] 吴文玲,冯登国. 分组密码工作模式的研究现状[J].计算机学报,2006,29(1):21-34.

[11] 李超,孙兵,李瑞林.分组密码的攻击方法与实例分析[M].北京:科学出版社,2010.

[12] 王永,李盛竹.基于多个Logistic映射的分组加密算法[J].计算机工程,2007,33(22):162-164.

WU Wei-min,born in 1956,professor,CCF member(E200030580M),his research interests include data structure and algorithm,visual computing,compiler, virtual machine technology, and intelligent system.

李坚锐(1989-),男,广东汕头人,硕士生,研究方向为数据安全和软件保护。E-mail:372695978@qq.com

LI Jian-rui,born in 1989,MS candidate,his research interests include data security, and software protection.

林志毅(1979-),男,福建连江人,博士,讲师,研究方向为自然计算和模式识别。E-mail:16045411@qq.com

LIN Zhi-yi,born in 1979,PhD,lecturer,his research interests include natural computing, and pattern recognition.

Research on the cipher block random link encryption mode based on GPU

WU Wei-min,LI Jian-rui,LIN Zhi-yi

(School of Computer Science,Guangdong University of Technology,Guangzhou 510006,China)

Most of the traditional block cipher modes cannot be applied effectively on GPU. We study the traditional encryption models and put forward a packet encryption model cipher,called block random link encryption mode (RCBC),which is efficient,safe and meets parallel computing requirements.This model has a high efficiency,and increases the difficulty of decryption at the same time.Experimental results show that the proposed encryption algorithm has efficient processing ability on CPU_GPU.

GPU;data encryption;operation mode

1007-130X(2015)01-0036-06

2013-04-10;

2013-09-23基金项目:高性能计算中心多策略数据安全保护支撑平台研发(20012Y2-00046)

TP309.7

A

10.3969/j.issn.1007-130X.2015.01.006

吴伟民(1956-),男,广东深圳人,教授,CCF会员(E200030580M),研究方向为数据结构和算法、可视计算、编译、虚拟机技术和智能系统。E-mail:wuwm@gdut.edu.cn

通信地址:510006 广东省广州市广东工业大学计算机学院

Address:School of Computer Science,Guangdong University of Technology,Guangzhou 510006,Guangdong,P.R.China

猜你喜欢
明文密文密钥
一种支持动态更新的可排名密文搜索方案
基于模糊数学的通信网络密文信息差错恢复
密码系统中密钥的状态与保护*
一种对称密钥的密钥管理方法及系统
奇怪的处罚
基于ECC的智能家居密钥管理机制的实现
一种基于密文分析的密码识别技术*
奇怪的处罚
四部委明文反对垃圾焚烧低价竞争
云存储中支持词频和用户喜好的密文模糊检索