Chinese Journal of Computers   Full Text
Title	Forgery Attack on PMAC and TMAC-V with Random Message
Authors	CHEN Jie1) HU Yu-Pu1) WEI Yong-Zhuang1),2)
Address	1)(Key Laboratory of Computer Networks & Information Security of Ministry of Education, Xidian University, Xi’an 710071) 2)(School of Information and Communication, Guilin University of Electronic Technology， Guilin, Guangxi 541004)
Year	2007
Issue	No.10(1827—1832)
Abstract &   Background	Abstract A Message Authentication Code ( MAC ) is a hash function with secret key, which satisfies that different keys can induce different hash functions. Therefore，receiver can verify whether the message is forged from sender. At the same time, receiver can also verify who send the message. PMAC, a fully parallelizable MAC scheme based on block cipher, is proposed by Black and Rogaway in Eurocrypt 2002. In 2005, Mitchell presented TMAC-V to improve the security of TMAC. This paper presents a new forgery attack on PMAC and TMAC-V with random message, which make use of the principle of differential identical in part of the mode. The new attack can forge the PMAC and TMAC-V of random message, with a probability of 86.5% higher than 63% in the known reference. The complexity of this new attack is ［0，2n/2+1，1，0］ for PMAC where no truncation is performed. For PMAC where truncation is performed, the complexity of this attack is ［0，2n/2+1，[n/τ]，2n-τ］. And the complexity of this attack is ［0，2n/2+1，1，0］ for TMAC-V. keywords message authentication code； block cipher； mode of operation; forgery attack； birthday collision background This research is supported by the National Natural Science Foundation of China under grant No.60673072, and the National High Technology Research and Development Program (863 Program) of China (2007AA01Z435), and the Natural Science Basic Research Plain in Shaanxi Province of China (Program No.2007F37). This paper focuses on the field of forgery attacks on MACs which based on block cipher. The research group has done much research work in the design and analysis of block ciphers and other related work of block ciphers. A Message Authentication Code ( MAC ) is a hash function with secret key, which satisfies that different keys can induce different hash functions. Therefore，receiver can verify whether the message is forged from sender. At the same time, receiver can also verify who send the message. MAC algorithms have two forms that based on block cipher and based on hash function. This paper research MACs based on block cipher, which are PMAC and TMAC-V. PMAC, a fully parallelizable MAC scheme based on block cipher, is proposed by Black and Rogaway in Eurocrypt 2002. In 2005, Mitchell presented TMAC-V to improve the security of TMAC. A MAC is secure if for an adversary who does not know the secret key K, it is computationally infeasible to perform an existential forgery under an adaptive chosen text attack. In the conference of ACISP 2006, Lee et al. devised forgery attack on PMAC and TMAC-V. But their method need fixed message, with a probability of 63%. This paper presents a new forgery attack on PMAC and TMAC-V with random message, which make use of the principle of differential identical in part of the mode. The new attack can forge the PMAC and TMAC-V of random message, with a probability of 86.5% higher than 63% in the known reference. The complexity of this new attack is ［0，2n/2+1，1，0］ for PMAC where no truncation is performed. For PMAC where truncation is performed, the complexity of this attack is ［0，2n/2+1，[n/τ]，2n-τ］. And the complexity of this attack is ［0，2n/2+1，1，0］ for TMAC-V.