| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Framework for Describing Block Cipher Cryptanalysis
November 2006 (vol. 55 no. 11)
pp. 1402-1409
Block ciphers provide confidentiality by encrypting confidential messages into unintelligible form, which are irreversible without knowledge of the secret key used. During the design of a block cipher, its security against cryptanalysis must be considered. History has shown that a cipher designed without an adequate treatment of this will often lead to flaws and attacks by other researchers, sometimes devastatingly so. The problem for an aspiring cipher designer is that there are no standard texts on block cipher cryptanalysis because it is a fast changing field. The commonly available references are academic journals and conference proceedings, which may not be easy to grasp for researchers new to cryptanalysis. This paper presents the Xi framework, which is designed to compactly describe the block cipher cryptanalysis techniques regardless of their individual differences. This provides the cryptanalyst with a general framework to describe attacks on block ciphers, with the additional capabilities of allowing specification of the technical details of each different type of attack and of comparison of their respective strengths. Comparing different distinguishers in this framework also allows us to see natural generalizations and trigger nice open problems. We then show how to apply this Xi framework to the description of various attacks on popular and recent block ciphers.
[1] K. Aoki, “Practical Evaluation of Security against Generalized Interpolation Attack,” IEICE Trans. Fundamentals, special section on cryptography and information security, vol. E83-A, no. 1, pp.33-38, 2000.
[2] E. Biham, “New Types of Cryptanalytic Attacks Using Related Keys,” J. Cryptology, vol. 7, no. 4, pp. 229-246, 1994.
[3] E. Biham, A. Biryukov, and A. Shamir, “Miss in the Middle Attacks on IDEA, Khufu and Khafre,” Proc. Fast Software Encryption '99, pp. 124-138, 1999.
[4] E. Biham, O. Dunkelman, and N. Keller, “The Rectangle Attack —Rectangling the Serpent,” Proc. Eurocrypt '01, pp. 340-357, 2001.
[5] E. Biham, O. Dunkelman, and N. Keller, “Related-Key Boomerang and Rectangle Attacks,” Proc. Eurocrypt '05, 2005.
[6] E. Biham and A. Shamir, “Differential Cryptanalysis of DES-Like Cryptosystems,” J. Cryptology, vol. 4, no. 1, pp. 3-72, 1991.
[7] A. Biryukov, “Methods of Cryptanalysis,” PhD dissertation, Technion, Israel, 1999.
[8] A. Biryukov and A. Shamir, “Structural Cryptanalysis of SASAS,” Proc. Eurocrypt '01, pp. 394-405, 2001.
[9] A. Biryukov and D. Wagner, “Slide Attacks,” Proc. Fast Software Encryption '99, pp. 245-259, 1999.
[10] A. Biryukov and D. Wagner, “Advanced Slide Attacks,” Proc. Eurocrypt '00, pp. 589-606, 2000.
[11] J. Daemen, L. Knudsen, and V. Rijmen, “The Block Cipher SQUARE,” Proc. Fast Software Encryption '97, pp. 149-165, 1997.
[12] J. Daemen and V. Rijmen, The Design of Rijndael—AES—The Advanced Encryption Standard. Springer-Verlag, 2002.
[13] A.C. Doyle, “The Sign of Four,” Lippincott's Magazine, Feb. 1890.
[14] S. Furuya, “Slide Attacks with a Known-Plaintext Cryptanalysis,” Proc. Int'l Conf. Information Security and Cryptology (ICISC '01), pp.214-225, 2002.
[15] T. Jakobsen and L. Knudsen, “The Interpolation Attack on Block Ciphers,” Proc. Fast Software Encryption '97, pp. 28-40, 1997.
[16] J. Kelsey, T. Kohno, and B. Schneier, “Amplified Boomerang Attacks against Reduced-Round MARS and Serpent,” Proc. Fast Software Encryption '00, pp. 75-93, 2000.
[17] L. Knudsen, “Truncated and Higher Order Differentials,” Proc. Fast Software Encryption '94, pp. 196-211, 1995.
[18] L. Knudsen, “DEAL—A 128-Bit Block Cipher,” AES Submission, 1998, http://www.ii.uib.no/~larsr/papersdeal.ps .
[19] L. Knudsen, “Block Ciphers—A Survey,” Proc. State of the Art in Applied Cryptography, pp. 18-48, 1998.
[20] L. Knudsen, “Contemporary Block Ciphers,” Proc. Lectures on Data Security, Modern Cryptology Theory, and Practice, pp. 105-126, 1999.
[21] L. Knudsen and D. Wagner, “Integral Cryptanalysis,” Proc. Fast Software Encryption '02, pp. 112-127, 2002.
[22] K. Kurosawa, T. Iwata, and V.D. Quang, “Root Finding Interpolation Attack,” Proc. Selected Areas in Cryptography '00, pp.303-314, 2001.
[23] S. Lucks, “Saturation Attacks—A Bait for Twofish,” Proc. Fast Software Encryption '01, pp. 1-15, 2002.
[24] M. Matsui, “Linear Cryptanalysis Method for DES Cipher,” Proc. Eurocrypt '93, pp. 386-397, 1993.
[25] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997.
[26] S. Moriai, T. Shimoyama, and T. Kaneko, “Interpolation Attacks of the Block Cipher: SNAKE,” Proc. Fast Software Encryption '99, pp.275-289, 1999.
[27] NIST, “Advanced Encryption Standard (AES),” Federal Information Processing Standard Publication 197 (FIPS PUB 197), US Dept. of Commerce, Nov. 2001.
[28] R.C.-W. Phan, “Expressing the Slide, Amplified Boomerang, Rectangle and Square Attacks under the Commutative Diagram Cryptanalysis Framework,” Computer Standards & Interfaces, Elsevier, 2006.
[29] R.C.-W. Phan and S. Furuya, “Sliding Properties of the DES Key Schedule and Potential Extensions to the Slide Attacks,” Proc. Int'l Conf. Information Security and Cryptography (ICISC '02) pp. 138-148, 2003.
[30] M. Rabin, “Probabilistic Algorithms in Finite Fields,” SIAM J. Computing, vol. 9, no. 2, pp. 273-280, 1980.
[31] B. Schneier, Applied Cryptography. Wiley, 1996.
[32] D. Wagner, “The Boomerang Attack,” Proc. Fast Software Encryption '99, pp. 156-170, 1999.
[33] D. Wagner, “Towards a Unifying View of Block Cipher Cryptanalysis,” Proc. Fast Software Encryption '04, invited paper, 2004, http://www.cs.berkeley.edu/~daw/talksFSE04unify.ps .
Index Terms:
Encryption, cryptanalysis, block ciphers, framework, generalization, distinguishers.
Citation:
Raphael C.-W. Phan, Mohammad Umar Siddiqi, "A Framework for Describing Block Cipher Cryptanalysis," IEEE Transactions on Computers, vol. 55, no. 11, pp. 1402-1409, Nov. 2006, doi:10.1109/TC.2006.169
