zbMATH — the first resource for mathematics

The software performance of authenticated-encryption modes. (English) Zbl 1307.94119
Joux, Antoine (ed.), Fast software encryption. 18th international workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-21701-2/pbk). Lecture Notes in Computer Science 6733, 306-327 (2011).
Summary: We study software performance of authenticated-encryption modes CCM, GCM, and OCB. Across a variety of platforms, we find OCB to be substantially faster than either alternative. For example, on an Intel i5 (“Clarkdale”) processor, good implementations of CCM, GCM, and OCB encrypt at around 4.2 cpb, 3.7 cpb, and 1.5 cpb, while CTR mode requires about 1.3 cpb. Still we find room for algorithmic improvements to OCB, showing how to trim one blockcipher call (most of the time, assuming a counter-based nonce) and reduce latency. Our findings contrast with those of D. A. McGrew and J. Viega [Indocrypt 2004, Lect. Notes Comput. Sci. 3348, 343–355 (2004; Zbl 1113.94315)], who claimed similar performance for GCM and OCB.
For the entire collection see [Zbl 1217.68011].

94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. J. Cryptology 21(4), 469–491 (2008); Earlier version in ASIACRYPT 2000 · Zbl 1161.94435 · doi:10.1007/s00145-008-9026-x
[2] Bellare, M., Rogaway, P., Wagner, D.: The EAX mode of operation. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 389–407. Springer, Heidelberg (2004) · Zbl 1079.68537 · doi:10.1007/978-3-540-25937-4_25
[3] Bernstein, D.: The Poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 32–49. Springer, Heidelberg (2005) · Zbl 1140.68382 · doi:10.1007/11502760_3
[4] Bernstein, D.J., Schwabe, P.: New AES software speed records. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 322–336. Springer, Heidelberg (2008) · Zbl 1203.94093 · doi:10.1007/978-3-540-89754-5_25
[5] Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Rogaway, P.: UMAC: fast and secure message authentication. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 216–233. Springer, Heidelberg (1999) · Zbl 0940.94020 · doi:10.1007/3-540-48405-1_14
[6] Chakraborty, D., Sarkar, P.: A general construction of tweakable block ciphers and different modes of operations. IEEE Trans. on Information Theory 54(5) (May 2008) · Zbl 1328.94062 · doi:10.1109/TIT.2008.920247
[7] Dworkin, M.: Recommendation for block cipher modes of operation: the CCM mode for authentication and confidentiality. NIST Special Publication 800-38C (May 2004)
[8] Dworkin, M.: Recommendation for block cipher modes of operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D (November 2007)
[9] Ekdahl, P., Johansson, T.: A new version of the stream cipher SNOW. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 47–61. Springer, Heidelberg (2003) · Zbl 1027.68596 · doi:10.1007/3-540-36492-7_5
[10] Ferguson, N., Whiting, D., Schneier, B., Kelsey, J., Lucks, S., Kohno, T.: Helix: fast encryption and authentication in a single cryptographic primitive. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 330–346. Springer, Heidelberg (2003) · Zbl 1254.68115 · doi:10.1007/978-3-540-39887-5_24
[11] Gligor, V., Donescu, P.: Fast encryption and authentication: XCBC encryption and XECB authentication modes. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 92–108. Springer, Heidelberg (2002) · Zbl 1073.68629 · doi:10.1007/3-540-45473-X_8
[12] Gueron, S.: Intel’s New AES instructions for enhanced performance and security. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 51–66. Springer, Heidelberg (2009) · Zbl 1291.94091 · doi:10.1007/978-3-642-03317-9_4
[13] Gueron, S., Kounavis, M.: Intel carry-less multiplication instruction and its usage for computing the GCM mode (revision 2), White paper (May 2010), http://www.intel.com · Zbl 1234.94044
[14] Halevi, S.: An observation regarding Jutla’s modes of operation. Cryptology ePrint report 2001/015, April 2 (2001)
[15] IEEE Standard 802.11i-2004. Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Security Enhancements (2004)
[16] ISO/IEC 19772. Information technology – Security techniques – Authenticated encryption, 1st edn. (February 15, 2009)
[17] Iwata, T.: Authenticated encryption mode for beyond the birthday bound security. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 125–142. Springer, Heidelberg (2008) · Zbl 1142.94345 · doi:10.1007/978-3-540-68164-9_9
[18] Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (2006) · Zbl 1234.94049 · doi:10.1007/11799313_20
[19] Iwata, T., Yasuda, K.: BTM: A single-key, inverse-cipher-free mode for deterministic authenticated encryption. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 313–330. Springer, Heidelberg (2009) · Zbl 1267.94067 · doi:10.1007/978-3-642-05445-7_20
[20] Iwata, T., Yasuda, K.: HBS: a single-key mode of operation for deterministic authenticated encryption. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 394–415. Springer, Heidelberg (2009) · Zbl 1248.94074 · doi:10.1007/978-3-642-03317-9_24
[21] Jutla, C.: Encryption modes with almost free message integrity. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 529–544. Springer, Heidelberg (2001) · Zbl 0981.94036 · doi:10.1007/3-540-44987-6_32
[22] Käsper, E., Schwabe, P.: Faster and timing-attack resistant AES-GCM. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 1–17. Springer, Heidelberg (2009) · Zbl 1290.94102 · doi:10.1007/978-3-642-04138-9_1
[23] Katz, J., Yung, M.: Unforgeable encryption and chosen ciphertext secure modes of operation. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, p. 284. Springer, Heidelberg (2001) · Zbl 0994.68629 · doi:10.1007/3-540-44706-7_20
[24] Kohno, T., Viega, J., Whiting, D.: CWC: A high-performance conventional authenticated encryption mode. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 408–426. Springer, Heidelberg (2004) · Zbl 1079.68549 · doi:10.1007/978-3-540-25937-4_26
[25] Krovetz, T.: Message authentication on 64-bit architectures. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 327–341. Springer, Heidelberg (2007) · Zbl 1161.68444 · doi:10.1007/978-3-540-74462-7_23
[26] Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. Full version of this paper (January 2011) · Zbl 1307.94119
[27] Leiserson, C., Prokop, H., Randall, K.: Using de Bruijn sequences to index a 1 in a computer word (July 7, 1998) (unpublished manuscript)
[28] Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications (Revised Edition). Cambridge University Press, Cambridge (1994) · Zbl 0820.11072 · doi:10.1017/CBO9781139172769
[29] Liskov, M., Rivest, R., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002) · Zbl 1026.94533 · doi:10.1007/3-540-45708-9_3
[30] Lucks, S.: Two-pass authenticated encryption faster than generic composition. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 284–298. Springer, Heidelberg (2005) · Zbl 1140.94359 · doi:10.1007/11502760_19
[31] McGrew, D.: An interface and algorithms for authenticated encryption. IETF RFC 5116 (January 2008) · Zbl 1133.03307
[32] McGrew, D., Viega, J.: The security and performance of the Galois/Counter Mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004); Also Cryptology ePrint report 2004/193, with somewhat different performance results · Zbl 1113.94315 · doi:10.1007/978-3-540-30556-9_27
[33] OpenSSL: The Open Source Toolkit for SSL/TLS, http://www.openssl.org/
[34] Rogaway, P.: Authenticated-encryption with associated-data. In: CCS 2002. ACM Press, New York (2002)
[35] Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004) · Zbl 1094.94035 · doi:10.1007/978-3-540-30539-2_2
[36] Rogaway, P., Bellare, M., Black, J.: OCB: A block-cipher mode of operation for efficient authenticated encryption. ACM Trans. on Information and System Security 6(3), 365–403 (2003); Earlier version, with T. Krovetz, in CCS 2001 · Zbl 05453902 · doi:10.1145/937527.937529
[37] Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 373–390. Springer, Heidelberg (2006) · Zbl 1140.94369 · doi:10.1007/11761679_23
[38] Tsaban, B., Vishne, U.: Efficient linear feedback shift registers with maximal period. Finite Fields and Their Applications 8(2), 256–267 (2002), Also CoRR cs.CR/0304010 (2003) · Zbl 1015.94005 · doi:10.1006/ffta.2001.0339
[39] VIA Technologies. VIA Padlock programming guide (2005)
[40] Whiting, D., Housley, R., Ferguson, N.: AES encryption & authentication using CTR mode & CBC-MAC. IEEE P802.11 doc 02/001r2 (May 2002)
[41] Whiting, D., Housley, R., Ferguson, N.: Counter with CBC-MAC (CCM). IETF RFC 3610 (September 2003)
[42] Zeng, G., Han, W., He, K.: High efficiency feedback shift register: \(\sigma\)-LFSR. Cryptology ePrint report 2007/114 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.