Impossible-Differential Attacks on block-cipher based Hash and Compression Functions using 3D and Whirlpool
Resumo
In this paper, we analyse block-cipher-based hash functions, which means hash functions that use block ciphers as compression functions in a mode of operation, such as Davies-Meyer (DM), Matyas-Meyer-Oseas (MMO) and Miyaguchi-Preneel (MP), for instance. We use impossible differentials (ID) to distinguish the compression (or hash) function from an ideal primitive (a random oracle) by detecting a nonrandom behavior. We applied an ID analysis to an 8-round variant of the 3D block cipher used in MMO mode, as a compression function of a hypothetical hash function. This attack effectively improves upon the previously known distinguishing ID attacks on reduced-round 3D. We can also attack a hash function using 3D as compression function in DM mode. Finally, we attacked the compression function in Whirlpool with a 5-round W cipher in MP mode with 2100 time and 264 memory.
Palavras-chave:
impossible differentials, block-cipher-based hash functions, modes of operation, Whirlpool hash function
Referências
Baigneres, T.: Quantitative Security of Block Ciphers: Designs and Cryptanalysis Tools. PhD Thesis, Ecole Polytechnique Federale de Lausanne (2008)
Barak, B., Aref, M.R.: Impossible Differential Attack on seven-round AES-128. IET Information Security, (2):2, 28–32 (2008)
Barkan,E., Biham, E.: In How Many Ways can you write Rijndael?. In: Y Zheng (Ed.), Asiacrypt 2002, Springer, LNCS 2501, 160–175 (2002)
Barreto, P.S.L.M., Rijmen, V.: The Whirlpool Hashing Function. available at http://www.larc.usp.br/pbarreto/WhirlpoolPage.html (2003)
Biham, E., Biryukov, A., Shamir, A.: Miss-in-the-Middle Attacks on IDEA and Khufu. In: Knudsen, L.R. (Ed.), Fast Software Encryption (FSE), Springer, LNCS 1636, 124–138 (1999)
Cheon, J.H., Kim, M., Kim, K., Lee, J.Y., Kang,S.: Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. 4th International Conference on Information Security and Cryptology (ICISC), Springer, LNCS 2288, 39–49 (2001)
Daemen,J., Rijmen,V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer (2002)
Damgard, I.: A Design Principle for Hash Functions. In Brassard,G. (Ed.), Crypto’89, 9th Annual International Cryptology Conference, 1989. Springer, LNCS 435, 416–427 (1990)
Dong, L.,Wu,W.,Wu, S., Zou, J.: Known-key distinguishers on round-reduced 3D block cipher. Information Security Applications (WISA), Springer, LNCS 7115, 55–69 (2012)
FIPS197: Advanced Encryption Standard (AES). FIPS PUB 197 Federal Information Processing Standard Publication 197, U.S. Department of Commerce (2001)
Gligoroski, D.: Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains. Faculty of Information Technology, Norwegian Univ. of Science and Technology, Trondheim, Norway.
Knudsen, L.R.: DEAL – a 128-bit Block Cipher. Technical Report #151, University of Bergen, Dept. of Informatics, Norway (1998)
Knudsen, L.R.: Nonrandom Properties of reduced-round Whirlpool. NES/DOC/UIB/WP5/016/2, Aug. 15 (2002)
Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schlaffer, M.: Rebound Distinguishers: results on the full Whirlpool Compression Function. Asiacrypt 2009, 15th International Conference, Springer, LNCS 5912, 126–143 (2009)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland Mathematical Library (1977)
Mendel, F., Rechberger, C., Schlaffer,M., Thomsen, S.S.: The Rebound Attack: cryptanalysis of reduced Whirlpool and Grøstl. In: Dunkelman, O. (Ed.), Fast Software Encryption (FSE) 2009, Springer, LNCS 5665, 260–276 (2009)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1997)
Merkle, R.C.: One way hash functions and DES. In Brassard,G. (Ed.), Crypto’89, 9th Annual International Cryptology Conference, Springer, LNCS 435, 428–446 (1990)
Mouha, N., Bjorstad, T.E., Preneel, B.: Non-randomness in the Sarmal compression function. The Ecrypt Hash Function website http://ehash.iaik.tugraz.at/wiki/Sarmal
Nakahara Jr, J.: 3D: a Three-Dimensional Block Cipher. In: M.K.Franklin, L.C.K.Hui, D.S.Wong (Eds.), Cryptology and Network Security (CANS), Springer, LNCS 5339, 252–267 (2008)
Nakahara Jr, J.: New Impossible Differential and Known-Key Distinguishers for the 3D Cipher. In: Bao, F., Weng, J. (Eds.), The 7th Information Practice and Experience Conference (ISPEC), Springer, LNCS 6672, 208–221 (2011)
NIST: Cryptographic Hash Algorithm Competition. available at http://csrc.nist.gov/groups/ST/hash/sha-3/index.html (2007)
NIST: Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register, vol. 72, no. 212, Nov. 2 (2007)
Rijmen, V., Preneel, B., De Win, E.: On weaknesses of non-surjective round functions. Design, Codes and Cryptography (12):3, 253–266 (1997)
Barak, B., Aref, M.R.: Impossible Differential Attack on seven-round AES-128. IET Information Security, (2):2, 28–32 (2008)
Barkan,E., Biham, E.: In How Many Ways can you write Rijndael?. In: Y Zheng (Ed.), Asiacrypt 2002, Springer, LNCS 2501, 160–175 (2002)
Barreto, P.S.L.M., Rijmen, V.: The Whirlpool Hashing Function. available at http://www.larc.usp.br/pbarreto/WhirlpoolPage.html (2003)
Biham, E., Biryukov, A., Shamir, A.: Miss-in-the-Middle Attacks on IDEA and Khufu. In: Knudsen, L.R. (Ed.), Fast Software Encryption (FSE), Springer, LNCS 1636, 124–138 (1999)
Cheon, J.H., Kim, M., Kim, K., Lee, J.Y., Kang,S.: Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. 4th International Conference on Information Security and Cryptology (ICISC), Springer, LNCS 2288, 39–49 (2001)
Daemen,J., Rijmen,V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer (2002)
Damgard, I.: A Design Principle for Hash Functions. In Brassard,G. (Ed.), Crypto’89, 9th Annual International Cryptology Conference, 1989. Springer, LNCS 435, 416–427 (1990)
Dong, L.,Wu,W.,Wu, S., Zou, J.: Known-key distinguishers on round-reduced 3D block cipher. Information Security Applications (WISA), Springer, LNCS 7115, 55–69 (2012)
FIPS197: Advanced Encryption Standard (AES). FIPS PUB 197 Federal Information Processing Standard Publication 197, U.S. Department of Commerce (2001)
Gligoroski, D.: Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains. Faculty of Information Technology, Norwegian Univ. of Science and Technology, Trondheim, Norway.
Knudsen, L.R.: DEAL – a 128-bit Block Cipher. Technical Report #151, University of Bergen, Dept. of Informatics, Norway (1998)
Knudsen, L.R.: Nonrandom Properties of reduced-round Whirlpool. NES/DOC/UIB/WP5/016/2, Aug. 15 (2002)
Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schlaffer, M.: Rebound Distinguishers: results on the full Whirlpool Compression Function. Asiacrypt 2009, 15th International Conference, Springer, LNCS 5912, 126–143 (2009)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland Mathematical Library (1977)
Mendel, F., Rechberger, C., Schlaffer,M., Thomsen, S.S.: The Rebound Attack: cryptanalysis of reduced Whirlpool and Grøstl. In: Dunkelman, O. (Ed.), Fast Software Encryption (FSE) 2009, Springer, LNCS 5665, 260–276 (2009)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1997)
Merkle, R.C.: One way hash functions and DES. In Brassard,G. (Ed.), Crypto’89, 9th Annual International Cryptology Conference, Springer, LNCS 435, 428–446 (1990)
Mouha, N., Bjorstad, T.E., Preneel, B.: Non-randomness in the Sarmal compression function. The Ecrypt Hash Function website http://ehash.iaik.tugraz.at/wiki/Sarmal
Nakahara Jr, J.: 3D: a Three-Dimensional Block Cipher. In: M.K.Franklin, L.C.K.Hui, D.S.Wong (Eds.), Cryptology and Network Security (CANS), Springer, LNCS 5339, 252–267 (2008)
Nakahara Jr, J.: New Impossible Differential and Known-Key Distinguishers for the 3D Cipher. In: Bao, F., Weng, J. (Eds.), The 7th Information Practice and Experience Conference (ISPEC), Springer, LNCS 6672, 208–221 (2011)
NIST: Cryptographic Hash Algorithm Competition. available at http://csrc.nist.gov/groups/ST/hash/sha-3/index.html (2007)
NIST: Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register, vol. 72, no. 212, Nov. 2 (2007)
Rijmen, V., Preneel, B., De Win, E.: On weaknesses of non-surjective round functions. Design, Codes and Cryptography (12):3, 253–266 (1997)
Publicado
19/11/2012
Como Citar
FREITAS, Daniel Santana de; NAKAHARA JR, Jorge.
Impossible-Differential Attacks on block-cipher based Hash and Compression Functions using 3D and Whirlpool. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 12. , 2012, Curitiba.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 99-111.
DOI: https://doi.org/10.5753/sbseg.2012.20539.
