对称密码和哈希函数的结构化分析
|
摘要
对称密码和哈希函数是现代密码学中的基础的领域,很多上层的密码方案都可以基于底层的对称密码和哈希函数来完成。过去人们一般认为很难通过可证明安全理论对对称密码和哈希函数进行分析,对称密码和哈希函数的设计更多是通过一些测试,经验的总结,并没有非常强的理论依据。
然而,设计一个对称密码或者哈希函数并不是盲目的,人们通常首先需要设计一种构造方案,搭建一个基本的骨架,然后再不断细化内部的各个部分。分组密码的常用构造有Feistel结构和Substitution-Permutation-Network结构。再往下具体划分有Lai-Massey, Gen-Skipjack, Gen-CAST256, Gen-MARS, SMS4, Four-Cell, RC6等等。对于流密码而言,很多则是基于线性移位寄存器(LFSR)的构造。有的流密码则是基于分组密码的运行模式直接得到。对于哈希函数,一般流行的方法都实质是基于分组密码的方法的,例如MD4, MD5, SHA-1, MDC-2等等。
对分组密码的构造的安全性进行研究,就是对其伪随机性或不可区分性进行研究,如果分组密码的内部模块是理想的,若能证明基于该理想的模块能够构造出理想的分组密码,则说明该构造是没有问题的,这也是当前学术界公认的研究方法。基于LFSR的流密码由于其数学性质丰富,容易从数学角度来研究其输出密钥流的伪随机性,例如周期性,平衡性,自相关性等等。这一套研究方法是不同于分组密码的,需要用到更多有限域理论上的知识。一般来说,这类流密码的好处就是其部分数学性质是可以证明的,典型的例子就是wG流密码,其密钥流具有固定的周期,平衡性和理想两阶自相关性。同时,由于基于LFSR的流密码在硬件上的效率非常高,在实际中得到了很好的应用。
对于哈希函数的构造,自MD5, SHA-1等已被广泛应用的哈希函数相继被找出漏洞之后,整个密码学界也重新掀起了对哈希函数的研究热潮。很多新的可证明安全模型,如Indistinguishability、Indifferentiability等被用来证明哈希函数的迭代构造的安全性。对于压缩函数的构造,流行的方法是采用基于分组密码的方法,但也有一些其他的基于数学困难问题的构造,如基于多项式的压缩函数被提出。
由于对称密码和哈希函数构造的相似性,本文从算法的基本构造入手,对常用的对称密码学的构造进行结构化的分析,取得了以下的进展：
1.对分组密码中的Lai-Massey构造方案进行了伪随机性分析,找到了对Lai-Massey及Extended Lai-Massey构造的2轮伪随机区分器及3轮强伪随机区分器,并且利用马尔科夫链理论在理论上首次证明了多轮Lai-Massey构造可以达到超出生日界限的安全性,这是已知最好的对Lai-Massey结构的分析。
2.提出了一种对分组密码结构不可能差分的统一方法,对若干种常用的分组密码构造的方案,如Gen-Skipjack, Gen-CAST256,Gen-MARS, SMS4, Four-Cell, RC6等进行了不可能差分分析,取得了较好的结果,否定了亚密2000年Sung等人提出的猜想,推翻了FSE2009Pudovkina的结论。
3.研究了一类数学性质良好的WG流密码的构造,并设计了一个轻量级的WG-7流密码,对其安全性进行了充分的分析并对其实现,并分析了其在RFID的认证协议上应用的可行性。
4.研究了基于多元多项式构造哈希函数的安全性,并指出此类哈希函数不能抵抗高阶差分攻击。
5.在基于分组密码的哈希函数构造进行了新的分析,对基于分组密码的哈希函数进行全面性的分析归纳。解决了Hirose留下的公开问题,并发现了FSE2009最佳论文中定理的漏洞,且对其修正。
6.成功的攻破了Lee等人提出的一类哈希率为2/3的基于三轮Feistel结构的哈希函数,否定了该构造具有设计者宣称的理想抗碰撞安全性。
7.对基于PGV构造的哈希函数在pfMD、chopMD、NMAC/HMAC迭代下的不可区分性(Indifferentiability)进行了归纳性研究,首次提出这四种迭代模式在不同PGV构造下具有不同的安全性,并且修正了Coron等人美密论文和Chang等人亚密论文的安全性证明。
Symmetric-key algorithms and hash functions play a fundamental role in modern cryp-tography. They are primitives in cryptography and many high-level protocols can be buildfrom these primitives. However, it is hard to give a provable security analysis on symmetric-key cryptography. Many symmetric-key algorithms and hash functions are built by experi-ence and lack of rigorous theoretical proof.
Fortunately, there are some principles for us to design block ciphers and hash functions.We usually first build a high-level construction and framework based on some ideal com-ponents, then we consider the details in the internal component. For block cipher construc-tions, there are two main designs: Feistel structure and Substitution-Permutation-Networkstructure, there are also many extended designs such as Lai-Massey, Gen-Skipjack, Gen-CAST256, Gen-MARS, SMS4, Four-Cell, RC6. Usually a stream cipher is based on linearfeedback shift registers (LFSR), but some stream ciphers are built from block ciphers byusing the corresponding mode of operation. For hash functions, actually most constructionsare based on block ciphers, such as MD4, MD5, SHA-1, MDC-2.
We usually treat a good block cipher as a pseudorandom permutation, thus cryptanal-ysis on a block cipher usually is related to the pseudorandomness or indistinguishabilityof this cipher. If we have an ideal internal component and we can prove the security of aconstruction based on this internal component, we say it is a construction with provable se-curity. It is also a popular research line for researchers in the literature. For LFSR-basedstream ciphers, researchers usually focus on the pseudorandomnes of the key stream, suchas period, balance and auto-correlation property. This method is different from that analysisin block ciphers and more knowledge about finite fields are required. The benefit of this typeof stream cipher is that some of the security properties can be proved, a typical example isthe WG stream cipher which has long period, balance and ideal two-level auto-correlationproperty. LFSR-based stream ciphers are also widely used in practice since they are veryefficient in hardware.
After flaws in widely used hash functions such as MD5, SHA-1are found, researchon hash functions is becoming hot. Some new security models such as Indistinguishability,Indifferentiability are proposed to prove the security of the iterative modes of hash construc-tions. For compression function constructions, the popular way is to built on block ciphers.But some compression functions are based on hard mathematical problems, such as multi-variate polynomial based hash functions.
In this thesis we give a structural analysis on symmetric-key algorithms and hash func-tions due to their design similarity. We obtain the following results:
1. We find that the two-round (extended) Lai-Massey scheme is not pseudorandom andthree-round (extended) Lai-Massey is not strong pseudorandom. We use the couplingtechnology from Markov chain theory to prove beyond-birthday-bound for the (strong)pseudorandomness of many-round Lai-Massey. Currently this is the best securitybound for Lai-Massey scheme.
2. We give an impossible differential cryptanalysis on Gen-Skipjack, Gen-CAST256,Gen-MARS, SMS4, Four-Cell, RC6block cipher structure and obtain some goodresults. According to the results, we disprove Sung et al.’s conjecture proposed inAsiacrypt’2000and Pudovkina’s claim in FSE’2009.
3. We design a lightweight stream cipher WG-7based on the original WG stream cipher.We analyze the security and apply it to RFID authentication protocols.
4. We analyze the security of multivariate polynomial hash functions and point out thesehash functions cannot be secure against high order differential cryptanalysis.
5. We give a synthesis analysis on blockcipher-based hash functions and solve the openproblem left by Hirose and discover the flaws in the best paper of FSE’2009.
6. We succeed in attacking a rate-2/3hash construction proposed by Lee et al. Our attackcontradicts its security claims made by the designer.
7. We give a synthesis indifferentiable analysis of the pfMD, chopMD, NMAC/HMACbased on different PGV constructions. We show that these four constructions havedifferent security under different PGV constructions. We also revise Coron et al. andChang et al.’s security proof.
然而,设计一个对称密码或者哈希函数并不是盲目的,人们通常首先需要设计一种构造方案,搭建一个基本的骨架,然后再不断细化内部的各个部分。分组密码的常用构造有Feistel结构和Substitution-Permutation-Network结构。再往下具体划分有Lai-Massey, Gen-Skipjack, Gen-CAST256, Gen-MARS, SMS4, Four-Cell, RC6等等。对于流密码而言,很多则是基于线性移位寄存器(LFSR)的构造。有的流密码则是基于分组密码的运行模式直接得到。对于哈希函数,一般流行的方法都实质是基于分组密码的方法的,例如MD4, MD5, SHA-1, MDC-2等等。
对分组密码的构造的安全性进行研究,就是对其伪随机性或不可区分性进行研究,如果分组密码的内部模块是理想的,若能证明基于该理想的模块能够构造出理想的分组密码,则说明该构造是没有问题的,这也是当前学术界公认的研究方法。基于LFSR的流密码由于其数学性质丰富,容易从数学角度来研究其输出密钥流的伪随机性,例如周期性,平衡性,自相关性等等。这一套研究方法是不同于分组密码的,需要用到更多有限域理论上的知识。一般来说,这类流密码的好处就是其部分数学性质是可以证明的,典型的例子就是wG流密码,其密钥流具有固定的周期,平衡性和理想两阶自相关性。同时,由于基于LFSR的流密码在硬件上的效率非常高,在实际中得到了很好的应用。
对于哈希函数的构造,自MD5, SHA-1等已被广泛应用的哈希函数相继被找出漏洞之后,整个密码学界也重新掀起了对哈希函数的研究热潮。很多新的可证明安全模型,如Indistinguishability、Indifferentiability等被用来证明哈希函数的迭代构造的安全性。对于压缩函数的构造,流行的方法是采用基于分组密码的方法,但也有一些其他的基于数学困难问题的构造,如基于多项式的压缩函数被提出。
由于对称密码和哈希函数构造的相似性,本文从算法的基本构造入手,对常用的对称密码学的构造进行结构化的分析,取得了以下的进展：
1.对分组密码中的Lai-Massey构造方案进行了伪随机性分析,找到了对Lai-Massey及Extended Lai-Massey构造的2轮伪随机区分器及3轮强伪随机区分器,并且利用马尔科夫链理论在理论上首次证明了多轮Lai-Massey构造可以达到超出生日界限的安全性,这是已知最好的对Lai-Massey结构的分析。
2.提出了一种对分组密码结构不可能差分的统一方法,对若干种常用的分组密码构造的方案,如Gen-Skipjack, Gen-CAST256,Gen-MARS, SMS4, Four-Cell, RC6等进行了不可能差分分析,取得了较好的结果,否定了亚密2000年Sung等人提出的猜想,推翻了FSE2009Pudovkina的结论。
3.研究了一类数学性质良好的WG流密码的构造,并设计了一个轻量级的WG-7流密码,对其安全性进行了充分的分析并对其实现,并分析了其在RFID的认证协议上应用的可行性。
4.研究了基于多元多项式构造哈希函数的安全性,并指出此类哈希函数不能抵抗高阶差分攻击。
5.在基于分组密码的哈希函数构造进行了新的分析,对基于分组密码的哈希函数进行全面性的分析归纳。解决了Hirose留下的公开问题,并发现了FSE2009最佳论文中定理的漏洞,且对其修正。
6.成功的攻破了Lee等人提出的一类哈希率为2/3的基于三轮Feistel结构的哈希函数,否定了该构造具有设计者宣称的理想抗碰撞安全性。
7.对基于PGV构造的哈希函数在pfMD、chopMD、NMAC/HMAC迭代下的不可区分性(Indifferentiability)进行了归纳性研究,首次提出这四种迭代模式在不同PGV构造下具有不同的安全性,并且修正了Coron等人美密论文和Chang等人亚密论文的安全性证明。
Symmetric-key algorithms and hash functions play a fundamental role in modern cryp-tography. They are primitives in cryptography and many high-level protocols can be buildfrom these primitives. However, it is hard to give a provable security analysis on symmetric-key cryptography. Many symmetric-key algorithms and hash functions are built by experi-ence and lack of rigorous theoretical proof.
Fortunately, there are some principles for us to design block ciphers and hash functions.We usually first build a high-level construction and framework based on some ideal com-ponents, then we consider the details in the internal component. For block cipher construc-tions, there are two main designs: Feistel structure and Substitution-Permutation-Networkstructure, there are also many extended designs such as Lai-Massey, Gen-Skipjack, Gen-CAST256, Gen-MARS, SMS4, Four-Cell, RC6. Usually a stream cipher is based on linearfeedback shift registers (LFSR), but some stream ciphers are built from block ciphers byusing the corresponding mode of operation. For hash functions, actually most constructionsare based on block ciphers, such as MD4, MD5, SHA-1, MDC-2.
We usually treat a good block cipher as a pseudorandom permutation, thus cryptanal-ysis on a block cipher usually is related to the pseudorandomness or indistinguishabilityof this cipher. If we have an ideal internal component and we can prove the security of aconstruction based on this internal component, we say it is a construction with provable se-curity. It is also a popular research line for researchers in the literature. For LFSR-basedstream ciphers, researchers usually focus on the pseudorandomnes of the key stream, suchas period, balance and auto-correlation property. This method is different from that analysisin block ciphers and more knowledge about finite fields are required. The benefit of this typeof stream cipher is that some of the security properties can be proved, a typical example isthe WG stream cipher which has long period, balance and ideal two-level auto-correlationproperty. LFSR-based stream ciphers are also widely used in practice since they are veryefficient in hardware.
After flaws in widely used hash functions such as MD5, SHA-1are found, researchon hash functions is becoming hot. Some new security models such as Indistinguishability,Indifferentiability are proposed to prove the security of the iterative modes of hash construc-tions. For compression function constructions, the popular way is to built on block ciphers.But some compression functions are based on hard mathematical problems, such as multi-variate polynomial based hash functions.
In this thesis we give a structural analysis on symmetric-key algorithms and hash func-tions due to their design similarity. We obtain the following results:
1. We find that the two-round (extended) Lai-Massey scheme is not pseudorandom andthree-round (extended) Lai-Massey is not strong pseudorandom. We use the couplingtechnology from Markov chain theory to prove beyond-birthday-bound for the (strong)pseudorandomness of many-round Lai-Massey. Currently this is the best securitybound for Lai-Massey scheme.
2. We give an impossible differential cryptanalysis on Gen-Skipjack, Gen-CAST256,Gen-MARS, SMS4, Four-Cell, RC6block cipher structure and obtain some goodresults. According to the results, we disprove Sung et al.’s conjecture proposed inAsiacrypt’2000and Pudovkina’s claim in FSE’2009.
3. We design a lightweight stream cipher WG-7based on the original WG stream cipher.We analyze the security and apply it to RFID authentication protocols.
4. We analyze the security of multivariate polynomial hash functions and point out thesehash functions cannot be secure against high order differential cryptanalysis.
5. We give a synthesis analysis on blockcipher-based hash functions and solve the openproblem left by Hirose and discover the flaws in the best paper of FSE’2009.
6. We succeed in attacking a rate-2/3hash construction proposed by Lee et al. Our attackcontradicts its security claims made by the designer.
7. We give a synthesis indifferentiable analysis of the pfMD, chopMD, NMAC/HMACbased on different PGV constructions. We show that these four constructions havedifferent security under different PGV constructions. We also revise Coron et al. andChang et al.’s security proof.
引文
[1] E. Andreeva, G. Neven，B. Preneel, and r.Shirmpton. Seven-property-preservieg hashing: Rox. InKaoru Kurosawa, editor, ASIACRYPT2007’ volume LNCS4833, pages130-146. Springer,2007.
[21J. P. Aumasson and W. Meier. Analysis of multivariate hash functions. In Information Security andCryptology-ICISC2007, volume LNCS4817，pages309-323. Springer-Verlag，2007.
[3] M. Bellare，J. Kilian, and P. Rogaway. The security of cipher block chaining. In Advances inCryptology-CRYPTO'94y volume LNCS839，pages341-358. Sprioger-Verlag,1994,
[41M. Bellare and T. Ristenpart. Multi-property-preserving hash domain extension: The emd trans?form. In X. Lai Chen and K.，editors, ASIACRYPT'2006, volume LNCS4284，pages299-314.Springer-Verlag,2006.
[5] M, Bellare and T. Ristenpart Hash functions in the dedicated-key setting: Design choices and nipptransforms. In ICALP2007, volume LNCS4596，pages339410. Springer,2007.
[6j G. Bcrtoni, J. Dae men, M Peeters, and G. V. Assche. On the indiffcrentiability of tlic spongeconstruction. In Advances in Cryptology-EUROCRYPTQ8, volume LNCS4965, pages181-197,Istanbul, Turkey,2008. Springer-Verlag.
[71L. Bettale, J. Faug芑re，and L. Perret. Security analysis of multivariate polynomials for hashing. InInscrypt’2009，volume LNCS5487, pages115-124. Springer-Verlag,2009.
[8]R. Bhaltacharyya, A. Maiidal, and M. Naridi. Indifferenliability characterization of hash functionsand optimal bounds of popular domain extensions. In Progress in Cryptology-IND OCRYPT2009^volume LNCS5922，pages199-218，New Delhi, India,2009. Springer-Verlag.
[9]E. Bihanr, A. Biryukov, and A. Shamir. Cryptanalysis of skipjack reduced to31rounds usingimpossible diffrcntials. lo Advances in Cryptology-EVROCRYPT99, volume LNCS2595, pages12-23. Spirnger-Vedag，1999,
[10]O. Billet, M Robshaw，and T*Peyrin, On building hash functions from multivariate quadraticequations. In Proc ofACISPy volume LNCS4586，pages82-95. Springer-Verlag,2007.
[11]A. Biryukov and A. Shamir Cryptanalytic time/memory/data tradeoffs for stream ciphers. InASlACRYPrOO, volume LNCS1976，pages1-13. Springer-Verlag,2000.
[121L Black, M Cochran, and T. Shrimpton. On the impossibility of highly-eiffcicnt blockciphcr-bascdhash functions, volume3494of Lecture Notes in Computer Science, pages526—541，Aarhus,Denmark,2(K)5. Springer Verlag.
[13] J. Black, M. Cochran, and T. Shrimpton. On the impossibility of highly-efficient blockcipher-basedhash functions. Journal of Cryptology,22(3):311-329,2009.
[!4] L Black, R Rogaway, and r Shrimpton, Black-box analysis of the block-cipher-bascd hash-function constructions from PGV, In Advances in Cryptology-Crypto2002，Proceedings, volume2442of Lecture Notes in Computer Science，pages320-335. Springer-Verlag,2002,
[15]J. Black, P. Rogaway, T. Shrimpton, and M. Slam. An analysis of the blockcipher-based hashfunctions from PGV. Journal of Cryptology,23(4):519-545,2010.
[16]D. Chang, S. Lee，M. Nandi, and M. Yung, Indifferentiable secuirty analysis of popular hashfunctions with preifx-free padding. In Advances in Cryptology-ASIACRYPT06, volume LNCS4284, pages283-298，Shanghai, China，2006. Springer Verlag.
[I7J D. Chang, M. Nandi, J. Lee, L Sung, S. Hong, J. Lim, H. Park, and K. Chun. Compression functiondesign pirnciples supporting variable output lengths from a single small function. IEICE Transac?tions on Fundamentals of Electronics, Communications and Computer Sciences，E91-A(9):2607-2614,2008.
[18] V. Chcpyzhov, T. Johansson, and B. Smeets. A simple algoirthm for fast correlation attacks onstream ciphcrs. In Fast Sotfware Encryption2000’ volume LNCS1978，pages181-195. Springer-Vcrlag,2000.fl9] J. Choy，G. Chew, K. Khoo, and H. Yap. Cryptographic properties and application of a generalizedunbalanced feislel network structure. In Proc of ACI SP*20099volume LNCS5594，pages73—89.Spring-Verlag,2009.
[20]L Choy and H. Yap. Impossible boomerang attack for block cipher structures. In Proc ofIWSEC2009, volume LNCS5824, pages22-37. Springer-Verlag,2009.
[21]J. S. Coron, Y. Dodis，C. Malinaud, and P. Puniya. Merkle-damgad revisited: How to constructa hash function. In Advances in Cryptology-CRYPTO，05’ volume LNCS3621，pages430-448.Springer-Verlag,2005.
[221J-S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle-damgard revisited: How to construct ahash function (full version), http://people.csail.niit.edu/dodis/ps/merkle.ps,2005.
[23] J. S. Coron, Y. Dodis，A. Mandal, and Y. Seurin. A domain extender for the ideal cipher. In Theoryof Cryptography-TCC，2010，volume LNCS5978，pages273-289，Zuirch, Switzerland，2010.Springer-Verlag.
[241J. S. Coron, J, Patarin, and Y. Seurin. The random oracle model and the ideal cipher model areequivalent. In David Wagner, editor, Advances in Cryptology-CRYPTO2008，volume LNCS5157，pages1-20. Springer-Verlag,2008,
[25] M Courtois. Fast algebraic attacks on stream ciphers with linear feedback. In Advances inCryptology-C'rypto2003y volume LNCS2729，pages176-194. Springer-Verlag’2003.
[261N. Courtois and W. Meier. Algebraic attacks on stream ciphers witli lienar feedback. In Advancesin Cryptology-Eurocrypt '2003, volume LNCS2656，pages345-359. Springer,2003.
[27]【，B.Darngard. A design principle for hash functions. In G. Brassard，editor, Advances inCryptology-Proc.Crypto f89t volume LNCS435，pages416-427. Springer-Verlag，Berlin,1990.
[28]DES. Data Encryption Standard. National Tech. Info. Services, Springifeld, USA,1977.
[29\J. Ding and B. Yang. Multivariates polynomials for hashing. In INSCRYPT2007y volume LNCS4990. Springer,2008.
[30]1. Dinur and A. Shamir. Cube attacks on tweakable black box polynomials. In Advances inCryptology-Eurocrypt'2009y volume LNCS5479，pages278-299. Springer,2009.
[31]Y. Dodis, L. Reyzin, R. L. RivesU and E. Shen. Indifferentiability of permuiation-based compres?sion functions and tree-based modes of operation, with applications to md6. In FSE、2009，volumeLNCS5665，pages104-121, Leuven, Belgium,2009, Springer-Verlag.
[32]Y. Dodis，T. Ristcnpart, and T. Shrimpton, Salvaging merkle-damgard for practical applications.In EUROCRYPT2009, volume LNCS5479，pages371-388. Springer,2009.
[33]T. Eisenbarlli, S. Kumar，C. Paar,八.Posclunanii, and L. Uhsadcl.八survey of lightweight-cryptography implementations. IEEE Design&Test of Computers,24(6):522-533,2007.
[341D. Engels, X. Fan, G. Gong, H. Hu，and E. M. Smith. Hummingbird: ultra-lightweighl cryptogra?phy for resoucre-constrained devices. In Financial Cryptography2010, volume LNCS6054，pages3-18. Spirnger-Verlag,2010.
[35] S. Even and Y. Mansour. A construction of a cipher from a single pseudorandom permutation.Journal ofCryptology,10(3):151-162,1997.
[36J X. Fan，IL Hu, G. Gong, E. M Smith, and D. Engels. Lightweight implementation of hummingbirdcryptographic algorithm on4-bit microcontrollers. In RISC2009, pages838-844，2009.
[37] H. Feistel. Cryptography and computer privacy. Scientiifc American,228(5):15-23,1973.
[381HPS. PIPS180-1Secure Hash Standard. Federal Information Processing Standard (FIPS), Pub?lication180-1, National Institute of Standards and Technology, US Department of Commerce,Washington D.C，1995.
[39]FIPS. FIPS-197: Advanced Encryption Standard, november200L available athttp://csrc.nist.gov/publications/ifps/ifps197/ifps-197.pdf”2001.
[40]E. Fleischmann, M, Gorski, and S. Lucks. On the security of tandem-DM volume5665LNCSof Lecture Notes in Computer Science (including subseries Lecture Notes in Artiifcial Intelligenceand Lecture Notes in Bioinformatics), pages84—103, Leuven, Belgium,2009. Springer Verlag.
[411E-Fleischmariii, M. Gorski, and S. Lucks. Security of cyclic double block length bash functions.In Cryptography and Coding2009’ volume LNCS5921, pages153-175. Springer-Verlag,2009.
[42J G. Gong and A. Youssef. Cryptographic properties of the Welch-Gong transformation sequencegenerators. IEEE Transaction on Information Theory’48(11):2837-2846,2002.
[43]Z. Gong, X. J. Lai, and K. E Chen. A syntlietic indiffercntiability analysis of some block-ciphcr-bascd hash functions. Designs Codes and Cryptography,48(3):293-305,2008.
[44]T. Good and M. Benaissa. Aes on fpga from the fastest to the smallest. In CHES2005，volumeLNCS3659，pages427-440. Springer,2005.
[45]M. Hattori, S. Hirose, and S. Yoshida. Analysis of double block length hash functions. Cryptogra?phy and Coding，Proceedings,2898:290-302,2003.
[46]K. Hidenori and M. Masakatu. Indifferentiability of single-block-length and rate-1compression1'uiicLions. IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences, E90-A:2301-2308,2007.
[471S. Hirose. Secure block ciphers are not sufficient for one-way hash functions in the Preneel-Govaerts-Vaiidewalle model. Selected Areas in Cryptography,2595:339-352，2003.
[48]S. Hirose. Provably secure double-block-length hash functions in a black-box model. InformationSecurity and Cryptology-ICISC2004，LNCS3506:330-342,2004.
[49]S. Hirose. Weak security notions of cryptographic unkeyed hash functions and their ampliliabil-ity. leice Transactions on Fundamentals of Electronics Communications arid Computer SciencesyE88A(l):33-38，2005.
[50]S. Ilirose. A security analysis of double-block-length hash functions with the rate1? leice Transac?tions on Fundamentals of Electronics Communications and Computer Sciences、E89A(10):2575-2582，2006.
[511S. Hirose. Some plausible constructions of double-block-length hash functions. In Fast SotfwareEncryption, volume LNCS4047，pages210-225,2006.
[52J S. Hirose and R Kuwakado. A scheme to base a hash function on a block cipher, volume5381LNCS of Lecture Notes in Computer Science (including subs eries Lecture Notes in Artiifcial In?telligence and Lecture Notes in Bioinformatics》，pages262-275，Sackville, NB，Canada，2008.Springer Verlag.
[53] S, Hirose and H, Kuwakado, Efifcient pseudorandom-function modes of a block-cipher-basedhash function. leice Transactions on Fundamentals of Electronics Communications and ComputerSciences, E92A(10):2447-2453,2009.
[541S. Hirose, J. H. Park, and A. Yun. A simple variant of the merkle-damgfKrd scheme with a per?mutation. In Kaoru Kurosawa, editor, ASIACRYPT2007y volume LNCS4833，pages113—129.Springer,2007.
[55J V.\\Hoang and P. Rogaway. On generalized feistel networks. In T. Rabin, editor, CRYPTO20】0,volume LNCS6223，pages613-630, Springer,2010.
[56] W. llohl, X. Lai，T_Meier, and C. Waldvogel. Secuirty of iterated hash functions based on blockciphers. In Advances in Cryptology-CRYPTO '93, volume LNCS773, pages379-379，SantaBarbara, CA, United states,1994, Springer-Verlag.
[571S. Hong and J. Lim J. Kim. Impossible differential cryptanalysis using matrix metJiod. DiscreteMathematics，310:998-1002，2010.
[58] ISCX ISO/IEC10118Information technology-Security techniques-Hash-functions,1994.
[591T. Jakobsen and L. R. Kiiudsen. The interpolation attack on block ciphers. In Eli Biham，ediior，FastSoftware Encryption-FSE，97，volume LNCS1267，pages28-40, I laifa, Israel,1997. Springcr-Verlag.160] A. Joux. Mullicollisioas in iterated hash functions, application lo cascaded constructions. In Ad?vances in Cryptology-CRYPTO，04’ volume LNCS3152，pages306-316. Springer-Verlag,2004.
[61] P. Junod and S. Vaudenay. FOX: a new family of block ciphers. In Selected Areas in Cryptography-SAC,2004，volume LNCS3357，pages114-129. Springer-Verlag，2004.
[621J-Katz and Y. Lindell. Introduction to modern cryptography. CRC Press，2007.
[63] L Kelsey and B, Schneien Second preimages on n-bit hash functions in much less ihan2n work. InAdvances in Cryptology-EUROCRYPTQ5, volume LNCS3494, pages474^t90, Springer-Verlag,2005.
[64J L Kim, S. Hong, J*Sung, S*Lee, and J. Lim. Impossible differential cryptanalysis for block cipherstructures. In INDOCRYPT2003, volume LNCS2904, pages82-96. Springer-Verlag,2003.
[65] L. R. Knudsen. Truncated and higher order differentials. In Bart Preoeel, editor, Fast SotfwareE*ncryption-FSE94, volume LNCS1008，pages196-211, Leuveo, Belgium,1995, Springer-Verlag.
[661L. R. Kiiudsen. Truncated and higher order differentials. In B. Preneel，editor, FSE，volume LNCS1008，pages196-211. Springer,1995.
[67]L, R, Knudsen, X. L Lai, and B. Preneel, Attacks on fast double block length hash functions.Journal of Cryptology,11(1):59-72,1998.
[68]Y. Ko, S. Hong, W. Lee, S, Lee, and J.S. Kang. Related key differential attacks on27rounds ofxtea and full-round gost. In Fast Sotfware Encryption2004，volume LNCS3017，pages299-316.Springer,20()4.
[69J Z. Kohavi. Switching and Finite Automata Theory. McGraw-Hill,1978.
[70J【【.Kuwakado and S*Hirose, Differentiability of four preifx-free PGV hash functions, IEICEElectronics Express,6(13):955-958,2009.
[71] H, Kuwakado and M Morii. Compression functions suitable for the imilU-property-preservingtransform. IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences，E91-A(l0):2851-2859，2008.
[72J X.On the design and security of block ciphers, volume1of ETH Series in InformationProcessing. Hartung-Gorre Verlag, Konstanz,1992,
[731X. Lai. Higher order derivatives and differential cryplanalysis. In Communicatoms and Cryptogra?phy: Two Sides of One Tapestry” pages227_233，Switzerland，1994. Kluwer Academic Publishers.
[74] X. Lai and J. L. Masscy.八proposal for a new block encrypiton standard. In Damgard Ivan,editor, Advances in Cryptology-EURQCRYPT90y volume LNCS473，pages389404，Aarhus,Denmark,1990. Springer-Verlag.「751X. Lai and J. L. Massey. Markov ciphers and differential cryplanalysis. In Donald W. Davies,editor，Advances in Cryptology-EUROCRYPT'91, volume LNCS547，pages17-38? Brighton,UK,1991, Springer-Verlag.
[76] X. Lai and L L. Massey. Hash functions based on block ciphers. In R. A. Rueppel，edtior, Advancesin Crypt*ography-Eurocrypt92, volume LNCS658, pages55-7(1Springer-Verlag,1992.
[77J L Lee, S. Hong, L Sung, and II. Park. A new double-block-lengtli hash function using feistelstructure. In J. H. Park et al, editor, ISA2009, volume LNCS5576，pages11-20，2009.
[78J L Lee, M. Stam, and J. Steinberger. The preimage secuirty of double-block-length compressionfunctions, http://eprintiacr.org/2011/2l(Xpdf，2011.
[79] J. Lee and J. Stcinbcrger. Multi-property-preserving domain extension using polynomial-basedmodes of operation. In Advances in Cryptology ‘EUROCRYPT，l()’ volume LNCS6110，pages573-596，French Riviera, France,2010. Springer-Verlag.
[801D. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. American MaltiemaiicalSociety,2008.
[81]R. Lidl and H.Niederreiter. Finite ifelds. Encyclopedia of Mathematics and its applications.Addision-Wesley Publishing Company,1983.
[82]J. Lu. Attacking reduced-round versions of the sms4block cipher in the Chinese wapi standard. InProc of/CICSW, volume LNCS4861, pages306-318. Springer-Verlag,2007.
[831M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom func?tions. SIA M Journal on Computing,17(2):373-386,1988.
[84J S. Lucks. A collision-resistant rate-1doublc-block-lengtli hash function. Id Symmetric Cryptogra?phy, number07021in Dagstuhl Seminar Proceedings, Dagstuhl, Germany,2007. InternationalesBegcgnungs-und Forschungszentrum fur Informatik (IBFI)，Schloss DagstuW, Germany.
[85] Y. Luo and X. Lai. On the security of multivariate hash functions. Journal of Shanghai JiaotortgUniversity (Science)^14(2):219-222，2009.
[86J Y. Luo, X. Lai, and Z, Gong. Pseudorandomness analysis of the (extended) lai-massey scheme.Information Processing LMtersy111(2):90-96,2010.
[87] Yiyuan Luo, Zheng Gong, Ming Duan, Bo Zhu，and Xuejia Lai. Revisiting Ihe indifferenliabilityof PGV hash functions. Cryptology ePrint Archive, Report2009/265,2009. http://eprint.iacr.org/.
[88J U. Maurer, K. Pietrzak, and R. Rcnnen Indistinguishability ampliifcation. In A. Menezes，editor,CRYPTO2007，volume LNCS4622，pages139-149. Springer,2007.
[89] U. Maurer, R. Ronncr, and C. Holenstein. Tndifferentiability, inpossibilily results on reductions,and applications to the random oracle methodology, Io TCC2004, pages21-39，2004.
[901U. M. Maurer. A simpliifed and generalized treatment of luby-rackoff pseudorandom permuialiongenerators. In Advances in Cryptology-EUROCRYPTvolume LNCS658，pages239-255.Springer-Verlag, Berlin,1992.
[91] A. Maximov and A. Biryukov, Two trivial attacks on irivium. In Selected Areas in Cryptography2007，volume LNCS4876，pages36-55. Springer,2007.
[921G. Meiser, T. Eisenbarth, K. Lemke-Rust, and C. Paar. Software implementation of estream profilei ciphers on embedded8-bit avr microcontrollers. In SASC2007，2007.
[93]A. J. Menezes, R C van Oorschot, and S. A. Vanstone. Handbook ofA pplied Cryptography. CRCPress’1997.
[94]R. C. Merkle. One way hash functions and DES. In Advances in Cryptology-CRYPTO,89，volumeLNCS435，pages428-446. Springer-Verlag,1989.
[951I. Mirinov.(not so) random shuflfes of RC4. In CRYPTO2002’ volume LNCS2442，pages304-319. Springer,2002.
[96] S. Moriai and S. Vaudenay. On the pseudorandomness of top-level schemes of block ciphers. InAdvances in Cryptology-ASIACRYPT00, volume LNCS1976，pages289-302, Springer-Verlag,2000.
[971B. Morris, P. Rogaway, and T. Stegers. How to encipher messages on a small domain deterministicencryption and the thorp shuflfe. In CRYPTO2009，volume LNCS2009，pages2B6-302. Springer,2009.
[98j M, Nandi. Towards optimal double-length hash functions. In INDOCRYPT05, volume LNCS3797，pages77-89. Springer-Verlag,2005.
[99] M. Naiidi, W. Lee, K. Sakurai, and S. Lee, Security analysis of a2/3-rate double length compressionf’unction in the black-box model. In Fast Software Encryption-FSE2005, volume LNCS3557,pages243-254. Springer-Vedag,2005.
[100J M. Naor and O, Rciogold, From unpredictability to indistinguishability; A simple constructionof pseudo-random functions from macs (extended abstract). In Hugo Krawczyk，editor, CRYPTO,volume LNCS1462，pages267-282. Springer，1998.
[101]M Naor and CX Reingold On the construction of pseudorandom permutations: Luby-Rackoffrevisited. Journal of Cryptology,12(1):22-66,1999.
[102]Y，Nawaz and G. Gong, WG; A family of stream ciphers with designed randomness properties.Information Science,178(7):1903-1916,2008.
[103j NISI: Third (ifnal) round candidates,2010. http://csrc.oist.gov/groups/ST/hash/sha-3/Round3/submissions-rnd3,html,
[104] K. Nybcrg and L. R. Knudscn. Provable secuirty against differential cryptanalysis. Journal ofCryptology,8(1):27-37,1995.
[105J D. Otte. Avr-crypto-lib, http://www,das-labor.org/wiki/avr-crypto-l!b/en,2009,
[106] O. Ozen and M. Stam. Anotlicr glance at double-length hashing. In Cryptography and Coding,12th IMA International Conference, Cryptography and Coding2009, volume LNCS5921, pages176-201. Springer-Verlag, Berlin,2009.1107J J. Patario. How to construct pseudorandom and super pseudorandom permutations from one singlepseudorandom function. In Raincr A, Rucppel, editor, Advances in Cryptology-EUROCRYPT'92,volume LNCS658, pages256—266，Balatonliired, Hungary,1993. Springer-Verlag.
[1081J. Patarin”. The coefifcients H” technique. In R. Avanzi Sica, L. Keliher, and P., editors, SelectedAreas in Cryptography-SAC2008，volume LNCS5381, pages328-345. Spirnger，2009.
[109j T. Pcyirn, H, Gilbert, E Muller, and M Robshaw, Combining compression functions and blockcipher-based hash functions. Advances in Cryptology-ASIACRYPT2006，4284:315-331468,2006.
[110|B. Prcneel. Hash functions and mac algorithms based on block ciphers. In Proceedings of the19976th IMA International Conference on Cryptography and Coding, Dec1997’ volume1355of Lec?ture Notes in Computer Science, pages270-270. Cirencester, United kingdom,1997. Compilationand indexing terms, Copyright2010Elsevier Inc. Compendex199803413225703029743.『1111B. Preneel. The stale of cryptographic hash functions. In Lectures on Data Security, ModernCryptology in Theory and Practice, Summer School, Aarhus, Denmark,1998.
[112]B. Preneel, R. Govaerts, and J. Vandcwalle. Hash functions based on block ciphers; A syntheticapproach. In IXR, Stinson, editor, Advances in Cryptology ‘Proc. Crypto'93y volume LNCS773，pages368-378. Springer-Verlag, Berlin,1993.
[113]M. Pudovkina.On impossible truncated differentials of generalized feis-tel and skipjack ciphers.In FSE2009rump session. Avaiablc at:http://fsc2009rump.cryp.to/e31bba5dl227cac5ef0daa6bcbf66f27.pdf,2009.
[114J T, Ristcnpart and1\Shrimpton. I low to build a hash function from any collision-resistant func-lion. In Advances in Cryptology-AS!ACRYPT’07，volume LNCS4833，pages147-163，KuchingtMalaysia,2007. Springer-Verlag.
[115]R. Rivest, M. Robshaw, R. Sidney, and Y. Yin. The RC6block cipher,1998.ftp://rsasecurity.com/pub/rsalabs/rc6/rc6v11.pdf,
[116]R. L. Rivest. The md4message digest algorithm. In S. Vanstone, editor, Advances in Cryptology-CRYPT(),90，volume LNCS537，pages303-311. Springer-Verlag,1991.\1171R. L. Rivest. The MD5message digest algorithm. In Request for Comments (RFC)1321. IiiiernetActivities Board, Internet Privacy Task Force,1992.
[118]S. Ronjonr and T. Helleselh. Attacking the iflter generator over gf{2m). In WAIFA2007，volumeLNCS4547, pages264-275. Springer,2007.
[119]S. Ronjom and l\I Iclleseth. A new attack on the iflter generator. IEEE Transactions on InformationTheory,53(5):1752-1758,2007.
[120j B. Sadcghiyan and J. Pieprzyk. On necessary and suiffcient conditions for the construction of superpseudorandom permutations. In Abstracts ofASlACRYPT91, volume LNCS739，pages194-209.Springer-Verlag,1991.
[121] Satoh, JVL llaga, and K. Kurosawa. Towards secure and fast hash functions. IEICE Transactionson Fundamentals of Electronics, Communications and Computer Sciences, E82-A(1):55-62,1999.『1221C. Shannon.(Communication theory of secrecy systems. Bell System Technical Journal,28(4):656-715,1949.
[123]T. Siegenthaler. Corerlation-immunity of nonlinear combining functions for cryptographic appli?cations. IEEE Trans. Info. Theory，30(5):776-780,19B4.
[124]SMS4. Specication of SMS4, block cipher for WLAN products SMS4(in Chinese). Avaiable at:http://www.oscca.gov.cn/IIpFile/200621016423197990.pdf.『1251M. Stam. Block cipher based hashing revisited. In Fast Software Encryption2009，volume LNCS5665，pages67-83. Springer, Berlin,2009?
[126J J. P, Stcinberger The collision intractability of MDC-2in the ideal-cipher model. In Advances inCryptology-Proceedings of EUROCRYPT2007, volume LNCS4515of Lecture Notes in ComputerScience, pages34-51, Barcelona, Spain,2007. Springer Verlag’ Berlin.
[127] J, Sung, S‘Lee, J. Lim, S. Hong, and S. Park. Provable security for the skipjack-like struc?ture against differential cryptanalysis and linear cryptanalysis. In Advances in Cryptology-ASlACRYPrOO, volume LNCS1976，pages274-288. Springer-Verlag,2000.
[1281S. Vaudenay. Provable security for block ciphers by decorrelation. In Theoretical Aspects ofComputer Science-STAGS*98y volume LNCS1373，pages249-275. Springer,1998,
[129]S-Vaudenay. Oil the Lai-Massey scheme. In Advances in Cryptology-ASIACRYPT'99, volumeLNCS1716’ pages8-19. Springer-Verlag,1999.
[130]S. Vaudenay. Decorrelation; A theory for block cipher security. Journal of Cryptology,16(4):249-286，2003.
[131]M Vogt, A. Poschmaoo, and C Paar. Cryptography is feasible on4-bit microcontrollers-a proofof concept. In IEEE International Conference on RFID, pages241-248,2009.
[132]D4Wagner. A generalized birthday problem. In M. Yung, editor, CRYPTO2002, volume LNCS2442, pages288-303. Springer,2002.
[133]X. Wang, Y. L Yin, and H, Yu. Finding collisions in the full SHA-L In Victor Shoup，editor,Advances in Cryptology-CRFTO，05’ volume LNCS3621, pages17-36, Santa Barbara, CA，USA,2005. Spirnger-Verlag.
[134|X. Wang and H. Yu. How lo break MD5and other hash functions. In Ronald Cramer, editor,Advances in Cryptology-EUROCRYPT05, volume LNCS3494, pages19一35，Aarhus, Denmark,2005. Spirnger-Verlag.
[1351W. Wu，L. Zhang, L. Zhang, and W. Zhang. Security analysis of the gf-nlfsr structure and four-cellblock cipher In Proc oflClCS2009, volume LNCS5927，pages17-31. Springer-Verlag,2009.
[136]IL Yap. Impossible differential characteirstics of extended feistel networks with provable secuirtyagainst differential cryptanalysis. In SecTech2008, volume COS29，pages103-121，2009.
[137]A, Yun, J*Park, and L Lee. On lai-massey and quasi-feistel ciphers. Designs Codes and Cryptog?raphy,58:45-72，2011.
[21J. P. Aumasson and W. Meier. Analysis of multivariate hash functions. In Information Security andCryptology-ICISC2007, volume LNCS4817，pages309-323. Springer-Verlag，2007.
[3] M. Bellare，J. Kilian, and P. Rogaway. The security of cipher block chaining. In Advances inCryptology-CRYPTO'94y volume LNCS839，pages341-358. Sprioger-Verlag,1994,
[41M. Bellare and T. Ristenpart. Multi-property-preserving hash domain extension: The emd trans?form. In X. Lai Chen and K.，editors, ASIACRYPT'2006, volume LNCS4284，pages299-314.Springer-Verlag,2006.
[5] M, Bellare and T. Ristenpart Hash functions in the dedicated-key setting: Design choices and nipptransforms. In ICALP2007, volume LNCS4596，pages339410. Springer,2007.
[6j G. Bcrtoni, J. Dae men, M Peeters, and G. V. Assche. On the indiffcrentiability of tlic spongeconstruction. In Advances in Cryptology-EUROCRYPTQ8, volume LNCS4965, pages181-197,Istanbul, Turkey,2008. Springer-Verlag.
[71L. Bettale, J. Faug芑re，and L. Perret. Security analysis of multivariate polynomials for hashing. InInscrypt’2009，volume LNCS5487, pages115-124. Springer-Verlag,2009.
[8]R. Bhaltacharyya, A. Maiidal, and M. Naridi. Indifferenliability characterization of hash functionsand optimal bounds of popular domain extensions. In Progress in Cryptology-IND OCRYPT2009^volume LNCS5922，pages199-218，New Delhi, India,2009. Springer-Verlag.
[9]E. Bihanr, A. Biryukov, and A. Shamir. Cryptanalysis of skipjack reduced to31rounds usingimpossible diffrcntials. lo Advances in Cryptology-EVROCRYPT99, volume LNCS2595, pages12-23. Spirnger-Vedag，1999,
[10]O. Billet, M Robshaw，and T*Peyrin, On building hash functions from multivariate quadraticequations. In Proc ofACISPy volume LNCS4586，pages82-95. Springer-Verlag,2007.
[11]A. Biryukov and A. Shamir Cryptanalytic time/memory/data tradeoffs for stream ciphers. InASlACRYPrOO, volume LNCS1976，pages1-13. Springer-Verlag,2000.
[121L Black, M Cochran, and T. Shrimpton. On the impossibility of highly-eiffcicnt blockciphcr-bascdhash functions, volume3494of Lecture Notes in Computer Science, pages526—541，Aarhus,Denmark,2(K)5. Springer Verlag.
[13] J. Black, M. Cochran, and T. Shrimpton. On the impossibility of highly-efficient blockcipher-basedhash functions. Journal of Cryptology,22(3):311-329,2009.
[!4] L Black, R Rogaway, and r Shrimpton, Black-box analysis of the block-cipher-bascd hash-function constructions from PGV, In Advances in Cryptology-Crypto2002，Proceedings, volume2442of Lecture Notes in Computer Science，pages320-335. Springer-Verlag,2002,
[15]J. Black, P. Rogaway, T. Shrimpton, and M. Slam. An analysis of the blockcipher-based hashfunctions from PGV. Journal of Cryptology,23(4):519-545,2010.
[16]D. Chang, S. Lee，M. Nandi, and M. Yung, Indifferentiable secuirty analysis of popular hashfunctions with preifx-free padding. In Advances in Cryptology-ASIACRYPT06, volume LNCS4284, pages283-298，Shanghai, China，2006. Springer Verlag.
[I7J D. Chang, M. Nandi, J. Lee, L Sung, S. Hong, J. Lim, H. Park, and K. Chun. Compression functiondesign pirnciples supporting variable output lengths from a single small function. IEICE Transac?tions on Fundamentals of Electronics, Communications and Computer Sciences，E91-A(9):2607-2614,2008.
[18] V. Chcpyzhov, T. Johansson, and B. Smeets. A simple algoirthm for fast correlation attacks onstream ciphcrs. In Fast Sotfware Encryption2000’ volume LNCS1978，pages181-195. Springer-Vcrlag,2000.fl9] J. Choy，G. Chew, K. Khoo, and H. Yap. Cryptographic properties and application of a generalizedunbalanced feislel network structure. In Proc of ACI SP*20099volume LNCS5594，pages73—89.Spring-Verlag,2009.
[20]L Choy and H. Yap. Impossible boomerang attack for block cipher structures. In Proc ofIWSEC2009, volume LNCS5824, pages22-37. Springer-Verlag,2009.
[21]J. S. Coron, Y. Dodis，C. Malinaud, and P. Puniya. Merkle-damgad revisited: How to constructa hash function. In Advances in Cryptology-CRYPTO，05’ volume LNCS3621，pages430-448.Springer-Verlag,2005.
[221J-S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle-damgard revisited: How to construct ahash function (full version), http://people.csail.niit.edu/dodis/ps/merkle.ps,2005.
[23] J. S. Coron, Y. Dodis，A. Mandal, and Y. Seurin. A domain extender for the ideal cipher. In Theoryof Cryptography-TCC，2010，volume LNCS5978，pages273-289，Zuirch, Switzerland，2010.Springer-Verlag.
[241J. S. Coron, J, Patarin, and Y. Seurin. The random oracle model and the ideal cipher model areequivalent. In David Wagner, editor, Advances in Cryptology-CRYPTO2008，volume LNCS5157，pages1-20. Springer-Verlag,2008,
[25] M Courtois. Fast algebraic attacks on stream ciphers with linear feedback. In Advances inCryptology-C'rypto2003y volume LNCS2729，pages176-194. Springer-Verlag’2003.
[261N. Courtois and W. Meier. Algebraic attacks on stream ciphers witli lienar feedback. In Advancesin Cryptology-Eurocrypt '2003, volume LNCS2656，pages345-359. Springer,2003.
[27]【，B.Darngard. A design principle for hash functions. In G. Brassard，editor, Advances inCryptology-Proc.Crypto f89t volume LNCS435，pages416-427. Springer-Verlag，Berlin,1990.
[28]DES. Data Encryption Standard. National Tech. Info. Services, Springifeld, USA,1977.
[29\J. Ding and B. Yang. Multivariates polynomials for hashing. In INSCRYPT2007y volume LNCS4990. Springer,2008.
[30]1. Dinur and A. Shamir. Cube attacks on tweakable black box polynomials. In Advances inCryptology-Eurocrypt'2009y volume LNCS5479，pages278-299. Springer,2009.
[31]Y. Dodis, L. Reyzin, R. L. RivesU and E. Shen. Indifferentiability of permuiation-based compres?sion functions and tree-based modes of operation, with applications to md6. In FSE、2009，volumeLNCS5665，pages104-121, Leuven, Belgium,2009, Springer-Verlag.
[32]Y. Dodis，T. Ristcnpart, and T. Shrimpton, Salvaging merkle-damgard for practical applications.In EUROCRYPT2009, volume LNCS5479，pages371-388. Springer,2009.
[33]T. Eisenbarlli, S. Kumar，C. Paar,八.Posclunanii, and L. Uhsadcl.八survey of lightweight-cryptography implementations. IEEE Design&Test of Computers,24(6):522-533,2007.
[341D. Engels, X. Fan, G. Gong, H. Hu，and E. M. Smith. Hummingbird: ultra-lightweighl cryptogra?phy for resoucre-constrained devices. In Financial Cryptography2010, volume LNCS6054，pages3-18. Spirnger-Verlag,2010.
[35] S. Even and Y. Mansour. A construction of a cipher from a single pseudorandom permutation.Journal ofCryptology,10(3):151-162,1997.
[36J X. Fan，IL Hu, G. Gong, E. M Smith, and D. Engels. Lightweight implementation of hummingbirdcryptographic algorithm on4-bit microcontrollers. In RISC2009, pages838-844，2009.
[37] H. Feistel. Cryptography and computer privacy. Scientiifc American,228(5):15-23,1973.
[381HPS. PIPS180-1Secure Hash Standard. Federal Information Processing Standard (FIPS), Pub?lication180-1, National Institute of Standards and Technology, US Department of Commerce,Washington D.C，1995.
[39]FIPS. FIPS-197: Advanced Encryption Standard, november200L available athttp://csrc.nist.gov/publications/ifps/ifps197/ifps-197.pdf”2001.
[40]E. Fleischmann, M, Gorski, and S. Lucks. On the security of tandem-DM volume5665LNCSof Lecture Notes in Computer Science (including subseries Lecture Notes in Artiifcial Intelligenceand Lecture Notes in Bioinformatics), pages84—103, Leuven, Belgium,2009. Springer Verlag.
[411E-Fleischmariii, M. Gorski, and S. Lucks. Security of cyclic double block length bash functions.In Cryptography and Coding2009’ volume LNCS5921, pages153-175. Springer-Verlag,2009.
[42J G. Gong and A. Youssef. Cryptographic properties of the Welch-Gong transformation sequencegenerators. IEEE Transaction on Information Theory’48(11):2837-2846,2002.
[43]Z. Gong, X. J. Lai, and K. E Chen. A syntlietic indiffercntiability analysis of some block-ciphcr-bascd hash functions. Designs Codes and Cryptography,48(3):293-305,2008.
[44]T. Good and M. Benaissa. Aes on fpga from the fastest to the smallest. In CHES2005，volumeLNCS3659，pages427-440. Springer,2005.
[45]M. Hattori, S. Hirose, and S. Yoshida. Analysis of double block length hash functions. Cryptogra?phy and Coding，Proceedings,2898:290-302,2003.
[46]K. Hidenori and M. Masakatu. Indifferentiability of single-block-length and rate-1compression1'uiicLions. IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences, E90-A:2301-2308,2007.
[471S. Hirose. Secure block ciphers are not sufficient for one-way hash functions in the Preneel-Govaerts-Vaiidewalle model. Selected Areas in Cryptography,2595:339-352，2003.
[48]S. Hirose. Provably secure double-block-length hash functions in a black-box model. InformationSecurity and Cryptology-ICISC2004，LNCS3506:330-342,2004.
[49]S. Hirose. Weak security notions of cryptographic unkeyed hash functions and their ampliliabil-ity. leice Transactions on Fundamentals of Electronics Communications arid Computer SciencesyE88A(l):33-38，2005.
[50]S. Ilirose. A security analysis of double-block-length hash functions with the rate1? leice Transac?tions on Fundamentals of Electronics Communications and Computer Sciences、E89A(10):2575-2582，2006.
[511S. Hirose. Some plausible constructions of double-block-length hash functions. In Fast SotfwareEncryption, volume LNCS4047，pages210-225,2006.
[52J S. Hirose and R Kuwakado. A scheme to base a hash function on a block cipher, volume5381LNCS of Lecture Notes in Computer Science (including subs eries Lecture Notes in Artiifcial In?telligence and Lecture Notes in Bioinformatics》，pages262-275，Sackville, NB，Canada，2008.Springer Verlag.
[53] S, Hirose and H, Kuwakado, Efifcient pseudorandom-function modes of a block-cipher-basedhash function. leice Transactions on Fundamentals of Electronics Communications and ComputerSciences, E92A(10):2447-2453,2009.
[541S. Hirose, J. H. Park, and A. Yun. A simple variant of the merkle-damgfKrd scheme with a per?mutation. In Kaoru Kurosawa, editor, ASIACRYPT2007y volume LNCS4833，pages113—129.Springer,2007.
[55J V.\\Hoang and P. Rogaway. On generalized feistel networks. In T. Rabin, editor, CRYPTO20】0,volume LNCS6223，pages613-630, Springer,2010.
[56] W. llohl, X. Lai，T_Meier, and C. Waldvogel. Secuirty of iterated hash functions based on blockciphers. In Advances in Cryptology-CRYPTO '93, volume LNCS773, pages379-379，SantaBarbara, CA, United states,1994, Springer-Verlag.
[571S. Hong and J. Lim J. Kim. Impossible differential cryptanalysis using matrix metJiod. DiscreteMathematics，310:998-1002，2010.
[58] ISCX ISO/IEC10118Information technology-Security techniques-Hash-functions,1994.
[591T. Jakobsen and L. R. Kiiudsen. The interpolation attack on block ciphers. In Eli Biham，ediior，FastSoftware Encryption-FSE，97，volume LNCS1267，pages28-40, I laifa, Israel,1997. Springcr-Verlag.160] A. Joux. Mullicollisioas in iterated hash functions, application lo cascaded constructions. In Ad?vances in Cryptology-CRYPTO，04’ volume LNCS3152，pages306-316. Springer-Verlag,2004.
[61] P. Junod and S. Vaudenay. FOX: a new family of block ciphers. In Selected Areas in Cryptography-SAC,2004，volume LNCS3357，pages114-129. Springer-Verlag，2004.
[621J-Katz and Y. Lindell. Introduction to modern cryptography. CRC Press，2007.
[63] L Kelsey and B, Schneien Second preimages on n-bit hash functions in much less ihan2n work. InAdvances in Cryptology-EUROCRYPTQ5, volume LNCS3494, pages474^t90, Springer-Verlag,2005.
[64J L Kim, S. Hong, J*Sung, S*Lee, and J. Lim. Impossible differential cryptanalysis for block cipherstructures. In INDOCRYPT2003, volume LNCS2904, pages82-96. Springer-Verlag,2003.
[65] L. R. Knudsen. Truncated and higher order differentials. In Bart Preoeel, editor, Fast SotfwareE*ncryption-FSE94, volume LNCS1008，pages196-211, Leuveo, Belgium,1995, Springer-Verlag.
[661L. R. Kiiudsen. Truncated and higher order differentials. In B. Preneel，editor, FSE，volume LNCS1008，pages196-211. Springer,1995.
[67]L, R, Knudsen, X. L Lai, and B. Preneel, Attacks on fast double block length hash functions.Journal of Cryptology,11(1):59-72,1998.
[68]Y. Ko, S. Hong, W. Lee, S, Lee, and J.S. Kang. Related key differential attacks on27rounds ofxtea and full-round gost. In Fast Sotfware Encryption2004，volume LNCS3017，pages299-316.Springer,20()4.
[69J Z. Kohavi. Switching and Finite Automata Theory. McGraw-Hill,1978.
[70J【【.Kuwakado and S*Hirose, Differentiability of four preifx-free PGV hash functions, IEICEElectronics Express,6(13):955-958,2009.
[71] H, Kuwakado and M Morii. Compression functions suitable for the imilU-property-preservingtransform. IEICE Transactions on Fundamentals of Electronics, Communications and ComputerSciences，E91-A(l0):2851-2859，2008.
[72J X.On the design and security of block ciphers, volume1of ETH Series in InformationProcessing. Hartung-Gorre Verlag, Konstanz,1992,
[731X. Lai. Higher order derivatives and differential cryplanalysis. In Communicatoms and Cryptogra?phy: Two Sides of One Tapestry” pages227_233，Switzerland，1994. Kluwer Academic Publishers.
[74] X. Lai and J. L. Masscy.八proposal for a new block encrypiton standard. In Damgard Ivan,editor, Advances in Cryptology-EURQCRYPT90y volume LNCS473，pages389404，Aarhus,Denmark,1990. Springer-Verlag.「751X. Lai and J. L. Massey. Markov ciphers and differential cryplanalysis. In Donald W. Davies,editor，Advances in Cryptology-EUROCRYPT'91, volume LNCS547，pages17-38? Brighton,UK,1991, Springer-Verlag.
[76] X. Lai and L L. Massey. Hash functions based on block ciphers. In R. A. Rueppel，edtior, Advancesin Crypt*ography-Eurocrypt92, volume LNCS658, pages55-7(1Springer-Verlag,1992.
[77J L Lee, S. Hong, L Sung, and II. Park. A new double-block-lengtli hash function using feistelstructure. In J. H. Park et al, editor, ISA2009, volume LNCS5576，pages11-20，2009.
[78J L Lee, M. Stam, and J. Steinberger. The preimage secuirty of double-block-length compressionfunctions, http://eprintiacr.org/2011/2l(Xpdf，2011.
[79] J. Lee and J. Stcinbcrger. Multi-property-preserving domain extension using polynomial-basedmodes of operation. In Advances in Cryptology ‘EUROCRYPT，l()’ volume LNCS6110，pages573-596，French Riviera, France,2010. Springer-Verlag.
[801D. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. American MaltiemaiicalSociety,2008.
[81]R. Lidl and H.Niederreiter. Finite ifelds. Encyclopedia of Mathematics and its applications.Addision-Wesley Publishing Company,1983.
[82]J. Lu. Attacking reduced-round versions of the sms4block cipher in the Chinese wapi standard. InProc of/CICSW, volume LNCS4861, pages306-318. Springer-Verlag,2007.
[831M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom func?tions. SIA M Journal on Computing,17(2):373-386,1988.
[84J S. Lucks. A collision-resistant rate-1doublc-block-lengtli hash function. Id Symmetric Cryptogra?phy, number07021in Dagstuhl Seminar Proceedings, Dagstuhl, Germany,2007. InternationalesBegcgnungs-und Forschungszentrum fur Informatik (IBFI)，Schloss DagstuW, Germany.
[85] Y. Luo and X. Lai. On the security of multivariate hash functions. Journal of Shanghai JiaotortgUniversity (Science)^14(2):219-222，2009.
[86J Y. Luo, X. Lai, and Z, Gong. Pseudorandomness analysis of the (extended) lai-massey scheme.Information Processing LMtersy111(2):90-96,2010.
[87] Yiyuan Luo, Zheng Gong, Ming Duan, Bo Zhu，and Xuejia Lai. Revisiting Ihe indifferenliabilityof PGV hash functions. Cryptology ePrint Archive, Report2009/265,2009. http://eprint.iacr.org/.
[88J U. Maurer, K. Pietrzak, and R. Rcnnen Indistinguishability ampliifcation. In A. Menezes，editor,CRYPTO2007，volume LNCS4622，pages139-149. Springer,2007.
[89] U. Maurer, R. Ronncr, and C. Holenstein. Tndifferentiability, inpossibilily results on reductions,and applications to the random oracle methodology, Io TCC2004, pages21-39，2004.
[901U. M. Maurer. A simpliifed and generalized treatment of luby-rackoff pseudorandom permuialiongenerators. In Advances in Cryptology-EUROCRYPTvolume LNCS658，pages239-255.Springer-Verlag, Berlin,1992.
[91] A. Maximov and A. Biryukov, Two trivial attacks on irivium. In Selected Areas in Cryptography2007，volume LNCS4876，pages36-55. Springer,2007.
[921G. Meiser, T. Eisenbarth, K. Lemke-Rust, and C. Paar. Software implementation of estream profilei ciphers on embedded8-bit avr microcontrollers. In SASC2007，2007.
[93]A. J. Menezes, R C van Oorschot, and S. A. Vanstone. Handbook ofA pplied Cryptography. CRCPress’1997.
[94]R. C. Merkle. One way hash functions and DES. In Advances in Cryptology-CRYPTO,89，volumeLNCS435，pages428-446. Springer-Verlag,1989.
[951I. Mirinov.(not so) random shuflfes of RC4. In CRYPTO2002’ volume LNCS2442，pages304-319. Springer,2002.
[96] S. Moriai and S. Vaudenay. On the pseudorandomness of top-level schemes of block ciphers. InAdvances in Cryptology-ASIACRYPT00, volume LNCS1976，pages289-302, Springer-Verlag,2000.
[971B. Morris, P. Rogaway, and T. Stegers. How to encipher messages on a small domain deterministicencryption and the thorp shuflfe. In CRYPTO2009，volume LNCS2009，pages2B6-302. Springer,2009.
[98j M, Nandi. Towards optimal double-length hash functions. In INDOCRYPT05, volume LNCS3797，pages77-89. Springer-Verlag,2005.
[99] M. Naiidi, W. Lee, K. Sakurai, and S. Lee, Security analysis of a2/3-rate double length compressionf’unction in the black-box model. In Fast Software Encryption-FSE2005, volume LNCS3557,pages243-254. Springer-Vedag,2005.
[100J M. Naor and O, Rciogold, From unpredictability to indistinguishability; A simple constructionof pseudo-random functions from macs (extended abstract). In Hugo Krawczyk，editor, CRYPTO,volume LNCS1462，pages267-282. Springer，1998.
[101]M Naor and CX Reingold On the construction of pseudorandom permutations: Luby-Rackoffrevisited. Journal of Cryptology,12(1):22-66,1999.
[102]Y，Nawaz and G. Gong, WG; A family of stream ciphers with designed randomness properties.Information Science,178(7):1903-1916,2008.
[103j NISI: Third (ifnal) round candidates,2010. http://csrc.oist.gov/groups/ST/hash/sha-3/Round3/submissions-rnd3,html,
[104] K. Nybcrg and L. R. Knudscn. Provable secuirty against differential cryptanalysis. Journal ofCryptology,8(1):27-37,1995.
[105J D. Otte. Avr-crypto-lib, http://www,das-labor.org/wiki/avr-crypto-l!b/en,2009,
[106] O. Ozen and M. Stam. Anotlicr glance at double-length hashing. In Cryptography and Coding,12th IMA International Conference, Cryptography and Coding2009, volume LNCS5921, pages176-201. Springer-Verlag, Berlin,2009.1107J J. Patario. How to construct pseudorandom and super pseudorandom permutations from one singlepseudorandom function. In Raincr A, Rucppel, editor, Advances in Cryptology-EUROCRYPT'92,volume LNCS658, pages256—266，Balatonliired, Hungary,1993. Springer-Verlag.
[1081J. Patarin”. The coefifcients H” technique. In R. Avanzi Sica, L. Keliher, and P., editors, SelectedAreas in Cryptography-SAC2008，volume LNCS5381, pages328-345. Spirnger，2009.
[109j T. Pcyirn, H, Gilbert, E Muller, and M Robshaw, Combining compression functions and blockcipher-based hash functions. Advances in Cryptology-ASIACRYPT2006，4284:315-331468,2006.
[110|B. Prcneel. Hash functions and mac algorithms based on block ciphers. In Proceedings of the19976th IMA International Conference on Cryptography and Coding, Dec1997’ volume1355of Lec?ture Notes in Computer Science, pages270-270. Cirencester, United kingdom,1997. Compilationand indexing terms, Copyright2010Elsevier Inc. Compendex199803413225703029743.『1111B. Preneel. The stale of cryptographic hash functions. In Lectures on Data Security, ModernCryptology in Theory and Practice, Summer School, Aarhus, Denmark,1998.
[112]B. Preneel, R. Govaerts, and J. Vandcwalle. Hash functions based on block ciphers; A syntheticapproach. In IXR, Stinson, editor, Advances in Cryptology ‘Proc. Crypto'93y volume LNCS773，pages368-378. Springer-Verlag, Berlin,1993.
[113]M. Pudovkina.On impossible truncated differentials of generalized feis-tel and skipjack ciphers.In FSE2009rump session. Avaiablc at:http://fsc2009rump.cryp.to/e31bba5dl227cac5ef0daa6bcbf66f27.pdf,2009.
[114J T, Ristcnpart and1\Shrimpton. I low to build a hash function from any collision-resistant func-lion. In Advances in Cryptology-AS!ACRYPT’07，volume LNCS4833，pages147-163，KuchingtMalaysia,2007. Springer-Verlag.
[115]R. Rivest, M. Robshaw, R. Sidney, and Y. Yin. The RC6block cipher,1998.ftp://rsasecurity.com/pub/rsalabs/rc6/rc6v11.pdf,
[116]R. L. Rivest. The md4message digest algorithm. In S. Vanstone, editor, Advances in Cryptology-CRYPT(),90，volume LNCS537，pages303-311. Springer-Verlag,1991.\1171R. L. Rivest. The MD5message digest algorithm. In Request for Comments (RFC)1321. IiiiernetActivities Board, Internet Privacy Task Force,1992.
[118]S. Ronjonr and T. Helleselh. Attacking the iflter generator over gf{2m). In WAIFA2007，volumeLNCS4547, pages264-275. Springer,2007.
[119]S. Ronjom and l\I Iclleseth. A new attack on the iflter generator. IEEE Transactions on InformationTheory,53(5):1752-1758,2007.
[120j B. Sadcghiyan and J. Pieprzyk. On necessary and suiffcient conditions for the construction of superpseudorandom permutations. In Abstracts ofASlACRYPT91, volume LNCS739，pages194-209.Springer-Verlag,1991.
[121] Satoh, JVL llaga, and K. Kurosawa. Towards secure and fast hash functions. IEICE Transactionson Fundamentals of Electronics, Communications and Computer Sciences, E82-A(1):55-62,1999.『1221C. Shannon.(Communication theory of secrecy systems. Bell System Technical Journal,28(4):656-715,1949.
[123]T. Siegenthaler. Corerlation-immunity of nonlinear combining functions for cryptographic appli?cations. IEEE Trans. Info. Theory，30(5):776-780,19B4.
[124]SMS4. Specication of SMS4, block cipher for WLAN products SMS4(in Chinese). Avaiable at:http://www.oscca.gov.cn/IIpFile/200621016423197990.pdf.『1251M. Stam. Block cipher based hashing revisited. In Fast Software Encryption2009，volume LNCS5665，pages67-83. Springer, Berlin,2009?
[126J J. P, Stcinberger The collision intractability of MDC-2in the ideal-cipher model. In Advances inCryptology-Proceedings of EUROCRYPT2007, volume LNCS4515of Lecture Notes in ComputerScience, pages34-51, Barcelona, Spain,2007. Springer Verlag’ Berlin.
[127] J, Sung, S‘Lee, J. Lim, S. Hong, and S. Park. Provable security for the skipjack-like struc?ture against differential cryptanalysis and linear cryptanalysis. In Advances in Cryptology-ASlACRYPrOO, volume LNCS1976，pages274-288. Springer-Verlag,2000.
[1281S. Vaudenay. Provable security for block ciphers by decorrelation. In Theoretical Aspects ofComputer Science-STAGS*98y volume LNCS1373，pages249-275. Springer,1998,
[129]S-Vaudenay. Oil the Lai-Massey scheme. In Advances in Cryptology-ASIACRYPT'99, volumeLNCS1716’ pages8-19. Springer-Verlag,1999.
[130]S. Vaudenay. Decorrelation; A theory for block cipher security. Journal of Cryptology,16(4):249-286，2003.
[131]M Vogt, A. Poschmaoo, and C Paar. Cryptography is feasible on4-bit microcontrollers-a proofof concept. In IEEE International Conference on RFID, pages241-248,2009.
[132]D4Wagner. A generalized birthday problem. In M. Yung, editor, CRYPTO2002, volume LNCS2442, pages288-303. Springer,2002.
[133]X. Wang, Y. L Yin, and H, Yu. Finding collisions in the full SHA-L In Victor Shoup，editor,Advances in Cryptology-CRFTO，05’ volume LNCS3621, pages17-36, Santa Barbara, CA，USA,2005. Spirnger-Verlag.
[134|X. Wang and H. Yu. How lo break MD5and other hash functions. In Ronald Cramer, editor,Advances in Cryptology-EUROCRYPT05, volume LNCS3494, pages19一35，Aarhus, Denmark,2005. Spirnger-Verlag.
[1351W. Wu，L. Zhang, L. Zhang, and W. Zhang. Security analysis of the gf-nlfsr structure and four-cellblock cipher In Proc oflClCS2009, volume LNCS5927，pages17-31. Springer-Verlag,2009.
[136]IL Yap. Impossible differential characteirstics of extended feistel networks with provable secuirtyagainst differential cryptanalysis. In SecTech2008, volume COS29，pages103-121，2009.
[137]A, Yun, J*Park, and L Lee. On lai-massey and quasi-feistel ciphers. Designs Codes and Cryptog?raphy,58:45-72，2011.