Forkcipher: a new primitive for authenticated encryption of very short messages. (English) Zbl 1455.94111
Galbraith, Steven D. (ed.) et al., Advances in cryptology – ASIACRYPT 2019. 25th international conference on the theory and application of cryptology and information security, Kobe, Japan, December 8–12, 2019. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 11922, 153-182 (2019).
Summary: Highly efficient encryption and authentication of short messages is an essential requirement for enabling security in constrained scenarios such as the CAN FD in automotive systems (max. message size 64 bytes), massive IoT, critical communication domains of 5G, and Narrowband IoT, to mention a few. In addition, one of the NIST lightweight cryptography project requirements is that AEAD schemes shall be “optimized to be efficient for short messages (e.g., as short as 8 bytes)”.
In this work we introduce and formalize a novel primitive in symmetric cryptography called forkcipher. A forkcipher is a keyed primitive expanding a fixed-lenght input to a fixed-length output. We define its security as indistinguishability under a chosen ciphertext attack (for \(n\)-bit inputs to \(2n\)-bit outputs). We give a generic construction validation via the new iterate-fork-iterate design paradigm.
We then propose ForkSkinny as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight cipher following the TWEAKEY framework. We conduct extensive cryptanalysis of ForkSkinny against classical and structure-specific attacks.
We demonstrate the applicability of forkciphers by designing three new provably-secure nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominantly short messages, while at the same time allowing handling arbitrary messages sizes.
Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of ForkSkinny we achieve the best performance when directly compared with the most efficient mode instantiated with SKINNY.
For the entire collection see [Zbl 1428.94009].
In this work we introduce and formalize a novel primitive in symmetric cryptography called forkcipher. A forkcipher is a keyed primitive expanding a fixed-lenght input to a fixed-length output. We define its security as indistinguishability under a chosen ciphertext attack (for \(n\)-bit inputs to \(2n\)-bit outputs). We give a generic construction validation via the new iterate-fork-iterate design paradigm.
We then propose ForkSkinny as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight cipher following the TWEAKEY framework. We conduct extensive cryptanalysis of ForkSkinny against classical and structure-specific attacks.
We demonstrate the applicability of forkciphers by designing three new provably-secure nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominantly short messages, while at the same time allowing handling arbitrary messages sizes.
Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of ForkSkinny we achieve the best performance when directly compared with the most efficient mode instantiated with SKINNY.
For the entire collection see [Zbl 1428.94009].
Keywords:
authenticated encryption; new primitive; forkcipher; ForkSkinny; lightweight cryptography; short messagesReferences:
| [1] | 3GPP TS 22.261: Service requirements for next generation new services and markets. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3107 |
| [2] | 3GPP TS 36.213: Evolved Universal Terrestrial Radio Access (E-UTRA); Physical layer procedures. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2427 |
| [3] | CAN FD Standards and Recommendations. https://www.can-cia.org/news/cia-in-action/view/can-fd-standards-and-recommendations/2016/9/30/ |
| [4] | ISO 11898-1:2015: Road vehicles - Controller area network (CAN) - Part 1: Data link layer and physical signalling. https://www.iso.org/standard/63648.html |
| [5] | NB-IoT: Enabling New Business Opportunities. http://www.huawei.com/minisite/iot/img/nb_iot_whitepaper_en.pdf |
| [6] | Specification of Secure Onboard Communication. https://www.autosar.org/fileadmin/user_upload/standards/classic/4-3/AUTOSAR_SWS_SecureOnboardCommunication.pdf |
| [7] | Abdelkhalek, A., Sasaki, Y., Todo, Y., Tolba, M., Youssef, A.M.: MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99-129 (2017) |
| [8] | Anderson, E.; Beaver, C.; Draelos, T.; Schroeppel, R.; Torgerson, M.; Wang, H.; Pieprzyk, J.; Varadharajan, V., ManTiCore: encryption with joint cipher-state authentication, Information Security and Privacy, 440-453, 2004, Heidelberg: Springer, Heidelberg · Zbl 1098.94610 · doi:10.1007/978-3-540-27800-9_38 |
| [9] | Andreeva, E., et al.: COLM v1 (2014). https://competitions.cr.yp.to/round3/colmv1.pdf |
| [10] | Andreeva, E., Lallemand, V., Purnal, A., Reyhanitabar, R., Roy, A., Vizar, D.: Forkcipher: a new primitive for authenticated encryption of very short messages. Cryptology ePrint Archive, Report 2019/1004 (2019). https://eprint.iacr.org/2019/1004 |
| [11] | Andreeva, E.; Neven, G.; Preneel, B.; Shrimpton, T.; Kurosawa, K., Seven-property-preserving iterated hashing: ROX, Advances in Cryptology - ASIACRYPT 2007, 130-146, 2007, Heidelberg: Springer, Heidelberg · Zbl 1153.94342 · doi:10.1007/978-3-540-76900-2_8 |
| [12] | Ankele, R.; Banik, S.; Chakraborti, A.; List, E.; Mendel, F.; Sim, SM; Wang, G.; Gollmann, D.; Miyaji, A.; Kikuchi, H., Related-key impossible-differential attack on reduced-round Skinny, Applied Cryptography and Network Security, 208-228, 2017, Cham: Springer, Cham · Zbl 1521.94024 · doi:10.1007/978-3-319-61204-1_11 |
| [13] | Ankele, R.; Kölbl, S.; Cid, C.; Jacobson, M. Jr, Mind the gap - a closer look at the security of block ciphers against differential cryptanalysis, Selected Areas in Cryptography - SAC 2018, 163-190, 2018, Cham: Springer, Cham · Zbl 1447.94017 · doi:10.1007/978-3-030-10970-7_8 |
| [14] | Aumasson, J.P., et al.: CHAE: challenges in authenticated encryption. ECRYPT-CSA D1.1, Revision 1.05, 1 March 2017 |
| [15] | Avanzi, R.: Method and apparatus to encrypt plaintext data. US patent 9294266B2 (2013). https://patents.google.com/patent/US9294266B2/ |
| [16] | Banik, S.; Iwata, T.; Cheon, JH, Midori: a block cipher for low energy, Advances in Cryptology - ASIACRYPT 2015, 411-436, 2015, Heidelberg: Springer, Heidelberg · Zbl 1382.94057 · doi:10.1007/978-3-662-48800-3_17 |
| [17] | Banik, S., et al.: Cryptanalysis of forkaes. Cryptology ePrint Archive, Report 2019/289 (2019). https://eprint.iacr.org/2019/289 |
| [18] | Beierle, C.; Robshaw, M.; Katz, J., The SKINNY family of block ciphers and its low-latency variant MANTIS, Advances in Cryptology - CRYPTO 2016, 123-153, 2016, Heidelberg: Springer, Heidelberg · Zbl 1372.94412 · doi:10.1007/978-3-662-53008-5_5 |
| [19] | Beierle, C., et al.: Skinny-AEAD and Skinny-Hash. NIST LWC Candidate (2019) |
| [20] | Bellare, M.; Okamoto, E.; Davida, G.; Mambo, M., Practice-oriented provable-security, Information Security, 221-231, 1998, Heidelberg: Springer, Heidelberg · Zbl 0928.68043 · doi:10.1007/BFb0030423 |
| [21] | Bellare, M., Goldreich, O., Mityagin, A.: The power of verification queries in message authentication and authenticated encryption. IACR Cryptology ePrint Archive 2004, 309 (2004) |
| [22] | Bellare, M.; Kohno, T.; Namprempre, C., Breaking and provably repairing the SSH authenticated encryption scheme: a case study of the encode-then-encrypt-and-mac paradigm, ACM Trans. Inf. Syst. Secur., 7, 2, 206-241, 2004 · Zbl 1291.94056 · doi:10.1145/996943.996945 |
| [23] | Bellare, M.; Namprempre, C.; Okamoto, T., Authenticated encryption: relations among notions and analysis of the generic composition paradigm, Advances in Cryptology — ASIACRYPT 2000, 531-545, 2000, Heidelberg: Springer, Heidelberg · Zbl 0973.68059 · doi:10.1007/3-540-44448-3_41 |
| [24] | Bellare, M.; Ristenpart, T.; Lai, X.; Chen, K., Multi-property-preserving hash domain extension and the EMD transform, Advances in Cryptology - ASIACRYPT 2006, 299-314, 2006, Heidelberg: Springer, Heidelberg · Zbl 1172.94561 · doi:10.1007/11935230_20 |
| [25] | Bellare, M.; Rogaway, P.; Okamoto, T., Encode-then-encipher encryption: how to exploit nonces or redundancy in plaintexts for efficient cryptography, Advances in Cryptology — ASIACRYPT 2000, 317-330, 2000, Heidelberg: Springer, Heidelberg · Zbl 0974.94008 · doi:10.1007/3-540-44448-3_24 |
| [26] | Bernstein, D.J.: Cryptographic competitions: CAESAR. http://competitions.cr.yp.to |
| [27] | Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Farfalle: parallel permutation-based cryptography. IACR Transactions on Symmetric Cryptology 2017, (2017). https://tosc.iacr.org/index.php/ToSC/article/view/855 |
| [28] | Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., 4, 1, 3-72, 1991 · Zbl 0729.68017 · doi:10.1007/BF00630563 |
| [29] | Borghoff, J.; Wang, X.; Sako, K., PRINCE - a low-latency block cipher for pervasive computing applications, Advances in Cryptology - ASIACRYPT 2012, 208-225, 2012, Heidelberg: Springer, Heidelberg · Zbl 1292.94035 · doi:10.1007/978-3-642-34961-4_14 |
| [30] | Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: ASCON v1.2 (2014). https://competitions.cr.yp.to/round3/asconv12.pdf |
| [31] | Hoang, VT; Krovetz, T.; Rogaway, P.; Oswald, E.; Fischlin, M., Robust authenticated-encryption AEZ and the problem that it solves, Advances in Cryptology - EUROCRYPT 2015, 15-44, 2015, Heidelberg: Springer, Heidelberg · Zbl 1365.94485 · doi:10.1007/978-3-662-46800-5_2 |
| [32] | Jean, J., Nikolić, I., Peyrin, T., Seurin, Y.: Deoxys v1.41 v1 (2016). https://competitions.cr.yp.to/round3/deoxysv141.pdf |
| [33] | Jean, J.; Nikolić, I.; Peyrin, T.; Sarkar, P.; Iwata, T., Tweaks and keys for block ciphers: the TWEAKEY framework, Advances in Cryptology - ASIACRYPT 2014, 274-288, 2014, Heidelberg: Springer, Heidelberg · Zbl 1317.94113 · doi:10.1007/978-3-662-45608-8_15 |
| [34] | Katz, J.; Yung, M.; Goos, G.; Hartmanis, J.; van Leeuwen, J.; Schneier, B., Unforgeable encryption and chosen ciphertext secure modes of operation, Fast Software Encryption, 284-299, 2001, Heidelberg: Springer, Heidelberg · Zbl 0994.68629 · doi:10.1007/3-540-44706-7_20 |
| [35] | Kranz, T., Leander, G., Wiemer, F.: Linear cryptanalysis: key schedules and tweakable block ciphers. IACR Trans. Symmetric Cryptol. 2017(1), 474-505 (2017) |
| [36] | Krovetz, T., Rogaway, P.: OCB v1.1 (2014). https://competitions.cr.yp.to/round3/ocbv11.pdf |
| [37] | Krovetz, T.; Rogaway, P.; Joux, A., The software performance of authenticated-encryption modes, Fast Software Encryption, 306-327, 2011, Heidelberg: Springer, Heidelberg · Zbl 1307.94119 · doi:10.1007/978-3-642-21702-9_18 |
| [38] | Liskov, M.; Rivest, RL; Wagner, D.; Yung, M., Tweakable block ciphers, Advances in Cryptology — CRYPTO 2002, 31-46, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94533 · doi:10.1007/3-540-45708-9_3 |
| [39] | Matsui, M.; Helleseth, T., Linear cryptanalysis method for DES cipher, Advances in Cryptology — EUROCRYPT 1993, 386-397, 1994, Heidelberg: Springer, Heidelberg · Zbl 0951.94519 · doi:10.1007/3-540-48285-7_33 |
| [40] | McGrew, DA; Viega, J.; Canteaut, A.; Viswanathan, K., The security and performance of the Galois/Counter Mode (GCM) of operation, Progress in Cryptology - INDOCRYPT 2004, 343-355, 2004, Heidelberg: Springer, Heidelberg · Zbl 1113.94315 · doi:10.1007/978-3-540-30556-9_27 |
| [41] | Namprempre, C.; Rogaway, P.; Shrimpton, T.; Nguyen, PQ; Oswald, E., Reconsidering generic composition, Advances in Cryptology - EUROCRYPT 2014, 257-274, 2014, Heidelberg: Springer, Heidelberg · Zbl 1332.94092 · doi:10.1007/978-3-642-55220-5_15 |
| [42] | NIST: DRAFT Submission Requirements and Evaluation Criteria for the Lightweight Cryptography Standardization Process (2018). https://csrc.nist.gov/Projects/Lightweight-Cryptography |
| [43] | Paterson, K.G., Yau, A.K.L.: Cryptography in theory and practice: the case of encryption in ipsec. IACR Cryptology ePrint Archive 2005, 416 (2005). http://eprint.iacr.org/2005/416 |
| [44] | Paterson, KG; Yau, AKL; Vaudenay, S., Cryptography in theory and practice: the case of encryption in IPsec, Advances in Cryptology - EUROCRYPT 2006, 12-29, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94034 · doi:10.1007/11761679_2 |
| [45] | Reyhanitabar, MR; Susilo, W.; Mu, Y.; Boyd, C.; González Nieto, J., Analysis of property-preservation capabilities of the ROX and ESh hash domain extenders, Information Security and Privacy, 153-170, 2009, Heidelberg: Springer, Heidelberg · Zbl 1284.94104 · doi:10.1007/978-3-642-02620-1_11 |
| [46] | Rogaway, P., Authenticated-encryption with associated-data, ACM CCS, 2002, 98-107, 2002 |
| [47] | Rogaway, P., Practice-oriented provable security and the social construction of cryptography, IEEE Secur. Priv., 14, 6, 10-17, 2016 · doi:10.1109/MSP.2016.122 |
| [48] | Rogaway, P.; Shrimpton, T.; Vaudenay, S., A provable-security treatment of the key-wrap problem, Advances in Cryptology - EUROCRYPT 2006, 373-390, 2006, Heidelberg: Springer, Heidelberg · Zbl 1140.94369 · doi:10.1007/11761679_23 |
| [49] | Sadeghi, S.; Mohammadi, T.; Bagheri, N., Cryptanalysis of reduced round SKINNY block cipher, IACR Trans. Symmetric Cryptol., 2018, 3, 124-162, 2018 |
| [50] | Sui, H.; Wu, W.; Zhang, L.; Wang, P.; Qing, S.; Zhou, J.; Liu, D., Attacking and fixing the CS mode, Information and Communications Security, 318-330, 2013, Cham: Springer, Cham · Zbl 1346.94125 · doi:10.1007/978-3-319-02726-5_23 |
| [51] | Tolba, M.; Abdelkhalek, A.; Youssef, AM; Joye, M.; Nitaj, A., Impossible differential cryptanalysis of reduced-round SKINNY, Progress in Cryptology - AFRICACRYPT 2017, 117-134, 2017, Cham: Springer, Cham · Zbl 1408.94969 · doi:10.1007/978-3-319-57339-7_7 |
| [52] | Whiting, D., Housley, R., Ferguson, N.: Counter with CBC-MAC (CCM). IETF RFC 3610 (Informational), September 2003. http://www.ietf.org/rfc/rfc3610.txt |
| [53] | Wu, H.: ACORN v3 (2014). https://competitions.cr.yp.to/round3/acornv3.pdf |
| [54] | Wu, H., Huang, T.: MORUS v2 (2014). https://competitions.cr.yp.to/round3/morusv2.pdf |
| [55] | Wu, H., Preneel, B.: AEGIS v1.1 (2014). https://competitions.cr.yp.to/round3/aegisv11.pdf |
| [56] | Zhang, P.; Zhang, W., Differential cryptanalysis on block cipher skinny with MILP program, Secur. Commun. Netw., 2018, 3780407:1-3780407:11, 2018 |
| [57] | Zhang, W.; Rijmen, V., Division cryptanalysis of block ciphers with a binary diffusion layer, IET Inf. Secur., 13, 2, 87-95, 2019 · doi:10.1049/iet-ifs.2018.5151 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
