Example of simple flawed hashing algorithm vulnerable to preimaging attacks

Question

I am looking for an example of a simple hashing algorithm that can be shown to be vulnerable to multiple preimage attacks for a specified input length.

For example, if I know that the input data is exactly 160 bytes and generates a 16 byte hash, then there exists some method of finding other inputs that are 160 bytes in length and generate an identical 16 byte hash without resorting to pure brute forcing.

Please note that I do not mean using something like MD5 or SHA1. I understand that these are designed to make this impractical. This algorithm would be a textbook example of the flawed design of a hashing algorithm and how that flaw can be practically exploited. I have tried Google, but much of what turns up is theoretical research on known, secure algorithms.

Accipitridae · Accepted Answer · 2011-03-26 06:42:38Z

2

A simple example is the TEA-based hash function that was used in the XBOX. This hash function was susceptible to a simple second preimage attack. The flaw was that it used the cipher TEA in a Davis-Meyer construction. The attack exploits that TEA has equivalent keys. Hash collisions can be found by simple bit flipping.

A book that describes this attack is "Hacking the XBOX" by Andrew "bunnie" Huang.

answered Mar 26, 2011 at 6:42

Accipitridae

3,21421 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tom Zych · Accepted Answer · 2011-03-26 02:19:21Z

1

What you're asking for is a weak hashing algorithm. Strong hashing algorithms are hard. Weak ones are easy.

Here's one off the top of my head in pseudocode:

hash[0..15] = all 0
for i in range(0..159):
    hash[i % 16] ^= data[i]

Here, each hash byte is the xor of ten data bytes. Very easy to solve, yes? I'm sure you can think of equally easy ones.

answered Mar 26, 2011 at 2:19

Tom Zych

13.7k9 gold badges38 silver badges55 bronze badges

Collectives™ on Stack Overflow

Example of simple flawed hashing algorithm vulnerable to preimaging attacks

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related