2012 | OriginalPaper | Buchkapitel
Optimal Collision Security in Double Block Length Hashing with Single Length Key
verfasst von : Bart Mennink
Erschienen in: Advances in Cryptology – ASIACRYPT 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The idea of double block length hashing is to construct a compression function on 2
n
bits using a block cipher with an
n
-bit block size. All optimally secure double length hash functions known in the literature employ a cipher with a key space of double block size, 2
n
-bit. On the other hand, no optimally secure compression functions built from a cipher with an
n
-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying
n
-bit keyed block cipher collisions can be found in about 2
n
/2
queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2
n
-bit key space crucially rely on the presence of these extra
n
key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to 2
n
(1 −
ε
)
queries and preimage resistance up to 2
3
n
(1 −
ε
)/2
queries, for any
ε
> 0. To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space.