On the impossibility of highly-efficient blockcipher-based hash functions
The authors investigate the idea of building hash functions from blockciphers. During the years various schemes have been proposed. Although some of them are provably secure they are viewed as inefficient since the blockcipher key has to be changed each round. For the conventional blockciphers this key change is undesirable since scheduling a new key entails a significant computational cost. In the focus of this work, the authors put the question of whether it is possible to achieve provable security without incurring this cost. Fix a small nonempty set of blockcipher keys \(\mathcal{K}\). A blockcipher-based hash function is said to be highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from \(\mathcal{K}\). During the years a few highly-efficient constructions have been proposed, but no one has been able to prove their security. In the present paper the authors prove that in the ideal-cipher model it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. This result implies, in particular, that the TWeakable Chain Hash construction suggested by \textit{M. Liskov, R. L. Rivest}, and \textit{D. Wagner} [Lect. Notes Comput. Sci. 2442, 31--46 (2002; Zbl 1026.94533)] is not correct under an instantiation suggested for this construction nor can TCH be correctly instantiated by any other efficient means.
- On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
- Hash functions based on block ciphers: A synthetic approach
- The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function
- Merkle-Damgård Revisited: How to Construct a Hash Function
- HCH: A New Tweakable Enciphering Scheme Using the Hash-Counter-Hash Approach
- Getting the Best Out of Existing Hash Functions; or What if We Are Stuck with SHA?
- Faster Luby-Rackoff ciphers
- Looking Back at a New Hash Function
- A Scheme to Base a Hash Function on a Block Cipher
- On the power of memory in the design of collision resistant hash functions
- Analysis of SHA-1 in encryption mode
- Black-box analysis of the block-cipher-based hash-function constructions from PGV
- Bounds on the Efficiency of Generic Cryptographic Constructions
- Building a Collision-Resistant Compression Function from Non-compressing Primitives
- Communication Theory of Secrecy Systems*
- Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers
- Cryptanalysis of the Hash Functions MD4 and RIPEMD
- Efficient Collision Search Attacks on SHA-0
- Finding Collisions in the Full SHA-1
- Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?
- Hash functions based on block ciphers: A synthetic approach
- How to Break MD5 and Other Hash Functions
- scientific article; zbMATH DE number 4195165 (Why is no real title available?)
- scientific article; zbMATH DE number 954401 (Why is no real title available?)
- On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
- On Tweaking Luby-Rackoff Blockciphers
- One Way Hash Functions and DES
- Tweakable block ciphers
- Universal classes of hash functions
- A synthetic indifferentiability analysis of some block-cipher-based hash functions
- Overcoming cryptographic impossibility results using blockchains
- On the effective block size in Harper's theorem
- On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups
- On the Security of Hash Functions Employing Blockcipher Postprocessing
- The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function
- Secure block ciphers are not sufficient for one-way hash functions in the Preneel-Govaerts-Vandewalle model
- On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
- Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don’t Exist
- An analysis of the blockcipher-based hash functions from PGV
- Impossibility of indifferentiable iterated blockciphers from 3 or less primitive calls
- Lower bound on number of compression calls of a collision-resistance preserving hash
This page was built for publication: On the impossibility of highly-efficient blockcipher-based hash functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1027986)