摘要
本文对基于分组密码的消息认证码进行了研究,包括消息认证码的安全性分析,消息认证码算法的改进,安全性证明的改进以得到一个更好的上界等,主要成果有:
(1)OMAC1``算法是OMAC的一个改进算法,旨在消除OMAC中最后两个密钥之间的简单代数关系,提高OMAC抵抗密钥恢复攻击和伪造攻击的能力。但有关研究表明,即使在底层分组密码是一个伪随机置换的假设下,也不能证明OMAC1``的安全性。能构造一个满足一定条件的伪随机置换,使得利用该伪随机置换的OMAC1``不再安全,攻击者仅需一次询问便能得到成功的伪造。因此,OMAC1``并没有真正提高OMAC的安全性,OMAC1``的安全性较OMAC弱。因为OMAC1``的密钥之间存在常数异或的关系,当底层分组密码满足在一定相关密钥攻击下是一个RKA-PRP的更高安全性假设,证明了OMAC1``是一个伪随机函数。
(2)尽管目前一些分组密码在已知的相关密钥攻击下仍然是安全的,但和伪随机置换的假设相比,分组密码在一定相关密钥攻击下是一个RKA-PRP的假设要求过高。事实上,几乎所有基于分组密码的消息认证码的安全性都是建立在底层分组密码是一个伪随机置换的假设上。将两个密钥之间的固定差分设为全0,并在CBC链中引入一个加密的常数,改进了OMAC1``算法。改进的OMAC1``能在底层分组密码是一个伪随机置换的假设下,证明是一个伪随机函数。并分析了改进方法的合理性。
(3)基于有向无环图DAG结构的消息认证码利用满足伪随机函数保持性的一系列带权图。它包含了许多广泛使用的消息认证码,比如XCBC,TMAC,OMAC,以及PMAC等。改进了基于DAG的消息认证码的安全性证明,得到一个新的上界O ( qσ2 n),其中,q是攻击者询问的次数,σ是所有询问所包含的分组总数。
(4)PMAC是一种可并行运算的消息认证码。消息的所有分组在分组密码加密前先要进行掩盖,以防止利用明文特征进行攻击。但这个过程也泄露了可以利用的信息。利用这些边信息,得到一种新的PMAC的攻击方法,该方法在长消息的应用环境很实用。
(5)证明了OPMAC是一个伪随机函数,原OPMAC仅证明了其具有不可伪造性。对一个消息认证码来说,伪随机函数是一个比不可伪造性更强的安全性定义。OPMAC不仅仅具有不可伪造性,还是一个伪随机函数。而且,所得到的新上界是用所有询问所包含的分组总数表示的形式,不再是用最长消息长度表示的形式。当询问消息的长度严重失衡时,这是一个更好的界。
(6)在一些安全协议中,经常需要同时认证一组数据。但普通消息认证码的输入仅为单个的字符串,因此,有必要设计一种输入可为字符串向量的消息认证码。文中得到两种不同的输入可为字符串向量的消息认证码的构造方法。第一个基于合成的通用哈希函数,先用一个并行的通用哈希函数处理字符串向量,所得结果输入另一个通用哈希函数,然后用分组密码加密得到认证标记。并在底层分组密码是一个伪随机置换的假设下,证明了它是一个伪随机函数。但它需要三个密钥。第二种构造方法利用分组密码,模拟PMAC的结构,得到的输入可为字符串向量的消息认证码具有双层可并行运算的结构。它仅需一个密钥。最后,证明了它的安全性。
Message authentication codes based on the block cipher are researched, including the security analysis of some message authentication codes, the improvement of some message authentication codes, improving the security analysis of message authentication codes in order to obtain better upper bounds etc. We obtain the main results as follows:
(1) OMAC1`` is an improvement of OMAC for avoiding the simple algebraic relationship between the last two keys and enhancing the resistance of OMAC to the key recovery attack and forgery attack. But some research result shows that OMAC1`` is not provable secure even if the underlying block cipher is a pseudorandom permutation. A pseudorandom permutation with some property can be constructed and if this pseudorandom permutation is used in OMAC1``, then OMAC1`` is completely insecure and simple forgery attacks can be obtained by using only one oracle query. So, the security of OMAC is not really improved by OMAC1``. OMAC1`` is less secure than the original OMAC. As the use of keys related by some fixed xor difference in the OMAC1``, under the stronger assumption that the underlying block cipher is a RKA-PRP against a certain class of related key attacks, OMAC1`` is proved to be a pseudorandom function.
(2) Although existing block ciphers are still secure against known related key attacks, the assumption of RKA-PRP against a certain class of related key attacks on the block cipher is still stronger than the standard pseudorandom permutation assumption. Actually, almost all block cipher based message authentication codes proved their securities under the assumption of the underlying block cipher as a pseudorandom permutation. By setting the fixed xor difference of the keys to all zeros and using the encryption of some constant in the CBC computation, OMAC1`` is improved. The improved OMAC1`` can be proved to be secure under the standard pseudorandom permutation assumption. Also, the rationality of the modification is analyzed.
(3) A message authentication code based on the DAG construction uses a sequence of colored graphs that are PRF-preserving. It includes many known constructions like XCBC, TMAC, OMAC, PMAC etc. An improved security analysis of the message authentication code using DAG construction is presented. The newly obtained bound is O ( qσ2 n), where an adversary can make at most q queries with at mostσmany blocks.
(4) PMAC is a parallelizable message authentication code. The message blocks are masked before they are encrypted by the block cipher in order to avoid the attacks using the properties of the messages. But some useful information is issued in this process. Using this side channel, a new attack is proposed against PMAC. It is very practical in the setting where long messages are authenticated.
(5) Originally, OPMAC is only proved to be unforgeable. Now, it is proved that OPMAC is also a pseudorandom function. For a message authentication code, PRF is a stronger security definition than unforgeability. So, OPMAC is not only unforgeable, but also it is a pseudorandom function. Furthermore, the new bound is expressed in terms of the total blocks in all the queries of an adversary, while the previous bound is expressed in terms of the maximum length of each query. This new bound is better than the original bound, if the lengths of queries are heavily unbalanced.
(6) In some security protocols, there is usually a need to authenticate a group of data. But ordinary message authentication codes only take a single string as input, so it is necessary to design a message authentication code accepting a vector of strings as input. We present two constructions for vector-input message authentication codes. The first one makes use of the composition of universal hash families. First, the vector of strings is processed by a parallel universal hash function, the result is put into another universal hash function, and then it is encrypted. Under the assumption that the underlying block cipher is a pseudorandom permutation, its security is proved. But it needs three keys. The second construction uses only block ciphers. It simulates the structure of PMAC, the resultant vector-input message authentication code is two-level parallelizable. It needs only one key. At last, its security is proved.
引文
[1]王育民,刘建伟.通信网的安全——理论与技术.西安:西安电子科技大学出版社,1999.
[2]Schneier B著.吴世忠等译.应用密码学(第二版).北京:机械工业出版社,2000.185- 212.
[3]卢开澄.计算机密码学——计算机网络中的数据保密与安全.北京:清华大学出版社,1998.
[4] B.Schneier. Applied Cryptography Second Edition: protocols, algorithms, and Source Code in C.New York: John Wiley & Sons, Inc. 1996.
[5]王新梅,马文平,武传坤.纠错密码理论.北京:人民邮电出版社,2001.
[6]武传坤.密码学中的布尔函数.西安电子科技大学博士论文.1993.
[7]冯登国.频谱理论及其在通信保密技术中的应用.西安电子科技大学博士论文.1995.
[8]易训.分组密码的设计与分析.西安电子科技大学博士论文.1995.
[9]姚小波.零知识证明系统.西安电子科技大学博士后研究工作报告.1996.
[10]吴文玲.密码安全的度量指标.西安电子科技大学博士论文.1997.
[11]温巧燕.密码学中的相关免疫函数研究.西安电子科技大学博士论文.1997.
[12]胡豫濮.分组密码的设计与安全性分析.西安电子科技大学博士论文.1999.
[13]韦宝典.高级加密标准AES中的若干问题的研究.西安电子科技大学博士论文.2004.
[14]刘景美.现代密码算法分析与研究.西安电子科技大学博士论文.2006.
[15]徐胜波,马文平,王新梅.无线通信网中的安全技术.北京:人民邮电出版社,2003.
[16] Kerckhoffs A.. La Cryptographie Militaire. Journal des Sciences Militaires, IX: 5-38, Jan 1883.
[17] Shannon E. C.. A Mathematical Theory of Communication. The Bell SystemTechnical Journal. July/October, 1948, Vol. 27, No.4.379-423,623-656.
[18] National Bureau of Standards. Federal Information Processing Standard Publication 46:Data Encryption Standard (DES). 1977.
[19] Biham E., Shamir A.. Differential cryptanalysis of DES-like cryptosystems. Advances in Cryptology Crypto '90. Berlin:Springer-Verlag,1991. 2-21.
[20] Matsui M.. Linear cryptanalysis method for DES cipher. EUROCRYPT'93. Berlin: Springer-Verlag, 1994. 386-397.
[21] Diffie W., Hellman M. E.. New direction in cryptography. IEEE Trans. on Information Theory. Nov 1976, Vol. IT-22, No. 6, pp. 644-654.
[22] Rivest R.L., Shamir A., Adleman L.M. A method for obtaining digital signatures and public key cryptosystem. Communications of the ACM. 1978, Vol.21, No. 2. l20-126.
[23] ELGamal T.. A public-key cryptosystem and a signature scheme based on discrete a1ogorihms. CRYPTO’84. Berlin: Springer-Verlag, 1985.
[24] Miller V. S.. Use of elliptic curves in cryptography . CRYPTO’85. Berlin: Springer, 1986. 417-426.
[25] Simmons G. J. Authentication theory/coding theory . Advances in Cryptology- CRYPTO’84. Berlin: Springer-Verlag,1985.411-431.
[26] Bellare M., Kilian J., Rogaway P.. The security of the cipher block chaining message authentication code . Journal of Computer System Science. 2000,Vol. 61, No. 3, 362-399.
[27] National Institute of Standard and Technology. NIST Special Publication 800-38B. Recommendation for block cipher modes of operation: the CMAC mode for authentication . 2005.
[28] Black J., Rogaway P.. A block cipher mode of operation for parallelizable message authentication. EUROCRYPT 2002 . Berlin: Springer, 2002. 384-397.
[29] Bellare M., Guerin R., Rogaway P.. XOR-MAC: new methods for message authentication using finite pseudorandom functions. CRYPTO’95. Berlin: Springer- Verlag, 1995. 15-28.
[30] Black J., Halevi S., Krawczyk H., etc.. UMAC: fast and secure message authentication . CRYPTO 1999 . Berlin: Springer, 1999. 216-233.
[31] Bernstein D. J.. The poly1305-AES message-authentication code . FSE 2005. Berlin: Springer, 2005.32-49.
[32] Minematsu K., Tsunoo Y.. Provable secure MACs from differentially-uniform permutations and AES-based implementations. FSE 2006. Berlin: Springer, 2006. 226- 241.
[33] Iwata T., Kurosawa K.. OMAC: one-key CBC MAC. FSE 2003. Berlin: Springer, 2003.129-153.
[34] Bellare M., Canetti R., Krawczyk H.. Keying hash functions for message authentication . CRYPTO 1996 . Berlin: Springer, 1996.1-15.
[35] Bellare M., Canetti R., Krawczyk H.. Pseudorandom functions revisited: the cascade construction and its concrete security. FOCS, 1996. 514-523.
[36] Yasuda K.“Sandwich”is indeed secure: how to authentication a message with just one hashing. ACISP 2007. Berlin: Springer, 2007.355-369.
[37] Hirose S., Park J. H., Yun A.. A simple variant of the Merkle-Damg?rd scheme with a permutation. ASIACRYPT 2007.Berlin: Springer, 2007.113-129.
[38] Bellare M., Kilian J., Rogaway P.. The security of cipher block chaining. CRYPTO’94. Berlin: Springer, 1994.340-358.
[39] Petrank E., Rackoff C.. CBC MAC for real-time data sources. J. Cryptology, 2000, vol. 13, no. 3. 315-338.
[40] Bellare M., Pietrzak K., Rogaway P.. Improved security analysis of CBC MAC. CRYPTO 2005 . Berlin: Springer, 2005. 527-541.
[41] Vaudenay S.. Decorrelation over infinite domains: the encrypted CBC-MAC case. SAC 2000. Berlin: Springer, 2001.189-201.
[42] Jaulmes E, Joux A., Valette F.. On the security of randomized CBC-MAC beyond the birthday paradox limit: a new construction. FSE 2002. Berlin: Springer, 2002. 237- 251.
[43] Black J., Rogaway P.. CBC MACs for arbitrary-length messages: the three keyconstructions. CRYPTO 2000. Berlin: Springer, 2000.197-215.
[44] Kurosawa K., Iwata T.. TMAC: two-key CBC MAC. CT-RSA 2003. Berlin: Springer, 2003. 33-49.
[45] Iwata T., Kurosawa K.. OMAC: one-key CBC MAC. FSE 2003. Berlin: Springer, 2003. 129-153.
[46] Nandi M.. Fast and secure CBC-type MAC algorithms. FSE 2009. International Association for Cryptologic Research, 2009. 375-393.
[47] Mitchell C. J.. On the security of XCBC, TMAC and OMAC. [EB/OL] http://www. rhul.ac.uk/mathematics/techreports.
[48] Mitchell C. J.. Partial key recovery attacks on XCBC, TMAC and OMAC. Cryptography and Coding 2005. Berlin: Springer, 2005.155-167.
[49] Iwata T., Kurosawa K.. On the security of a new variant of OMAC. ICISC 2003. Berlin: Springer, 2004. 67-78.
[50] Bellare M., Kohno T.. A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. EUROCRYPT 2003 . Berlin: Springer, 2003. 491-506.
[51] Wang P., Feng D., Wu W. etc.. On the unprovable security of 2-key XCBC. ACISP 2008 . Berlin: Springer, 2008.230-238.
[52] Iwata T., Kohno T.. New security proofs for the 3GPP confidentiality and integrity algorithms. FSE 2004. Berlin: Springer, 2004. 427-445.
[53] Iwata T., Kurosawa K.. How to enhance the security of the 3GPP confidentiality and integrity algorithms. FSE 2005. Berlin: Springer, 2005. 268-283.
[54] Luby M., Rackoff C.. How to construct pseudorandom permutations from pseudorandom functions . SIAM J. Comput..1988, vol. 17, no. 2.373-386.
[55] Jutla S. C.. RPF domain extension using DAGs. TCC 2006. Berlin: Springer, 2006. 561-580.
[56] Nandi M.. A simple and unified method of proving indistinguishing. INDOCRYPT 2006. Berlin: Springer, 2006. 317-334.
[57] Maurer U.. Indistinguishability of random systems. EUROCRYPT 2002. Berlin: Springer-Verlag, 2002.110-133.
[58] Iwata T., Kurosawa K.. Stronger security bounds for OMAC, TMAC, and XCBC . INDOCRYPT 2003. Berlin:Springer, 2003. 402-415.
[59] Bellare M., Pietrzak K., Rogaway P.. Improved security analysis for CBC MACs . CRYPT 2005. Berlin: Springer, 2005.527-541.
[60] Pietrzak K.. A tight bound for EMAC. ICALP 2006. Berlin: Springer, 2006. 168-179.
[61] Minematsu K., Matsushima T.. New Bounds for PMAC, TMAC, and XCBC. FSE 2007. International Association for Cryptologic Resaerch, 2007.434-451.
[62] Nandi M., Mandal A.. Improved security analysis of PMAC. [EB/OL] http://eprint. iacr.org/2007/031.
[63] Nandi M.. Improved security analysis of OMAC. [EB/OL]http://eprint. iacr.org/2007/292.
[64] Preneel B., Oorschot P.. MDx-MAC and building fast MACs from hash functions. CRYPTO’95. Berlin: Springer- Verlag, 1995.1-14.
[65] Preneel B., Oorschot P.. On the security of iterated message authentication codes. IEEE transactions on information theory. January 1999, vol. 45, no. 1.188-199.
[66] G. Yuval. How to swindle Ranbin. Cryptologia. 1979, vol. 3. 187-189.
[67] Preneel B., Oorschot P.. Key recovery attack on ANSI X 9.19 retail MAC. Electronics letters. 1996, vol. 32, no. 17.1568-1569.
[68] Knudsen R. L.. Chosen-text attack on CBC-MAC. Electronics letters. 1997, vol. 33, no. 1. 48-49.
[69] Knudsen R. L., Preneel B.. MacDES: MAC algorithm based on DES. Electronics letters.1998, vol. 34, no. 9. 871-873.
[70] Coppersmith D., Mitchell J. C.. Attacks on MacDES MAC algorithm. Electronics Letters.1999, 35.1626-1627.
[71] Coppersmith D., Knudsen R. L., Mitchell J. C.. Key recovery and forgery attacks on the MacDES MAC algorithm. CRYPTO’2000. Berlin: Springer-Verlag, 2000. 184- 196.
[72] Semanko M.. L-collision attacks against randomized MACs. CRYPTO 2000 .
Berlin: Springer-Verlag, 2000. 216-228.
[73] Bricat K., Mitchell J. C.. New CBC-MAC forgery attacks. ACISP 2001. Berlin: Springer-Verlag, 2001.3-14.
[74] Brincat K., Mitchell J. C.. Key recovery attacks on MACs based on properties of cryptographic APIs. Cryptography and Coding 2001. Berlin: Springer-Verlag, 2001.63-72.
[75] Sung J., Hong D., Lee S.. Key recovery attacks on the RMAC, TMAC, and IACBC . ACISP 2003. Berlin: Springer-Verlag, 2003. 265-273.
[76] Mitchell J. C.. Key recovery attack on ANSI retail MAC. Electronics Letters.2003, vol. 39, no. 12. 361-362.
[77] Mitchell J. C.. Truncation attacks on MACs. Electronics Letters. 2003, vol. 39, no. 20. 1439-1440.
[78] Mitchell J. C.. Partial key recovery attacks on XCBC, TMAC, and OMAC. Cryptography and Coding 2005. Berlin: Springer-Verlag, 2005.155-167.
[79] Knudsen R. L., Mitchell J. C.. Partial key recovery attack against RMAC . J. Cryptology, 2005, 18: 375-389.
[80] Contini S., Yin L. Y.. Forgery and partial key-recovery attacks on HMAC and NMAC using hash collisions. ASIACRYPT 2006. International Association for Cryptologic 2006.37-63.
[81] Lee C., Kim J., Sung J.,etc.. Forgery and key recovery attacks on PMAC and Mitchell’s TMAC variant [A]. L. Batten and R. Safavi-Naini (Eds.): ACISP 2006[C], LNCS 4058, pp. 421-431, 2006, Springer-Verlag Berlin Herdelberg 2006.
[82]陈杰,胡予濮,韦永壮.随机消息伪造攻击PMAC和TMAC-V.计算机学报.2007,10,Vol. 30, No. 10.1827-1832.
[83] Wang X., Wang W., Jia K., etc.. New distinguishing attack on MAC using secret-prefix method . FSE 2009. International Association for Cryptologic Resaerch 2009.363-374.
[84] Wang X., Yu H., Wang W. etc.. Cryptanalysis on HMAC/ NMac- MD5 AND MD5-MAC. EUROCRYPT 2009. International Association for Cryptologic Research 2009.121-133.
[85] Yuan Z., Jia K., Wang W., etc..Distinguishing and forgery attacks on Alred and its AES-based instance Alpha-MAC. [EB/OL] http://eprint.iacr.org/2008/516.
[86] Jia K, Wang X., Yuan Z., etc.. Distinguishing attack and second-preimage attack on the CBC-like MACs.[EB/OL] http://eprint.iacr.org/2008/542.
[87] Yu H., Wang X.. Distinguishing attack on the secret-prefix MAC based on the 39-step SHA-256. ACISP 2009. Berlin: Springer-Verlag, 2009.185-201.
[88] Yuan Z., Wang W., Jia K., etc.. New birthday attacks on some MACs based on block cipher . CRYPTO 2009. International Association for Cryptologic Resaerch 2009. 209-230.
[89] Bernstein J. B.. How to stretch random functions: the security of protected counter sums. J. Cryptology .1999,12:185-192.
[90] Gligor D. V., Donescu P.. Fast encryption and authentication: XCBC encryption and XECB authentication modes. FSE 2001. Berlin: Springer-Verlag, 2002. 92-108.
[91] Wang D., Lin D., Wu W.. A variant of Poly1305 MAC and its security proof . CIS 2005.Berlin: Springer-Verlag, 2005.375-380.
[92] Wang D., Lin D., Wu W.. OPMAC: one-key poly1305 MAC. Inscrypt 2006. Berlin: Springer-Verlag, 2006.78-87.
[93] Carter J., Wegman M.. Universal classes of hash functions. Journal of Computer and System Sciences. 1979, vol. 18.143-154.
[94] Wegman M., Carter J.. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences.1981, vol.22. 265-279.
[95] Okeya K., Iwata T.. Side channel attacks on message authentication codes. IPSJ Digital Courier. 2006, Aug,Vol. 2.
[96] McGrew A. D., Viega J.. The galois/ counter mode of operation (GCM).[EB/OL] http://www.cryptobarn.com/ papers/gcm-spec.pdf.
[97] Stinson D. R.. Universal hashing and authentication codes. Design, Codes and Cryptography.1994, 4(4). 369-380.
[98] Black J.. Message Authentication Code.UC Davis.2000.
[99] Goldwasser S., Bellare M.. Lecture notes on cryptography.[EB/OL]http://www.cse.ucsd.edu/mihir/ crypto-lectures.html.
[100] National Institute of Standards and Technology. NIST Special Publication 800-38A, Recommendation for Block Cipher Modes of Operation: Methods and Techniques .Washington D.C.: U. S. Government Printing Office, 2001.
[101] National Institute of Standards and Technology. Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality [EB/OL] http://csrc. nist.gov/publications/nistpubs/800-38C/SP800-38C.pdf.
