保留格式加密的雙擾工作模式

張玉安，王 野，漆駿鋒，胡伯良

(1.北京海泰方圓科技股份有限公司，北京100094；2.電子科技大學，四川 成都611731)

0 引言

為防止一些敏感信息被偷窺，信息加密是一種較好的應對措施。但有些情形并不需要對大量明文進行加密，比如，有一些表格，每張表格上只有手機號、身份證號和電子郵箱地址等較為敏感，其他內(nèi)容無需加密。如果將這些數(shù)字串或字符串用AES或者SM4 等分組密碼算法加密，需要按128 bit(16 B)數(shù)據(jù)組作分組處理，產(chǎn)生的密文是16 B，有些字節(jié)是不方便打印的。如果將16 B 密文轉(zhuǎn)換成十進制數(shù)字，一般會變?yōu)橐粋€39 位數(shù)，不僅表格內(nèi)寫不下，操作起來也不方便。為解決這類問題，一些保留格式加密(Format Preserving Encryption，F(xiàn)PE)[1]算法方案被提出并開始走向應用。2011 年美國NIST 曾經(jīng)推薦將源自FFX 方案[2]的保留格式加密算法FF1和FF3 確立為AES 標準工作模式[3-4]。

保留格式加密算法能夠?qū) 個數(shù)字加密成N個數(shù)字，將一串字母加密成同樣長度的一串字母，即加密后能使密文保持明文的長度和數(shù)據(jù)類型。近年來出現(xiàn)了很多種保留格式算法方案，但是多數(shù)方案都難以被推廣應用。困擾這些方案的核心問題是實用性和安全性。如果不允許明文組(和密文組)空間較小則不實用；如果允許明文組(和密文組)空間很小，則可能會有安全隱患[5-7]。為此，本文提出一種專門的保留格式算法工作模式，可較好地規(guī)避因明密文空間較小可能引發(fā)的安全問題。

另外，近幾年出現(xiàn)了一些以功率消耗少、內(nèi)存占用少為特點的輕量級分組密碼算法。有些輕量級分組密碼算法的分組長度只有32 bit[8-9]，在較長的密文數(shù)據(jù)段中容易存在密文組重復。如果是ECB(電子密本)模式加密，密文組重復意味著出現(xiàn)了明文組重復。這意味著分組較小時報文明文格式特征易于外露。本文給出的雙擾工作模式能夠彌補分組密碼算法因明文組 (密文組) 空間較小引發(fā)的某些安全缺陷。

1 保留格式算法的一種雙擾工作模式

絕大多數(shù)保留格式加密算法都屬于分組密碼算法。分組密碼的默認工作模式是ECB[10]。但是，如DES、AES 等密碼算法還可以有OFB (輸出反饋)、CFB(密文反饋)、CTR(計數(shù)器)等工作模式。當AES(或DES)算法以OFB、CFB 或CTR 模式[11]工作時，通常被稱為分組密碼算法以序列方式工作，本質(zhì)上這已經(jīng)是序列密碼，不再擁有分組密碼的代替作業(yè)特征。對于一般的保留格式加密算法，默認的工作模式也是ECB，即一組碼符被替換成另一組碼符，解密時把它替換回來。如果要對長段碼符的多個分組進行保留格式加密，除了ECB 模式，能否采用類似OFB、CFB 或CTR 等序列模式呢？ 因為保留格式加密很可能要面對明密文空間較小的情形，以序列密碼方式工作時會因為亂數(shù)序列周期較小而被破譯。

正是由于保留格式加密方案允許明密文空間較小，當攻擊者獲得了很多個明密對以后，就有可能因為密文組碰撞導致更多報文的明文泄露，甚至成就攻擊者有條件嘗試一些針對密鑰的已知明文攻擊。為此，本文提出一種“雙擾工作模式”。其基本思想是對明文組和密文組加擾。明文組(密文組)由若干個碼構(gòu)成，每個碼可看作是一個m 進制數(shù)，加擾是碼與碼對應相加，約定其為按位模m 加（碼間沒有進位），用符號“◎”表示。其逆變換為按位模m 減,用符號“Θ”表示。例如，字符集大小m=10，每組碼數(shù)N=4，分組碼0567 與7538 的模10 加為0567◎7578=7035，0567 與7538 的 模10 減 為0567Θ 7578=3099。

設明文字符集大小為m，分組長度為N 個碼符。用FPEnc(P，K)表示用密鑰K 對明文組P 作ECB 模式保留格式加密。如果使用IV(初始向量)且IV 與明文組類型不同，則需要按某規(guī)則將IV 轉(zhuǎn)化為N 位m 進制數(shù)，使IV 與明文組同類型。若不使用IV，則默認IV=0。雙擾工作模式的加密方法如下：

(1)以N 個碼為一組，將明文段分為t 個組P1，P2，P3，…，Pt。

(2)用密鑰K 將IV 加密(如果不使用IV 則將“0”加密)，得S0=FPEnc(IV，K)，稱S0為秘密IV。計算S1=FPEnc(0◎S0，K)=FPEnc(S0，K)。對i=2，3，…，t，計算Si=FPEnc((Si-1◎Si-2)，K)。得到擾序列S0，S1，S2，…，St。

(3)加密各個明文組。對i=1，2，3，…，t，作如下操作：

①將明文組Pi與擾碼Si-1按位模m 加(明文加擾)，得P=Pi◎Si-1。

②將P 加密，即得到C=FPEnc(P，K)。

③將C 與Si按位模m 加(密文加擾)，即得Ci=C◎Si。Ci為 第i 個 密 文 組。

雙擾工作模式分組加密流程如圖1 所示。

雙擾工作模式的解密方法與加密方法相似，需要加解密雙方約定是否使用IV。解密時步驟(3)中的加密運算相應地變?yōu)榻饷苓\算，按位模m 加相應地變?yōu)榘次荒 減,參見圖2。即步驟(3)相應地變?yōu)閷=1，2，3，…，t，作如下操作：

①將密文組Ci與擾碼Si按位模m 減(密文解擾)，得C=CiΘSi。

②將C 解密，即計算P=FPDec(C，K)。

③將P 與Si-1按位模m 減(明文解擾)，即解得明文組Pi=PΘSi-1。

上述三小步可用式子描述為：

Pi=FPDec((CiΘSi)，K)ΘSi-1。

IV 的作用在于產(chǎn)生擾碼序列初值S0。對攻擊者來說，IV 是可見的，但S0是不可預測的。不同的IV產(chǎn)生不同的S0，導致產(chǎn)生不同的擾碼序列。

圖1 雙擾工作模式分組加密流程示意圖

2 對雙擾工作模式的性能分析

保留格式加密算法的雙擾工作模式實際是將ECB 模式與序列加密模式相互混合，可以直觀地理解為每個數(shù)據(jù)組的加密過程分為三步：(1)用一組擾碼對輸入的明文組實施加擾；(2)對加了擾的明文組作多輪迭代式分組加密；(3)用另一組擾碼對分組加密后的輸出密文進行加擾。對于實用的現(xiàn)代分組密碼算法，唯密文攻擊[12]幾乎沒有成功希望，所以，較為現(xiàn)實的攻擊方向當屬已知明文攻擊[13-14]和選擇明文(密文)攻擊[15]。為了能夠形成攻擊所需要的數(shù)據(jù)條件，攻擊者必須設法搜索和猜設一定數(shù)量的明密對。

在通常的ECB 或CBC(密文分組鏈接)工作模式下，當攻擊者截獲了某用戶的長段密文后，通過研究密文產(chǎn)生場景、收集與該用戶相關(guān)的相近長度明文數(shù)據(jù)、關(guān)注密文解譯方公開流露出的等長明文段落等，將某些明文段與密文段形成明密對應，進而猜設到一些明密對。甚至有可能找到密文組重復，暴露明文結(jié)構(gòu)特征，為猜設明文提供重要佐證。之后，可以開展一些已知明文攻擊或選擇明文攻擊類研究課題。當明文組空間較小時，如果密文數(shù)據(jù)量較大，這類攻擊有可能產(chǎn)生實質(zhì)效果。

圖2 雙擾工作模式解密流程示意圖

在CBC 工作模式下，假設用戶加密明文段P=(p0，p1，p2，…，pn)產(chǎn) 生 了 密 文C=(c0，c1，c2，… ，cn)，而且用戶在不變更密鑰情況下又加密明文段Q=(q0，q1，q2，…，qm)產(chǎn)生了密文D=(d0，d1，d2，…，dm)。如果攻擊者在C 和D 這兩份密文之間找到了相同的 密 文 組，比 如 有ci=dk，1 ≤i ≤n，1 ≤k ≤m，那 么，依據(jù)分組迭代時相同的密文輸出必定有相同的明文輸入，攻擊者可以推出ci-1⊕pi=dk-1⊕qk，得到ci-1⊙dk-1=pi⊙qk，這里“⊕”表示數(shù)據(jù)組異或，“⊙”表示邏 輯 同。進 而 有pi⊕qk=ci-1⊕dk-1。由 于ci-1和dk-1在密文中可見，ci-1⊕dk-1是已知的，因此，通過找到并研究相同密文組，攻擊者可以發(fā)現(xiàn)兩明文組間的差值，這將有助于猜設明文。同理，若在一份較長密文內(nèi)找到了相同密文組，比如有ci=ck，可以獲知明文組pi與pk間的差值。所以，若能在密文數(shù)據(jù)中找到相同的密文組，則CBC 模式是有安全缺陷的，而雙擾工作模式不存在此類安全隱患。

在CTR 或OFB 模式下，如果用戶不慎重復使用了IV，會導致信息泄露。而在雙擾工作模式情形，重用IV 意味著分組序號相同的兩個數(shù)據(jù)組，加在明文上的擾碼相同、 加在密文上的擾碼也相同，具體擾碼是什么不可預測。其攻擊難度大于ECB 模式只有兩個明密對時，求取密鑰或者預測其他明密對。即使同一個IV 重復使用 n 次，雙擾工作模式的安全強度也會優(yōu)于已知n 個明密對情形的已知明文攻擊。

雙擾工作模式的中心思想是通過多次加密IV產(chǎn)生秘密擾碼序列，擾亂分組迭代的輸入和輸出。采用本文給出的雙擾工作模式，即使攻擊者獲得了某密文段落的明文，仍然得不到明密對，因為攻擊者不能準確地猜設用于明文組和密文組的擾碼。當明文組序號不相同時，即使出現(xiàn)相同的密文組也無助于猜設明文信息。

擁有若干明密對構(gòu)成的適度數(shù)據(jù)條件，是密碼分析和破譯的基本素材，也是破譯成功的必備基礎。雙擾工作模式遏制了攻擊者獲取有效數(shù)據(jù)的能力，使攻擊者不能具備開展密碼分析研究的數(shù)據(jù)條件。破壞了攻擊者的攻擊能力，某個層面上等同于該工作模式增強了算法的安全強度。

由于雙擾工作模式每加密一個明文組近似等于做兩次ECB 加密和兩次按位模m 加，在效率方面它只相當于通常CBC 或CTR 模式的近二分之一。大多數(shù)情形下，這不會影響實際應用。另外，由于擾碼的產(chǎn)生與明密文無關(guān)，致使擾碼序列可以預計算或并行計算，從而可以使雙擾工作模式的運算時間在可并行環(huán)境下逼近CBC 模式。

3 結(jié)論

算法的工作模式也是算法安全性的一個組成部分。好的工作模式可以彌補算法設計上的某些不足，為算法安全性加分，但也可能為算法工作效率減分。安全與效率通常是相互制約的兩個方面。對于保留格式加密算法，面對的場景可能是明文組空間較小，需要加密的數(shù)據(jù)量不大。所以，實際應用中用戶對效率的要求不高，安全性更為重要，這將使得雙擾工作模式擁有較好的應用前景。本文給出的雙擾工作模式實質(zhì)上是分組密碼算法的一種通用工作模式，它并不局限于保留格式加密中的應用，僅僅是用于保留格式加密算法時，因為數(shù)據(jù)分組可能較小，安全性方面的優(yōu)點較為突出。