羅 影,劉冬梅,康紅娟

(1.衛(wèi)士通信息產(chǎn)業(yè)股份有限公司,四川成都610041;2.解放軍78007部隊,四川成都610041; 3.四川長虹電器股份有限公司,四川成都610041)

NIST新分組密碼工作模式及快速實現(xiàn)研究*

羅 影1,劉冬梅2,康紅娟3

(1.衛(wèi)士通信息產(chǎn)業(yè)股份有限公司,四川成都610041;2.解放軍78007部隊,四川成都610041; 3.四川長虹電器股份有限公司,四川成都610041)

分組密碼是密碼學(xué)中使用最為廣泛的工具之一,而分組密碼的工作模式是指使用分組密碼對任意長度的消息進行加解密、認證等的方案。美國國家標準與技術(shù)研究院(NIST)積極致力于分組密碼工作模式的研究,十余年來陸續(xù)發(fā)布了大量的工作模式。文中集中討論了NIST近幾年發(fā)布的幾種新型工作模式,包括加密認證模式GCM、磁盤加密模式XTS、密鑰封裝模式KeyWrap,并且對這幾種新型工作模式的快速實現(xiàn)進行了深入研究。

分組密碼 工作模式 加密 認證

0 引 言

分組密碼是密碼學(xué)中使用最廣泛的工具之一,但它只能處理固定長度的消息,如何利用分組密碼來處理實際工作中遇到的任意長度的消息,這就是分組密碼的工作模式需要解決的問題。近年來,隨著密碼理論的不斷提高以及各組織機構(gòu)對工作模式的廣泛征集,越來越多的國外研究人員開始關(guān)注分組密碼的工作模式這一領(lǐng)域。

美國國家標準與技術(shù)研究院(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年及之前出現(xiàn)的多種工作模式,討論其設(shè)計理念和安全模型。同年,溫鳳桐在文獻[3]中介紹了多種工作模式,并對其中一些模式進行了安全性分析。近年來NIST陸續(xù)發(fā)布了多個新的工作模式,2007年11月公布的SP800-38D給出了加密認證模式GCM;2010年1月公布的SP800-38E給出了磁盤加密模式XTS;2012年12月公布的SP800-38F給出了密鑰封裝模式Key-Wrap;2013年7月公布了SP800-38G草案[4],這是一種稱為保留格式加密(FPE)的工作模式。但國內(nèi)討論這些新型工作模式的文章并不多見。

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:表示計數(shù)器。

2 分組算法AES

AES是比利時密碼學(xué)家Joan Daemen和Vincent Rijmen所設(shè)計的分組密碼算法,NIST于2001年正式發(fā)布該算法,并在2002年將它發(fā)布為有效標準,目前該算法已成為全世界最流行的一種分組加密標準。文中將以AES為例進行討論。

眾多開源密碼算法庫均支持AES,其中使用最廣泛的當屬OpenSSL,它是一個C語言編寫的支持跨平臺的安全開發(fā)包,功能強大,囊括了主要的密碼算法,并提供豐富的應(yīng)用程序供測試。另一個開源密碼算法庫LibTomCrypt結(jié)構(gòu)清晰,短小精干,非常適合初學(xué)密碼學(xué)和期望對密碼學(xué)有進一步了解的人士。表1給出了LibTomCrypt、rijndael-alg-fst、OpenSSL的AES加解密速度,測試平臺為WinXP SP2 32位、英特爾Core 2 Duo E8400@3.00 GHz處理器、2 GB DDR2 800MHz內(nèi)存,測試中未使用多線程加速,表1中將LibTomCrypt、OpenSSL、rijndaelalg-fst分別簡記為Tom、SSL、fst。

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

英特爾在比較新的CPU上提供了AES-NI指令,可以直接調(diào)用這些指令來進行AES加解密,這一套指令可以大大提升加解密速度,文獻[5]討論了AES的硬件實現(xiàn)以及優(yōu)化。

3 工作模式

早期提出的ECB、CBC、CFB、OFB模式在很多文獻中都有詳細記載,因此本節(jié)不再討論。2004年5月公布的CCM加密認證模式,其計數(shù)器生成函數(shù)和各參數(shù)的選擇較復(fù)雜,限制頗多,存在諸多爭議,與此同時Mihir Bellare等提出EAX模式希望取代CCM,因為相較之下EAX更簡單且各方面表現(xiàn)均較優(yōu),但到目前為止EAX還沒有取代CCM。

本節(jié)討論的模式主要是較新的模式,包括2007年公布的GCM模式,2010年公布的磁盤加密模式XTS,2012年公布的密鑰封裝模式KeyWrap。另外,2001年公布的CTR模式雖然頒布較早,但該模式是后期許多增強型工作模式的基礎(chǔ),因此仍值得仔細研究。

3.1 CTR

CTR模式對計數(shù)器加密后再與明密文異或。這種模式的優(yōu)點是:該模式能并行處理多塊數(shù)據(jù);分組密碼算法只對計數(shù)器加密,而不是直接處理明密文;支持隨機訪問,即可以只計算其中一塊,而不是像CBC模式一樣計算整個數(shù)據(jù)鏈;只需要分組密碼算法的加密算法。

由于該工作模式有以上諸多優(yōu)點,因此后來的很多工作模式都采用了這一方案。比如,CCM模式巧妙地結(jié)合了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建議計數(shù)器采用格式:

式中,Counter為大端表示,從1開始并循環(huán)累加1。

CTR模式能并行處理多塊數(shù)據(jù),因此可以充分利用多線程、流水線、多指令、大寄存器和SIMD指令等方法進行加速。其次,分組算法只對計數(shù)器加密而不依靠明密文,因此可以準備足夠多的存儲空間來存儲計數(shù)器的加密結(jié)果,這樣一來最終的輸出結(jié)果僅僅是一系列的異或,這將大大提高運算效率。第三,CTR支持隨機訪問,使用者如果只想獲取其中少量數(shù)據(jù),只需要計算對應(yīng)部分的數(shù)據(jù)而不是象CBC一樣計算整個數(shù)據(jù)鏈。最后,CTR只需分組密碼算法的加密算法而不需要分組密碼算法的解密算法,這使得該模式更加簡潔,在輕量級計算環(huán)境中更具優(yōu)勢,比如RFID、無線傳感器、可穿戴設(shè)備等應(yīng)用場景。

3.2 GCM

GCM是一種有大吞吐能力的加密認證模式。其中主要使用了類似CTR的GCTR和源自CBC的GHASH。計算Y=GCTRK(ICB,X)的方式和CTR一樣,這里的ICB為初始計數(shù)器,計數(shù)器CB的自加方式inc32(CB)是只有低32位做mod232的加1運算,高位保持不變。

本小節(jié)以AES為例討論GCM算法,因此分組長度為128比特。記消息A的補足長度為Clen(A)= (128-(len(A)mod128))mod128,運算·H表示有限域GF(2128)上的乘法。GHASHH(X)模塊的計算方式如下(X的長度為分組長度128的整數(shù)倍):

第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為關(guān)聯(lián)數(shù)據(jù)):

第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長度異?；騦en(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的優(yōu)化方式。GHASH則大量地使用二元域上的乘法運算。另外,GCM只用到分組密碼算法的加密算法沒有用到分組密碼算法的解密算法,這使得GCM在實現(xiàn)規(guī)模上更具優(yōu)勢。二元域上的乘法運算可以通過查表的方式進行優(yōu)化,根據(jù)存儲數(shù)據(jù)的多少和預(yù)計算的繁簡程度,可以分為4種方法:簡單的8比特存儲表法(需存儲64 KB/密鑰)、簡單的4比特存儲表法(需存儲8KB/密鑰)、復(fù)雜的8比特存儲表法(需存儲1 kB+64 KB/密鑰)、復(fù)雜的4比特存儲表法(需存儲64B+256B/密鑰)[6]。軟件實現(xiàn)中64 KB/密鑰的存儲空間可以接受,這個存儲方式的主要思路是將Z=X·H按字節(jié)劃分

這里的B(X,j)表示X的第j個字節(jié),Mi[]是需要預(yù)先計算并存儲的16個表,每個表有256個元。根據(jù)這一思想,Z=X·H僅需要16次查表和15次128比特數(shù)據(jù)的異或。128比特數(shù)據(jù)的異或等操作可以通過SSE指令集進行加速。

3.3 XTS

磁盤加密模式是一種專門為磁盤加密存儲設(shè)計的特殊工作模式。加密時將準備寫入扇區(qū)的數(shù)據(jù)進行加密后再存儲到扇區(qū),解密時希望能直接讀取任意扇區(qū)的信息進行解密。其次磁盤加密中希望密文不要擴張,即不要存儲額外的信息。

XTS屬于可調(diào)密碼,可調(diào)密碼和通常的密碼算法相比,輸入多了一個可以公開的調(diào)節(jié)值。調(diào)節(jié)值與明文異或后送入加密模塊,加密得到的密文再次與調(diào)節(jié)值做異或才得到密文,這可簡單地理解為前后白化。增加的調(diào)節(jié)值增強了密文的多變性,其次改變調(diào)節(jié)值的代價比改變密鑰小,而且調(diào)節(jié)值可以公開。在XTS中調(diào)節(jié)值通常是數(shù)據(jù)單元所在位置,所以不需要額外的存儲空間。XTS中定義的數(shù)據(jù)單元類似扇區(qū),由多個連續(xù)的數(shù)據(jù)塊組成,這些數(shù)據(jù)塊在數(shù)據(jù)單元內(nèi)有唯一的編號。

本節(jié)以AES為例討論XTS算法。記j為數(shù)據(jù)塊在數(shù)據(jù)單元內(nèi)的編號,i為調(diào)節(jié)值,密鑰K=k1‖k2。二元域GF(2128)的生成多項式為f(x)=x128+x7+x2+x1+1,該多項式的尾部x7+x2+x1+1用二進制表示為10000111,即數(shù)字135。GF(2128)中元素B與本原元α的乘法B×α可以表示為:

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

數(shù)據(jù)塊P加密C=BEnc(K,P,i,j)過程為:

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

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

數(shù)據(jù)單元進行加密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使用同一個密鑰對各個數(shù)據(jù)單元分別進行加密。XTS解密與加密類似,但需要用到分組密碼算法的解密算法。

在數(shù)據(jù)塊加密BEnc(K,P,i,j)中,密鑰K的有效期通常會持續(xù)多個數(shù)據(jù)單元,調(diào)節(jié)值i在整個數(shù)據(jù)單元內(nèi)不改變,序號j則是數(shù)據(jù)塊的序號。數(shù)據(jù)單元內(nèi)的加密可以優(yōu)化為只計算1次w=CIPHk2(i),而不是每個數(shù)據(jù)塊都計算此值。其次,數(shù)據(jù)單元內(nèi)的數(shù)據(jù)塊可順序加密,即在加密明文塊時先更新白化值w=w×α,再用此白化值對進行前后白化處理。第三,因為數(shù)據(jù)單元之間無相關(guān)性,所以可以并行處理各數(shù)據(jù)單元,尤其是同一密鑰有效期內(nèi)的數(shù)據(jù)單元。另外,如果出現(xiàn)個別數(shù)據(jù)單元被反復(fù)寫入的情況,可以緩存相關(guān)數(shù)據(jù)單元的CIPHk2(i)值,這些緩存值將大大減少加密次數(shù),從而提升效率。

3.4 密鑰封裝

密鑰封裝(Key Wrap)是密鑰管理系統(tǒng)保護密鑰的一種方式,比如密鑰存儲在不安全的存儲設(shè)備中,或者需要在網(wǎng)絡(luò)中傳輸密鑰。2001年NIST發(fā)布AES密鑰封裝算法,電信行業(yè)協(xié)會隨后發(fā)布了使用TDES的密鑰封裝算法,2008年,美國標準認可委員會發(fā)布了金融服務(wù)業(yè)的密鑰封裝算法。由于之前發(fā)布的標準不涉及填充,因此IETF在2009年發(fā)布了RFC 5649,描述了帶填充的密鑰封裝算法。2012年NIST發(fā)布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比特的明文封裝需要執(zhí)行6n次加密。該模式的應(yīng)用場景中敏感數(shù)據(jù)通常很簡短,因此加密的總次數(shù)不會太多,用普通的方式實現(xiàn)該工作模式也不會對整體效率產(chǎn)生太大影響。

4 結(jié) 語

文本集中討論了NIST在最近幾年發(fā)布的幾種新型工作模式,包括2007年發(fā)布的加密認證模式GCM、2010年發(fā)布的磁盤加密模式XTS、2012年發(fā)布的密鑰封裝模式,并對這些模式的快速實現(xiàn)進行研究。

NIST對分組密碼工作模式的研究工作任在繼續(xù),目前正在討論SP800-38G草案,這是一種稱為保留格式加密((FPE)的工作模式,可以應(yīng)用于金融信息安全業(yè)、數(shù)據(jù)庫的透明加密等方面。這是后續(xù)工作關(guān)注的一個方面。

很多標準化組織也在致力于工作模式標準化的相關(guān)工作,如ISO/IEC、IEEE、ANSI、IETF等,它們也提出很多分組密碼工作模式,如ISO-IEC 19772、IEEE P1619系列等。另外,加密認證模式競賽CAESAR正在如火如荼的進行。這些都是今后工作關(guān)注的一個方面。

[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] 吳文玲,馮登國.分組密碼工作模式的研究現(xiàn)狀[J].計算機學(xué)報,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].北京:郵電大學(xué),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實現(xiàn)與仿真[J].通信技術(shù),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—),女,碩士,工程師,主要研究方向為數(shù)字版權(quán)管理和內(nèi)容保護。

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

A

1002-0802(2014)09-1066-05

10.3969/j.issn.1002-0802.2014.09.018

羅 影(1981—),男,碩士,工程師,主要研究方向為信息安全;

2014-05-16;

2014-07-18 Received date：2014-05-16;Revised date：2014-07-18