×

The Oribatida v1.3 family of lightweight authenticated encryption schemes. (English) Zbl 1468.94393

Summary: Permutation-based modes have been established for lightweight authenticated encryption, as can be seen from the high interest in the ongoing NIST lightweight competition. However, their security is upper bounded by \(O( \sigma^2/2^c )\) bits, where \(\sigma\) are the number of calls and \(c\) is the hidden capacity of the state. The development of more schemes that provide higher security bounds led to the in [A. Chakraborti et al., “ Beetle family of lightweight and secure authenticated encryption ciphers”, IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018, No. 2, 218–241 (2018; doi:10.13154/tches.v2018.i2.218-241 )] proposal Beetle that raised the bound to \(O(r \sigma /2^c)\), where \(r\) is the public rate of the state. While authenticated encryption can be performed in an on-line manner, authenticated decryption assumes that the resulting plaintext is buffered and never released if the corresponding tag is incorrect. Since lightweight devices may lack the resources for buffering, additional robustness guarantees, such as integrity under release of unverified plaintexts (Int-RUP), are desirable. In this stronger setting, the security of the established schemes, including Beetle, is limited by \(O(q_p q_d/2^c)\), where \(q_d\) is the maximal number of decryption queries, and \(q_p\) that of off-line primitive queries, which motivates novel approaches. This work proposes Oribatida, a permutation-based AE scheme that derives \(s\)-bit masks from previous permutation outputs to mask ciphertext blocks. Oribatida can provide a security bound of \(O( r \sigma^2/2^{c+s})\), which allows smaller permutations for the same level of security. It provides a security level dominated by \(O(\sigma_d^2/2^c)\) under Int-RUP adversaries, which eliminates the dependency on primitive queries. We prove its security under nonce-respecting and Int-RUP adversaries. We show that our Int-RUP bound is tight and show general attacks on previous constructions.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
11T06 Polynomials over finite fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity

Software:

SIMECK; SPECK; SIMON
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] M. A. Abdelraheem, J. Alizadeh, H. AlKhzaimi, M. R. Aref, N. Bagheri, P. Gauravaram, and M. M. Lauridsen. Improved Linear Cryptanalysis of Round Reduced SIMON. IACR Cryptology ePrint Archive, 2014:681, 2014.
[2] M. A. Abdelraheem, J. Alizadeh, H. A. AlKhzaimi, M. R. Aref, N. Bagheri, and P. Gauravaram. Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48. In A. Biryukov and V. Goyal, editors, INDOCRYPT, volume 9462 of LNCS, pages 153-179. Springer, 2015. · Zbl 1377.94024
[3] F. Abed, E. List, S. Lucks, and J. Wenzel. Differential Cryptanalysis of Round-Reduced Simon and Speck. In C. Cid and C. Rechberger, editors, FSE, volume 8540 of LNCS, pages 525-545. Springer, 2014.
[4] J. Alizadeh, N. Bagheri, P. Gauravaram, A. Kumar, and S. K. Sanadhya. Linear Cryptanalysis of Round Reduced SIMON. IACR Cryptology ePrint Archive, 2013:663, 2013.
[5] R. AlTawy, G. Gong, M. He, A. Jha, K. Mandal, M. Nandi, and R. Rohit. SpoC: An Authenticated Cipher. Technical report, Feb 24 2019. First-round submission to the NIST Lightweight Cryptography Competition. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/spoc-spec.pdf.
[6] E. Andreeva, B. Bilgin, A. Bogdanov, A. Luykx, B. Mennink, N. Mouha, and K. Yasuda. APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography. In C. Cid and C. Rechberger, editors, FSE, volume 8540 of LNCS, pages 168-186. Springer, 2014. · Zbl 1382.94044
[7] E. Andreeva, A. Bogdanov, A. Luykx, B. Mennink, N. Mouha, and K. Yasuda. How to Securely Release Unverified Plaintext in Authenticated Encryption. In P. Sarkar and T. Iwata, editors, ASIACRYPT I, volume 8873 of LNCS, pages 105-125. Springer, 2014. · Zbl 1306.94021
[8] E. Andreeva, J. Daemen, B. Mennink, and G. V. Assche. Security of Keyed Sponge Constructions Using a Modular Proof Approach. In G. Leander, editor, FSE, volume 9054 of LNCS, pages 364-384. Springer, 2015. · Zbl 1382.94045
[9] J. Aumasson, P. Jovanovic, and S. Neves. NORX: Parallel and Scalable AEAD. In M. Kutylowski and J. Vaidya, editors, ESORICS II, volume 8713 of LNCS, pages 19-36. Springer, 2014. · Zbl 1443.94088
[10] R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, and L. Wingers. The SIMON and SPECK Families of Lightweight Block Ciphers. IACR Cryptology ePrint Archive, 2013:404, 2013.
[11] M. Bellare, A. Boldyreva, L. R. Knudsen, and C. Namprempre. Online Ciphers and the Hash-CBC Construction. In J. Kilian, editor, CRYPTO, volume 2139 of LNCS, pages 292-309. Springer, 2001. · Zbl 1002.94520
[12] M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Eflcient Protocols. In D. E. Denning, R. Pyle, R. Ganesan, R. S. Sandhu, and V. Ashby, editors, ACM CCS, pages 62-73. ACM, 1993.
[13] G. Bertoni, J. Daemen, S. Hoffert, M. Peeters, G. V. Assche, and R. V. Keer. Farfalle: parallel permutation-based cryptography. IACR Trans. Symmetric Cryptol., 2017(4):1-38, 2017.
[14] G. Bertoni, J. Daemen, M. Peeters, and G. V. Assche. On the Indifferentiability of the Sponge Construction. In N. P. Smart, editor, EUROCRYPT, volume 4965 of LNCS, pages 181-197. Springer, 2008. · Zbl 1149.94304
[15] G. Bertoni, J. Daemen, M. Peeters, and G. V. Assche. Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications. In A. Miri and S. Vaudenay, editors, SAC, volume 7118 of LNCS, pages 320-337. Springer, 2011. · Zbl 1292.94030
[16] G. Bertoni, J. Daemen, M. Peeters, and G. V. Assche. Permutation-based encryption, authentication and authenticated encryption. Directions in Authenticated Ciphers, 2012.
[17] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. Sponge functions. In ECRYPT hash workshop, volume 2007, 2007.
[18] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. On the security of the keyed sponge construction. In SHA-3 competition (round 3), volume 2011, 2011.
[19] G. Bertoni, J. Daemen, M. Peeters, G. van Assche, and R. van Keer. Ketje v2. 2016. Submission to the CAESAR competition http://competitions.cr.yp.to/caesar-submissions.html.
[20] G. Bertoni, J. Daemen, M. Peeters, G. van Assche, and R. van Keer. Keyak v2. 2016. Submission to the CAESAR competition http://competitions.cr.yp.to/caesar-submissions.html.
[21] A. Bhattacharjee, E. List, C. M. López, and M. Nandi. The Oribatida Family of Lightweight Authenticated Encryption Schemes Version v1.2. Technical report, Sep 27 2019. Second-round submission to the NIST Lightweight Cryptography Competition. https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/oribatida-spec-round2.pdf.
[22] A. Biryukov, A. Roy, and V. Velichkov. Differential Analysis of Block Ciphers SIMON and SPECK. In C. Cid and C. Rechberger, editors, FSE, volume 8540 of LNCS, pages 546-570. Springer, 2014.
[23] J. Black and P. Rogaway. A Block-Cipher Mode of Operation for Parallelizable Message Authentication. In L. R. Knudsen, editor, EUROCRYPT, volume 2332 of LNCS, pages 384-397. Springer, 2002. · Zbl 1056.94520
[24] A. Chakraborti, N. Datta, A. Jha, C. M. Lopez, M. Nandi, and Y. Sasaki. LOTUS-AEAD and LOCUS-AEAD. Technical report, Feb 26 2019. First-round submission to the NIST Lightweight Cryptography Competition. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/lotus-aead-and-locus-aead-spec.pdf.
[25] A. Chakraborti, N. Datta, M. Nandi, and K. Yasuda. Beetle Family of Lightweight and Secure Authenticated Encryption Ciphers. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(2):218-241, 2018. Updated version at https://eprint.iacr.org/2018/805.
[26] A. Chakraborti, N. Datta, M. Nandi, and K. Yasuda. Beetle Family of Lightweight and Secure Authenticated Encryption Ciphers. http://eprint.iacr.org/2018/805, 2018.
[27] A. Chakraborti, A. Jha, C. M. Lopez, M. Nandi, and Y. Sasaki. ESTATE. Technical report, Mar 29 2019. First-round submission to the NIST Lightweight Cryptography Competition. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/spoc-spec.pdf.
[28] D. Chang, M. Dworkin, S. Hong, J. Kelsey, and M. Nandi. A Keyed Sponge Construction with Pseudorandomness in the Standard Model. In The Third SHA-3 Candidate Conference, volume 3, page 7, March 2012.
[29] H. Chen and X. Wang. Improved Linear Hull Attack on Round-Reduced Simon with Dynamic Key-Guessing Techniques. In T. Peyrin, editor, FSE, volume 9783 of LNCS, pages 428-449. Springer, 2016. · Zbl 1387.94073
[30] S. Chen and J. P. Steinberger. Tight Security Bounds for Key-Alternating Ciphers. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT, volume 8441 of LNCS, pages 327-350. Springer, 2014. Full version at https://eprint.iacr.org/2013/222. · Zbl 1317.94096
[31] J. Coron, Y. Dodis, A. Mandal, and Y. Seurin. A Domain Extender for the Ideal Cipher. In D. Micciancio, editor, TCC, volume 5978 of LNCS, pages 273-289. Springer, 2010. Full version at https://eprint.iacr.org/2009/356. · Zbl 1274.94054
[32] J. Daemen, B. Mennink, and G. V. Assche. Full-State Keyed Duplex with Built-In Multi-user Support. In T. Takagi and T. Peyrin, editors, ASIACRYPT II, volume 10625 of LNCS, pages 606-637. Springer, 2017. · Zbl 1417.94055
[33] I. Dinur, O. Dunkelman, M. Gutman, and A. Shamir. Improved Top-Down Techniques in Differential Cryptanalysis. In K. E. Lauter and F. Rodríguez-Henríquez, editors, LATINCRYPT, volume 9230 of LNCS, pages 139-156. Springer, 2015. · Zbl 1370.94505
[34] C. Dobraunig, M. Eichlseder, F. Mendel, and M. Schläffer. Ascon v1.2 Submission to the CAESAR Competition. September 15 2016. Submission to the CAESAR competition. http://competitions.cr.yp.to/caesar-submissions.html.
[35] C. Dobraunig and B. Mennink. Security of the Suflx Keyed Sponge. IACR Trans. Symmetric Cryptol., 2019(4):223-248, 2019.
[36] M. Dworkin. FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. Technical report, 2015.
[37] P. Gaži, K. Pietrzak, and S. Tessaro. The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC. In R. Gennaro and M. Robshaw, editors, CRYPTO I, volume 9215 of LNCS, pages 368-387. Springer, 2015. · Zbl 1375.94127
[38] S. Halevi. EME*: Extending EME to Handle Arbitrary-Length Messages with Associated Data. In A. Canteaut and K. Viswanathan, editors, INDOCRYPT, volume 3348 of LNCS, pages 315-327. Springer, 2004. · Zbl 1113.94310
[39] V. T. Hoang, T. Krovetz, and P. Rogaway. Robust Authenticated-Encryption AEZ and the Problem That It Solves. In E. Oswald and M. Fischlin, editors, EUROCRYPT (1), volume 9056 of LNCS, pages 15-44. Springer, 2015. Full version at https://eprint.iacr.org/2014/793. · Zbl 1365.94485
[40] ISO/IEC. Information technology - Automatic identification and data capture techniques - Part 21: Crypto Suite SIMON Security Services for Air Interface Communications. https://www.iso.org/standard/70388.html, Oct 2018.
[41] P. Jovanovic, A. Luykx, and B. Mennink. Beyond 2^c/2 Security in Sponge-Based Authenticated Encryption Modes. In P. Sarkar and T. Iwata, editors, ASIACRYPT I, volume 8873 of LNCS, pages 85-104. Springer, 2014. · Zbl 1306.94065
[42] S. Kölbl, G. Leander, and T. Tiessen. Observations on the SIMON Block Cipher Family. In R. Gennaro and M. Robshaw, editors, CRYPTO, volume 9215 of LNCS, pages 161-185. Springer, 2015. · Zbl 1369.94546
[43] K. Kondo, Y. Sasaki, Y. Todo, and T. Iwata. On the Design Rationale of SIMON Block Cipher: Integral Attacks and Impossible Differential Attacks against SIMON Variants. IEICE Transactions, 101-A(1):88-98, 2018.
[44] Z. Liu, Y. Li, and M. Wang. Optimal Differential Trails in SIMON-like Ciphers. IACR Trans. Symmetric Cryptol., 2017(1):358-379, 2017.
[45] Z. Liu, Y. Li, and M. Wang. The Security of SIMON-like Ciphers Against Linear Cryptanalysis. IACR Cryptology ePrint Archive, 2017:576, 2017.
[46] M. Matsui. On Correlation Between the Order of S-boxes and the Strength of DES. In A. D. Santis, editor, EUROCRYPT, volume 950 of LNCS, pages 366-375. Springer, 1994.
[47] U. M. Maurer, R. Renner, and C. Holenstein. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In M. Naor, editor, TCC, volume 2951 of LNCS, pages 21-39. Springer, 2004. · Zbl 1197.94196
[48] B. Mennink. Key Prediction Security of Keyed Sponges. IACR Trans. Symmetric Cryptol., 2018(4):128-149, 2018.
[49] B. Mennink, R. Reyhanitabar, and D. Vizár. Security of full-state keyed sponge and duplex: Applications to authenticated encryption. In T. Iwata and J. H. Cheon, editors, ASIACRYPT II, volume 9453 of LNCS, pages 465-489. Springer, 2015. · Zbl 1382.94142
[50] K. Minematsu. Parallelizable Rate-1 Authenticated Encryption from Pseudorandom Functions. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT, volume 8441 of LNCS, pages 275-292. Springer, 2014. Full version at https://eprint.iacr.org/2013/628.pdf. · Zbl 1332.94091
[51] N. Mouha, B. Mennink, A. V. Herrewege, D. Watanabe, B. Preneel, and I. Verbauwhede. Chaskey: An Eflcient MAC Algorithm for 32-bit Microcontrollers. In A. Joux and A. M. Youssef, editors, SAC, volume 8781 of LNCS, pages 306-323. Springer, 2014. · Zbl 1382.94145
[52] Y. Naito and K. Yasuda. New Bounds for Keyed Sponges with Extendable Output: Independence Between Capacity and Message Length. In T. Peyrin, editor, FSE, volume 9783 of LNCS, pages 3-22. Springer, 2016. · Zbl 1387.94094
[53] NIST. Submission Requirements and Evaluation Criteria for the Lightweight Cryptography Standardization Process. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/final-lwc-submission-requirements-august2018.pdf, August 27 2018.
[54] J. Patarin. The “Coeflcients H” Technique. In R. M. Avanzi, L. Keliher, and F. Sica, editors, SAC, volume 5381 of LNCS, pages 328-345. Springer, 2008.
[55] H. Raddum. Algebraic Analysis of the Simon Block Cipher Family. In K. E. Lauter and F. Rodríguez-Henríquez, editors, LATINCRYPT, volume 9230 of LNCS, pages 157-169. Springer, 2015. · Zbl 1370.94540
[56] P. Rogaway, M. Bellare, J. Black, and T. Krovetz. OCB: a block-cipher mode of operation for eflcient authenticated encryption. In M. K. Reiter and P. Samarati, editors, ACM-CCS, pages 196-205. ACM, 2001.
[57] P. Rogaway and T. Shrimpton. A Provable-Security Treatment of the Key-Wrap Problem. In S. Vaudenay, editor, EUROCRYPT, volume 4004 of LNCS, pages 373-390. Springer, 2006. · Zbl 1140.94369
[58] R. Rohit and G. Gong. Correlated Sequence Attack on Reduced-Round Simon-32/64 and Simeck-32/64. IACR Cryptology ePrint Archive, 2018:699, 2018.
[59] R. Rohit and S. Sarkar. [lwc-forum] ROUND 2 OFFICIAL COMMENT: Oribatida. NIST lwc forum mailing list, 17 September 17:09 2019.
[60] C. E. Shannon. Communication theory of secrecy systems. The Bell system technical journal, 28(4):656-715, 1949. · Zbl 1200.94005
[61] H. Sui, W. Wu, L. Zhang, and D. Zhang. LAEM (Lightweight Authentication Encryption Mode). Technical report, Mar 25 2019. First-round submission to the NIST Lightweight Cryptography Competition. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/LAEM-spec.pdf.
[62] Y. Todo and M. Morii. Bit-Based Division Property and Application to Simon Family. In T. Peyrin, editor, FSE, volume 9783 of LNCS, pages 357-377. Springer, 2016. · Zbl 1387.94102
[63] X. Wang, B. Wu, L. Hou, and D. Lin. Automatic Search for Related-Key Differential Trails in SIMON-like Block Ciphers Based on MILP. In L. Chen, M. Manulis, and S. Schneider, editors, ISC, volume 11060 of LNCS, pages 116-131. Springer, 2018.
[64] Z. Xiang, W. Zhang, Z. Bao, and D. Lin. Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers. In J. H. Cheon and T. Takagi, editors, ASIACRYPT I, volume 10031 of LNCS, pages 648-678, 2016. · Zbl 1404.94120
[65] H. Zhang, W. Wu, and Y. Wang. Integral Attack Against Bit-Oriented Block Ciphers. In S. Kwon and A. Yun, editors, ICISC, volume 9558 of LNCS, pages 102-118. Springer, 2015. · Zbl 1384.94114
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.