NIST新分組密碼工作模式及快速實現研究*

羅 影,劉冬梅,康紅娟

(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

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