Abstract
Many modes of operations for block ciphers or tweakable block ciphers do not require invertibility from their underlying primitive. In this work, we study fixed-length Tweakable Pseudorandom Function (TPRF) with large domain expansion, a novel primitive that can bring high security and significant performance optimizations in symmetric schemes, such as (authenticated) encryption.
Our first contribution is to introduce a new design paradigm, derived from the Iterate-Fork-Iterate construction, in order to build n-to-\(\alpha n\)-bit (\(\alpha \ge 2\)), n-bit secure, domain expanding TPRF. We dub this new generic composition masked Iterate-Fork-Iterate \(\textsf{mIFI}\). We then propose a concrete TPRF instantiation \(\textsf {ButterKnife} \) that expands an n-bit input to 8n-bit output via a public tweak and secret key. \(\textsf {ButterKnife} \) is built with high efficiency and security in mind. It is fully parallelizable and based on Deoxys-BC, the AES-based tweakable block cipher used in the authenticated encryption winner algorithm in the defense-in-depth category of the CAESAR competition. We analyze the resistance of ButterKnife to differential, linear, meet-in-the-middle, impossible differentials and rectangle attacks. A special care is taken to the attack scenarios made possible by the multiple branches.
Our next contribution is to design and provably analyze two new TPRF-based deterministic authenticated encryption (DAE) schemes called \(\textsf{SAFE}\) and \(\textsf{ZAFE}\) that are highly efficient, parallelizable, and offer \((n+\min (n,t))/2\) bits of security, where n, t denote respectively the input block and the tweak sizes of the underlying primitives. We further implement \(\textsf{SAFE}\) with \(\textsf {ButterKnife} \) to show that it achieves an encryption performance of 1.18 c/B for long messages on Skylake, which is \(24\%\) faster than the comparable Crypto’17 TBC-based \(\textsf{ZAE}\) DAE. Our second candidate \(\textsf{ZAFE}\), which uses the same authentication pass as \(\textsf{ZAE}\), offers a similar level of speedup. Besides, we show that \(\textsf {ButterKnife} \), when used in Counter Mode, is slightly faster than \(\textsf{AES}\) (0.55 c/B vs 0.63 c/B on Skylake).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Better probability estimates might be obtained with the sandwich technique [18].
- 2.
Taken from https://github.com/Shay-Gueron/AES-GCM-SIV (September 2021).
References
Advanced Encryption Standard (AES). National Institute of Standards and Technology, NIST FIPS PUB 197, U.S. Department of Commerce (2001)
Andreeva, E., Bhati, A.S., Preneel, B., Vizár, D.: 1, 2, 3, fork: counter mode variants based on a generalized forkcipher. IACR Trans. Symmetric Cryptol. 2021(3), 1–35 (2021)
Andreeva, E., Cogliati, B., Lallemand, V., Minier, M., Purnal, A., Roy, A.: Masked iterate-fork-iterate: a new design paradigm for tweakable expanding pseudorandom function. Cryptology ePrint Archive, Report 2022/1534 (2022). https://eprint.iacr.org/2022/1534
Andreeva, E., Lallemand, V., Purnal, A., Reyhanitabar, R., Roy, A., Vizár, D.: Forkcipher: a new primitive for authenticated encryption of very short messages. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 153–182. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34621-8_6
Andreeva, E., Reyhanitabar, R., Varici, K., Vizár, D.: Forking a blockcipher for authenticated encryption of very short messages. Cryptology ePrint Archive, Report 2018/916 (2018). https://eprint.iacr.org/2018/916
Andreeva, E., Weninger, A.: A forkcipher-based pseudo-random number generator. In: Tibouchi, M., Wang, X. (eds.) ACNS 2023, Part II. LNCS, vol. 13906, pp. 3–31. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33491-7_1
Banik, S., Bogdanov, A., Luykx, A., Tischhauser, E.: SUNDAE: small universal deterministic authenticated encryption for the internet of things. IACR Trans. Symm. Cryptol. 2018(3), 1–35 (2018)
Banik, S., et al.: Cryptanalysis of ForkAES. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 43–63. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-21568-2_3
Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5
Bhati, A.S., Dufka, A., Andreeva, E., Roy, A., Preneel, B.: Skye: A Fast KDF based on Expanding PRF and its Application to Signal. Cryptology ePrint Archive, Paper 2023/781 (2023). https://eprint.iacr.org/2023/781. (to appear in ACM ASIACCS)
Bhattacharya, S., Nandi, M.: Revisiting variable output length XOR pseudorandom function. IACR Trans. Symmetric Cryptol. 2018(1), 314–335 (2018)
Bogdanov, A., Lauridsen, M.M., Tischhauser, E.: Comb to pipeline: fast software encryption revisited. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 150–171. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_8
Chen, S., Steinberger, J.P.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_19
Cid, C., Huang, T., Peyrin, T., Sasaki, Y., Song, L.: A security analysis of Deoxys and its internal tweakable block ciphers. IACR Trans. Symm. Cryptol. 2017(3), 73–107 (2017)
Dai, W., Hoang, V.T., Tessaro, S.: Information-theoretic indistinguishability via the chi-squared method. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 497–523. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_17
Demirci, H., Selçuk, A.A.: A meet-in-the-middle attack on 8-round AES. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_7
Derbez, P., et al.: Cryptanalysis of AES-PRF and its dual. IACR Trans. Symm. Cryptol. 2018(2), 161–191 (2018)
Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 393–410. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_21
Dutta, A., Guo, J., List, E.: Forking sums of permutations for optimally secure and highly efficient PRFs. Cryptology ePrint Archive, Report 2022/1609 (2022). https://eprint.iacr.org/2022/1609
Gueron, S.: Intel’s new AES instructions for enhanced performance and security (invited talk). In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 51–66. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03317-9_4
Gueron, S., Kounavis, M.E.: Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode. Technical report, Intel Corporation (2014). https://software.intel.com/sites/default/files/managed/72/cc/clmul-wp-rev-2.02-2014-04-20.pdf
Gueron, S., Langley, A., Lindell, Y.: AES-GCM-SIV: specification and analysis. IACR Cryptol. ePrint Arch. 2017, 168 (2017)
Gueron, S., Langley, A., Lindell, Y.: AES-GCM-SIV: nonce misuse-resistant authenticated encryption. RFC 8452, pp. 1–42 (2019)
Gueron, S., Lindell, Y.: GCM-SIV: full nonce misuse-resistant authenticated encryption at under one cycle per byte. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 109–119. ACM Press (2015)
Housley, R.: Using advanced encryption standard (AES) CCM mode with IPsec encapsulating security payload (ESP). RFC, 4309 (2005)
Iwata, T., Minematsu, K.: Stronger security variants of GCM-SIV. IACR Trans. Symm. Cryptol. 2016(1), 134–157 (2016). https://tosc.iacr.org/index.php/ToSC/article/view/539
Iwata, T., Minematsu, K., Peyrin, T., Seurin, Y.: ZMAC: block cipher mode for highly secure message authentication. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 34–65. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-63697-9_2
Iwata, T., Seurin, Y.: Reconsidering the security bound of AES-GCM-SIV. IACR Trans. Symm. Cryptol. 2017(4), 240–267 (2017)
Jean, J., Nikolic, I., Peyrin, T.: Tweaks and keys for block ciphers: the TWEAKEY framework. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 274–288. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_15
Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: Deoxys v1. 41. Submitted to CAESAR (2016)
Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: Deoxys v1.43 (2018)
Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: The deoxys AEAD family. J. Cryptol. 34(3), 31 (2021)
Kelsey, J., Kohno, T., Schneier, B.: Amplified boomerang attacks against reduced-round MARS and Serpent. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 75–93. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_6
Kranz, T., Leander, G., Wiemer, F.: Linear cryptanalysis: key schedules and tweakable block ciphers. IACR Trans. Symm. Cryptol. 2017(1), 474–505 (2017)
Li, R., Jin, C.: Meet-in-the-middle attacks on round-reduced tweakable block cipher Deoxys-BC. IET Inf. Secur. 13(1), 70–75 (2019)
Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_3
List, E., Nandi, M.: Revisiting full-PRF-secure PMAC and using it for beyond-birthday authenticated encryption. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 258–274. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-52153-4_15
Liu, Y., Shi, B., Dawu, G., Zhao, F., Li, W., Liu, Z.: Improved meet-in-the-middle attacks on reduced-round Deoxys-BC-256. Comput. J. 63(12), 1859–1870 (2020)
McGrew, D.A., 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). https://doi.org/10.1007/978-3-540-30556-9_27
Mennink, B., Neves, S.: Optimal PRFs from blockcipher designs. IACR Trans. Symm. Cryptol. 2017(3), 228–252 (2017)
Moazami, F., Mehrdad, A., Soleimany, H.: Impossible differential cryptanalysis on Deoxys-BC-256. ISC Int. J. Inf. Secur. 10(2), 93–105 (2018)
Dworkin, M.: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D (2007)
Peyrin, T., Seurin, Y.: Counter-in-tweak: authenticated encryption modes for tweakable block ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 33–63. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_2
Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Reiter, M.K., Samarati, P. (eds.) ACM CCS 2001, pp. 196–205. ACM Press (2001)
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). https://doi.org/10.1007/11761679_23
Zhao, B., Dong, X., Jia, K.: New related-tweakey boomerang and rectangle attacks on Deoxys-BC including BDT effect. IACR Trans. Symm. Cryptol. 2019(3), 121–151 (2019)
Acknowledgments
Elena Andreeva was supported in part by the Austrian Science Fund (FWF) grant SpyCoDe with number 10.55776/F8507-N. Part of this work was written while Benoît Cogliati was affiliated with the CISPA Helmholtz Center for Information Security.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Details on ButterKnife
ButterKnife Constants. In ButterKnife the round constant RC[i] is the AES round constant in the ith round as defined below:
Existing Lower Bounds. The bounds are summarized in Table 5.
Reminder of the Best Results on Deoxys-BC-256 with 128-bit Key and Tweak. The results are summarized in Table 6.
1.1 A.1 Additional Aspects
In the main body we focused on distinguishers that do not take into account the final feed forward as this final operation makes it hard to mount a key recovery part at the bottom. The key recovery requires to invert rounds in value to access the end of the distinguisher, which is made difficult by the unknown value of the middle internal state. When given the full code book a zero-sum distinguisher can be constructed against one or more branches as described in [40, Appendix A.1] with distinguishing advantage \(1 - \frac{1}{2^{128}}\). In an integral attack, adding a round tweakey does not have any impact. This allows an adversary to apply the integral attacks on reduced-round AES to round-reduced ButterKnife also.
Cryptanalysis of ForkCiphers [8] applies as well, but with the difference that the reconstruction setting is not available given that one cannot make decryption queries. A reflection differential distinguishers might exist between two branches, but accessing it and building the required pair is troublesome.
B Graphical Representation of \(\textsf{SAFE}\)
C \(\textsf{ZMAC}\) Pseudocode
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Andreeva, E., Cogliati, B., Lallemand, V., Minier, M., Purnal, A., Roy, A. (2024). Masked Iterate-Fork-Iterate: A New Design Paradigm for Tweakable Expanding Pseudorandom Function. In: Pöpper, C., Batina, L. (eds) Applied Cryptography and Network Security. ACNS 2024. Lecture Notes in Computer Science, vol 14584. Springer, Cham. https://doi.org/10.1007/978-3-031-54773-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-031-54773-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-54772-0
Online ISBN: 978-3-031-54773-7
eBook Packages: Computer ScienceComputer Science (R0)