χ2 Attacks on Block-Cipher based Compression Functions
Resumo
In this paper, we report on χ2 analyses of block-cipher based (cryptographic) compression functions. Our aim is not to find collisions nor (second) preimages, but to detect non-random properties that may distinguish a compression function from an ideal primitive such as a random oracle. We study some well-known single-block modes of operation such as Davies-Meyer (DM), Matyas-Meyer-Oseas (MMO) and Miyaguchi-Preneel (MP), and double-block modes such as Hirose's, Tandem-DM, Abreast-DM, Parallel-DM and MDC-2. This paper shows how a weakness (χ2 correlation) in the underlying block cipher can propagate to the compression function via the mode of operation used in hash constructions. To demonstrate our ideas, we instantiated the block cipher underlying these modes with variable-round RC5, RC6 and ERC6 block ciphers.
Palavras-chave:
χ2 cryptanalysis, block-cipher-based (cryptographic) compression functions, single-and double-block-length modes of operation
Referências
Borst, J., Preneel, B., and Vandewalle, J. (1999). Linear cryptanalysis of RC5 and RC6. In Fast Software Encryption (FSE), LNCS 1636, pages 16–30. Springer.
Brachtl, B., Coppersmith, D., Hyden, M., Jr., S. M., Meyer, C., Oseas, J., Pilpel, S., and Schilling, M. (1990). Data authentication using modification detection codes based on a public one-way encryption function. US Patent 4908861.
El-Fishawy, N., Danaf, T., and Zaid, O. (2004). A modification of RC6 block cipher algorithm for data security (MRC6). In International Conference on Electrical, Electronic and Computer Engineering, pages 222–226.
Hirose, S. (2006). Some plausible constructions of double-block length hash functions. In Robshaw, M., editor, Fast Software Encryption Workshop, FSE 2006, LNCS 4047, pages 210–225. Springer.
Hohl, W., Lai, X., Meier, T., and Waldvogel, C. (1993). Security of iterated hash functions based on block ciphers. In D.R.Stinson, editor, Adv. in Cryptology, Crypto 1993, LNCS 773, pages 379–390. Springer.
Isogai, N., Miyaji, A., and Nonaka, M. (2002). Cryptanalysis of RC5-64 with improved correlation attack. In SCIS 2002, The 2002 Symposium on Cryptography and Information Security, pages 657–662. The Institute of Electronics, Information and Communications Engineers.
Jr., J. N., Sekar, G., de Freitas, D. S., Chiann, C., de Souza, R. H., and Preneel, B. (2009). A new approach to 2 cryptanalysis of block ciphers. In P.Samarati, editor, Information Security Conference (ISC), LNCS 5735, pages 1–16. Springer.
Kaufman, C., Perlman, R., and Speciner, M. (2002). Network Security: PRIVATE Communication in a PUBLIC World. Prentice-Hall.
Knudsen, L. (2002). Correlations in RC6 on 256-bit blocks. NESSIE technical report nes/doc/uib/wp5/022/1, Univ. of Bergen.
Knudsen, L. and Meier, W. (2000). Correlations in reduced round variants of RC6. In B.Schneier, editor, Fast Software Encryption, FSE 2000, 7th International Workshop, LNCS 1978, pages 94–108. Springer.
Lai, X. and Massey, J. (1993). Hash function based on block ciphers. In Adv. in Cryptology, Eurocrypt 1992, LNCS 658, pages 55–70. Springer.
Menezes, A., van Oorschot, P., and Vanstone, S. (1997). Handbook of Applied Cryptography. CRC Press.
Meyer, C. and Schilling, M. (1988). Secure program load with manipulation detection code. In Proceedings 6th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM 1988), pages 111–130.
Miyaji, A., Nonaka, M., and Takii, Y. (2002). Improved correlation attack on RC5. IEICE Trans. on Fundamentals, vol. E85-A, no. 1, 44–57.
NIST (1993). FIPS: Data encryption standard. Federal Information Processing Standards Publication 46-2, supersedes FIPS PUB 46-1.
NIST (2001). FIPS: Advanced encryption standard. Federal Information Processing Standards Publication 197.
NIST (2007a). Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register, vol. 72, no. 212, Nov.
NIST (2007b). Cryptographic hash algorithm competition. available at http://csrc.nist.gov/groups/ST/hash/sha-3/index.html.
Preneel, B., Govaerts, R., and Vandewalle, J. (1994). Hash functions based on block ciphers: a synthetic approach. In Adv. in Cryptology, Crypto 1993, LNCS 773, pages 368–378. Springer.
Ragab, A., Ismail, N., and Allah, O. (2001). Enhancements and implementation of RC6 block cipher for data security. IEEE TENCOM.
Rijmen, V., Preneel, B., and Win, E. D. (1997). On weaknesses of non-surjective round functions. Design, Codes and Cryptography, 12(3):253–266.
Rivest, R. (1994). The RC5 encryption algorithm. In Proceedings 2nd International Workshop on Fast Software Encryption (FSE), LNCS, pages 86–96. Springer.
Rivest, R., Robshaw, M., Sidney, R., and Yin, Y. (1998). The RC6 block cipher. http://www.rsa.com/rsalabs.
Shimoyama, T., Takeuchi, K., and Hayakawa, J. (2001). Correlation attack to the block cipher RC5 and the simplified variants of RC6. Advanced Encryption Standard (AES3) Conference, Jun.
Stallings, W. (2003). Cryptography and Network Security: Principles and Practice. Prentice Hall.
Brachtl, B., Coppersmith, D., Hyden, M., Jr., S. M., Meyer, C., Oseas, J., Pilpel, S., and Schilling, M. (1990). Data authentication using modification detection codes based on a public one-way encryption function. US Patent 4908861.
El-Fishawy, N., Danaf, T., and Zaid, O. (2004). A modification of RC6 block cipher algorithm for data security (MRC6). In International Conference on Electrical, Electronic and Computer Engineering, pages 222–226.
Hirose, S. (2006). Some plausible constructions of double-block length hash functions. In Robshaw, M., editor, Fast Software Encryption Workshop, FSE 2006, LNCS 4047, pages 210–225. Springer.
Hohl, W., Lai, X., Meier, T., and Waldvogel, C. (1993). Security of iterated hash functions based on block ciphers. In D.R.Stinson, editor, Adv. in Cryptology, Crypto 1993, LNCS 773, pages 379–390. Springer.
Isogai, N., Miyaji, A., and Nonaka, M. (2002). Cryptanalysis of RC5-64 with improved correlation attack. In SCIS 2002, The 2002 Symposium on Cryptography and Information Security, pages 657–662. The Institute of Electronics, Information and Communications Engineers.
Jr., J. N., Sekar, G., de Freitas, D. S., Chiann, C., de Souza, R. H., and Preneel, B. (2009). A new approach to 2 cryptanalysis of block ciphers. In P.Samarati, editor, Information Security Conference (ISC), LNCS 5735, pages 1–16. Springer.
Kaufman, C., Perlman, R., and Speciner, M. (2002). Network Security: PRIVATE Communication in a PUBLIC World. Prentice-Hall.
Knudsen, L. (2002). Correlations in RC6 on 256-bit blocks. NESSIE technical report nes/doc/uib/wp5/022/1, Univ. of Bergen.
Knudsen, L. and Meier, W. (2000). Correlations in reduced round variants of RC6. In B.Schneier, editor, Fast Software Encryption, FSE 2000, 7th International Workshop, LNCS 1978, pages 94–108. Springer.
Lai, X. and Massey, J. (1993). Hash function based on block ciphers. In Adv. in Cryptology, Eurocrypt 1992, LNCS 658, pages 55–70. Springer.
Menezes, A., van Oorschot, P., and Vanstone, S. (1997). Handbook of Applied Cryptography. CRC Press.
Meyer, C. and Schilling, M. (1988). Secure program load with manipulation detection code. In Proceedings 6th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM 1988), pages 111–130.
Miyaji, A., Nonaka, M., and Takii, Y. (2002). Improved correlation attack on RC5. IEICE Trans. on Fundamentals, vol. E85-A, no. 1, 44–57.
NIST (1993). FIPS: Data encryption standard. Federal Information Processing Standards Publication 46-2, supersedes FIPS PUB 46-1.
NIST (2001). FIPS: Advanced encryption standard. Federal Information Processing Standards Publication 197.
NIST (2007a). Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register, vol. 72, no. 212, Nov.
NIST (2007b). Cryptographic hash algorithm competition. available at http://csrc.nist.gov/groups/ST/hash/sha-3/index.html.
Preneel, B., Govaerts, R., and Vandewalle, J. (1994). Hash functions based on block ciphers: a synthetic approach. In Adv. in Cryptology, Crypto 1993, LNCS 773, pages 368–378. Springer.
Ragab, A., Ismail, N., and Allah, O. (2001). Enhancements and implementation of RC6 block cipher for data security. IEEE TENCOM.
Rijmen, V., Preneel, B., and Win, E. D. (1997). On weaknesses of non-surjective round functions. Design, Codes and Cryptography, 12(3):253–266.
Rivest, R. (1994). The RC5 encryption algorithm. In Proceedings 2nd International Workshop on Fast Software Encryption (FSE), LNCS, pages 86–96. Springer.
Rivest, R., Robshaw, M., Sidney, R., and Yin, Y. (1998). The RC6 block cipher. http://www.rsa.com/rsalabs.
Shimoyama, T., Takeuchi, K., and Hayakawa, J. (2001). Correlation attack to the block cipher RC5 and the simplified variants of RC6. Advanced Encryption Standard (AES3) Conference, Jun.
Stallings, W. (2003). Cryptography and Network Security: Principles and Practice. Prentice Hall.
Publicado
19/11/2012
Como Citar
FREITAS, Daniel Santana de; NAKAHARA JR, Jorge.
χ2 Attacks on Block-Cipher based Compression Functions. 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. 86-98.
DOI: https://doi.org/10.5753/sbseg.2012.20538.
