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

0 引 言

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

1 已有算法介紹與分析

1.1 k-樹算法

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

1.2 多碰撞算法

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

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

圖1 改進(jìn)3-樹算法

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

當(dāng)然也可以通過(guò)一種簡(jiǎn)單的方式，尋找p的最大值。Kazuhiro Suzuki提出球箱問(wèn)題，即m個(gè)球隨機(jī)扔進(jìn)m個(gè)箱子里，試尋找那個(gè)箱子中的球最多。這個(gè)問(wèn)題的解決方案是公知的，并且最大期望漸近值為：

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

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

因此，相比較經(jīng)典的k-樹算法，改進(jìn)的k-樹算法復(fù)雜度之比為:

2 newtree算法介紹

上述的三個(gè)列表分別經(jīng)過(guò)Wanger算法產(chǎn)生碰撞值vp，得到列表：

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

圖3 newtree算法(k=7)

3 復(fù)雜度分析

newtree算法每次運(yùn)行的可以找到方案的概率為：

4 結(jié) 語(yǔ)

基于糾錯(cuò)碼問(wèn)題(規(guī)則字譯碼問(wèn)題[11])設(shè)計(jì)的加密體制是目前抵抗量子計(jì)算機(jī)攻擊的主要方案之一。本文提出的newtree算法，這種攻擊算法可以對(duì)規(guī)則字譯碼問(wèn)題進(jìn)行攻擊，其復(fù)雜度優(yōu)于多碰撞算法的復(fù)雜度。

本文中我們給出了最近提出的多碰撞算法的一個(gè)改進(jìn)算法newtree，主要思路體現(xiàn)在對(duì)積極列表和消極列表的處理方式上，從結(jié)果的公式比較可以得到漸進(jìn)復(fù)雜度有所提高，但是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.