NIST新分组密码工作模式及快速实现研究*

2014-02-10刘冬梅康红娟

通信技术 2014年9期

关键词：密文密钥比特

罗影,刘冬梅,康红娟

(1.卫士通信息产业股份有限公司,四川成都610041;2.解放军78007部队,四川成都610041; 3.四川长虹电器股份有限公司,四川成都610041)

NIST新分组密码工作模式及快速实现研究*

罗影1,刘冬梅2,康红娟3

(1.卫士通信息产业股份有限公司,四川成都610041;2.解放军78007部队,四川成都610041; 3.四川长虹电器股份有限公司,四川成都610041)

分组密码是密码学中使用最为广泛的工具之一,而分组密码的工作模式是指使用分组密码对任意长度的消息进行加解密、认证等的方案。美国国家标准与技术研究院(NIST)积极致力于分组密码工作模式的研究,十余年来陆续发布了大量的工作模式。文中集中讨论了NIST近几年发布的几种新型工作模式,包括加密认证模式GCM、磁盘加密模式XTS、密钥封装模式KeyWrap,并且对这几种新型工作模式的快速实现进行了深入研究。

分组密码工作模式加密认证

0 引言

分组密码是密码学中使用最广泛的工具之一,但它只能处理固定长度的消息,如何利用分组密码来处理实际工作中遇到的任意长度的消息,这就是分组密码的工作模式需要解决的问题。近年来,随着密码理论的不断提高以及各组织机构对工作模式的广泛征集,越来越多的国外研究人员开始关注分组密码的工作模式这一领域。

美国国家标准与技术研究院(NIST)积极致力于分组密码工作模式的研究[1],2001年12月公布的SP800-38A给出了5种加密模式,包括ECB、CBC、CFB、OFB和CTR,2005年5月公布的SP800-38B给出了认证模式CMAC;2004年5月公布的SP800-38C给出了加密认证模式CCM。除了NIST,其它的标准化组织也推出了一系列的工作模式标准,如ISO/IEC 19772中提到的OCB2.0、EAX等,IEEE P1619中提到的XCB、EME等。吴文玲等人在文献[2]中介绍了2006年及之前出现的多种工作模式,讨论其设计理念和安全模型。同年,温凤桐在文献[3]中介绍了多种工作模式,并对其中一些模式进行了安全性分析。近年来NIST陆续发布了多个新的工作模式,2007年11月公布的SP800-38D给出了加密认证模式GCM;2010年1月公布的SP800-38E给出了磁盘加密模式XTS;2012年12月公布的SP800-38F给出了密钥封装模式Key-Wrap;2013年7月公布了SP800-38G草案[4],这是一种称为保留格式加密(FPE)的工作模式。但国内讨论这些新型工作模式的文章并不多见。

1 记号说明

CIPHK(X):在密钥K作用下使用分组算法对明文块X进行加密。

CIPH-K1(X):在密钥K作用下使用分组算法对密文块X进行解密。

X‖Y:表示两个比特串X和Y的连接。

LSBt(X):表示比特串X的最右边t比特。

MSBt(X):表示比特串X的最左边t比特。

P1,P2,…,Pn:表示明文块。

C1,C2,…,Cn:表示密文块。

T1,T2,…,Tn:表示计数器。

2 分组算法AES

AES是比利时密码学家Joan Daemen和Vincent Rijmen所设计的分组密码算法,NIST于2001年正式发布该算法,并在2002年将它发布为有效标准,目前该算法已成为全世界最流行的一种分组加密标准。文中将以AES为例进行讨论。

众多开源密码算法库均支持AES,其中使用最广泛的当属OpenSSL,它是一个C语言编写的支持跨平台的安全开发包,功能强大,囊括了主要的密码算法,并提供丰富的应用程序供测试。另一个开源密码算法库LibTomCrypt结构清晰,短小精干,非常适合初学密码学和期望对密码学有进一步了解的人士。表1给出了LibTomCrypt、rijndael-alg-fst、OpenSSL的AES加解密速度,测试平台为WinXP SP2 32位、英特尔Core 2 Duo E8400@3.00 GHz处理器、2 GB DDR2 800MHz内存,测试中未使用多线程加速,表1中将LibTomCrypt、OpenSSL、rijndaelalg-fst分别简记为Tom、SSL、fst。

表1 各版本的AES速度对比Table 1 AES software performance(Mb/s)

英特尔在比较新的CPU上提供了AES-NI指令,可以直接调用这些指令来进行AES加解密,这一套指令可以大大提升加解密速度,文献[5]讨论了AES的硬件实现以及优化。

3 工作模式

早期提出的ECB、CBC、CFB、OFB模式在很多文献中都有详细记载,因此本节不再讨论。2004年5月公布的CCM加密认证模式,其计数器生成函数和各参数的选择较复杂,限制颇多,存在诸多争议,与此同时Mihir Bellare等提出EAX模式希望取代CCM,因为相较之下EAX更简单且各方面表现均较优,但到目前为止EAX还没有取代CCM。

本节讨论的模式主要是较新的模式,包括2007年公布的GCM模式,2010年公布的磁盘加密模式XTS,2012年公布的密钥封装模式KeyWrap。另外,2001年公布的CTR模式虽然颁布较早,但该模式是后期许多增强型工作模式的基础,因此仍值得仔细研究。

3.1 CTR

CTR模式对计数器加密后再与明密文异或。这种模式的优点是:该模式能并行处理多块数据;分组密码算法只对计数器加密,而不是直接处理明密文;支持随机访问,即可以只计算其中一块,而不是像CBC模式一样计算整个数据链;只需要分组密码算法的加密算法。

由于该工作模式有以上诸多优点,因此后来的很多工作模式都采用了这一方案。比如,CCM模式巧妙地结合了CTR模式和CBC-MAC模式,EAX模式同样利用了CTR模式,GCM模式的加密部分就采用了CTR模式。

CTR加密过程如下:

第1步forj=1,2,…,n-1,Cj=Pj⊕CIPHK(Tj)

第2步Cn=Pn⊕MSBu(CIPHK(Tn))

CTR解密过程如下:

第1步forj=1,2,…,n-1,Pj=Cj⊕CIPHK(Tj)

第2步Pn=Cn⊕MSBu(CIPHK(Tn))

RFC3686建议计数器采用格式:

式中,Counter为大端表示,从1开始并循环累加1。

CTR模式能并行处理多块数据,因此可以充分利用多线程、流水线、多指令、大寄存器和SIMD指令等方法进行加速。其次,分组算法只对计数器加密而不依靠明密文,因此可以准备足够多的存储空间来存储计数器的加密结果,这样一来最终的输出结果仅仅是一系列的异或,这将大大提高运算效率。第三,CTR支持随机访问,使用者如果只想获取其中少量数据,只需要计算对应部分的数据而不是象CBC一样计算整个数据链。最后,CTR只需分组密码算法的加密算法而不需要分组密码算法的解密算法,这使得该模式更加简洁,在轻量级计算环境中更具优势,比如RFID、无线传感器、可穿戴设备等应用场景。

3.2 GCM

GCM是一种有大吞吐能力的加密认证模式。其中主要使用了类似CTR的GCTR和源自CBC的GHASH。计算Y=GCTRK(ICB,X)的方式和CTR一样,这里的ICB为初始计数器,计数器CB的自加方式inc32(CB)是只有低32位做mod232的加1运算,高位保持不变。

本小节以AES为例讨论GCM算法,因此分组长度为128比特。记消息A的补足长度为Clen(A)= (128-(len(A)mod128))mod128,运算·H表示有限域GF(2128)上的乘法。GHASHH(X)模块的计算方式如下(X的长度为分组长度128的整数倍):

第1步划分X=X1‖X2‖…‖Xm。

第2步For i=1 to m,

Yi=(Xi-1⊕Xi)·H

End for i

这里的Y0=0为全零块.

第3步ReturnYm。

GCM加密认证(C,T)=GCM-AEK(IV,P,A)的过程如下(A为关联数据):

第1步H=CIPHK(0),S=Clen(IV)。

第2步定义分块J0为:

Iflen(IV)=96,J0=IV‖031‖1。

else,J0=GHASHH(IV‖0s+64‖[len(IV)]64)。

第3步密文C=GCTRK(inc32(J0),P)。

第4步u=Clen(C),v=Clen(A),S=GHASHK(A‖0v‖C‖0u‖[len(A)]64‖[len(C)]64)。

第5步认证值T=MSBt(GCTRK(J0,S))。

GCM验证解密GCM-ADK(IV,C,A,T)的过程如下:

第1步若IV、A、C长度异常或len(T)≠t,返回验证失败。

第2步H=CIPHK(0),定义分块J0为:

Iflen(IV)=96,J0=IV‖031‖1。

else,s=Clen(IV),J0=GHASHH(IV‖0s+64‖[len(IV)]64)。

第3步明文P=GCTRK(inc32(J0),C)

第4步u=Clen(C),v=Clen(A),S=GHASHH(A‖0v‖C‖0u‖[len(A)]64‖[len(C)]64)。

第5步T′=MSBt(GCTRK(J0,S)),如果T′=T,返回明文P;否则返回失败。

GCM中使用的GCTR和CTR相似,因此可以沿用CTR的优化方式。GHASH则大量地使用二元域上的乘法运算。另外,GCM只用到分组密码算法的加密算法没有用到分组密码算法的解密算法,这使得GCM在实现规模上更具优势。二元域上的乘法运算可以通过查表的方式进行优化,根据存储数据的多少和预计算的繁简程度,可以分为4种方法:简单的8比特存储表法(需存储64 KB/密钥)、简单的4比特存储表法(需存储8KB/密钥)、复杂的8比特存储表法(需存储1 kB+64 KB/密钥)、复杂的4比特存储表法(需存储64B+256B/密钥)[6]。软件实现中64 KB/密钥的存储空间可以接受,这个存储方式的主要思路是将Z=X·H按字节划分

这里的B(X,j)表示X的第j个字节,Mi[]是需要预先计算并存储的16个表,每个表有256个元。根据这一思想,Z=X·H仅需要16次查表和15次128比特数据的异或。128比特数据的异或等操作可以通过SSE指令集进行加速。

3.3 XTS

磁盘加密模式是一种专门为磁盘加密存储设计的特殊工作模式。加密时将准备写入扇区的数据进行加密后再存储到扇区,解密时希望能直接读取任意扇区的信息进行解密。其次磁盘加密中希望密文不要扩张,即不要存储额外的信息。

XTS属于可调密码,可调密码和通常的密码算法相比,输入多了一个可以公开的调节值。调节值与明文异或后送入加密模块,加密得到的密文再次与调节值做异或才得到密文,这可简单地理解为前后白化。增加的调节值增强了密文的多变性,其次改变调节值的代价比改变密钥小,而且调节值可以公开。在XTS中调节值通常是数据单元所在位置,所以不需要额外的存储空间。XTS中定义的数据单元类似扇区,由多个连续的数据块组成,这些数据块在数据单元内有唯一的编号。

本节以AES为例讨论XTS算法。记j为数据块在数据单元内的编号,i为调节值,密钥K=k1‖k2。二元域GF(2128)的生成多项式为f(x)=x128+x7+x2+x1+1,该多项式的尾部x7+x2+x1+1用二进制表示为10000111,即数字135。GF(2128)中元素B与本原元α的乘法B×α可以表示为:

IfMBS(B)＞0,B×α=(B＜＜1)⊕135,elseB×α= (B＜＜1)(3)

数据块P加密C=BEnc(K,P,i,j)过程为:

第1步T=CIPHk2(i)×αj,

第2步C=CIPHk1(P⊕T)⊕T。

数据单元进行加密C=Enc(K,P,i)的流程如下:

第1步按分组大小划分,P=P0‖…‖Pm,最后一块的长度必须小于分组大小,即可为0比特;

第2步Forq=0 tom-2,

Cq=BEnc(K,pj,i,q);

第3步b=bitsize(Pm),

if(b==0)

Cm-1=BEnc(K,Pm-1,i,m-1),

Cm=empty;

else

t=BEnc(K,pm-1,i,m-1);

Cm-1=BEnc(K,Pm‖LBS128-b(t),i,m);

Cm=MBSb(t);

end if

第4步C=C0‖…‖Cm。

XTS使用同一个密钥对各个数据单元分别进行加密。XTS解密与加密类似,但需要用到分组密码算法的解密算法。

在数据块加密BEnc(K,P,i,j)中,密钥K的有效期通常会持续多个数据单元,调节值i在整个数据单元内不改变,序号j则是数据块的序号。数据单元内的加密可以优化为只计算1次w=CIPHk2(i),而不是每个数据块都计算此值。其次,数据单元内的数据块可顺序加密,即在加密明文块时先更新白化值w=w×α,再用此白化值对进行前后白化处理。第三,因为数据单元之间无相关性,所以可以并行处理各数据单元,尤其是同一密钥有效期内的数据单元。另外,如果出现个别数据单元被反复写入的情况,可以缓存相关数据单元的CIPHk2(i)值,这些缓存值将大大减少加密次数,从而提升效率。

3.4 密钥封装

密钥封装(Key Wrap)是密钥管理系统保护密钥的一种方式,比如密钥存储在不安全的存储设备中,或者需要在网络中传输密钥。2001年NIST发布AES密钥封装算法,电信行业协会随后发布了使用TDES的密钥封装算法,2008年,美国标准认可委员会发布了金融服务业的密钥封装算法。由于之前发布的标准不涉及填充,因此IETF在2009年发布了RFC 5649,描述了带填充的密钥封装算法。2012年NIST发布SP800-38F,其中描述了3种密钥封装方式:①AES KW,基于AES的不使用填充的密钥封装方案;②AES KWP,基于AES的带填充的密钥封装方案;③TKW,基于TDES的不使用填充的密钥封装方案。

这里需要特别说明的是,由于密钥封装方式涉及AES和TDES,所以密钥封装算法中以TDES的分组长度64比特作为基本字长。下面以AES为例讨论密钥加封解封,TDES的密钥加封解封方式类似。

明文P=P1‖…‖Pn为n个64比特,密文C=C0‖C1‖…‖Cn为(n+1)个64比特。

密钥加封KW-AE(P)具体步骤如下:

第1步A=0xA6A6A6A6A6A6A6A6,

Fori=1 ton,Ri=Pi

第2步Forj=0 to 5

Fori=1 ton

B=AESK(A||Ri)

A=MBS64(B)⊕(nj+i)

Ri=LSB64(B)

End fori

End forj

第3步C0=A,Fori=1 ton,Ci=Ri;

第4步ReturnC=C0‖C1‖…‖Cn

密钥解封KW-AD(C)步骤如下:

第1步SetA=C0,

Fori=1 ton,Ri=Ci

第2步Forj=5 to 0

Fori=nto 1

B=(A⊕(nj+i)‖Ri)

A=MBS64(B)

Ri=LSB64(B)

End fori

End forj

第3步IfA≠0xA6A6A6A6A6A6A6A6,

Return error

else

Fori=1 ton,Pi=Ri

ReturnP=P1‖…‖Pn

End if

在密钥加封时64n比特的明文封装需要执行6n次加密。该模式的应用场景中敏感数据通常很简短,因此加密的总次数不会太多,用普通的方式实现该工作模式也不会对整体效率产生太大影响。

4 结语

文本集中讨论了NIST在最近几年发布的几种新型工作模式,包括2007年发布的加密认证模式GCM、2010年发布的磁盘加密模式XTS、2012年发布的密钥封装模式,并对这些模式的快速实现进行研究。

NIST对分组密码工作模式的研究工作任在继续,目前正在讨论SP800-38G草案,这是一种称为保留格式加密((FPE)的工作模式,可以应用于金融信息安全业、数据库的透明加密等方面。这是后续工作关注的一个方面。

很多标准化组织也在致力于工作模式标准化的相关工作,如ISO/IEC、IEEE、ANSI、IETF等,它们也提出很多分组密码工作模式,如ISO-IEC 19772、IEEE P1619系列等。另外,加密认证模式竞赛CAESAR正在如火如荼的进行。这些都是今后工作关注的一个方面。

[1] NIST Computer Security Research Center.Current Block Cipher Mode[EB/OL].(2014-03-31)[2014-05-01].http://csrc.nist.gov/groups/ST/toolkit/BCM/current_modes.html.

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

WU Wen-ling,FENG Deng-guo.The State-of-The-Art of Research on Block Cipher Mode of Operation[J].Chinese Journal of Computers,2006,29(01):21-36.

[3] 温凤桐.分组密码工作模式的研究[D].北京:邮电大学,2006.

WEN Feng-tong.Research on the Block Cipher Mode of Operation[D].Beijing University of Posts and Telecommunications,2006.

[4] NationalInstitute of Standards and Technology(NIST). NIST Special Publication 800-38G Draft:Recommendation for Block Cipher Modes of Operation:Methods for Format-Preserving Encryption[EB/OL].(2014-03-31)[2014-05-03].http://csrc.nist.gov/publications/drafts/800-38g/sp800_38g_draft.pdf.

[5] 张慧霞,赵建平,李晓丽,等.AES密码算法的FPGA实现与仿真[J].通信技术,2013,46(09):83-85.

ZHANG Hui-xia,ZHAO Jian-ping,LI Xiao-li et al. Implementation and Simulation of AES Encryption Algerithm based on FPGA.Communications Technology,2013, 46(09):83-85.

[6] Victor Shoup.On Fast and Provably Secure Message Authentication Based on Universal Hashing[C]//Proceedings of 16th Annual International Cryptology Conference (CRYPTO'96).Santa Barbara,California,USA:LNCS 1996:313-328.

LUO Ying(1981-),male,M.Sci.,engineer,majoring in information security.

刘冬梅(1982—),女,硕士,助理研究员,主要研究方向为信息安全;

LIU Dong-mei(1982-),female,M.Sci.,assistant research fellow,majoring in information security.

康红娟(1983—),女,硕士,工程师,主要研究方向为数字版权管理和内容保护。

KANG Hong-juan(1983-),female,M.Sci.,engineer,majoring in digital copy-right management and content protection.

Operation Modes and Their Fast Implementations of NIST New Block Cipher

LUO Ying1,LIU Dong-mei2,Kang Hong-juan3
(1.Westone Information Industry,Ltd.,Chengdu Sichuan 610041,China;2.Unit 78007 of PLA, Chengdu Sichuan 610041,China;3.Sichuan Changhong Electric Co.,Ltd.,Chengdu Sichuan 610041,China)

Block cipher is one of the most widely-used tool in cryptography,and its operation mode features the use of a symmetric-key block-cipher algorithm in providing an infosec service,such as confidentiality or authentication.National Institute of Standards and Technology(NIST)actively works on block-cipher operation modes,and issues a variety of operation modes over the past decade.And several new operation modes are published in recent years,such as the Galois counter mode GCM,the XTS-AES mode for confidentiality on storage devices and the operation methods for key wrapping.This paper discusses these operation modes and their fast implementations.

block cipher,mode of operation,encryption,authentication

TP309

1002-0802(2014)09-1066-05

10.3969/j.issn.1002-0802.2014.09.018