Abstract
The pseudorandom function Farfalle, proposed by Bertoni et al. at ToSC 2017, is a permutation based arbitrary length input and output PRF. At its core are the public permutations and feedback shift register based rolling functions. Being an elegant and parallelizable design, it is surprising that the security of Farfalle has been only investigated against generic cryptanalysis techniques such as differential/linear and algebraic attacks and nothing concrete about its provable security is known. To fill this gap, in this work, we propose Farasha, a new permutation-based parallelizable PRF with provable security. Farasha can be seen as a simple and provable Farfalle-like construction where the rolling functions in the compression and expansion phases of Farfalle are replaced by a uniform almost xor universal (AXU) and a simple counter, respectively. We then prove that in the random permutation model, the compression phase of Farasha can be shown to be an uniform AXU function and the expansion phase can be mapped to an Even-Mansour block cipher. Consequently, combining these two properties, we show that Farasha achieves a security of \(\min \{\text {keysize, permutation size/2}\}\). Finally, we provide concrete instantiations of Farasha with AXU functions providing different performance trade-offs. We believe our work will bring new insights in further understanding the provable security of Farfalle-like constructions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Farasha means butterfly in Arabic.
- 2.
Farasha means butterfly in Arabic. Here Farasha-L and Farasha-R correspond to the left and right wing of a butterfly, respectively.
- 3.
For instance, if \(M_1 = a \Arrowvert a \Arrowvert a \Arrowvert a\) and \(M_2 = a \Arrowvert a \Arrowvert b \Arrowvert b\), then there are 6 distinct tuples.
- 4.
This means there exists a random function \(\textsf{Rand} \) which on an input \(M_i \in {\{0,1\}^\star }\) returns a random string \(Z_i \in {\{0,1\}^\star }\).
References
Aumasson, J., Henzen, L., Meier, W., Naya-Plasencia, M.: Quark: a lightweight hash. J. Cryptol. 26(2), 313–339 (2013). https://doi.org/10.1007/s00145-012-9125-6
Aumasson, J.-P., Jovanovic, P., Neves, S.: NORX: parallel and scalable AEAD. In: Kutyłowski, M., Vaidya, J. (eds.) ESORICS 2014. LNCS, vol. 8713, pp. 19–36. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11212-1_2
Bernstein, D.J.: Chacha, a variant of Salsa20. In: Workshop Record of SASC (2008). cr.yp.to/papers.html#chacha
Bernstein, D.J.: The Salsa20 family of stream ciphers. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68351-3_8
Bernstein, D.J., et al.: Gimli: a cross-platform permutation. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 299–320. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_15
Bertoni, G., Daemen, J., Peeters, M., Assche, G.: CAESAR submission: Ketje v2 (2014). http://ketje.noekeon.org/Ketjev2-doc2.0.pdf
Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Assche, G.V., Keer, R.V.: Farfalle: parallel permutation-based cryptography. IACR Trans. Symmetric Cryptol. 2017(4), 1–38 (2017). https://tosc.iacr.org/index.php/ToSC/article/view/801
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge-based pseudo-random number generators. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 33–47. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_3
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 320–337. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_19
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. In: Hash Functions Workshop (2007). https://keccak.team/files/SpongeFunctions.pdf
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Keccak specifications. Submission to NIST (Round 2) (2009)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Permutation-based encryption, authentication and authenticated encryption. DIAC (2012)
Beyne, T., Chen, Y.L., Dobraunig, C., Mennink, B.: Dumbo, jumbo, and delirium: parallel authenticated encryption for the lightweight circus. IACR Trans. Symmetric Cryptol. 2020(S1), 5–30 (2020). https://doi.org/10.13154/tosc.v2020.iS1.5-30
Black, J., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384–397. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_25
Bogdanov, A., Knežević, M., Leander, G., Toz, D., Varıcı, K., Verbauwhede, I.: spongent: a lightweight hash function. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 312–325. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_21
Boneh, D., Shoup, V.: A Graduate Course in Applied Cryptography (2020). cryptobook.us
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). https://doi.org/10.1109/TIT.2008.920247
Chang, D., Nandi, M.: A short proof of the PRP/PRF switching lemma (2008). http://eprint.iacr.org/2008/078
Daemen, J., Hoffert, S., Assche, G.V., Keer, R.V.: The design of Xoodoo and Xoofff. IACR Trans. Symmetric Cryptol. 2018(4), 1–38 (2018). https://doi.org/10.13154/tosc.v2018.i4.1-38
Daemen, J., Hoffert, S., Peeters, M., Assche, G.V., Keer, R.V.: Xoodyak, a lightweight cryptographic scheme. IACR Trans. Symmetric Cryptol. 2020(S1), 60–87 (2020). https://doi.org/10.13154/tosc.v2020.iS1.60-87
Daemen, J., Lamberger, M., Pramstaller, N., Rijmen, V., Vercauteren, F.: Computational aspects of the expected differential probability of 4-round AES and AES-like ciphers. Computing 85(1-2), 85–104 (2009). https://doi.org/10.1007/s00607-009-0034-y
Daemen, J., Massolino, P.M.C., Mehrdad, A., Rotella, Y.: The subterranean 2.0 cipher suite. IACR Trans. Symmetric Cryptol. 2020(S1), 262–294 (2020). https://doi.org/10.13154/tosc.v2020.iS1.262-294
Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: lightweight authenticated encryption and hashing (2021). https://doi.org/10.1007/s00145-021-09398-9
Dobraunig, C., Grassi, L., Guinet, A., Kuijsters, D.: Ciminion: symmetric encryption based on Toffoli-Gates over large finite fields. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 3–34. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_1
Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the even-mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_21
Dworkin, M.J.: SP 800-38D: recommendation for block cipher modes of operation: Galois/counter mode (GCM) and GMAC. National Institute of Standards & Technology (2007)
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10, 151–162 (1997). https://doi.org/10.1007/s001459900025
Granger, R., Jovanovic, P., Mennink, B., Neves, S.: Improved masking for tweakable blockciphers with applications to authenticated encryption. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 263–293. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_11
Gunsing, A., Daemen, J., Mennink, B.: Deck-based wide block cipher modes and an exposition of the blinded keyed hashing model. IACR Trans. Symmetric Cryptol. 2019(4), 1–22 (2019). https://doi.org/10.13154/tosc.v2019.i4.1-22
Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222–239. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_13
Jean, J., Nikolic, I., Peyrin, T., Seurin, Y.: Deoxys v1. 41. Submitted to CAESAR 124 (2016). https://competitions.cr.yp.to/round3/deoxysv141.pdf
Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_18
McGrew, D., Viega, J.: The Galois/counter mode of operation (GCM). Submission to NIST Modes of Operation Process 20, 0278–0070 (2004)
Minematsu, K.: Parallelizable rate-1 authenticated encryption from pseudorandom functions. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 275–292. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_16
Mouha, N., Luykx, A.: Multi-key security: the even-mansour construction revisited. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 209–223. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_10
Patarin, J.: The “coefficients H’’ technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328–345. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_21
Peyrin, T., Seurin, Y.: Counter-in-tweak: authenticated encryption modes for tweakable block ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. 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.: OCB: a block-cipher mode of operation for efficient authenticated encryption. ACM Trans. Inf. Syst. Secur. 6(3), 365–403 (2003). https://doi.org/10.1145/937527.937529
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
Acknowledgments
The authors would like to thank the reviewers of SAC 2022 for their insightful comments which improved the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Security Proofs
A Security Proofs
1.1 A.1 Proof of Lemma 1
Proof
Let \(\sigma _i\) be the number of queries to \(P_i\). By the PRP/PRF switching lemma, the advantage after switching \(P_i\) by PRF \(\rho _i\) is bounded by \(\frac{\sigma _i^2}{2 \cdot 2^b}\). Since the permutations as well as the functions are independent of each other, the total advantage of the \(\mu \) switchings is given by
1.2 A.2 PRF Security of \(\textsf {Farasha}^{\#}\)
In \(\textsf {Farasha}^{\#}\) (see Sect. 5.1), we first expand a k-bit key K to a 2k-bit key \(K' = P''(K)\). The key \(K'\) is then used as a key for Farasha. Denote the modified left-side as \(\textsf {Farasha}\text {-}\textsf {L}^{\#} (K,M) = \textsf {Farasha}\text {-}\textsf {L} (P''(K),M)\). Then, the security of \(\textsf {Farasha}^{\#}\) follows from Lemma 3.
Lemma 3
(PRF security of Farasha\(^{\#}\)). Consider Farasha as defined in Theorem 3 and additionally let and \(\textsf {Farasha}\text {-}\textsf {L}^{\#}\) as defined above. Then for adversaries \(\mathcal {A}, \mathcal {A}'\), we have
where \(q_{p''}\) is the number of primitive queries to \(P''\).
Proof
With another public permutation \(P''\) for the key expansion, \(P''^{\pm }\) is the additional (primitive) oracle available to the adversary \(\mathcal {A}\). Let \(\mathcal {A}\) make \(q_{p''}\) primitive queries to \(P''\) and denote its input-output pairs as \(\tau _{p''} = \{ (u_i, v_i)\, | \, P''(u_i) = v_i, \, 1 \le i \le q_{p''}\}\). Now, in addition to all cases in proof of Theorem 3, we need to consider an additional bad event, i.e., when one of the queries in \(\tau _{p''}\) matches the key K. The probability of this event is at most \(q_{p''}/2^k\). Given that the construction after the key expansion is identical to \(\textsf {Farasha}\text {-}\textsf {L} \), accounting for this term in Lemma 2 (resp. Theorem 3) gives the adversarial advantage of \(\textsf {Farasha}\text {-}\textsf {L}^{\#} \) (resp. \(\textsf {Farasha}^{\#}\)) as given in Eq. 25. This proves the lemma.
1.3 A.3 Proof of Theorem 2
Proof Idea. Let \((M_{ij}, C_{ij})\) denote the j-th plaintext and ciphertext pair corresponding to the EM instance with key \(K_i\), i.e., \(E_{K_i}\). Furthermore, \((x_j, y_j)\) denote the input/output of the j-th public permutation query. The bad events are identical to the independent keys analysis done in [35], and are as follows.
The probabilities that Eq. 26a and Eq. 26b hold is bounded by \(\epsilon \) due to the \(\epsilon \)-uniform-AXU property. The rest of the proof is identical to the one in [35], and the \(1/2^b\) term can be generalised to \(\epsilon \) with \(\epsilon =1/2^{b}\) for independent keys.
Proof
The adversarial model for the modified key setting is depicted in Fig. 3, with an adversary \(\mathcal {A}\) having bidirectional access to \(\mu +1\) oracles \((\mathcal {O}_1,\cdots , \mathcal {O}_{\mu }, \mathcal {O})\). In the ideal world, these are . In the real world, these are \((E_{K_1}, \cdots , E_{K_{\mu }}, P)\), where \(E_{K_i}(M_{ij}) = P(M_{ij} \oplus K_i) \oplus K_i\) for \(i = 1, \cdots , \mu \). Note that, in this setting, the keys \(K_i\) are the output of a keyed hash function \(H_K\) and satisfy the \(\epsilon \)-uniform-AXU property. The adversary makes \(\sigma _i\) queries to oracle \(\mathcal {O}_i\) (resp. \(q_p\) queries to oracle \(\mathcal {O}\)), which are captured in transcripts \(\tau _i\) for \(1 \le i \le \mu \) (resp. \(\tau _p\)). Thus, the transcripts in the real-world are:
We assume the adversary never makes duplicate queries, so that \(M_{ij} \ne M_{ij'}, C_{ij} \ne C_{ij'}, x_j \ne x_{j'}, y_i \ne y_{j'}\) for all \(i,j,j'\) where \(j\ne j'\). We denote the total number of keyed (or construction) queries by \(\sigma = \sum _{i=1}^{\mu }\sigma _i\).
After all the queries by \(\mathcal {A}\) are done, but before it outputs its decision, the key K (of the hash function \(H_K\)) in the real world and a dummy key in the ideal world is released to the adversary. This enables the adversary to compute the keys \((K_1, \cdots , K_{\mu })\). The interaction of \(\mathcal {A}\) with the oracles can be summarized by a transcript \(\tau = \{K, \tau _1, \cdots , \tau _{\mu }, \tau _p\}\) or equivalently, \(\tau = \{K_1, \cdots , K_{\mu }, \tau _1, \cdots , \tau _{\mu }, \tau _p\}\).
Without loss of generality we assume that \(\mathcal {A}\) is deterministic. Given the fixed deterministic adversary \(\mathcal {A}\), we denote the probability distribution of transcripts in the real world by X, and in the ideal world by Y. We say that a transcript \(\tau \) is attainable if it can be obtained from interacting with \((P_1, \cdots , P_{\mu }, P)\), i.e., \({\text {Pr}}{[Y = \tau ]} > 0\). In our proof, we use the H-coefficient technique, as given by Lemma 4.
Lemma 4
(H-coefficient Technique [36]). Let us consider a fixed deterministic adversary \(\mathcal {A}\), and let \(\mathcal {T}=\mathcal {T}_{good} \cup \mathcal {T}_{bad}\) be a partition of the set of attainable transcripts. Let \(\delta \) be such that for all \(\tau \in \mathcal {T}_{good}\)
Then, .
We say that a transcript \(\tau \in \mathcal {T}\) is bad if two different queries result in the same input (or output) to P, were \(\mathcal {A}\) interacting with the real world. Stated formally, \(\tau \) is bad if one of the following conditions is met:
A transcript that is not a bad transcript, is referred to as a good transcript.
Upper Bounding \({\text {Pr}}{[Y \in \mathcal {T}_{bad}]}.\) We want to upper bound the event that a transcript \(\tau \) in the ideal world satisfies Eq. 29a or 29b. Recall that for \(i = 1, \cdots , \mu \), keys \(K_i\) satisfy the \(\epsilon \)-uniform-AXU property. For any fixed \(i\ne i'\), there are at most \(2\sigma _i \sigma _{i'}\) possible plaintext pairs and ciphertext pairs. With keys satisfying \(\epsilon \)-AXU property, the probability of satisfying the condition in Eq. 29a is bounded by \(2\sigma _i \sigma _{i'} \epsilon \). Analogously, for any fixed i, there are at most \(2\sigma _i q_p\) distinct values in Eq. 29b. Since the keys are also \(\epsilon \)-uniform, the probability of satisfying the condition in Eq. 29b is bounded by \(2\sigma _i q_p \epsilon \). Therefore,
Lower Bounding Ratio \({\text {Pr}}{[X = \tau ]} / {\text {Pr}}{[Y = \tau ]}.\) Let us consider a good and attainable transcript \(\tau \in \mathcal {T}_{good}\). Then, denote by \(\varOmega _X = 2^{b} \cdot 2^b!\) the set of all possible oracles in the real world and by \(comp_X(\tau ) \subseteq \varOmega _X \) the set of oracles in \(\varOmega _X\) compatible with transcript \(\tau \). Define \(\varOmega _Y = 2^{b} \cdot (2^b!)^{\mu +1}\) and \(comp_Y(\tau )\) similarly. According to the H-coefficient technique:
First, we calculate \(|comp_X(\tau )|\). As \(\tau \in \mathcal {T}_{good}\), there are no two queries in \(\tau \) with the same input or output of the underlying permutation. Any query tuple in \(\tau \), therefore, fixes exactly one input-output pair of the underlying oracle. Because \(\tau \) consists of \(\sigma + q_p\) query tuples, the number of possible oracles in the real world equals \((2^b - \sigma - q_p)!\). By a similar reasoning, the number of possible oracles in the ideal world equals \(\prod _{i=1}^{\mu } (2^b - \sigma _i)! \cdot (2^b - q_p)!\). Therefore,
It then follows that \({\text {Pr}}{[X = \tau ]} /{\text {Pr}}{[Y = \tau ]} \ge 1\). Thus,
This proves the theorem.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Aaraj, N., Bellini, E., Jejurikar, R., Manzano, M., Rohit, R., Salazar, E. (2024). Farasha: A Provable Permutation-Based Parallelizable PRF. In: Smith, B., Wu, H. (eds) Selected Areas in Cryptography. SAC 2022. Lecture Notes in Computer Science, vol 13742. Springer, Cham. https://doi.org/10.1007/978-3-031-58411-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-58411-4_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-58410-7
Online ISBN: 978-3-031-58411-4
eBook Packages: Computer ScienceComputer Science (R0)