A new black box analysis of hash functions based on block ciphers
Tóm tắt
For the 64 most basic ways to construct a hash function H: {0, 1}* → {0, 1}
n
from a block cipher E: {0, 1}
n
× {0, 1}
n
→ {0, 1}
n
, Black et al. provided a formal and quantitative treatment of the 64 constructions, and proved that 20 schemes are collision resistant. This paper improves the upper and lower bounds and make contrast with a hash constructed from a random oracle. These 20 schemes have only one kind of collision resistance upper and lower bounds. In addition, we present new advantages for finding second preimages.
Tài liệu tham khảo
Merkle R C. One way hash functions and DES [C]// CRYPTO 1989, LNCS. Berlin: Springer-Verlag, 1990: 428–446.
Damgård I. A design principle for hash functions [C]// CRYPTO 1989, LCNS. Berlin: Springer-Verlag, 1990: 416–427.
Coron J S, Dodis Y, Malinaud C. How to construct a hash function [C]// CRYPTO 2005, LNCS. Berlin: Springer-Verlag, 2005: 430–448.
Dean R D, Formal aspects of mobile code security [D]. Princeton, New Jersey: Princeton University, 1999.
Joux A. Multicollisions in iterated hash functions: Application to cascaded constructions [C]// CRYPTO 2004, LNCS. Berlin: Springer-Verlag, 2004: 306–316.
Kelsey J, Schneier B. Second preimages on n-bit hash functions for much less than 2n work [C]// EUROCRYPT 2005, LNCS. Berlin: Springer-Verlag, 2005: 474–490.
Kelsey J, Kohno T. Herding hash functions and the nostradamus attack [C]// EUROCRYPT 2006, LNCS. Berlin: Springer-Verlag, 2006: 183–200.
Preneel B, Govaerts R, Vandewalle J. Hash functions based on block ciphers [C]// CRYPTO 1994, LNCS. Berlin: Springer-Verlag, 1994: 368–378.
Black J, Rogaway P, Shrimpton T, Black-box analysis of the block-cipher-based hash function constructions from PGV [C]// CRYPTO 2002, LNCS. Berlin: Springer-Verlag, 2002: 320–335.