Improving cache attacks by considering cipher structure

A concrete attack using side channel information from cache memory behaviour was proposed for the first time at ISITA 2002. The attack uses the difference between execution times associated with S-box cache-hits and cache-misses to recover the intermediate key. Recently, a theoretical estimation of the number of messages needed for the attack was proposed and it was reported that the average method obtains key information with fewer messages than maximum threshold or intermediate threshold method. Taking the structure of cipher into account, this paper provided the cache attack in which the average method is embodied, and provides improved key estimation. This paper includes the study on the attack that exploits internal collision. Yukiyasu Tsunoo received his BE degree from Waseda University in 1982, MS degree from JAIST, Dr.Eng from Chuo University. He joined NEC Software Hokuriku, Ltd. in 1985. He is now a research fellow of NEC Internet Systems Research Laboratories. He is engaged in the designing of common key ciphers and the study of evaluation technique. Dr. Tsunoo is a member of the Expert Commission of Information Security Research, The Institute of Electronics, Information and Communication Engineers, the Information Processing Society of Japan, the Japan Society for Security Management and the Atomic Energy Society of Japan. Etsuko Tsujihara received her BS degree from Aoyama Gakuin University in 1983. She joined NEC in 1983. She developed the VLSI automatic layout system. She joined NEC Software Hokuriku Ltd. in 1986 and Y.D.K. Co. Ltd. in 2004. She is engaged in the designing of common key ciphers and the study of evaluation technique. Maki Shigeri received her BE degree from University of Tsukuba in 1992. She joined NEC Software Hokuriku Ltd. in 1992. She is engaged in the designing of common key ciphers and the study of evaluation technique. Hiroyasu Kubo received his BE degree from Kanazawa Institute of Technology in 1990. He joined NEC Software Hokuriku Ltd. in 1990. He is engaged in the designing of common key ciphers and the study of evaluation technique. Kazuhiko Minematsu received his BS degree from Waseda University in 1996, MS degree in 1998 and joined NEC in 1998. He is engaged in the designing of common key ciphers and research on block cipher modes of operations. He is a member of the Information Processing Society of Japan, the Society of Information Theory and Its Applications.