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

羅宜元，　蘇慶剛2，

(1. 上海電機(jī)學(xué)院 電子信息學(xué)院, 上海 201306;

2. 華東師范大學(xué) 信息科學(xué)技術(shù)學(xué)院, 上海 200241)

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

羅宜元1，蘇慶剛2，1

(1. 上海電機(jī)學(xué)院 電子信息學(xué)院, 上海 201306;

2. 華東師范大學(xué) 信息科學(xué)技術(shù)學(xué)院, 上海 200241)

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

關(guān)鍵詞：計算機(jī)安全; 密碼學(xué); Even-Mansour; 分組密碼; 不可區(qū)分性

收稿日期：2015 - 07 - 03

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

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

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

中圖分類號：TP 309.7

文獻(xiàn)標(biāo)志碼：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

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

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

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

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

相應(yīng)地，其解密算法表示為

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

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

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

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

圖1　Even-Mansour結(jié)構(gòu)與單密鑰Even-Mansour結(jié)構(gòu)Fig.1　Even-Mansour structure and single key Even-Mansour structure

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

1基本符號術(shù)語和不可區(qū)分性

1.1　基本符號術(shù)語

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

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

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

1.2　不可區(qū)分性

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

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

另一個密碼體制為(Π,P),是理想的密碼體制，其中，Π和P均為均勻分布的隨機(jī)置換。A能夠?qū)σ粚︻A(yù)言機(jī)(O1,O2)中的O1和O2進(jìn)行正向或逆向查詢，其中，(O1,O2)為(E,P)，或為(Π,P)。A的任務(wù)是分別對O1和O2進(jìn)行正向或逆向查詢?nèi)舾纱魏?，能夠判?O1,O2)究竟是(E,P)還是(Π,P)。

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

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

信息論意義下的攻擊者A對O1和O2分別進(jìn)行正向或逆向查詢次數(shù)最大為qE和qP時，A的區(qū)分優(yōu)勢為

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

2不可區(qū)分性安全證明

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

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

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

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

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

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

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

PrIW[AΠ,P=1]=

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

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

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

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

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

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

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

PrRW[AE,P=1]=

先證明以下結(jié)論：

(1)

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

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

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

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

PrIW[Bad]=PrRW[Bad]

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

Adv(A)=

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

PrIW[Bad]

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

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

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

3結(jié)語

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

參考文獻(xiàn)：

[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.