Improving the security of MACs via randomized message preprocessing Conference Paper

Author(s): Dodis, Yevgeniy; Pietrzak, Krzysztof
Title: Improving the security of MACs via randomized message preprocessing
Title Series: LNCS
Abstract: “Hash then encrypt” is an approach to message authentication, where first the message is hashed down using an ε-universal hash function, and then the resulting k-bit value is encrypted, say with a block-cipher. The security of this scheme is proportional to εq2, where q is the number of MACs the adversary can request. As ε is at least 2−k, the best one can hope for is O(q2/2k) security. Unfortunately, such small ε is not achieved by simple hash functions used in practice, such as the polynomial evaluation or the Merkle-Damg ̊ard construction, where ε grows with the message length L. The main insight of this work comes from the fact that, by using ran- domized message preprocessing via a short random salt p (which must then be sent as part of the authentication tag), we can use the “hash then encrypt” paradigm with suboptimal “practical” ε-universal hash func- tions, and still improve its exact security to optimal O(q2/2k). Specif- ically, by using at most an O(logL)-bit salt p, one can always regain the optimal exact security O(q2/2k), even in situations where ε grows polynomially with L. We also give very simple preprocessing maps for popular “suboptimal” hash functions, namely polynomial evaluation and the Merkle-Damg ̊ard construction. Our results come from a general extension of the classical Carter- Wegman paradigm, which we believe is of independent interest. On a high level, it shows that public randomization allows one to use the potentially much smaller “average-case” collision probability in place of the “worst-case” collision probability ε.
Conference Title: FSE: Fast Software Encryption
Volume: 4593
Conference Dates: March 26-28, 2007
Conference Location: Luxembourg, Luxembourg
Publisher: Springer  
Date Published: 2007-10-11
Start Page: 414
End Page: 433
Copyright Statement: ⓒ International Association for Cryptologic Research 2007
DOI: 10.1007/978-3-540-74619-5_26
Open access: no
IST Austria Authors
Related IST Austria Work