Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm designing a cryptography-breaking assignment for a college-level introductory security course, and I'm looking for a hash function which is reasonably easy (but not too easy) to generate collisions for. The assignment is that the students are given a hash table implementation which uses such a function, and their task is to design a series of inputs which will tank the hash table's performance. I was originally thinking of modelling it off of PHP's associative array attack from a few years ago, but it's actually too simple (for integer keys, the index used is literally just the integer modded by the table size). Any ideas for something that might be a tad harder than this, but not so hard that a bunch of sophomores with a week's worth of crypto lectures couldn't solve it in a reasonable amount of time?


EDIT: To clarify, I'm looking for hash functions which are not cryptographically secure, and can be easily inverted (or at the very least caused to collide) without brute-force search of the input space. As a general rule, hash functions which you could even mistake for cryptographically secure are probably too hard to break for this assignment.

share|improve this question
CRC32? Or one with your own polynomial if you want to avoid them just googling a solution. – otus Nov 12 at 6:33
I’ld like to chime in with @otus… if that’s too hard, you could opt-in to a simpler CRC16 or maybe even CRC8. The later being near to a “pen-and-paper effort” assignment, yet nice enough to activate their brain. And if you need it a tad more difficult than CRC32, you could go for CRC64. Wikipedia has a table which might help (scroll down), and also lists some Polynomial representations which you could adapt to your own preferences as otus indicated. – e-sushi Nov 13 at 10:13

2 Answers 2

A mathematically elegant and rather simple way of hashing are the parity bits of a Hamming code, as small changes in the data will yield different parity bits. You can weakly hash 4-bit strings to 3-bit strings with the standard (7,4) Hamming code, but the general Hamming code construction has high enough rate that you can hash longer strings (say, 26 bits to 5 bits) with a very simple algorithm and give them a hint by showing how to break the (7,4) hash.

Actually, it does sound like a fun homework assignment to find a string of length $2^{20} - 21$ that hashes to a particular $20$ bit string using a $(2^{20}-1, 2^{20}-21)$ Hamming code

Of course there are better "real hashes", but you didn't want that, right? :)

share|improve this answer

You can tune the difficulty of finding collisions very simply by reducing the number of output bits from any hash function.

For example, if you take SHA-256 and reduce it to SHA-13 (by only returning the 13 least significant bits of the output), it becomes a far weaker hash function. Now the probability of finding a collision is a mere 1 in 2^13 for each attempt. If that's too weak, try SHA-42 or whatever you like.

share|improve this answer
I'd like this to be a non-brute force break. That is, the students should be able to identify some simple theoretical weakness. I was thinking, for example, of a prime modulus hash (where H(x, y) = p1x + p2y mod m for some p1, p2 and some prime m), but the modular arithmetic involved in breaking it is pretty tricky if you haven't seen the algebra before. – joshlf Nov 12 at 5:41
SHA-13 collision attack would require only about $2^7$ attempts, though I suppose you might as well use a 2nd preimage attack in that case. – otus Nov 12 at 6:37
Finding a specific collision, I should have said. – user2790167 Nov 12 at 9:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.