ESC的RO不可區別性

關鍵詞：密碼建構；隨機預言機；RO區別有利條件；隨機變換函數；隨機置換函數

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

1 前言

Maurer等人在文獻[3]中提出了不可區別性，后來由Coron等人在文獻[4]將其應用到了迭代的Hash函數。Andreeva等人在文獻[5]中正式證明任何對密碼建構發動的一般攻擊的成功概率上界是該攻擊對隨機預言機的成功概率加上RO區別有利條件的上界，這就是不可區別性的中心思想是，因此給出ESC的RO區別有利條件的上界將十分必要。

由于ESC與海綿建構不同的是在每次調用完變換（或置換）函數后對外部狀態進行的消息反饋異或，相應后尾狀態和后首狀態的內部狀態相同，屬于同一個超級節點，因此我們可利用文獻[2]中G. Bertoni等人對海綿建構不可區別性的證明方法來證明ESC的不可區別性。

2 ESC的RO區別有利條件

2.1 基本概念

定義1：一個超級節點指內部狀態相同的節點集。

定義2：ESC吸收字符串P后的前狀態是指那個對字符串P的最后一塊消息只進行了一次異或后得到的整體狀態，我們將用來表示。

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

定義4：ESC吸收字符串P后的后尾狀態指的是那個對相應后首狀態進行了消息反饋異或后得到的整體狀態，我們將用來表示。

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

2.2 攻擊者的情況

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

我們為f是隨機變換函數還有是隨機置換函數的情況都定義了模擬器。

（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

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

類似于文獻[2]，我們易得到以下引理：

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

引理2：攻擊者在擁有對一系列N<2c個詢問Q1的回復時區分隨

2.3 ESC的RO區別有利條件上界

定理1 當f是一個隨機變換函數時ESC的RO區別有利條件上界是：

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

類似于引理2我們有引理3. 攻擊者在擁有對一系列N<2c個詢問Q1的回復時區分隨機置換函數f和p[RO]的有利條件上界是：

參考文獻：

[1]陳偉彬.一個阻止內部碰撞轉狀態碰撞的海綿建構變體[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/.

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