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

郭 瑞金晨輝

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

1 引言

1990年，Lai和Massey利用一類與Feistel模型，廣義Feistel模型，SP網絡以及其各種變型和組合等都不相同的模型設計了國際數據加密標準算法IDEA[1]。1999年，Vaudenay研究了IDEA算法采用的密碼模型的一般化問題，提出了Lai-Massey結構[2]，其輪函數是，這里+表示某個群運算，雙射σ是該群上的正形置換(即雙射σ使仍是雙射)或α幾乎正形置換(使至多只有α個元素沒有原象)。實現速度快是該結構的主要特點。2004年，文獻[3,4]將Lai-Massey結構中的群運算具體為逐位模 2加，將雙射變換σ具體為正形置換具體為SPS模型，設計了FOX系列分組密碼算法(即 IDEA NXT)，從而給出了以 Lai-Massey結構為密碼模型的一個分組密碼實例。在對FOX算法的安全性分析方面，文獻[5,6]構造了FOX算法的3輪積分區分器，并給出了迄今最優的積分分析的結果，證明了4輪FOX64/64, 5輪FOX64/128, 6輪FOX64/192, 7輪FOX64/256對碰撞-積分攻擊不免疫；文獻[7,8]先后給出了FOX算法的4輪不可能差分區分器，并給出了相應的不可能差分分析結果；文獻[9]等則分析了FOX算法抗差錯攻擊的能力。此外，文獻[10]給出了FOX算法的差分碰撞攻擊。上述結果表明，在傳統分析方法下，FOX系列算法展現了充分的安全性冗余。由此可得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結構設計的角度出發，分析是否存在特定的群運算和正形置換使得Lai-Massey結構具有更好的偽隨機特性。為此，本文利用構造區分器的方法證明了雙射σ為任意正形置換時，3輪Lai-Massey結構具有偽隨機特性的必要性；證明了雙射σ為仿射正形置換時，3輪的Lai-Massey結構一定不具有超偽隨機特性。結論表明，基于非線性雙射σ設計的Lai-Massey結構可能具有更好的偽隨機特性。

2 基礎知識

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

2.1 偽隨機和超偽隨機置換

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所以，當σ是仿射函數時，有

證畢

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

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

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

所以，該區分算法的區分優勢為

證畢

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

此外，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次加密詢問，可以的優勢區分2輪Lai-Massey結構2LM 與隨機置換P。

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

所以，該區分算法的區分優勢為

證畢

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

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

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

進而得到等式：

及等式：

證畢

證畢

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] 吳文玲, 衛宏儒. 低圈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.