Attacks on single-pass confidentiality modes of operation
Resumo
The main contributions of this paper are efficient distinguishing attacks against block ciphers that are conventionally modeled as pseudorandom permutations (PRP). Formally, block ciphers operate on fixed-length blocks of n bits, for example, n = 128 for the Advanced Encryption Standard (AES). Our analysis takes place in the setting in which the messages are m bits long, representing the entire input plaintext, where m is variable and unrelated to n. We show distinguish-fromrandom attacks for any n-bit block cipher in the standard modes of operation for confidentiality: ECB, CBC, CFB, OFB, CTR and XTS. We demonstrate that in all these 1-pass modes any n-bit block cipher leaves 'footprints' that allows an adversary to efficiently (in time and memory) distinguish them from a random permutation. We claim that two passes (in opposite directions) over the m-bit message, with textdependent feedforward (chaining) and in streaming mode are sufficient to circumvent the presented attacks.
Palavras-chave:
left-to-right diffusion, distinguishing attacks, modes of operation, (super)pseudorandom permutations, IND-KPA, IND-CPA
Referências
Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. (1997). A concrete security treatment of symmetric encryption. In 38th Annual Symposium on Foundations of Computer Science, FOCS’97, pages 394–403.
Bellare, M. and Rogaway, P. (2006). The security of triple encryption and a framework for code-based game-playing proofs. In Vaudenay, S., editor, Adv. in Cryptology, Eurocrypt, volume 4004 of LNCS, pages 409–426. Springer.
Bellare, M., Rogaway, P., and Wagner, D. (2004). The eax mode of operation. In Fast Software Encryption (FSE), volume 3017 of LNCS, pages 389–407. Springer.
Biham, E. (1998). Cryptanalysis of multiple modes of operation. Journal of Cryptology, 11(1):45–58.
Campbell, C. (1978). Design and specification of cryptographic capabilities. In Brandstad, D., editor, Computer Security and the Data Encryption Standard, Special Publications 500-27, pages 54–66. National Bureau of Standards, US Dept of Commerce.
Chakraborty, D. and Sarkar, P. (2006). A new mode of encryption providing a tweakable strong pseudorandom permutation. In Fast Software Encryption (FSE), volume 4047 of LNCS, pages 293–309. Springer.
Courtois, N. (2006). How fast can be algebraic attacks on block ciphers? IACR ePrint archive 2006/168.
Crowley, P. (2000). Mercy: a fast large block cipher for disk sector encryption. In Schneier, B., editor, Fast Software Encryption (FSE), volume 1978 of LNCS, pages 49–63. Springer.
Daemen, J. and Rijmen, V. (2000). The block cipher bksq. In Quisquater, J.-J. and Schneier, B., editors, Third International Conference on Smart Card Research and Applications (CARDIS), volume 1820 of LNCS, pages 236–245. Springer.
Dworkin, M. (2001). Recommendation for block cipher modes of operation methods and techniques. National Institute of Standards and Technology NIST Special Publication 800-38A (2001).
Dworkin, M. (2004). Recommendation for block cipher modes of operation: The ccm mode for authentication and confidentiality. National Institute of Standards and Technology (NIST). NIST Special Publication 800-38C (2004).
Dworkin, M. (2010a). Recommendation for block cipher modes of operation: The xts-aes mode for confidentiality on storage devices. National Institute of Standards and Technology (NIST). NIST Special Publication 800-38E (2010).
Dworkin, M. (2010b). Recommendation for block cipher modes of operation: Three variants of ciphertext stealing for cbc mode. National Institute of Standards and Technology (NIST). Addendum to NIST SpecialPublication 800-38A (2010).
FIPS197 (2001). Advanced encryption standard (aes). FIPS PUB 197 Federal Information Processing Standard Publication 197, U.S. Department of Commerce (2001).
Halevi, S. and Rogaway, P. (2003). A tweakable enciphering mode. In Boneh, D., editor, Adv. in Cryptology, Crypto, volume 2729 of LNCS, pages 482–499. Springer.
Halevi, S. and Rogaway, P. (2004). A parallelizable enciphering mode. In CT-RSA, volume 2964 of LNCS, pages 292–304. Springer.
IEEE (2008). The xts-aes tweakable block cipher an extract from ieee std 1619-2007. The Institute of Electrical and Electronics Engineers, Inc.
Jutla, C. (2000). Parallelizable encryption mode with almost free message integrity. http://citeseer.ist.psu.edu/jula00parallelizable.html.
Jutla, C. (2001). Encryption modes with almost free message integrity. In Pfitzmann, B., editor, Adv. in Cryptology, Eurocrypt, volume 2045 of LNCS, pages 529–544. Springer.
Klimov, A. and Shamir, A. (2002). A new class of invertible mappings. In Cryptographic Hardware and Embedded Systems (CHES), volume 2523 of LNCS, pages 470–483. Springer.
Kohno, T., Viega, J., and Whiting, D. Cwc: a high-performance conventional authenticated encryption mode. Cryptology ePrint Archive, report 2003/106 (2003).
Luby, M. and Rackoff, C. (1988). How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2):373–386.
McGrew, D. and Viega, J. (2004). The security and performance of the galois/counter mode (gcm) of operation. In Canteaut, A. and Viswanathan, K., editors, Indocrypt, volume 3348 of LNCS, pages 343–355. Springer.
Menezes, A., van Oorschot, P., and Vanstone, S. (1997). Handbook of Applied Cryptography. CRC Press.
Naor, M. and Reingold, O. A pseudorandom encryption mode. Manuscript available at http://www.wisdom.wiezmann.ac.il/~naor.
Naor, M. and Reingold, O. (1999). On the construction of pseudorandom permutations: Lubyrackoff revisited. Journal of Cryptology, 12(1):29–66.
Rogaway, P. The emd mode of operation (a tweaked, wide-blocksize strong prp). Cryptology ePrint Archive 2002/148.
Rogaway, P. (2004). Efficient instantiations of tweakable block ciphers and refinements to modes ocb and pmac. In Lee, P., editor, Adv. in Cryptology, Asiacrypt, volume 3329 of LNCS, pages 16–31. Springer.
Sarkar, P. (2007). Improving upon the tet mode of operation. In Nam, K.-H. and Rhee, G., editors, Information Security and Cryptology (ICISC), volume 4817 of LNCS, pages 180– 192. Springer.
SISWG. Ieee security in storage working group (siswg). http://www.siswg.com.
Whiting, D., Housley, R., and Ferguson, N. Submission to nist: Counter with cbcmac (ccm) aes mode of operation. Computer Security Division, Computer Security Resource Center (NIST).
Bellare, M. and Rogaway, P. (2006). The security of triple encryption and a framework for code-based game-playing proofs. In Vaudenay, S., editor, Adv. in Cryptology, Eurocrypt, volume 4004 of LNCS, pages 409–426. Springer.
Bellare, M., Rogaway, P., and Wagner, D. (2004). The eax mode of operation. In Fast Software Encryption (FSE), volume 3017 of LNCS, pages 389–407. Springer.
Biham, E. (1998). Cryptanalysis of multiple modes of operation. Journal of Cryptology, 11(1):45–58.
Campbell, C. (1978). Design and specification of cryptographic capabilities. In Brandstad, D., editor, Computer Security and the Data Encryption Standard, Special Publications 500-27, pages 54–66. National Bureau of Standards, US Dept of Commerce.
Chakraborty, D. and Sarkar, P. (2006). A new mode of encryption providing a tweakable strong pseudorandom permutation. In Fast Software Encryption (FSE), volume 4047 of LNCS, pages 293–309. Springer.
Courtois, N. (2006). How fast can be algebraic attacks on block ciphers? IACR ePrint archive 2006/168.
Crowley, P. (2000). Mercy: a fast large block cipher for disk sector encryption. In Schneier, B., editor, Fast Software Encryption (FSE), volume 1978 of LNCS, pages 49–63. Springer.
Daemen, J. and Rijmen, V. (2000). The block cipher bksq. In Quisquater, J.-J. and Schneier, B., editors, Third International Conference on Smart Card Research and Applications (CARDIS), volume 1820 of LNCS, pages 236–245. Springer.
Dworkin, M. (2001). Recommendation for block cipher modes of operation methods and techniques. National Institute of Standards and Technology NIST Special Publication 800-38A (2001).
Dworkin, M. (2004). Recommendation for block cipher modes of operation: The ccm mode for authentication and confidentiality. National Institute of Standards and Technology (NIST). NIST Special Publication 800-38C (2004).
Dworkin, M. (2010a). Recommendation for block cipher modes of operation: The xts-aes mode for confidentiality on storage devices. National Institute of Standards and Technology (NIST). NIST Special Publication 800-38E (2010).
Dworkin, M. (2010b). Recommendation for block cipher modes of operation: Three variants of ciphertext stealing for cbc mode. National Institute of Standards and Technology (NIST). Addendum to NIST SpecialPublication 800-38A (2010).
FIPS197 (2001). Advanced encryption standard (aes). FIPS PUB 197 Federal Information Processing Standard Publication 197, U.S. Department of Commerce (2001).
Halevi, S. and Rogaway, P. (2003). A tweakable enciphering mode. In Boneh, D., editor, Adv. in Cryptology, Crypto, volume 2729 of LNCS, pages 482–499. Springer.
Halevi, S. and Rogaway, P. (2004). A parallelizable enciphering mode. In CT-RSA, volume 2964 of LNCS, pages 292–304. Springer.
IEEE (2008). The xts-aes tweakable block cipher an extract from ieee std 1619-2007. The Institute of Electrical and Electronics Engineers, Inc.
Jutla, C. (2000). Parallelizable encryption mode with almost free message integrity. http://citeseer.ist.psu.edu/jula00parallelizable.html.
Jutla, C. (2001). Encryption modes with almost free message integrity. In Pfitzmann, B., editor, Adv. in Cryptology, Eurocrypt, volume 2045 of LNCS, pages 529–544. Springer.
Klimov, A. and Shamir, A. (2002). A new class of invertible mappings. In Cryptographic Hardware and Embedded Systems (CHES), volume 2523 of LNCS, pages 470–483. Springer.
Kohno, T., Viega, J., and Whiting, D. Cwc: a high-performance conventional authenticated encryption mode. Cryptology ePrint Archive, report 2003/106 (2003).
Luby, M. and Rackoff, C. (1988). How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2):373–386.
McGrew, D. and Viega, J. (2004). The security and performance of the galois/counter mode (gcm) of operation. In Canteaut, A. and Viswanathan, K., editors, Indocrypt, volume 3348 of LNCS, pages 343–355. Springer.
Menezes, A., van Oorschot, P., and Vanstone, S. (1997). Handbook of Applied Cryptography. CRC Press.
Naor, M. and Reingold, O. A pseudorandom encryption mode. Manuscript available at http://www.wisdom.wiezmann.ac.il/~naor.
Naor, M. and Reingold, O. (1999). On the construction of pseudorandom permutations: Lubyrackoff revisited. Journal of Cryptology, 12(1):29–66.
Rogaway, P. The emd mode of operation (a tweaked, wide-blocksize strong prp). Cryptology ePrint Archive 2002/148.
Rogaway, P. (2004). Efficient instantiations of tweakable block ciphers and refinements to modes ocb and pmac. In Lee, P., editor, Adv. in Cryptology, Asiacrypt, volume 3329 of LNCS, pages 16–31. Springer.
Sarkar, P. (2007). Improving upon the tet mode of operation. In Nam, K.-H. and Rhee, G., editors, Information Security and Cryptology (ICISC), volume 4817 of LNCS, pages 180– 192. Springer.
SISWG. Ieee security in storage working group (siswg). http://www.siswg.com.
Whiting, D., Housley, R., and Ferguson, N. Submission to nist: Counter with cbcmac (ccm) aes mode of operation. Computer Security Division, Computer Security Resource Center (NIST).
Publicado
03/11/2014
Como Citar
MARKOWITCH, Olivier; NAKAHARA JR, Jorge.
Attacks on single-pass confidentiality modes of operation. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 14. , 2014, Belo Horizonte.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2014
.
p. 84-99.
DOI: https://doi.org/10.5753/sbseg.2014.20123.
