New HMAC Message Patches: Secret Patch and CrOw Patch

摘要

At Asiacrypt 2012, Peyrin et al. showed generic attacks against the HMAC design. They utilized a pair of related keys where only the relation between the keys is known to the attacker but not the keys themselves (the secret key model). On similar lines, at Crypto 2012, Dodis et al showed differentiability attacks based on ambiguous and colliding keys on HMAC in known/chosen key model. Peyrin et al. also proposed a patching scheme for HMAC and claimed that the proposed patch thwarts their attacks. In this work, we first show that the patch proposed by Peyrin et al. will not prevent their attacks for the HMAC construction for certain "good" cryptographic hash functions. Specifically, we show that no public and reversible patch will prevent their attack on HMAC instantiated with a weakly collision resistant hash function. Following this, we propose two different patches, called the secret patch and the collision resistant one way (CrOw) patch, to thwart the attacks of Peyrin et al. and Dodis et al. Our work is theoretical in nature, and does not threaten the security of HMAC used with standard hash functions. Further, both our patches are designed to be used as wrappers and do not affect the underlying HMAC construction. This property is similar to Peyrin et al.'s patch.