廣義生日攻擊的改進

李夢東 邵玉芳 孫玉情 蔡坤錦(北京電子科技學院 北京 00070)(西安電子科技大學通信工程學院 陜西 西安 7007)

0 引 言

在密碼分析技術中，碰撞搜索已經得到了廣泛的研究，其中較為典型的是廣義生日攻擊，它是眾所周知的生日攻擊[1]的推廣。廣義生日攻擊也被稱為k-列表問題，定義如下：已知k個列表和一個目標向量的異或結果為目標向量。Wagner首次研究廣義生日攻擊，對任何范圍的k值，他提出一個算法(k-樹算法[2])解決k-列表問題，2015年亞密會，Ivica Nikolic提出多碰撞算法[3]提高了算法的復雜度，該算法在處理消極列表方面與k-樹算法不同。

1 已有算法介紹與分析

1.1 k-樹算法

Problem1已知k個隨機列表和一個隨機向量x∈{0,1}n，試尋找x1∈L1,…,xk∈Lk滿足x1⊕x2⊕…⊕xk=x，一般情況下x=0。

1.2 多碰撞算法

2015年在亞密會上，Ivica Nikolic對Wagner的k-樹算法進行了改進，此次改進主要是基于部分多碰撞的思想，使用部分多碰撞算法處理消極列表。換句話說，不再是簡單地從消極列表中取出元素，而是從消極列表中找到固定比特位上具有相同值的向量集合。然后，迫使積極列表中的元素在對應的比特位上具有相同的比特。最后，把積極列表和消極列表合并滿足剩余的比特位產生碰撞。Ivica Nikolic把23兩種情況。接下來詳細介紹改進后的3-樹算法。

定義1集合S={x1,…,xp}，其中x1,…,xp是n比特的向量。如果lows(x1)=lows(x2)=…=lows(xp)，那么就形成向量末端s比特的部分多碰撞。

圖1 改進3-樹算法

Kazuhiro Suzuki指出[12]一個集合具有高概率產生多碰撞元素，可以得到：

當然也可以通過一種簡單的方式，尋找p的最大值。Kazuhiro Suzuki提出球箱問題，即m個球隨機扔進m個箱子里，試尋找那個箱子中的球最多。這個問題的解決方案是公知的，并且最大期望漸近值為：

Ivica Nikolic的多碰撞算法在k值較大(不是2的冪)的情況也是有效的。具體的操作如圖2所示，把k個列表分為kA個積極列表和kP個消極列表。

圖2 改進的k-樹算法(k>3)

因此，相比較經典的k-樹算法，改進的k-樹算法復雜度之比為:

2 newtree算法介紹

上述的三個列表分別經過Wanger算法產生碰撞值vp，得到列表：

v=v1⊕v2⊕v3,low[3l+1,4l](xip)=vP}

圖3 newtree算法(k=7)

3 復雜度分析

newtree算法每次運行的可以找到方案的概率為：

4 結 語

基于糾錯碼問題(規則字譯碼問題[11])設計的加密體制是目前抵抗量子計算機攻擊的主要方案之一。本文提出的newtree算法，這種攻擊算法可以對規則字譯碼問題進行攻擊，其復雜度優于多碰撞算法的復雜度。

本文中我們給出了最近提出的多碰撞算法的一個改進算法newtree，主要思路體現在對積極列表和消極列表的處理方式上，從結果的公式比較可以得到漸進復雜度有所提高，但是newtree算法的局限性是它只適用于2

[1] Mosteller F. Understanding the Birthday Problem[J]. Mathematics Teacher, 1962, 55(5):322- 325.

[2] Wagner D. A Generalized Birthday Problem[M]//Advances in Cryptology—CRYPTO 2002. Springer Berlin Heidelberg, 2002:288- 304.

[4] Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[M]//Algorithmic Number Theory. Springer Berlin Heidelberg, 1998:267- 288.

[5] Lyubashevsky V, Micciancio D, Peikert C, et al. SWIFFT: A Modest Proposal for FFT Hashing[M]//Fast Software Encryption. Springer Berlin Heidelberg, 2008:54- 72.

[6] Finiasz M, Gaborit P, Manuel S, et al.SHA-3 proposal: FSB. Submission to the SHA-3 NIST Competition (2008)[OL].http://www-rocq.inria.fr/secret/CBCrypto/index.php?pg=fsb.

[7] Meziani M, ?zgür Dagdelen, Cayrel P L, et al. S-FSB: An Improved Variant of the FSB Hash Family[M]//Information Security and Assurance. Springer Berlin Heidelberg, 2011:132- 145.

[8] Overbeck R. A multiple birthday attack on NTRU[J]. IEEE Comput Graph Appl, 2011, 31(6):45- 55.

[9] Bernstein D J, Lange T, Niederhagen R, et al. Implementing Wagner’s generalized birthday attack against the SHA-3 round-1 candidate FSB[C]. Cryptosith Org, 2010, 2009.

[10] Coron J S, Joux A. Cryptanalysis of a Provably Secure Cryptographic Hash Function[C]//G Brassard Advances in Cryptology-Crypto Lncs, 2004:416- 427.

[11] Finiasz M, Gaborit P, Sendrier N. Improved Fast Syndrome Based Cryptographic Hash Functions[C]//Proceedings of ECRYPT Hash Workshop 2007.

[12] Suzuki K, Tonien D, Kurosawa K, et al. Birthday Paradox for Multi-collisions[C]//International Conference on Information Security and Cryptology. Springer, Berlin, Heidelberg, 2006:29- 40.