關(guān)鍵詞：密碼建構(gòu)；隨機(jī)預(yù)言機(jī)；RO區(qū)別有利條件；隨機(jī)變換函數(shù)；隨機(jī)置換函數(shù)

DOI：10.16640/j.cnki.37-1222/t.2016.09.188

1 前言

Maurer等人在文獻(xiàn)[3]中提出了不可區(qū)別性，后來(lái)由Coron等人在文獻(xiàn)[4]將其應(yīng)用到了迭代的Hash函數(shù)。Andreeva等人在文獻(xiàn)[5]中正式證明任何對(duì)密碼建構(gòu)發(fā)動(dòng)的一般攻擊的成功概率上界是該攻擊對(duì)隨機(jī)預(yù)言機(jī)的成功概率加上RO區(qū)別有利條件的上界，這就是不可區(qū)別性的中心思想是，因此給出ESC的RO區(qū)別有利條件的上界將十分必要。

由于ESC與海綿建構(gòu)不同的是在每次調(diào)用完變換（或置換）函數(shù)后對(duì)外部狀態(tài)進(jìn)行的消息反饋異或，相應(yīng)后尾狀態(tài)和后首狀態(tài)的內(nèi)部狀態(tài)相同，屬于同一個(gè)超級(jí)節(jié)點(diǎn)，因此我們可利用文獻(xiàn)[2]中G. Bertoni等人對(duì)海綿建構(gòu)不可區(qū)別性的證明方法來(lái)證明ESC的不可區(qū)別性。

2 ESC的RO區(qū)別有利條件

2.1 基本概念

定義1：一個(gè)超級(jí)節(jié)點(diǎn)指內(nèi)部狀態(tài)相同的節(jié)點(diǎn)集。

定義2：ESC吸收字符串P后的前狀態(tài)是指那個(gè)對(duì)字符串P的最后一塊消息只進(jìn)行了一次異或后得到的整體狀態(tài)，我們將用來(lái)表示。

定義3：ESC吸收字符串P后的后首狀態(tài)是指的是那個(gè)用變換（或置換）處理相應(yīng)前狀態(tài)后得到的整體狀態(tài)，我們將用表示。

定義4：ESC吸收字符串P后的后尾狀態(tài)指的是那個(gè)對(duì)相應(yīng)后首狀態(tài)進(jìn)行了消息反饋異或后得到的整體狀態(tài)，我們將用來(lái)表示。

我們將用，，和來(lái)分別表示ESC吸收字符串P后后首狀態(tài)的內(nèi)部狀態(tài)，外部狀態(tài)和整體狀態(tài)；將用，，和來(lái)分別表示ESC吸收字符串P后后尾狀態(tài)的內(nèi)部狀態(tài)，外部狀態(tài)和整體狀態(tài)，我們知道ESC吸收同一個(gè)字符串P后后首狀態(tài)和相應(yīng)的后尾狀態(tài)的內(nèi)部狀態(tài)相同，而且擠壓階段可視為吸收零塊消息，因此后首狀態(tài)和相應(yīng)的后尾狀態(tài)相同（調(diào)用變換（或置換）函數(shù)后）；將用BHS、BTS和AS來(lái)分別表示吸收過(guò)程中相鄰的且內(nèi)部狀態(tài)相同的后首狀態(tài)、后尾狀態(tài)和前狀態(tài)，由此可知ESC吸收字符串過(guò)程中的整體狀態(tài)由這三種整體狀態(tài)組成。

2.2 攻擊者的情況

如圖1所示的攻擊者將區(qū)分兩個(gè)彼此都有兩個(gè)組件的系統(tǒng)。左邊的系統(tǒng)是隨機(jī)變換（或置換）f和ESC E的組合，攻擊者可以分別向兩個(gè)組件做詢(xún)問(wèn)，E將調(diào)用f來(lái)構(gòu)造它的回復(fù)，用E[f]來(lái)表示。E[f]提供交互界面H，如果f是一個(gè)隨機(jī)變換那么它只提供一個(gè)交互界面I1，接受一個(gè)的元素AS作為輸入然后返回同一集合里的一個(gè)元素；如果f是一個(gè)隨機(jī)置換，則它還提供一個(gè)交互界面I-1，接受一個(gè)來(lái)自的元素作為輸入BHT，然后返回該集合的一個(gè)元素。ESC只使用交互界面I1。右邊的系統(tǒng)由一個(gè)提供交互界面H的隨機(jī)預(yù)言機(jī)RO和一個(gè)模擬器p組成。為了構(gòu)造回復(fù)，模擬器可以詢(xún)問(wèn)RO，用p[RO]表示。模擬器不能查詢(xún)攻擊者向隨機(jī)預(yù)言機(jī)的詢(xún)問(wèn)。這里定義兩個(gè)模擬器，一個(gè)是在隨機(jī)變換的情況下，一個(gè)是在隨機(jī)置換的情況。變換模擬器只提供一個(gè)交互界面I1，置換模擬器提供兩個(gè)交互界面I1和I-1。用x表示（E[f]，f）或者（RO，p[RO]）。向系統(tǒng)x的一系列詢(xún)問(wèn)Q由一系列向交互界面H的詢(xún)問(wèn)Q0和一系列向交互界面I1（和I-1）的詢(xún)問(wèn)Q1組成。Q0是一系列對(duì)（其中，且輥一個(gè)正整數(shù)），Q1是一系列對(duì)（AS，1）或（BHT，-1），其中，且1表示連接的交互界面的是I1，-1表示連接的交互界面的是I-1。當(dāng)f是一個(gè)隨機(jī)變換函數(shù)時(shí)只有1的情況。

我們?yōu)閒是隨機(jī)變換函數(shù)還有是隨機(jī)置換函數(shù)的情況都定義了模擬器。

（1）變換模擬器

Algorithm 1 The transformation simulator p[RO]

1： Interface I1， taking node AS as input

2： if node AS has no outgoing edge then

3： if node AS is rooted and （no saturation） then

4：Construct path to BTT： find path to BTS， append called the result P

5：Write P aswhere P does not end with 0r

6： if Pcan be unpadded into M then

7： Assign to the value of blockwith Z = RO（M）

8： else：

9： Choose randomly and uniformly

10：end if

11：Choose randomly and uniformly from

12：Let

13：else

14：Choose randomly and uniformly from all nodes

15：end if

16：Add an edge from AS to BHT

17：end if

18：return the node BHT at the end of the outgoing edge from AS

（2）置換模擬器

Algorithm 2 The permutation simulator p[RO]

1：Interface I1， taking node AS as input

2：if node AS has no outgoing edge then

3：if node AS is rooted AND （no saturation） then

4：Construct path to BTT： find path to BTS， append and call the result P

5：Write P as where P does not end with 0r

6：if Pcan be unpadded into M then

7：Assign to the valuewith Z = RO（M）

8：Else

9：Choose randomly and uniformly

10：end if

11：Choose randomly and uniformly from and such that has no incoming edge yet

12：Let

13：else

14：Choose BHT randomly and uniformly from all nodes that have no incoming edge yet

15：end if

16：Add an edge from AS to BHT

17：end if

18：return the node BHT at the end of the outgoing edge from AS

19：Interface I-1 ， taking node BHT as input

20：if node BHT has no incoming edge then

21：Choose randomly and uniformly

22：Chooserandomly and uniformly from 2c＼R and such that has no outgoing edge yet

23：Let

24：Add an edge from BHT to AS

25：end if

26：return the node AS at the beginning of the incoming edge into BHT

在兩種情況下，模擬器表現(xiàn)得像一個(gè)確定性的函數(shù)然后對(duì)詢(xún)問(wèn)Q1作出與RO對(duì)詢(xún)問(wèn)Q0的回復(fù)一致的回復(fù)。對(duì)于模擬器它將最小化攻擊者可將系統(tǒng)（RO，p[RO]）與系統(tǒng)（E[f]，f）區(qū)分開(kāi)來(lái)的概率。模擬器記錄它收到的詢(xún)問(wèn)然后在一個(gè)模擬器圖對(duì)詢(xún)問(wèn)作出回復(fù)。剛開(kāi)始模擬器圖沒(méi)有邊然后每次向I1（AS）（或者I-1（BHT））的新詢(xún)問(wèn)它產(chǎn)生一個(gè)回復(fù)BHT（或者AS）并增加一條邊（AS，BHT） （或者（BHT，AS））。我們知道使用模擬器對(duì)她詢(xún)問(wèn)的回復(fù)，攻擊者能夠完全重新構(gòu)造模擬器圖。對(duì)于模擬器圖中節(jié)點(diǎn)的一個(gè)子集，攻擊者知道路徑，這個(gè)子集就是詢(xún)問(wèn)過(guò)程中產(chǎn)生的后尾狀態(tài)節(jié)點(diǎn)集。根超級(jí)節(jié)點(diǎn)集是的一個(gè)子集，它包含0c和所有能從它到達(dá)的超級(jí)節(jié)點(diǎn)，用表示。一個(gè)節(jié)點(diǎn)是連根節(jié)點(diǎn)如果。攻擊者知道所有后尾狀態(tài)節(jié)點(diǎn)的路徑還有節(jié)點(diǎn)（0r，0c）的空路徑。對(duì)于那些路徑中帶有填充信息的后尾狀態(tài)節(jié)點(diǎn)，攻擊者可以向系統(tǒng)的交互界面H詢(xún)問(wèn)以期望系統(tǒng)暴露出不一致性，那就是系統(tǒng)不是（E[f]，f）的證據(jù)。我們使用的模擬器可以保證在多達(dá)2c個(gè)詢(xún)問(wèn)Q1前模擬器圖是ESC一致的。當(dāng)模擬器收到一個(gè)詢(xún)問(wèn)I1（AS），其中AS是使得新路徑中帶有填充信息的連根節(jié)點(diǎn)時(shí)，它就會(huì)產(chǎn)生一個(gè)像BHT，并且像BHT對(duì)應(yīng)的后尾狀態(tài)節(jié)點(diǎn)BTT有了路徑，因此模擬器通過(guò)使用新路徑詢(xún)問(wèn)RO構(gòu)造BHT的外部狀態(tài)使得它是ESC一致的（除了所有零路徑）。當(dāng)模擬器收到一個(gè)對(duì)I1（AS）的一個(gè)詢(xún)問(wèn)其中AS不是連根節(jié)點(diǎn)時(shí)，到像BHT對(duì)應(yīng)的后尾狀態(tài)節(jié)點(diǎn)BTT的路徑并不暴露，所以模擬器隨機(jī)的從所有節(jié)點(diǎn)（當(dāng)f時(shí)隨機(jī)置換的情況下是沒(méi)有輸入邊的節(jié)點(diǎn)）中來(lái)選擇BHT。而且一次詢(xún)問(wèn)I1（AS）最多只導(dǎo)致一個(gè)節(jié)點(diǎn)的路徑被知道，那就是當(dāng)AS是連根節(jié)點(diǎn)時(shí)像BHT=I1（AS）對(duì)應(yīng)的后尾狀態(tài)節(jié)點(diǎn)BTT的路徑。為了實(shí)現(xiàn)這個(gè)，當(dāng)為一個(gè)連根節(jié)點(diǎn)AS選擇時(shí)，模擬器排除所有帶有輸出邊的超級(jí)節(jié)點(diǎn)，而且為了避免節(jié)點(diǎn)的多重路徑發(fā)生，模擬器還排除根超級(jí)節(jié)點(diǎn)，置換模擬器對(duì)I-1（BHT）的詢(xún)問(wèn)當(dāng)選擇時(shí)還通過(guò)排除根超級(jí)節(jié)點(diǎn)來(lái)避免暴露節(jié)點(diǎn)的路徑。

類(lèi)似于文獻(xiàn)[2]，我們易得到以下引理：

引理1：任何成本多達(dá)2c的詢(xún)問(wèn)Q0可以被轉(zhuǎn)換成一系列詢(xún)問(wèn)Q1，Q1提供給攻擊者至少同樣的信息而且成本不高于Q0。

引理2：攻擊者在擁有對(duì)一系列N<2c個(gè)詢(xún)問(wèn)Q1的回復(fù)時(shí)區(qū)分隨

2.3 ESC的RO區(qū)別有利條件上界

定理1 當(dāng)f是一個(gè)隨機(jī)變換函數(shù)時(shí)ESC的RO區(qū)別有利條件上界是：

證明：如引理1中所討論的，我們可以從詢(xún)問(wèn)系列Q0，Q1集合中來(lái)構(gòu)造一系列等價(jià)詢(xún)問(wèn)系列Q1。Q1，等價(jià)詢(xún)問(wèn)不會(huì)產(chǎn)生更高的成本并且提供至少相同的信息。所以不失一般性，我們只需考慮使用詢(xún)問(wèn)和它們的回復(fù)而沒(méi)有詢(xún)問(wèn)Q0的攻擊者。對(duì)任何固定的詢(xún)問(wèn)，我們看回從區(qū)分隨機(jī)變量與隨機(jī)變量的問(wèn)題。對(duì)于給定一系列成本為N的詢(xún)問(wèn)引理2限定了這樣一個(gè)攻擊者的有利條件的上界。模擬器是有效的而且運(yùn)行時(shí)間的上界是ts=O（N2），對(duì)于向模擬器的每個(gè)詢(xún)問(wèn)，如果AS是連根節(jié)點(diǎn)，它必須找出到BTT的路徑，如果該路徑是帶有填充信息的，則模擬器向隨機(jī)預(yù)言機(jī)發(fā)送一個(gè)成本是到BTT的路徑長(zhǎng)度的詢(xún)問(wèn)，到BTT的路徑長(zhǎng)度的上界是N。

類(lèi)似于引理2我們有引理3. 攻擊者在擁有對(duì)一系列N<2c個(gè)詢(xún)問(wèn)Q1的回復(fù)時(shí)區(qū)分隨機(jī)置換函數(shù)f和p[RO]的有利條件上界是：

參考文獻(xiàn)：

[1]陳偉彬.一個(gè)阻止內(nèi)部碰撞轉(zhuǎn)狀態(tài)碰撞的海綿建構(gòu)變體[J].科技傳播，2014（06）：149-150.

[2]G.Bertoni，J.Daemen，M.Peeters，and G.Van Assche，Cryptographic sponge functions[OL]，（2012/02/15）[2013/11/30]http：//sponge.noekeon.org/.

[3]U.Maurer， R. Renner， and C. Holenstein，Indifferentiability， impossibility results on reduc-tions， and applications to the random oracle methodology， Theory of Cryptography-TCC 2004 （M. Naor， ed.）， Lecture Notes in Computer Science， no. 2951， Springer-Verlag， 2004，pp. 21-39.

[4]J. Coron， Y. Dodis， C. Malinaud， and P. Puniya， Merkle-Damg?rd revisited： How to construct a hash function， Advances in Cryptology-Crypto 2005 （V. Shoup， ed.）， LNCS， no.3621， Springer-Verlag， 2005， pp. 430-448.

[5]E.Andreeva，B.Mennink， and B.Preneel，Security reductions of the second round SHA-3 candidates， Cryptology ePrint Archive， Report 2010/381，2010， http：//eprint.iacr.org/.

作者簡(jiǎn)介：陳偉彬（1987-），男，廣東汕頭人，碩士研究生，助教，研究方向：密碼學(xué)和數(shù)論等。