Internal Distinguishers in Indiﬀerentiable Hashing: The Shabal CasePosted on July 28th, 2010 No comments
We show the ﬁrst indiﬀerentiability proof of a hash construction C F which does not make the assumption that the inner primitive F is ideal, but allows the existence (up to certain bounds that we explicit) of statistical distinguishers on F. Our hash construction is a general domain extender that generalizes both Chop-MD and Shabal and we prove that this general mode of operation is indiﬀerentiable from a random oracle by providing tight security bounds when the inner primitive F is either an ideal compression function or a keyed permutation. Our proof provides the tightest possible security bounds on Chop-MD and even improves the original indiﬀerentiability proof of Shabal. We then extend our results to the case where F is not assumed ideal anymore, but presents some (possibly strong) form of statistical bias in its input-output behavior. Our results allow us to derive new indiﬀerentiability bounds for Shabal and show that the series of recently found (order-1, diﬀerential or rotational) distinguishers on its internal keyed permutation leave fully intact its indiﬀerentiability properties.
Authors: Emmanuel Bresson, Anne Canteaut, Thomas Fuhr, Thomas Icart, María Naya-Plasencia, Pascal Paillier, Jean-René Reinhard, Marion Videau
Note: This work was partially supported by the French Agence Nationale de la Recherche through the SAPHIR2 project under Contract ANR-08-VERS-014.