Lai-Massey結構偽隨機特性研究

郭 瑞金晨輝

(解放軍信息工程大學 鄭州 450004)

1 引言

1990年，Lai和Massey利用一類與Feistel模型，廣義Feistel模型，SP網(wǎng)絡以及其各種變型和組合等都不相同的模型設計了國際數(shù)據(jù)加密標準算法IDEA[1]。1999年，Vaudenay研究了IDEA算法采用的密碼模型的一般化問題，提出了Lai-Massey結構[2]，其輪函數(shù)是，這里+表示某個群運算，雙射σ是該群上的正形置換(即雙射σ使仍是雙射)或α幾乎正形置換(使至多只有α個元素沒有原象)。實現(xiàn)速度快是該結構的主要特點。2004年，文獻[3,4]將Lai-Massey結構中的群運算具體為逐位模 2加，將雙射變換σ具體為正形置換具體為SPS模型，設計了FOX系列分組密碼算法(即 IDEA NXT)，從而給出了以 Lai-Massey結構為密碼模型的一個分組密碼實例。在對FOX算法的安全性分析方面，文獻[5,6]構造了FOX算法的3輪積分區(qū)分器，并給出了迄今最優(yōu)的積分分析的結果，證明了4輪FOX64/64, 5輪FOX64/128, 6輪FOX64/192, 7輪FOX64/256對碰撞-積分攻擊不免疫；文獻[7,8]先后給出了FOX算法的4輪不可能差分區(qū)分器，并給出了相應的不可能差分分析結果；文獻[9]等則分析了FOX算法抗差錯攻擊的能力。此外，文獻[10]給出了FOX算法的差分碰撞攻擊。上述結果表明，在傳統(tǒng)分析方法下，F(xiàn)OX系列算法展現(xiàn)了充分的安全性冗余。由此可得Lai-Massey結構是一類安全性較高的密碼模型，值得進一步深入研究。

偽隨機特性是設計密碼模型需要滿足的基本條件。在雙射σ為正形置換的條件下，文獻[2]和文獻[11]使用不同的方法證明了Lai-Massey結構3輪復合可達偽隨機條件，4輪復合可達超偽隨機條件。針對不是任意群(如2mZ )上都存在正形置換的問題，文獻[2]指出可以利用該群上的幾乎正形置換設計雙射σ，且證明了此時Lai-Massey結構的偽隨機特性保持一致，從而推廣了Lai-Massey結構的應用范圍。然而，本文利用Lai-Massey結構的差分特性，證明了當雙射σ為仿射幾乎正形置換時，3輪Lai-Massey結構并不具有偽隨機特性。

此外，2009年Luo等人[12]將Lai-Massey結構的群運算具體為異或運算，雙射變換σ具體為線性正形置換，證明了Lai-Massey結構至少3輪復合達到偽隨機性，至少4輪復合達到超偽隨機性。但是，并未探討Lai-Massey結構中不同正形置換和群運算對其偽隨機特性的影響。因此，本文從Lai-Massey結構設計的角度出發(fā)，分析是否存在特定的群運算和正形置換使得Lai-Massey結構具有更好的偽隨機特性。為此，本文利用構造區(qū)分器的方法證明了雙射σ為任意正形置換時，3輪Lai-Massey結構具有偽隨機特性的必要性；證明了雙射σ為仿射正形置換時，3輪的Lai-Massey結構一定不具有超偽隨機特性。結論表明，基于非線性雙射σ設計的Lai-Massey結構可能具有更好的偽隨機特性。

2 基礎知識

本節(jié)首先給出偽隨機置換和超偽隨機置換的定義，然后介紹Lai-Massey結構及其偽隨機特性。

2.1 偽隨機和超偽隨機置換

定義 1[2]令 :F為以密鑰為索引的置換。如果對于任意概率多項式時間的攻擊者 A，都存在一個可忽略函數(shù)，使得

則稱F是偽隨機置換。其中密鑰k在密鑰空間中隨機均勻選取，置換P從群G到G上構成的所有置換集合中隨機選取。

定義 2[2]令 :F為以密鑰為索引的置換。如果對于任意概率多項式時間的攻擊者 A，都存在一個可忽略函數(shù)()nε，使得

則稱F是超偽隨機置換。其中密鑰k在密鑰空間中隨機均勻選取，置換P從群G到G上構成的所有置換集合中隨機選取。

與定義1中的攻擊者只具有選擇明文的權利相比，定義2的攻擊者A同時具有選擇明文和選擇密文的權利。

2.2 Lai-Massey結構及其偽隨機特性[1317]-

定義 3[2]設kF和σ是群G到自身的映射且σ是雙射，為交換群，k是圈密鑰，則稱以

為圈函數(shù)的分組密碼為 Lai-Massey結構，并稱kF是圈函數(shù)kQ的F函數(shù)，稱σ是圈函數(shù)kQ的σ函數(shù)。

為保證Lai-Massey結構的加解密的相似性，最后一圈的圈函數(shù)一般設置為。

引理1[2]設σ是群G上的α幾乎正形置換，如果攻擊者A具有選擇明文的權利，且詢問預言機的能力限定為概率多項式時間，則有

引理2[2]設σ是群G上的α幾乎正形置換，如果攻擊者A同時具有選擇明文和選擇密文的權利，且詢問預言機的能力限定為概率多項式時間，則有

3 雙射σ為仿射幾乎正形置換時，3輪Lai-Massey結構的區(qū)分器

特別地，在文獻[17]中，給出了幾乎正形置換的構造方法。

引理 3[17]設雙射函數(shù)σ是群G上的置換。如果存在2λ≥，對于任意的LG∈，等式()xxL σ - =在群G上最多有λ個解，則此σ置換即為幾乎正形置換，特別地，如果σ為仿射變換，則稱σ為仿射幾乎正形置換。

所以，當σ是仿射函數(shù)時，有

證畢

利用引理3給出的仿射幾乎正形置換的構造方法，再結合引理5，則3輪Lai-Massey結構3LM 與隨機置換P的區(qū)分器具體構造方法如下：

定理 1 設雙射σ是群G上的仿射幾乎正形置換。則攻擊者A進行2次加密詢問，可以的優(yōu)勢區(qū)分3輪Lai-Massey結構3LM 與隨機置換P。

當攻擊者A詢問加密預言機O為3LM 時。由引理5可知區(qū)分算法輸出為1的概率為1。

所以，該區(qū)分算法的區(qū)分優(yōu)勢為

證畢

文獻[2]證明了基于幾乎正形置換設計的 3輪Lai-Massey模型具有偽隨機特性，而定理1說明當雙射σ是群G上的仿射幾乎正形置換時，3輪的Lai-Massey模型與隨機置換是可區(qū)分的，從而給出一個反例。結論表明，基于仿射幾乎正形置換設計的Lai-Massey模型并不具有特別好的偽隨機性。即對于基于引理3構造的仿射幾乎正形置換不適用于Lai-Massey模型的設計。因為存在使得，此時作為選擇的消息，可以用于定理1中區(qū)分器的構造。

此外，Lai等人將Lai-Massey結構的群運算具體為異或運算，雙射變換σ具體為線性正形置換，證明了Lai-Massey結構至少3輪復合達到偽隨機性，至少4輪復合達到超偽隨機性[11]。但是，并未探討Lai-Massey結構中不同正形置換和群運算對其偽隨機特性的影響。下面進一步研究基于一般的群運算和正形置換設計的 Lai-Massey結構的偽隨機特性。

4 雙射σ為正形置換時，2輪Lai-Massey結構不具有偽隨機特性

引理6 對于2輪Lai-Massey結構(第2輪無σ變換)2LM ，選擇兩個不同的消息,進行加密，其中，則得到的輸出必然滿足等式，其中雙射, 0表示加法群G中的單位元。

證畢

定理 2 設σ是群G上的任意正形置換。則攻擊者A進行 2次加密詢問，可以的優(yōu)勢區(qū)分2輪Lai-Massey結構2LM 與隨機置換P。

證明 攻擊者A具有詢問加密預言機O的能力，其中O為2LM 或隨機置換P，攻擊者A構造可區(qū)分2輪Lai-Massey置換和均勻隨機置換的算法如下：

所以，該區(qū)分算法的區(qū)分優(yōu)勢為

證畢

5 雙射σ為仿射正形置換時，3輪 Lai-Massey結構不具有超偽隨機特性

下面，利用同時進行選擇明文和選擇密文的方式，構造3輪Lai-Massey結構與隨機置換的區(qū)分器。進而說明，當σ為仿射正形置換時，Lai-Massey結構至少4輪復合才具有超偽隨機特性。

引理7 對于3輪Lai-Massey結構3LM ，設σ是群G上的仿射正形置換。選擇兩個不同的消息進行加密，其中，得到輸出，再對進行解密，得到消息，其中要求2δ滿足等式。則必有等式成立。其中由仿射正形置換決定的唯一常數(shù)。

進而得到等式：

及等式：

證畢

證畢

6 結束語

本文深入研究了 Lai-Massey結構的偽隨機特性。首先，證明了基于仿射幾乎正形置換設計的 3輪Lai-Massey模型并不具有偽隨機特性，給出了設計者所得結論的一個反例。其次，證明了雙射σ為任意正形置換時，至少3輪Lai-Massey結構才具有偽隨機特性；證明了雙射σ為仿射正形置換時，至少4輪的Lai-Massey結構才具有超偽隨機特性。結論表明，構造偽隨機特性更好的Lai-Massey結構實例，雙射σ最好設計為非線性的正形置換或幾乎正形置換。因此，分析是否存在非線性的正形置換σ使得3輪的Lai-Massey結構具有超偽隨機特性，或者直接證明Lai-Massey結構是否至少4輪達到超偽隨機特性，是值得進一步研究的問題。

[1] Lai X and Massey J. A proposal for a new block encryption standard[J]. LNCS, 1990, 473: 389-404.

[2] Vaudenay S. On the Lai-Massey scheme[J]. LNCS, 1999, 1716:8-19.

[3] Junod P and Vaudenay S. FOX: a new family of block ciphers[J]. LNCS, 2005, 3357: 114-129.

[4] Nakahara J. An analysis of FOX[J]. LNCS, 2009, 2010:236-249.

[5] Wu Wen-ling, Zhang Wen-tao, and Feng Deng-guo. Integral cryptanalysis of reduced FOX block cipher[J]. LNCS, 2005,3935: 229-241.

[6] 吳文玲, 衛(wèi)宏儒. 低圈FOX分組密碼的碰撞-積分攻擊[J]. 電子學報, 2005, 33(7): 1307-1310.Wu Wen-ling and Wei Hong-ru. Collision-integral attack of reduced-round FOX[J]. Acta Electronica Sinica, 2005, 33(7):1307-1310.

[7] Wu Zhong-ming, Lai Xue-jia, Zhu Bo, et al.. Impossible differential cryptanalysis of FOX[J]. LNCS, 2010, 6163:236-249.

[8] 魏悅川, 孫兵, 李超. FOX密碼的不可能差分分析[J]. 通信學報, 2010, 31(9): 24-29.Wei Yue-chuan, Sun Bing, and Li Chao. Impossible differential attacks on FOX[J]. Journal on Communications,2010, 31(9): 24-29.

[9] Li Rui-lin, You Jian-xiong, Sun Bing, et al.. Fault analysis study of the block cipher FOX64[J]. Multimedia Tools and Applications, 2013, 63(3): 691-708.

[10] Chen Jie, Hu Yu-pu, Zhang Yue-yu, et al.. Differential collision attack on reduced FOX block cipher[J]. China Communications, 2012, 9(7): 71-76.

[11] Yun Aaram, Park Je Hong, and Lee Jooyoung. On Lai-Massey and quasi-Feistel ciphers[J]. Design Codes Cryptography, 2011, 58: 45-72.

[12] Luo Yi-yuan, Lai Xue-jia, and Gong Zheng.Pseudorandomness analysis of the (extended) Lai-Massey scheme[J]. Information Processing Letters, 2010, 111(2):90-96.

[13] Yu Yu. Pseudorandom generators from regular one-way functions: new constructions with improved parameters[OL].http://eprint.iacr.org/2013/270. 2013.

[14] Alexandra Boldyreva and Virendra Kumar. A new pseudorandom generator from Collision-Resistant hash functions[J]. LNCS, 2012, 7178: 187-202.

[15] Andrej Bogdanov, Zeev Dvir, Elad Verbin, et al..Pseudorandomness for width-2 branching programs[J].Theory of Computing, 2013, (9): 283-293.

[16] Luca Trevisan. Pseudorandomness and derandomization[J].Association for Computing Machinery, 2012, 18(3): 27-31.[17] Jacques Patarin. How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function[J]. LNCS, 1992, 658: 256-266.