Security of cryptographic hash functions: Difference between revisions

Revision as of 17:31, 1 January 2010

Revision as of 13:33, 2 January 2010

Line 16:

== Classical Hash Functions - Practical Approach to Security ==

Most hash functions are built on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. Various [[Bitwise operation|bitwise operations]] (e.g. rotations), [[Modular arithmetic|modular additions]] and [[One-way compression function|compression functions]] are used in iterative mode to ensure high complexity and pseudo-randomness of the output. In this way, the security is very hard to prove and the proof is usually not done. Only a few years ago, one of the most popular hash functions, [[SHA hash functions|SHA-1]], was shown to be less secure than its length suggested: collisions could be found in only 2^{69} tests, rather than the brute-force number of 2^{80}. The search for a "good:" hash function has thus become a hot topic.

In other words, most of the hash functions in use nowadays, are not provably secure collision-resistant. These hashes are not based on purely mathematical functions. This approach results generally in more effective hashing algorithms, but with the risk that a weakness of such a function will be eventually used to find collisions. The famous case is [[MD5]].

Line 39:

=== Downsides of Provable Approach ===

* ConstructConstructing a hash functionsfunction with provable security is much more difficult than using a intuitive approach where we just hope that the complexity of hashing algorithm is high enough to prevent adversary from finding collisions.

* Current collision-resistant hash algorithms that have provable security reductions are too inefficient to be used in practice.