TY - JOUR

T1 - Subversion Resilient Hashing

T2 - Efficient Constructions and Modular Proofs for Crooked Indifferentiability

AU - Bhattacharyya, Rishiraj

AU - Nandi, Mridul

AU - Raychaudhuri, Anik

PY - 2023/1/19

Y1 - 2023/1/19

N2 - 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 3 n + 1 many independent n -to- n -bit functions and 3 n 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. • 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. • 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.

AB - 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 3 n + 1 many independent n -to- n -bit functions and 3 n 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. • 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. • 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.

U2 - 10.1109/TIT.2023.3238115

DO - 10.1109/TIT.2023.3238115

M3 - Article

SN - 0018-9448

VL - 69

SP - 3302

EP - 3315

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -