2
$\begingroup$

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?

Thanks!

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ CRC32? Or one with your own polynomial if you want to avoid them just googling a solution. $\endgroup$
    – otus
    Nov 12, 2015 at 6:33
  • $\begingroup$ 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. $\endgroup$
    – e-sushi
    Nov 13, 2015 at 10:13

2 Answers 2

Reset to default
2
$\begingroup$

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? :)

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – joshlf
    Nov 12, 2015 at 5:41
  • $\begingroup$ 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. $\endgroup$
    – otus
    Nov 12, 2015 at 6:37
  • $\begingroup$ Finding a specific collision, I should have said. $\endgroup$
    – user2790167
    Nov 12, 2015 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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