Linear Analysis of reduced-round CAST-128 and CAST-256
Resumo
This paper describes a linear analysis of reduced-round versions of the CAST-128 and CAST-256 block ciphers. CAST-256 was a former candidate to the AES Development Process. Both ciphers use the same nonlinear components (fixed 8x32-bit S-boxes, key-dependent bit-rotation, modular addition and subtraction on 32-bit words) and a Feistel Network structure. We exploit the fact that the S-boxes are non-surjective mappings to construct iterative linear distinguishers for both ciphers. As far as we are aware of, this paper describes the first known-plaintext analysis of reduced-round variants of these ciphers.
Palavras-chave:
CAST-128, CAST-256, linear cryptanalysis
Referências
AES, The Advanced Encryption Standard Development Process, 1997, http://csrc.nist.gov/encryption/aes/
C.M. Adams, The CAST-128 Encryption Algorithm, RFC 2144, May 1997.
C.M. Adams, The CAST-256 Encryption Algorithm, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
C.M. Adams, Constructing Symmetric Ciphers using the CAST Design Procedure, Designs, Codes, and Cryptography, 12:(3), Nov. 1997, 283-316.
C.M. Adams, H.M. Heys, S.E. Tavares, M. Wiener, An Analysis of the CAST-256 Cipher, [link]
E. Biham, A Note on Comparing the AES Candidates, The AES Development Process, http://csrc.nist.gov/encryption/aes/round1/conf2/papers/biham2.pdf
A. Biryukov, C. De Cannière, Block Ciphers and Systems of Quadratic Equations, 10th Fast Software Encryption Workshop, T. Johansson, Ed., Springer-Verlag, LNCS 2887, 2003, 274-289. 9
U. Blöcher, M. Dichtl, Problems with the Linear Cryptanalysis of DES using More than One Active S-box per Round, 1st Fast Software Encryption Workshop, R. Anderson, Ed., Springer-Verlag, LNCS 809, 1994, 256-274.
L. Brown, J. Pieprzyk, Introducing the New LOKI97 Block Cipher, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
N.T. Courtois, J. Pieprzyk, Cryptanalysis of Block Ciphers with Overdefined Systems of Quadratic Equations, Adv. in Cryptology, Asiacrypt'02, Y. Zheng,Ed., Springer- Verlag, LNCS 2501, 2002, 267-287.
J. Daemen, L.R. Knudsen, V. Rijmen, The Block Cipher SQUARE, 4th Fast Software Encryption Workshop, E. Biham, Ed., Springer-Verlag, LNCS 1267, 1997, 149-165.
J. Daemen, V. Rijmen, The Design of Rijndael - AES - The Advanced Encryption Standard, Springer-Verlag, 2002.
GnuPG, Gnu Privacy Guard, http://www.gnupg.org/(en)/features.html
H.M. Heys, S.E. Tavares, On the Security of the CAST Encryption Algorithm, Canadian Conference on Electrical and Computer Engineering, 1994, 332-335.
J. Kelsey, B. Schneier, D. Wagner, Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X. NewDES, RC2 and TEA, Information and Commmunications Security, ICICS'97, First International Conference Proceedings, Springer-Verlag, Nov. 1997, 233-246.
L.R. Knudsen, DEAL - a 128-bit Block Cipher, Tech Report #151, Univ. of Bergen, Dept. of Informatics, Norway, Feb. 1998.
L.R. Knudsen, Weaknesses in LOKI97, 1999, http://csrc.nist.gov/encryption/aes/
L.R. Knudsen, J.E. Mathiassen, A Chosen-Plaintext Linear Attack on DES, 7th Fast Software Encryption Workshop, B. Schneier, Ed., Springer-Verlag, LNCS 1978, 2000, 262-272.
L.R. Knudsen, V. Rijmen, Ciphertext-Only Attack on Akelarre, Cryptologia, vol. XXIV, no. 2, Apr. 2000, 135-147.
M. Matsui, Linear Cryptanalysis Method for DES Cipher, Adv. in Cryptology, Eurocrypt' 93, T. Helleseth,Ed., Springer-Verlag, LNCS 765, 1994, 386-397.
M. Matsui, On Correlation Between the Order of S-boxes and the Strength of DES, Adv. in Cryptology, Eurocrypt'94, A. De Santis,Ed., Springer-Verlag, LNCS 950, 1995, 366-375.
M. Matsui, A. Yamagishi, A New Method for Known-Plaintext Attack of FEAL Cipher, Adv. in Cryptology, Eurocrypt'92, R.A. Rueppel,Ed., Springer-Verlag, LNCS 658, 1993, 81-91.
S. Moriai, T. Shimoyama, T. Kaneko, Higher-Order Differential Attack of a CAST cipher, Fast Software Encryption, 5th International Workshop Proceedings, Springer- Verlag, 1998, 17-31.
NBS, Data Encryption Standard (DES), FIPS PUB 46, Federal Information Processing Standards Publication 46, U.S. Department of Commerce, Jan. 1977. 10
K. Nyberg, Linear Approximation of Block Ciphers, Adv. in Cryptology, Eurocrypt'94, A. De Santis,Ed., Springer-Verlag, LNCS 950, 1995, 439-444.
V. Rijmen, B. Preneel, Erik DeWin, On Weaknesses of Non-Surjective Rounds Functions, Designs, Codes and Cryptography, vol. 12, 1997, 253-266.
R.L. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin, The RC6 Block Cipher, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
B. Schneier, J. Kelsey, Unbalanced Feistel Networks and Block Cipher Design, 3rd Fast Software Encryption Workshop, D. Gollmann,Ed., Springer-Verlag, LNCS 1039, 1996, 121-144.
A.A. Selc¸uk, On Bias Estimation in Linear Cryptanalysis, Progress in Cryptology - INDOCRYPT 2000, B. Roy, E. Okamoto, Eds., Springer-Verlag, LNCS 1977, 2000, 52-66.
J. Sung, J. Kim, C. Lee, S. Hong, Related-Cipher Attacks on Block Ciphers with Flexible Number of Rounds, Western European Workshop on Research in Cryptlogy, WEWoRC 2005, C. Wolf, S. Lucks, P.-W. Yau, Eds., Lecture Notes in Informatics (LNI), P-74.
Wikipedia, http://en.wikipedia.org/wiki/GNU Privacy Guard
C.M. Adams, The CAST-128 Encryption Algorithm, RFC 2144, May 1997.
C.M. Adams, The CAST-256 Encryption Algorithm, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
C.M. Adams, Constructing Symmetric Ciphers using the CAST Design Procedure, Designs, Codes, and Cryptography, 12:(3), Nov. 1997, 283-316.
C.M. Adams, H.M. Heys, S.E. Tavares, M. Wiener, An Analysis of the CAST-256 Cipher, [link]
E. Biham, A Note on Comparing the AES Candidates, The AES Development Process, http://csrc.nist.gov/encryption/aes/round1/conf2/papers/biham2.pdf
A. Biryukov, C. De Cannière, Block Ciphers and Systems of Quadratic Equations, 10th Fast Software Encryption Workshop, T. Johansson, Ed., Springer-Verlag, LNCS 2887, 2003, 274-289. 9
U. Blöcher, M. Dichtl, Problems with the Linear Cryptanalysis of DES using More than One Active S-box per Round, 1st Fast Software Encryption Workshop, R. Anderson, Ed., Springer-Verlag, LNCS 809, 1994, 256-274.
L. Brown, J. Pieprzyk, Introducing the New LOKI97 Block Cipher, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
N.T. Courtois, J. Pieprzyk, Cryptanalysis of Block Ciphers with Overdefined Systems of Quadratic Equations, Adv. in Cryptology, Asiacrypt'02, Y. Zheng,Ed., Springer- Verlag, LNCS 2501, 2002, 267-287.
J. Daemen, L.R. Knudsen, V. Rijmen, The Block Cipher SQUARE, 4th Fast Software Encryption Workshop, E. Biham, Ed., Springer-Verlag, LNCS 1267, 1997, 149-165.
J. Daemen, V. Rijmen, The Design of Rijndael - AES - The Advanced Encryption Standard, Springer-Verlag, 2002.
GnuPG, Gnu Privacy Guard, http://www.gnupg.org/(en)/features.html
H.M. Heys, S.E. Tavares, On the Security of the CAST Encryption Algorithm, Canadian Conference on Electrical and Computer Engineering, 1994, 332-335.
J. Kelsey, B. Schneier, D. Wagner, Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X. NewDES, RC2 and TEA, Information and Commmunications Security, ICICS'97, First International Conference Proceedings, Springer-Verlag, Nov. 1997, 233-246.
L.R. Knudsen, DEAL - a 128-bit Block Cipher, Tech Report #151, Univ. of Bergen, Dept. of Informatics, Norway, Feb. 1998.
L.R. Knudsen, Weaknesses in LOKI97, 1999, http://csrc.nist.gov/encryption/aes/
L.R. Knudsen, J.E. Mathiassen, A Chosen-Plaintext Linear Attack on DES, 7th Fast Software Encryption Workshop, B. Schneier, Ed., Springer-Verlag, LNCS 1978, 2000, 262-272.
L.R. Knudsen, V. Rijmen, Ciphertext-Only Attack on Akelarre, Cryptologia, vol. XXIV, no. 2, Apr. 2000, 135-147.
M. Matsui, Linear Cryptanalysis Method for DES Cipher, Adv. in Cryptology, Eurocrypt' 93, T. Helleseth,Ed., Springer-Verlag, LNCS 765, 1994, 386-397.
M. Matsui, On Correlation Between the Order of S-boxes and the Strength of DES, Adv. in Cryptology, Eurocrypt'94, A. De Santis,Ed., Springer-Verlag, LNCS 950, 1995, 366-375.
M. Matsui, A. Yamagishi, A New Method for Known-Plaintext Attack of FEAL Cipher, Adv. in Cryptology, Eurocrypt'92, R.A. Rueppel,Ed., Springer-Verlag, LNCS 658, 1993, 81-91.
S. Moriai, T. Shimoyama, T. Kaneko, Higher-Order Differential Attack of a CAST cipher, Fast Software Encryption, 5th International Workshop Proceedings, Springer- Verlag, 1998, 17-31.
NBS, Data Encryption Standard (DES), FIPS PUB 46, Federal Information Processing Standards Publication 46, U.S. Department of Commerce, Jan. 1977. 10
K. Nyberg, Linear Approximation of Block Ciphers, Adv. in Cryptology, Eurocrypt'94, A. De Santis,Ed., Springer-Verlag, LNCS 950, 1995, 439-444.
V. Rijmen, B. Preneel, Erik DeWin, On Weaknesses of Non-Surjective Rounds Functions, Designs, Codes and Cryptography, vol. 12, 1997, 253-266.
R.L. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin, The RC6 Block Cipher, 1st AES Conference, California, USA, Aug. 1998, http://csrc.nist.gov/encryption/aes/
B. Schneier, J. Kelsey, Unbalanced Feistel Networks and Block Cipher Design, 3rd Fast Software Encryption Workshop, D. Gollmann,Ed., Springer-Verlag, LNCS 1039, 1996, 121-144.
A.A. Selc¸uk, On Bias Estimation in Linear Cryptanalysis, Progress in Cryptology - INDOCRYPT 2000, B. Roy, E. Okamoto, Eds., Springer-Verlag, LNCS 1977, 2000, 52-66.
J. Sung, J. Kim, C. Lee, S. Hong, Related-Cipher Attacks on Block Ciphers with Flexible Number of Rounds, Western European Workshop on Research in Cryptlogy, WEWoRC 2005, C. Wolf, S. Lucks, P.-W. Yau, Eds., Lecture Notes in Informatics (LNI), P-74.
Wikipedia, http://en.wikipedia.org/wiki/GNU Privacy Guard
Publicado
27/08/2007
Como Citar
NAKAHARA JR, Jorge; RASMUSSEN, Mads.
Linear Analysis of reduced-round CAST-128 and CAST-256. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 7. , 2007, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 15-25.
DOI: https://doi.org/10.5753/sbseg.2007.20914.
