雜湊函數廣泛應用於通訊、安全計算等許多領域，可提供資料完整性、不可否認性等安全性質，以作為電子簽章、身分認證等密碼系統的重要關鍵。近年各種破密方法陸續被提出，證明某些常用雜湊函數是不安全，如MD5與SHA-1，因此許多新雜湊函數被提出以因應，如MD6與PHOTON。Dinur和Shamir在2009年歐洲密碼會議，提出一種新型態代數攻擊法，稱為可調多項式攻擊法，之後更延伸為可調多項式識別攻擊。這兩種攻擊分屬金鑰復原攻擊與識別攻擊，皆可廣泛應用於破解任何種類之密碼器，已知用於破解區塊加密器、串流加密器及雜湊函數等。本論文深入研究MD6與PHOTON雜湊函數，並探討可調多項式攻擊法與可調多項式識別攻擊，且實作於簡化版本之PHOTON與MD6；實作過程中，我們改善平行化功能，以增進攻擊效率，且提出一個快速驗證方法，可立即驗證實驗結果之正確性。根據實驗結果，我們分析PHOTON與MD6之安全性，並探討如何規劃實驗，以擁有較佳攻擊成果。最後提出建議如何搭配使用這兩項攻擊法，可兼具兩者優點，以判斷密碼元件之安全性。藉由實作，本論文可提供實作的觀點，供密碼系統設計者與攻擊者參考。

The hash function is widely used in the communications, secure computing and many other fields. It can provide many secure properties such as integrity and non-repudiation, and becomes the key technology in the protection of the security of the electronic signatures, identity authentications, and other cryptographic systems. Recently, many cryptanalysis show some well-known hash functions, like MD5 and SHA-1, are insecure. As a result, many new hash functions, such as MD6 and PHOTON, are developed. In 2009, Dinur and Shamir proposed the cube attack which belongs to key-recovery attack, and extended it to cube tester which is a kind of distinguisher attack. These attacks can be applied to block ciphers, stream ciphers and hash functions. In this thesis, we study MD6 and PHOTON hash functions, and successfully apply cube attacks and cube testers to reduced-round variants of MD6 and PHOTON. In implementations, we improve cube attack in a parallelized way for better efficiency, and propose a new validation method to verify the correctness of the cube attack results. According to our experiments, we analyze the security of MD6 and PHOTON, and discuss how to choose experiment parameters for better attack results. Finally, for combining both advantages, we suggest how to use these two attacks to analyze cryptographic primitives. This thesis could provide view of implementation for both cryptosystems designer and cryptanalysts.

參考資料
[1] J. Aumasson, I. Dinur, W. Meier, and A. Shamir, “Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium,” Fast Software Encryption, 2009.
[2] G. V. Bard, N. T. Courtois, J. Nakahara Jr, P. Sepehrdad and B. Zhang, “Algebraic, AIDA/Cube and Side Channel Analysis of KATAN Family of Block Ciphers,” 2011.
[3] E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid, “NIST SP800-57: Recommendation for Key Management,” which is available at http://csrc.nist.gov /publications/PubsSPs.html, May 2007.
[4] G. Bertoni, J. Daemen, M. Peeters, and G. Assche, “Sponge functions,” Ecrypt Hash Workshop, 2007.
[5] G. Bertoni, J. Daemen, M. Peeters, and G. Assche, “Distinguisher and Related-Key Attack on the Full AES-256,” CRYPTO, 2009.
[6] C. Boura, A. Canteaut and C. De Cannière, “Higher-Order Differential Properties of Keccak and Luffa,” Fast Software Encryption, 2011.
[7] I. Dinur and A. Shamir, “Side Channel Cube Attacks on Block Ciphers,” IACR, 2009.
[8] C. D. Cannière and B. Prenee, “New Stream Cipher Designs,” New Stream Cipher Designs, pp.84-97, 2008.
[9] I. Dinur and A. Shamir, “Cube Attacks on Tweakable Black Box Polynomials,” EUROCRYPT ’09, 2009.
[10] I. Dinur and A. Shamir, “Breaking Grain-128 with Dynamic Cube Attacks,” Fast Software Encryption, 2011.
[11] M. Duan and X. Lai, “Higher Order Differential Cryptanalysis Framework and its Applications,” International Conference on Information Science and Technology, 2010.
[12] J. Guo, T. Peyrin, A. Poschmann, “The PHOTON Family of Lightweight Hash Functions,” CRYPTO, 2011.
[13] J. Lathrop, “Cube Attacks on Cryptographic Hash Functions,” Rochester Institute of Technology Department of Computer Science, 2009.
[14] X. Lai, “High Order Derivatives and Differential Cryptanalysis,” 1992.
[15] M. Lamberger, F. Mendel, C. Rechberger, V. Rijmen, and M. Schlafer, “Rebound Distinguishers: Results on the Full Whirlpool Compression Function,” ASIACRYPT ’09, 2009.
[16] A. Kaminsky, “Parallel Cube Tester Analysis of the CubeHash One-way Hash Function,” 14th SIAM Conference on Parallel Processing for Scientific Computing, 2010.
[17] A. Kaminsky, “Cube test analysis of the statistical behavior of Cubehash and skein,” Cryptology ePrint Archive, Report 2010/262, 2010.
[18] F. Mendel, C. Rechberger , M. Schlaffer, S. S. Thomsen, “Rebound Attacks on the Reduced Grøstl Hash Function,” CT-RSA ’10, 2010.
[19] P. Mroczkowski and J. Szmidt, “The Cube Attack on Courtois Toy Cipher,” Proceedings of WEWoRC, 2009.
[20] P. Mroczkowski and J. Szmidt, “The Cube Attack on Stream Cipher Trivium and Quadraticity Tests,” CRYPTO, 2010.
[21] P. Mroczkowski and J. Szmidt, “The Cube Attack in the Algebraic Cryptanalysis of CTC2,” Concepts and Implementations for Innovative Military Communications and Information Technologies, 2010.
[22] P. Mroczkowski and J. Szmidt, “The Cube Attack on Courtois Toy Cipher,” Proceedings of WEWoRC, 2009.
[23] J. Nechvatal, “Public Key Cryptography,” Contemporary Cryptography: The Science of Information Integrity, G. Simmons ed., IEEE, 1992.
[24] National Institute of Standards and Technology, “NIST, FIPS 180-2; Secure Hash Standard,” which is available at http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf, August 2002.
[25] NIST Cryptographic Hash Algorithm Competition, which is available at http://csrc.nist.gov/groups/ST/hash/sha-3/index.html.
[26] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, and L. Bassham., “NIST SP800-22 Revision 1a: A statistical test suite for random and pseudorandom number generators for cryptographic applications,” which is available at http://csrc.nist.gov /publications/PubsSPs.html, Apr. 2010.
[27] L. Rivest, “The MD6 Hash Function,” CRYPTO ’08, 2008.
[28] X. Wang and H. Yu, “How to Break MD5 and Other Hash Functions,” EUROCRYPT ’05, 2005.
[29] D. Watanabe, Y. Hatano, T. Yamada and T. Kaneko, “Higher Order Differential Attack on Step-Reduced Variants of Luffa v1,” Fast Software Encryption, 2010.
[30] B. Zhu, W. Yu and T. Wang, “A Practical Platform for Cube-Attack-like Cryptanalyses,” Cryptography/Network Security Course Project, 2010.
[31] B. Zhu, G. Gong, X. Lai and K. Chen, “Another View on Cube Attack, Cube Tester, AIDA and Higher Order Differential Cryptanalysis,”2012.