Abstract In this paper, we study the security of the Key-Alternating Feistel (KAF) ciphers, a class of key alternating ciphers with the Feistel structure, where each round of the cipher is instantiated with n -bit public round permutation $$P_i$$ P i , namely the i -th round of the cipher maps $$\begin{aligned} (X_L, X_R) \mapsto (X_R, P_i(X_R \oplus K_i) \oplus K_i \oplus X_L). \end{aligned}$$ ( X L , X R ) ↦ ( X R , P i ( X R ⊕ K i ) ⊕ K i ⊕ X L ) . We have shown that our 5 round construction with independent round permutations and independent round keys achieves 2 n /3-bit security in the random permutation model, i.e., the setting where the adversary is allowed to make forward and inverse queries to the round permutations in a black box way.

We consider the problem of constructing secure cryptographic hash functions from subverted ideal primitives. Hash functions are used to instantiate Random Oracles in cryptographic protocols. The indifferentiability security notion is a popular tool to certify the structural soundness of a hash design for such instantiations. In CRYPTO 2018, Russell, Tang, Yung, and Zhou introduced the notion of crooked-indifferentiability to extend this paradigm even when the underlying primitive of the hashing mode is subverted. They showed that an$n$-to-$n$-bit function implemented using Enveloped XOR construction (EXor) with$3n+1$many independent$n$-to-$n$-bit functions and$3n^{2}$-bit random seed can be proven secure asymptotically in the crooked-indifferentiability setting. Unfortunately, known techniques to prove crooked-indifferentiability are extremely complicated, and no practical hashing mode has been analyzed in this setting. 1) We introduce new techniques to prove crooked-indifferentiability. We establish that upper bounding the subversion probability of a chaining query is sufficient to argue subversion resistance of a standard indifferentiable mode of operation. Our technique links standard indifferentiability and crooked-indifferentiability and circumvents the complications of proving the consistency of the simulator in the crooked setting. 2) We prove crooked-indifferentiability of the sponge construction when the underlying primitive is modelled as an$n$-to-$n$-bit random function. Our proofs only require$n$-bit randomly chosen but fixed IV and do not mandate any independent function requirement. The result naturally extends to the Merkle-Damgård domain extension with prefix-free padding. Our results minimize required randomness and solve the main open problem raised by Russell, Tang, Yung, and Zhou.