Dodis, Yevgeniy; Pietrzak, Krzysztof ZIST Austria
“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 ε.
414 - 433
FSE: Fast Software Encryption
Dodis Y, Pietrzak KZ. Improving the security of MACs via randomized message preprocessing. In: Vol 4593. Springer; 2007:414-433. doi:10.1007/978-3-540-74619-5_26
Dodis, Y., & Pietrzak, K. Z. (2007). Improving the security of MACs via randomized message preprocessing (Vol. 4593, pp. 414–433). Presented at the FSE: Fast Software Encryption, Springer. https://doi.org/10.1007/978-3-540-74619-5_26
Dodis, Yevgeniy, and Krzysztof Z Pietrzak. “Improving the Security of MACs via Randomized Message Preprocessing,” 4593:414–33. Springer, 2007. https://doi.org/10.1007/978-3-540-74619-5_26.
Y. Dodis and K. Z. Pietrzak, “Improving the security of MACs via randomized message preprocessing,” presented at the FSE: Fast Software Encryption, 2007, vol. 4593, pp. 414–433.
Dodis Y, Pietrzak KZ. 2007. Improving the security of MACs via randomized message preprocessing. FSE: Fast Software Encryption, LNCS, vol. 4593, 414–433.
Dodis, Yevgeniy, and Krzysztof Z. Pietrzak. Improving the Security of MACs via Randomized Message Preprocessing. Vol. 4593, Springer, 2007, pp. 414–33, doi:10.1007/978-3-540-74619-5_26.