對單密鑰Even-Mansour分組密碼的簡單安全性證明

羅宜元，　蘇慶剛2，

(1. 上海電機學院 電子信息學院, 上海 201306;

2. 華東師范大學 信息科學技術學院, 上海 200241)

對單密鑰Even-Mansour分組密碼的簡單安全性證明

羅宜元1，蘇慶剛2，1

(1. 上海電機學院 電子信息學院, 上海 201306;

2. 華東師范大學 信息科學技術學院, 上海 200241)

摘要：Even-Mansour結構是最簡單的構造分組密碼的方法。利用Kilian-Rogaway的游戲論證方法，給出了單密鑰Even-Mansour分組密碼的一個簡單的不可區分安全性證明，大大簡化了之前的一般性證明方法。

關鍵詞：計算機安全; 密碼學; Even-Mansour; 分組密碼; 不可區分性

收稿日期：2015 - 07 - 03

基金項目：國家自然科學基金項目資助(61402280)；上海電機學院重點學科資助(13XKJ01，A1-1201-14-005)

作者簡介：羅宜元(1986 - )，男，講師，博士，主要研究方向為信息安全和密碼學，E-mail： luoyy@sdju.edu.cn

文章編號2095 - 0020(2015)05 -0272 - 05

中圖分類號：TP 309.7

文獻標志碼：A

Abstract：Even-Mansour cipher is the simplest block cipher based on a public permutation. In this paper we propose a simple indistinguishability proof for single key Even-Mansour cipher based on Killian-Rogaway’s game playing method. The proof presented in this paper is much simpler than previous proofs.

Simple Security Proof for Single Key Even-Mansour Cipher

LUOYiyuan1,SU Qinggang2,1

(1. School of Electronics Information Engineering, Shanghai Dianji University,

Shanghai 201306, China; 2. School of Information Science Technology,

East China Normal University, Shanghai 200241, China)

Key words： computer security; cryptography; Even-Mansour; block cipher; indistinguishability

隨著計算機網絡、云計算、大數據等信息技術的快速發展，人們逐漸享受到互聯網的便利，但同時，信息安全問題卻愈來愈突出。在信息安全技術中，密碼學處于基礎性的地位，是信息安全技術的核心，也是攻擊者最難攻破的模塊。在密碼學中，分組密碼扮演著基礎的角色，其通常被稱為密碼學原語，很多應用協議方案等都可以基于分組密碼算法來實現。由于分組密碼應用的廣泛性，使得人們對其安全性有著十分嚴格的要求。整個密碼學術界從來沒有停止過對分組密碼結構的分析。

從設計結構來看，分組密碼的常用構造有3種： ① Feistel結構，以數據加密標準(Data Encryption Standard, DES)算法為代表[1]。對于Feistel結構安全性的證明，是由Luby等[2]開始的。②Lai-Massey結構[3]，以FOX算法為代表[4]。Lai-Massey 結構具有與Feistel結構相同的安全界限。③ 迭代式Even-Mansour結構，也即密鑰交替密碼結構，以高級加密標準(Advanced Encryption Standard, AES)算法為代表[5]。近幾年，學術界掀起了對該結構安全性證明的熱潮。而該結構最早是基于Even-Mansour結構擴展而來的[6]。

Even-Mansour分組密碼是最簡單的設計一個分組密碼的方法。該密碼基于一個公開的n比特置換P，將n比特的明文與一個n比特密鑰k1異或后作為P的輸入，得到的輸出再與另一個n比特密鑰k2異或，得到n比特密文。Even-Mansour密碼的加密表示為

y=E(x)=P(x⊕k1)⊕k2

相應地，其解密算法表示為

x=D(y)=P-1(y⊕k2)⊕k1

其中，x和y分別為明文和密文；E為加密函數；D為解密函數；P為公開置換，P-1為該P的逆。

Even等[6]認為該結構是最簡結構，因為去除k1或k2后該結構將不安全，且很容易對其進行攻擊。而Dunkelman等[7]認為該結構并不是最簡單的結構，并給出了更簡單的單密鑰Even-Mansour結構。在該結構中，令k1=k2=k,用一個密鑰k就能達到同樣的安全界限,該結構被稱為單密鑰 Even-Mansour結構(SEM)。Even-Mansour結構和單密鑰Even-Mansour結構如圖1所示。

Dunkelman等給出的安全界限為O(qEqP/2n)，其中，qE和qP分別是攻擊者查詢E和P的次數。然而，他們的安全性證明僅證明該結構在存在性偽造攻擊下的安全性。Bogdanov等[8]證明了t輪迭代式Even-Mansour密碼在區分性攻擊下的安全界限，即當t≥2時，t輪迭代式Even-Mansour結構的不可區分性為O(q3/22n)，其中，q為攻擊者對每一個置換的查詢最大次數。隨后，Lampe等[9]證明了t輪迭代式Even-Mansour結構的不可區分性為O(qt+2/2t n)。Chen等[10]證明了t輪迭代式Even-Mansour結構所能達到的最好的安全界限為O(qt+1/2t n)。Chen等[11]證明了2輪Even-Mansour結構所能達到的最好的安全界限。這些安全性證明都非常復雜，令人費解。

圖1　Even-Mansour結構與單密鑰Even-Mansour結構Fig.1　Even-Mansour structure and single key Even-Mansour structure

從目前來看，還沒有公開文獻給出單密鑰Even-Mansour結構的詳細的不可區分性安全證明。本文基于Kilian-Rogaway的游戲論證方法[12]，給出了單密鑰Even-Mansour對于自適應性選擇明密文攻擊者A下的不可區分性的精確界限qEqP/2n-1，其中，qE和qP分別是攻擊者A對E和P進行查詢(正向或逆向)的次數。與之前的證明相比，本文大大縮減了篇幅，證明方法也較為簡單。

1基本符號術語和不可區分性

1.1　基本符號術語

(1)Pn為在n比特上的所有的(2n)!個置換的集合。

(3) 一個n比特的置換P被稱為部分定義的，指該置換當前只被定義了一部分輸入及輸出值。令Dom(P)表示P當前被定義部分的定義域，令Range(P)表示P當前被定義部分的值域，且令

(4) 一個攻擊者A稱為對(E,P)信息論意義下的自適應性選擇明文和密文攻擊者，表示A能夠對(E,P)里的E和P分別進行自適應性的正向或逆向查詢；A的計算能力是無限的，但是A的查詢次數是有限制的。

1.2　不可區分性

在本文的不可區分性分析中，攻擊者A將要區分兩個密碼體制： 一個密碼體制為(E,P)，也就是現實中的單密鑰Even-Mansour密碼體制，即P為均勻隨機置換，

E(x)=P(x⊕k)⊕k

另一個密碼體制為(Π,P),是理想的密碼體制，其中，Π和P均為均勻分布的隨機置換。A能夠對一對預言機(O1,O2)中的O1和O2進行正向或逆向查詢，其中，(O1,O2)為(E,P)，或為(Π,P)。A的任務是分別對O1和O2進行正向或逆向查詢若干次后，能夠判斷(O1,O2)究竟是(E,P)還是(Π,P)。

AO1,O2輸出為1表示其猜測(O1,O2)為現實世界中的密碼體制，也就是(O1,O2)為(E,P)，A的區分優勢可以表示為

其中，Pr[Aspan class="emphasis_superscript">E,P=1]為A與(E,P)交互一定次數時輸出為1的概率；Pr[AΠ,P=1]為A與(Π,P)交互一定次數時輸出為1的概率。

信息論意義下的攻擊者A對O1和O2分別進行正向或逆向查詢次數最大為qE和qP時，A的區分優勢為

圖2　信息論意義攻擊者A區分現實世界與理想世界Fig.2　Attacker A distinguishes the real world from an ideal world

2不可區分性安全證明

定理1給定一對預言機(O1,O2)，且(O1,O2)是(E,P)或(Π,P)，則對于任意的、對O1和O2分別進行正向或逆向查詢次數最大為qE和qP的信息論意義下選擇明、密文攻擊的A，其對一個n比特分組長度的單密鑰Even-Mansour分組密碼(E,P)與(Π,P)區分的概率優勢為

(1) A對O1正向查詢x，查詢結果如下：

(c) 定義O1(x)=y，返回y。

(c) 定義O1(x)=y，返回x；

(3) A對O2正向查詢x，查詢結果如下：

(b) 定義O2(x)=y，返回y。

(b) 定義O2(x)=y，返回x。

PrIW[AΠ,P=1]=

同樣的，假設(O1,O1-1,O2,O2-1)是現實世界，定義現實世界游戲(Real World, RW)的查詢規則如下。

(1) A對O1正向查詢x，查詢結果如下：

(a) 若O2(x ⊕ k)已定義，則設置標記Bad為True,返回O2(x ⊕ k)⊕ k；

(3) A對O2正向查詢x，查詢結果如下：

(b) 定義O2(x)=y，返回y。

(b) 定義O2(x)=y，返回x。

此時可明顯看出，游戲RW精確地模擬了現實世界的情形。令PrRW[·]為處于RW時相應事件的概率，則有

PrRW[AE,P=1]=

先證明以下結論：

(1)

式(1)表示在Bad為False時，攻擊者A將對區分(E,E-1,P,P-1)和(Π,Π-1,P,P-1)無任何概率優勢。由IW和RW游戲規則可見，在Bad為False時，用黑體標示的事件并未發生。

(1) 比較在游戲IW和RW中O1的輸出，假設此時O1和O2已經分別被查詢(正向或逆向)qE和qP次，且Bad仍為False。

(2) 比較在游戲IW和RW中O2的輸出，由游戲IW和RW中第(3)、(4)步可以看出O2在兩個游戲中的輸出是等概率分布的。

由游戲IW和RW中第(1)、(2)步可見，

PrIW[Bad]=PrRW[Bad]

這是由于當Bad=True時，兩者顯然是等價的。因此，攻擊者A區分(E,E-1,P,P-1)的(Π,Π-1,P,P-1)概率優勢可以界定為在游戲IW和RW中的事件Bad為True的概率，形式化的表示為

Adv(A)=

PrIW[AΠ,P=1|Bad]PrIW[Bad]-

PrIW[Bad]

因此，現在的任務就轉為求在游戲IW中事件Bad為True的概率。當A在對O1和O2分別進行查詢(正向或逆向)qE和qP次后，對于每一對查詢(x,O1(x)),(y,O2(y)),最多會有2個密鑰導致事件Bad為True，即

k=x⊕y或k=O1(x)⊕O2(y)

qEqP對查詢最多會有2qEqP個密鑰k導致事件Bad為True，而密鑰k總的數量為2n個，故得出

3結語

本文給出了對單密鑰Even-Mansour分組密碼的一個簡單的不可區分性證明。雖然近些年Even-Mansour結構被廣泛研究，但是對單密鑰Even-Mansour的不可區分性證明并未見之于公開文獻。現有文獻對于多輪Even-Mansour的一般性證明過于復雜，本文借鑒了Killian和Rogaway的思想，采用了游戲的方式給出了單密鑰Even-Mansour對于自適應性選擇明密文攻擊下的不可區分性的界限。下一步的工作將是將此證明思路推廣到多輪Even-Mansour結構的證明上，期望解決當前學術界對多輪Even-Mansour結構安全性證明過于復雜的問題。

參考文獻：

[1]DES.Data Encryption Standard[S].[S.L.]：Springer,1977.

[2]Luby M，Rackoff C.How to construct pseudorandom permutations from pseudorandom functions[J].SIAM Journal on Computing,1988,7(2)： 373-386.

[3]Vaudenay S.On the Lai-Massey scheme[C]∥Advances in Cryptology-ASIACRYPT’99.Berlin： Springer-Verlag,1999： 8-19.

[4]Junod P，Vaudenay S.FOX： a new family of block ciphers[C]∥Selected Areas in Cryptography-SAC 2004.Berlin： Springer-Verlag,2005： 114-129.

[5]Daemen J，Rijmen V.The Design of Rijndael： AES-The Advanced Encryption Standard[M].Berlin： New York： Springer-Verlag,2002： 1-10

[6]Even S，Mansour Y.A construction of a cipher from a single pseudorandom permutation[J].Journal of Cryptology，1997,10(3)： 151-162.

[7]Dunkelman O，Keller N，Shamir A.Minimalism in cryptography： The Even-Mansour scheme revisited[C]∥Advances in Cryptology： EUROCRYPT 2012.Berlin： Springer-Verlag,2012： 336-354.

[8]Bogdanov A，Knudsen L R，Leander G，et al.Key-Alternating ciphers in a provable setting： Encryption using a small number of public permutations[C]∥Advances in Cryptology： EUROCRYPT 2012.Berlin： Springer-Verlag,2012： 45-62.

[9]Lampe R，Patarin J，Seurin Y.An asymptotically tight security analysis of the iterated Even-Mansour cipher[C]∥Advances in Cryptology： ASIACRYPT 2012.Berlin： Springer-Verlag,2012： 278-295.

[10]Chen Shan，Steinberger J.Tight security bounds for key-alternating ciphers[C]∥Advances in Cryptology： EUROCRYPT 2014.Berlin： Springer-Verlag,2014： 327-350.

[11]Chen Shan，Lampe R，Lee J，et al.Minimizing the two-round Even-Mansour cipher[C]∥34th Annual Cryptology Conference： CRYPTO 2014.Berlin： Springer-Verlag,2014： 39-56.

[12]Kilian J，Rogaway P.How to protect des against exhaustive key search(an analysis of DESX)[J].Journal of Cryptology，2001,4(1)： 17-35.