基于k-分割Feistel網絡的FPE方案

李經緯，賈春福，劉哲理，李敏

（1. 南開大學 信息技術科學學院，天津 300071；2. 福建師范大學 網絡安全與密碼技術重點實驗室, 福建 福州350007）

1 引言

保留格式加密(FPE, format-preserving encryption)[1]是一種新型加密技術，通過將某種特定格式的明文加密為與其具有相同格式的密文，使現有數據庫中數據的加解密，既不需要改動應用系統，也不需要改動數據庫結構。此外，FPE還可應用于數據遮蔽[2]、網絡數據安全[3]和格式依賴加密[4]等領域。

國外已取得一些FPE相關理論研究成果[5～9]。其中，文獻[5]關注整數集上的 FPE問題，提出generalized-Feistel方法，該方法首次將Feistel網絡引入到FPE方案構建。其后FPE方案FFSEM[6]、FFX[7,8]、BPS[9]等都延續這一思想，采用各種類型2-分割Feistel網絡。

表1 Feistel網絡在典型FPE方案中的應用情況

目前，處理charsn上的FPE問題即意味著構造分組長度為n的FPE密碼(盡管文獻[9]提出BPS方案的CBC模式，但未給出相關安全性分析)。然而當前2-分割Feistel網絡，在n相當大時，使用的偽隨機函數輸入和輸出寬度也相當大，設計和實現一個大規模偽隨機函數通常是困難的[10]。

作者已在文獻[11]中對已有 FPE模型進行了分析，提出 FPE方案設計框架，將任意問題域的 FPE方案構造轉移為編碼方案設計和整數FPE算法設計。本文在此基礎上，關注當前 FPE方案中各種類型Feistel網絡的適用性，針對使用2-分割Feistel網絡構造的FPE密碼分組長度適應范圍較小的問題，提出基于k-分割type-2 Feistel網絡的FPE方案，以滿足各種長度數據的加密需求。該方案結合 cycle-walking[5]可以解決任意整數集上的FPE問題。最后通過實驗發現和分析各種 Feistel網絡達到雪崩準則所需輪次數和時間開銷，以驗證type-2 Feistel網絡可以使用較小規模偽隨機函數構造各種分組長度密碼。

2 Feistel網絡在FPE中的應用分析

目前已提出的FPE方案多數使用Feistel網絡，表1總結了Feistel網絡在典型FPE方案中應用情況，考慮的主要要素包括：Feistel網絡類型、偽隨機函數構造方法和輪次數等。

由表1可知如下內容。

1) 當前FPE方案均采用2-分割Feistel網絡，包括平衡Feistel網絡、非平衡Feistel網絡、交互式Feistel網絡以及它們的數值形式。2-分割Feistel網絡都將輸入等長或不等長地劃分為L和R這2部分，然后使用偽隨機函數分別執行如圖 1所示的輪運算，以形成下一輪輸入。

圖1 2-分割Feistel網絡

2) Feistel網絡的效率主要取決于偽隨機函數。當前使用Feistel網絡的FPE方案中，偽隨機函數構造方法包括基于偽隨機置換的構造方案[6]和基于消息認證碼的構造方案[3,7,9]，其本質都是填充原輸入，通過偽隨機置換或消息認證碼作用，形成函數輸出[12]。

3) 在采用安全偽隨機函數的情況下，Feistel網絡安全性與輪次數相關。文獻[13～15]證明至少6輪運算才能保證Feistel網絡在各種攻擊模型(已知明文攻擊、自適應選擇明文攻擊和自適應選擇明文密文攻擊)下的安全性。文獻[16]進一步分析一般 Feistel網絡(包括平衡、非平衡、交互式和type-1, 2, 3 Feistel網絡)超越生日邊界的安全性，證明執行足夠多輪運算后，一般Feistel網絡在選擇密文攻擊下，能夠抵抗 2m(1-ε)次惡意查詢(這里m為一般Feistel網絡使用的偽隨機函數輸入寬度，ε為大于0的極小數)。

3 基于k-分割Feistel網絡的FPE方案

針對2-分割Feistel網絡構造的FPE密碼分組長度適應范圍較小的問題，構造基于k-分割Feistel網絡的整數FPE方案(這里以4-分割為例，如果輸入寬度很大，可考慮增加子分組數目)。該方案還可進一步擴展，結合文獻[11]或 rank-then-encipher方法[3]解決復雜問題域(如正則語言等)中的FPE問題。

3.1k-分割Feistel網絡

k-分割Feistel網絡包括type-1、type-2和type-3，通過將輸入比特串等分為k個子分組，能夠有效避免大寬度偽隨機函數設計和實現的困難，已被廣泛應用于各種分組密碼的構造，例如CAST-256(type-1)、RC6(type-2)和 MARS(type-3)等。其每一輪工作原理如圖2所示。

圖2k-分割Feistel網絡(k= 4的情況)

1) Type-1 Feistel網絡執行X2'=FK(X1)⊕X2，連接X2'||X3||X4||X1作為下一輪迭代輸入。

2) Type-2 Feistel網絡執行X2'=FK1(X1)⊕X2和X4'=FK2(X3) ⊕X4，連接X2'||X3||X4'||X1作為下一輪迭代輸入。

3) Type-3 Feistel網絡執行X2'=FK1(X1)⊕X2，X3'=FK2(X2) ⊕X3和X4'=FK3(X3) ⊕X4，連接X2'||X3'||X4'||X1作為下一輪迭代輸入。

3.2 基于type-2 Feistel網絡的整數FPE方案

在k-分割Feistel網絡中，type-2具有安全和效率的最佳平衡：①擴散性方面，type-2只需較少輪次即可達到與type-1相當的安全性，而type-3每一輪運算需調用更多次偽隨機函數，計算復雜性較高[17]；②雪崩效應方面，雖然 type-2滿足雪崩準則所需 Feistel輪次數略大于type-3，但在調用偽隨機函數次數上，type-2大約只是type-3的一半[18]。

因此，試圖設計基于type-2 Feistel網絡的整數FPE方案，描述如下。

系統初始化 setup：初始化系統參數，包括：①基于type-2 Feistel網絡的加密算法所需參數，如輪次數r、偽隨機函數F和子分組數目k等；②待解決問題域?n= { 0,1,… ,n-1}；③密鑰K= (K1,K2)。

加密過程encrypt：輸入明文整數M，執行type-2 Feistel網絡加密過程。圖 3描述了k= 4時使用type-2 Feistel網絡加密的Enc_Feistel算法。

圖3 Enc_Feistel算法

Enc_Feistel算法將輸入整數X表示為二進制形式Xbin，并均勻分割為，如果|Xbin|位數不足，則以0填充，然后執行r輪運算，以加密二進制串最后返回的十進制形式作為算法輸出。

單純Feistel網絡只適用于加密二進制符號串，可通過結合cycle-walking方法確保二進制輸出最終落在指定整數集內，以解決任意整數集上的FPE問題。結合cycle-walking的整個加密過程如圖4所示。

圖4 基于type-2 Feistel網絡的整數FPE方案

解密過程 decrypt：類似于 encrypt，將整數密文Y編碼為二進制數后，進行基于type-2 Feistel網絡的解密，并結合cycle-walking，直到有合法明文輸出為止。

3.3 偽隨機函數構造

Type-2 Feistel網絡的效率主要取決于采用的偽隨機函數，設計安全高效的偽隨機函數是構造基于type-2 Feistel網絡FPE密碼的關鍵。上節提出的FPE方案將采用截斷偽隨機置換輸出的方式構造偽隨機函數。

如圖5所示，在采用截斷偽隨機置換的構造方式中，首先將輸入串X和調整因子t填充為適應偽隨機置換分組長度的二進制向量Vector，不足分組長度時以0填充，然后基于密鑰K使用偽隨機置換加密Vector（這里i=1或2），最后根據所需位數截斷加密結果。

圖5 偽隨機函數構造算法

需要指出的是：①在偽隨機函數構造中引入調整因子，以保證每一輪使用的偽隨機函數不同(如圖5所示，可將當前輪次數作為偽隨機函數調整因子輸入)；②采用的偽隨機置換 PRP可以是任意安全的對稱分組密碼(例如DES、AES等)，但PRP分組長度必須不小于偽隨機函數輸入輸出規模，如果待構造的偽隨機函數輸入輸出規模超過一個 PRP分組長度，只能通過增加type-2 Feistel網絡子分組個數，將大規模偽隨機函數的構造分散為構造多個小規模偽隨機函數。

3.4 安全性分析

2002年，Black和Rogaway[5]首次提出保留格式加密標準安全目標，即偽隨機置換安全。FPE本質是特定消息空間內的偽隨機置換。

2011年，文獻[19]總結保留格式加密的相關攻擊模型和安全目標，指出FPE是一種特殊的對稱密碼，其安全性歸約為采用基礎模塊的安全性。

本文提出的 FPE方案基礎模塊包括：①type-2 Feistel網絡，用于構造分組長度略大于logn的分組密碼(這里n為待加密消息空間大小)；②cycle-walking，用于保證分組密碼最終輸出在可接受范圍內。鑒于文獻[16]對type-2 Feistel網絡超越生日邊界安全性的結論以及文獻[5]和文獻[3]關于 cycle-walking不會降低密碼安全性的分析，因此，基于type-2 Feistel網絡構建的整數FPE方案是安全的。

3.5 效率分析

Type-2 Feistel網絡每一輪加密的時間消耗包括：①將輸入劃分成k個長度為m位子分組的時間tsplit(不失一般性，這里始終假設k= 4)；②偽隨機函數作用子分組的時間tcompute；③連接各子分組形成下一輪輸入或最終密文的時間tjoint。如果采用的輪次數為r，則type-2 Feistel網絡加密總耗時TFeistel=tsplit+ 2rtcompute+tjoint。

為確保type-2 Feistel網絡加密結果最終輸出在可接受范圍內，需結合cycle-walking方法。其中，每次迭代結果屬于指定整數集的概率與該整數集大小和基于type-2 Feistel網絡的密碼分組長度相關。

如果待加密消息空間為n?，所采用密碼分組長度為N。假設type-2 Feistel網絡構造的密碼為理想分組密碼(即對任意明文加密，其密文為消息空間任意點的概率都相同)，那么每一次迭代輸出結果落入n?的概率約為

通常情況下，為使概率值p盡可能大，可根據待加密消息空間大小構造合適寬度的Feistel網絡。此時 type-2 Feistel網絡的寬度應為不小于且能被k整除的整數，因此各子分組寬度為整個type-2 Feistel網絡寬度(這里表示不小于x的最小整數)。

需要指出的是，雖然能夠通過構造合適寬度的Feistel網絡，在一定程度上降低迭代次數，但是，由于每一次迭代輸出結果落入n?的概率為，因此，應在偽隨機函數構造許可的情況下，盡可能使用較少子分組數目；是方案最壞情況，此時每次迭代輸出屬于n?的近似概率為

根據以上分析，應用所提方案處理n?上的FPE問題，在n略大于 2sk時，效率較低。事實上，目前基于Feistel網絡的整數FPE方案均存在上述缺陷，在任意整數集上探索無需結合cycle-walking的高效FPE方案仍為開放性問題。

4 實驗

以雪崩準則作為加密算法實際安全性指標，對比分析各種分組長度下，type-2 Feistel網絡與當前FPE方案中其他 Feistel網絡達到雪崩準則所需Feistel輪次數和時間開銷。

4.1 雪崩準則

分組密碼設計目的在于通過提供足夠混淆和擴散特性，以抵抗對手針對密碼體制的統計分析。混淆和擴散對密文的影響可用雪崩準則衡量：如果一種密碼滿足雪崩準則，那么在任何時候，改變其輸入比特串中某一位，將會致使至少一半輸出比特發生改變[20]，其數學定義如下。

定義1E為分組長度為N的分組密碼，如果對于任意密鑰K和明文X1≠X2但|X1|=|X2|，都有

成立，那么E滿足雪崩準則。這里，dist(·,·)為漢明距離，Exp(·)為期望。

4.2 達到雪崩準則的Feistel網絡輪次數分析

實驗環境為：CPU為Intel(R) Core 2 Quad，主頻 2.66GHz，內存 3GB。測試的分組長度為128～512bit，并規定：①對于每種分組長度，隨機產生密鑰及該分組長度下的明文A、B，這里A、B僅有一個比特不同；②采用AES作為基礎分組密碼構造偽隨機函數。當偽隨機函數規模要求小于128bit時，直接截斷密文作為函數輸出；當偽隨機函數規模要求大于128bit時，這種構造是困難的，這里通過截斷 AES-CBC的密文來近似偽隨機函數；③分別使用 FFSEM(對應平衡 Feistel網絡)、FFX-1(對應非平衡 Feistel網絡)、FFX-2(對應交互式Feistel網絡)和type-2 Feistel網絡對A和B進行加密，若存在100輪以內運算使該類型Feistel網絡達到雪崩準則，表明成功，否則認為失敗。

針對每種分組長度和Feistel網絡類型，進行了100次測試，并對成功達到雪崩準則所需的平均輪次數以及成功次數進行統計，實驗數據如表2所示。

表2 Feistel網絡成功達到雪崩準則時平均輪次數

由表2可知如下內容。

1) FFSEM的平衡Feistel網絡在128～256bit分組長度范圍內，只需較少輪次數，然而分組長度超過256bit時，需構造128bit以上的偽隨機函數，此時采用的截斷AES-CBC密文方式，達成的效果明顯不如基于AES的截斷方法，因此造成失敗次數增加。但隨分組長度繼續增加，成功次數略有回升，說明采用AES-CBC密文截斷方式構造的近似偽隨機函數，隨著單個分組長度范圍內構造的函數規模的增加，隨機性也會緩慢提升，但仍達不到要求。

2) FFX-1的非平衡Feistel網絡(這里采用3:2非平衡劃分)在128～192bit分組長度范圍內，采用直接截斷AES的方式構造偽隨機函數，較少輪次即可達到雪崩準則。然而，當分組長度為224bit時，需通過AES-CBC密文截斷構造具有90bit輸入和134bit輸出的偽隨機函數，近似構造方式導致的較低隨機性嚴重影響Feistel網絡效率。其后，Feistel網絡成功率和輪次效率逐漸提升是因為FFX-1采用擴張的偽隨機函數(輸入寬度小于輸出寬度)，隨分組長度增加，擴張效果愈發明顯，一定程度降低了不良偽隨機函數的影響。

3) FFX-2的交互式Feistel網絡(這里采用3:2非平衡劃分)在128～192bit范圍內具有較高輪次效率。由于與FFX-1相同的原因，并且FFX-2在偶數輪次采用壓縮的偽隨機函數(輸入寬度大于輸出寬度)，在224～320bit范圍內，輪次效率降至最低。其后，隨偽隨機函數規模的增加，效率和成功率緩慢提升。但分組長度為448bit時，偶數輪次需構造具有268bit輸入和 180bit輸出的偽隨機函數，采用AES-CBC密文截斷方式，可能造成碰撞(不同輸入被映射為相同輸出)，效率極低。

4) Type-2 Feistel網絡在整個分組長度范圍內，均可采用AES直接截斷的方式構造偽隨機函數，所需輪次數和成功率都具有穩定性。

由以上分析可知，目前較大規模偽隨機函數很難構造，AES-CBC無法達到真正偽隨機性，導致FFSEM和FFX-2效果不佳；FFX-1采用擴張的偽隨機函數，一定程度上降低了不良偽隨機函數的影響，但在224～288bit范圍內，所需偽隨機函數規模剛好超過一個AES分組長度，輪次效率和成功率仍然較低；type-2能夠使用較小規模偽隨機函數應對較大分組長度范圍內數據加密的情況，具有廣泛實用性。

4.3 達到雪崩準則的Feistel網絡效率分析

由于FFSEM和FFX-2在分組長度較大時失敗幾率較高，其輪次數無法真正說明問題，因此這里將僅對FFX-1和type-2完成不同分組長度下數據加密的時間開銷進行對比分析。

實驗規定如4.2節，這里只測試FFX-1和type-2成功達到雪崩準則時，消耗的平均時間。需要指出的是，這里的時間消耗包括2部分：①對隨機產生的樣例A和B進行Feistel輪運算加密消耗的時間；②每一輪加密結束后，比較輸出結果與原始明文間比特位差異消耗的時間。

圖6對比了FFX-1和type-2成功達到雪崩準則的時間效率（當分組長度為224bit時，使用FFX-1的100組樣例，在100輪運算內均不能滿足雪崩準則），其變化趨勢由4.2節討論的輪次數決定，這里不再詳述。需要指出的是，分組長度在128～208bit范圍內，FFX-1和type-2都采用直接AES截斷方式構造，但FFX-1每一輪只需調用一次偽隨機函數，而type-2需調用2次，因此，FFX-1在較短分組長度情況下，效率優于type-2。

圖6 Feistel網絡成功達到雪崩準則時的時間消耗

由以上分析可知，FFX-1存在224～304bit的低效范圍，而且效率具有嚴重的不穩定性。type-2 Feistel網絡在整個分組長度范圍內都能穩定地在2ms內達到雪崩準則，具有較高效率。

5 結束語

本文關注當前FPE方案中Feistel網絡的適用性，從Feistel網絡類型、偽隨機函數構造方式以及輪次數與安全性的關系，分析了Feistel網絡在FPE中應用現狀。

目前FPE中Feistel網絡都為2-分割，對偽隨機函數要求較高，不能適應于構造靈活分組長度的FPE密碼。針對此問題，提出基于k-分割的type-2 Feistel網絡的FPE方案，該方案結合cycle-walking能夠解決任意整數集上的FPE問題。但是，也指出在結合cycle-walking時，最壞情況下每一次迭代輸出落入n?的概率大約只有(這里k為 type-2 Feistel網絡劃分的子分組個數)，效率較低。

基于Feistel網絡的FPE方案，核心在于Feistel網絡，由于Feistel網絡的不同，使其具有不同適用性。通過實驗對比各種Feistel網絡達到雪崩準則所需輪次數和時間開銷，發現 type-2 Feistel網絡在128～512bit分組長度范圍內均可采用AES直接截斷的方式構造偽隨機函數，具有較高成功率和穩定的效率，從而驗證了基于 type-2 Feistel網絡構造的FPE方案具有廣泛的實用性。

[1] SPIES T. Format preserving encryption. unpublished white paper[EB/OL]. http://www.voltage.com, 2008.

[2] RADHAKRISHNAN R, KHARRAZI M, MEMON N. Data masking:a new approach for steganography[J]. Journal of VLSI Signal Processing, 2005, 41(3):293-303.

[3] BELLARE M, RISTENPART T, ROGAWAY P,et al. Format- preserving encryption[A]. Selected Areas in Cryptography 16th Annual International Workshop, SAC 2009[C]. Springer, Lecture Notes in Computer Science, 2009. 295-312.

[4] STUTZ T, UHL A. Efficient format-compliant encryption of regular languages: block-based cycle-walking[A]. 11th IFIP TC 6/TC 11 International Conference[C]. Springer, Lecture Notes in Computer Science, 2010. 81-92.

[5] BLACK P, ROGAWAY P. Ciphers with arbitrary finite domains[A].Topics in Cryptology-CT-RSA’02[C]. 2002. 114-130.

[6] SPIES T. Feistel finite set encryption mode[EB/OL]. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-s pec.pdf.

[7] BELLARE M, ROGAWAY P, SPIES T. The FFX mode of operation for format-preserving encryption[EB/OL]. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf.

[8] BELLARE M, ROGAWAY P, SPIES T. Addendum to the FFX mode of operation for format-preserving encryption[EB/OL]. http://csrc.ncsl.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ ffx-spec2.pdf.

[9] BRIER E, PEYRIN T, STERN J. BPS: a format-preserving encryption proposal[EB/OL]. http://brutus.ncsl.nist.gov/groups/ST/ tookit/BCM/documents/proposedmodes/bps/bps-spec.pdf.

[10] CANDA V, TRUNG T. Scalable block ciphers based on Feistel-like structure[J]. Tara Mt Math Publ, 2002, 25: 39-66.

[11] 劉哲理, 賈春福, 李經緯. 保留格式加密模型研究[J]. 通信學報,2011, 32(6): 184-190.LIU Z L, JIA C F, LI J W. Research on format-preserving encryption modes[J]. Journal on Communications, 2011, 32(6): 184-190.

[12] HALL C, WAGNER D, KELSEY J,et al. Building PRFs from PRPs[A]. LNCS 1462: Fast Software Encryption[C]. Berlin: Springer,1998. 370-389.

[13] LUBY M, RACKOFF C. How to construct pseudorandom permutations from pseudorandom functions[J]. SIAM Journal on Computing,1988, 17(2): 373-386.

[14] PATARIN J. Pseudorandom permutations based on the DES scheme[A].LNCS 514: Eurocode’90[C]. Berlin: Springer, 1990. 193- 204.

[15] PATARIN J. Security of random Feistel schemes with 5 or more rounds[A]. LNCS 3152: 24th Annual International Cryptology Conference[C]. Berlin: Springer, 2004. 135-158.

[16] HOANG T, ROGAWAY P. On generalized Feistel networks[A].LNCS 6223: 30th Annual International Cryptology Conference[C].Berlin: Springer, 2010. 613-630.

[17] IBRAHIM S, MAAROF M, IDRIS N. Avalanche analysis of extended Feistel network[EB/OL]. http://eprints.utm.my/3258/1/Subariah_PARS05.pdf.

[18] IBRAHIM S, MAAROF M. Diffusion analysis of a scalable Feistel network[A]. Proceeding of 3rd World Enformatika Conference, Istanbul[C]. 2005.98-101.

[19] 劉哲理, 賈春福, 李經緯. 保留格式加密技術研究[J]. 軟件學報.2012,23(1):152-170.LIU Z L, JIA C F, LI J W. Research on format-preserving encryption techniques[J]. Journal of Software, 2012,23(1):152-170.

[20] HEYS H, TAVARES S. Avalanche characteristics of substitution permutation encryption networks[J]. IEEE Transactions on Computer,44(9): 1131-1139.