×

zbMATH — the first resource for mathematics

Modes of operations for encryption and authentication using stream ciphers supporting an initialisation vector. (English) Zbl 1291.94148
Summary: We describe a systematic framework for using a stream cipher supporting an initialisation vector (IV) to perform various tasks of authentication and authenticated encryption. These include message authentication code (MAC), authenticated encryption (AE), authenticated encryption with associated data (AEAD) and deterministic authenticated encryption (DAE) with associated data. Several schemes are presented and rigourously analysed. A major component of the constructions is a keyed hash function having provably low collision and differential probabilities. Methods are described to efficiently extend such hash functions to take multiple inputs. In particular, double-input hash functions are required for the construction of AEAD schemes. An important practical aspect of our work is that a designer can combine off-the-shelf stream ciphers with off-the-shelf hash functions to obtain secure primitives for MAC, AE, AEAD and DAE(AD).

MSC:
94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Document 1: Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 & 128-EIA3: 128-EEA3 & 128-EIA3 specification. http://gsmworld.com/our-work/programmes-and-initiatives/fraud-and-security/gsm_security_algorithms.htm (2011). Accessed 18 Dec 2013
[2] eSTREAM, the ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/ . Accessed 18 Dec 2013
[3] Ågren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: a new version of grain-128 with optional authentication. Int. J. Wirel. Mob. Comput. 5(1), 48–59 (2011) · doi:10.1504/IJWMC.2011.044106
[4] Bellare, M., Namprempre, C.: Authenticated encryption: Relations among notions and analysis of the generic composition paradigm. In: Okamoto, T. (ed.) Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3-7, 2000, Proceedings of Lecture Notes in Computer Science, vol. 1976, pp. 531–545. Springer (2000) · Zbl 0973.68059
[5] Bellare, M., Rogaway, P.: Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography. In: Okamoto, T. (ed.) Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3-7, 2000, Proceedings of Lecture Notes in Computer Science, vol. 1976, pp. 317–330. Springer (2000) · Zbl 0974.94008
[6] Berbain, C., Gilbert, H.: On the security of IV dependent stream ciphers. In: Biryukov, A. (ed.) FSE. Lecture Notes in Computer Science, vol. 4593, pp. 254–273. Springer (2007) · Zbl 1186.94423
[7] Bernstein, D.J.: Cycle counts for authenticated encryption. Workshop Record of SASC 2007: The State of the Art of Stream Ciphers. http://cr.yp.to/papers.html#aecycles . Accessed 18 Dec 2013
[8] Bernstein, D.J.: The Poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (eds.) FSE. Lecture Notes in Computer Science, vol. 3557, pp. 32–49. Springer (2005) · Zbl 1140.68382
[9] Bernstein, D.J.: Stronger security bounds for Wegman-Carter-Shoup authenticators. In: Cramer, R. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 3494, pp. 164–180. Springer (2005) · Zbl 1137.94364
[10] Bernstein, D.J.: Polynomial evaluation and message authentication. http://cr.yp.to/papers.html#pema (2007)
[11] Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Rogaway, P.: UMAC: fast and secure message authentication. In: Wiener, M.J. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 1666, pp. 216–233. Springer (1999) · Zbl 0940.94020
[12] Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979) · Zbl 0412.68090 · doi:10.1016/0022-0000(79)90044-8
[13] Chakraborty, D., Sarkar, P.: A general construction of tweakable block ciphers and different modes of operations. IEEE Trans. Inf. Theory 54(5), 1991–2006 (2008) · Zbl 1328.94062 · doi:10.1109/TIT.2008.920247
[14] Dworkin, M.: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D. csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf (2011)
[15] Ekdahl, P., Johansson, T.: A new version of the stream cipher SNOW. In: Nyberg, K., Heys, H.M. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 2595, pp. 47–61. Springer (2002) · Zbl 1027.68596
[16] 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. Lecture Notes in Computer Science, vol. 2887, pp. 330–346. Springer (2003) · Zbl 1254.68115
[17] Fuhr, T., Gilbert, H., Reinhard, J.-R., Videau, M.: Analysis of the initial and modified versions of the candidate 3GPP integrity algorithm 128-EIA3. In: Miri, A., Vaudenay, S. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 7118, pp. 230–242. Springer (2011) · Zbl 1292.94064
[18] Gilbert, E.N., MacWilliams, F.J., Sloane, N.J.A.: Codes which detect deception. Bell Syst. Tech. J. 53, 405–424 (1974) · Zbl 0275.94006 · doi:10.1002/j.1538-7305.1974.tb02751.x
[19] Gligor, V.D., Donescu, P.: Fast encryption and authentication: XCBC encryption and XECB authentication modes. In: Matsui, M. (ed.) FSE. Lecture Notes in Computer Science, vol. 2355, pp. 92–108. Springer (2001) · Zbl 1073.68629
[20] Halevi, S., Krawczyk, H.: MMH: software message authentication in the Gbit/second rates. In: Biham, E. (ed.) Fast Software Encryption. Lecture Notes in Computer Science, vol. 1267, pp. 172–189. Springer (1997) · Zbl 1385.94039
[21] Iwata, T., Yasuda, K.: Hbs: a single-key mode of operation for deterministic authenticated encryption. In: Dunkelman, O. (ed.) FSE. Lecture Notes in Computer Science, vol. 5665, pp. 394–415. Springer (2009) · Zbl 1248.94074
[22] Jutla, C.S.: Encryption modes with almost free message integrity. In: Pfitzmann, B. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 2045, pp. 529–544. Springer (2001) · Zbl 0981.94036
[23] Katz, J., Yung, M.: Complete characterization of security notions for probabilistic private-key encryption. In: STOC, pp. 245–254 (2000) · Zbl 1296.94122
[24] Krovetz, T.D.: Software-Optimized Universal Hashing and Message Authentication. PhD thesis, University of California, Davis. http://fastcrypto.org/umac/umac_thesis.pdf (2000)
[25] McGrew, D.A., Viega, J.: The security and performance of the Galois/Counter Mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT. Lecture Notes in Computer Science, vol. 3348, pp. 343–355. Springer (2004) · Zbl 1113.94315
[26] Minematsu, K.: A short universal hash function from bit rotation, and applications to blockcipher modes. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec. Lecture Notes in Computer Science, vol. 8209, pp. 221–238. Springer (2013) · Zbl 1319.94080
[27] Muller, F.: Differential attacks against the Helix stream cipher. In: Roy, B.K. Meier, W. (eds.) Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004, Revised Papers. Lecture Notes in Computer Science, vol. 3017, pp. 94–108. Springer (2004) · Zbl 1079.68557
[28] Okamoto, T. (ed.): Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3–7, 2000, Proceedings of Lecture Notes in Computer Science, vol. 1976. Springer (2000) · Zbl 0952.00064
[29] Rabin, M.O., Winograd, S.: Fast evaluation of polynomials by rational preparation. Commun. Pur. Appl. Math. 25, 433–458 (1972) · Zbl 0238.12002 · doi:10.1002/cpa.3160250405
[30] Rogaway, P.: Authenticated-encryption with associated-data. In: Atluri, V. (ed.) ACM Conference on Computer and Communications Security, pp. 98–107. ACM (2002)
[31] Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 3329, pp. 16–31. Springer (2004) · Zbl 1094.94035
[32] Rogaway, P.: Nonce-based symmetric encryption. In: Roy, B.K., Meier, W. (eds.) Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5–7, 2004, Revised Papers. Lecture Notes in Computer Science, vol. 3017, pp. 348–359. Springer (2004) · Zbl 1079.68559
[33] Rogaway, P., Bellare, M., Black, J.: OCB: a block-cipher mode of operation for efficient authenticated encryption. ACM Trans. Inf. Syst. Secur. 6(3), 365–403 (2003) · Zbl 05453902 · doi:10.1145/937527.937529
[34] Rogaway, P., Coppersmith, D.: A software-optimised encryption algorithm. In: Anderson, R.J. (ed.) FSE. Lecture Notes in Computer Science, vol. 809, pp. 56–63. Springer (1993) · Zbl 0943.94519
[35] Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4004, pp. 373–390. Springer (2006) · Zbl 1140.94369
[36] Roy, B.K., Meier, W. (ed.): Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5–7, 2004, Revised Papers. Lecture Notes in Computer Science, vol. 3017. Springer (2004) · Zbl 1051.68023
[37] Sarkar, P.: A new multi-linear hash family. Des. Codes Crypt. 69(3), 351–367 (2013) · Zbl 1274.94111
[38] Sarkar, P.: A general mixing strategy for the ECB-Mix-ECB mode of operation. Inf. Process. Lett. 109(2), 121–123 (2008) · Zbl 1191.68286 · doi:10.1016/j.ipl.2008.09.012
[39] Sarkar, P.: Efficient tweakable enciphering schemes from (block-wise) universal hash functions. IEEE Trans. Inf. Theory 55(10), 4749–4759 (2009) · Zbl 1367.94343 · doi:10.1109/TIT.2009.2027487
[40] Sarkar, P.: Pseudo-random functions and parallelizable modes of operations of a block cipher. IEEE Trans. Inf. Theory 56(8), 4025–4037 (2010) · Zbl 1366.94565 · doi:10.1109/TIT.2010.2050921
[41] Sarkar, P.: A simple generic construction of authenticated encryption with associated data. ACM Trans. Inf. Syst. Secur. 13(4), 33 (2010) · Zbl 05889880 · doi:10.1145/1880022.1880027
[42] Sarkar, P.: A trade-off between collision probability and key size in universal hashing using polynomials. Des. Codes Cryptogr. 58(3), 271–278 (2011) · Zbl 1215.68098 · doi:10.1007/s10623-010-9408-6
[43] Shoup, V.: On fast and provably secure message authentication based on universal hashing. In: Koblitz, N. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 1109, pp. 313–328. Springer (1996) · Zbl 1329.94087
[44] Stinson, D.R.: Universal hashing and authentication codes. Des. Codes Cryptogr. 4(4), 369–380 (1994) · Zbl 0812.94011 · doi:10.1007/BF01388651
[45] Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981) · Zbl 0461.68074 · doi:10.1016/0022-0000(81)90033-7
[46] Winograd, S.: A new algorithm for inner product. IEEE Trans. Comput. 17, 693–694 (1968) · Zbl 0174.46703 · doi:10.1109/TC.1968.227420
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.