Publication

An Analysis of the Blockcipher-Based Hash Functions from PGV

Martijn Stam
2010
Journal Articles

Abstract

Preneel, Govaerts, and Vandewalle (1993) considered the 64 most basic ways to construct a hash function H: {0, 1}*->{0, 1}(n) from a blockcipher E: {0, 1}(n) x {0, 1}(n)->{0,1}(n). They regarded 12 of these 64 schemes as secure, though no proofs or formal claims were given. Here we provide a proof-based treatment of the PGV schemes. We show that, in the ideal-cipher model, the 12 schemes considered secure by PGV really are secure: we give tight upper and lower bounds on their collision resistance. Furthermore, by stepping outside of the Merkle-Damgard approach to analysis, we show that an additional 8 of the PGV schemes are just as collision resistant (up to a constant). Nonetheless, we are able to differentiate among the 20 collision-resistant schemes by considering their preimage resistance: only the 12 initial schemes enjoy optimal preimage resistance. Our work demonstrates that proving ideal-cipher-model bounds is a feasible and useful step for understanding the security of blockcipher-based hash-function constructions.

Official source

https://infoscience.epfl.ch/entities/publication/7a88df7d-35b3-4cbc-83be-685d82afc4cd

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Martijn Stam
2010
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/7a88df7d-35b3-4cbc-83be-685d82afc4cd

About this result

Related concepts (18)

One-way compression function

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

Cryptographic hash function

A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of bits) that has special properties desirable for a cryptographic application: the probability of a particular -bit output result (hash value) for a random input string ("message") is (as for any good hash), so the hash value can be used as a representative of the message; finding an input string that matches a given hash value (a pre-image) is unfeasible, assuming all input str

Preimage attack

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its (set of possible inputs). In the context of attack, there are two types of preimage resistance: preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input that hashes to that output; i.e., given , it is difficult to find an such that () = .

Related publications (30)

Secure and Efficient Cryptographic Algorithms in a Quantum World

Loïs Evan Huguenin-Dumittan

Since the advent of internet and mass communication, two public-key cryptographic algorithms have shared the monopoly of data encryption and authentication: Diffie-Hellman and RSA. However, in the last few years, progress made in quantum physics -- and mo ...

EPFL2024

Near Collision Attack Against Grain V1

Willi Meier, Subhadeep Banik, Daniel Patrick Collins

A near collision attack against the Grain v1 stream cipher was proposed by Zhang et al. in Eurocrypt 18. The attack uses the fact that two internal states of the stream cipher with very low hamming distance between them, produce similar keystream sequences ...

2023

Making Classical (Threshold) Signatures Post-quantum for Single Use on a Public Ledger

Serge Vaudenay, Laurane Chloé Angélina Marco, Abdullah Talayhan

The Bitcoin architecture heavily relies on the ECDSA signature scheme which is broken by quantum adversaries as the secret key can be computed from the public key in quantum polynomial time. To mitigate this attack, bitcoins can be paid to the hash of a pu ...

2023