I need to hash a message into a string of 30 chars. What's the best and most secure hash function for this usage?
+1
A:
Just use SHA1 and trim to 30 characters.
import hashlib
hash = hashlib.sha1("your message").hexdigest()[:30]
It's been proven that cutting characters off a cryptographically secure hash function such as SHA1 has negligible effects on its security (can't find the reference now though)
quantumSoup
2010-08-21 06:37:16
SHA-1's collisions will probably be found soon. If you don't care about collision-resistance, MD5 is sufficient. If you do, then the truncated hash only has a 60 bits of security, which isn't very much.
tc.
2010-08-21 08:14:32
Surely for good hashes it reduces the security in proportion of the exponent. For example, finding a collision on a 40-char SHA1 hexdigest is 2^80 by brute force, so finding a collision on the first 30 chars is "only" 2^60 by brute force. The best known collision attack on SHA1 is actually only something like 2^51, though, not 2^80. I have no idea whether that approach can be adapted to find a first-120-bit collision in less than 2^51. The reason for the discrepancy, though: SHA1 is not really a "cryptographically secure" hash function any more, at least where collisions matter.
Steve Jessop
2010-08-21 14:38:05
@tc How did you come up with "60 bits"?
quantumSoup
2010-08-21 15:00:10
@Steve 2^60 is a HUGE number. That's more than the age of the universe in seconds. And yes, SHA1 is still considered a cryptographically secure hash function, because 2^51 steps is still unfeasible to brute-force. Also, finding a way to generate collisions for entire hash in less steps DOES NOT translate into the same for the first 120 bits.
quantumSoup
2010-08-21 15:06:24
I wish people who have no clue about cryptography would stop downvoting on answers they have little to no knowledge to judge. FFS
quantumSoup
2010-08-21 15:07:27
@tc "SHA-1's collisions will probably be found soon." And what makes you think that?
quantumSoup
2010-08-21 15:11:17
Note for example that NIST has now forbidden SHA-1 for signed hashes. It's still considered good for HMAC and PRNG. A 2^51 collision attack on the full hash doesn't *necessarily* find a collision on the first 120 bits in 2^39 (which is entirely feasible), but it might find one in less than 2^51. Or there might be relatively minor adaptations that mean it could. Not knowing the details of how SHA-1 attacks work, I don't know, but I do know not to mess around with crypto primitives that are perilously close to the edge of sound...
Steve Jessop
2010-08-21 15:46:38
The collision is on 51-round SHA-1; this is different from 2^51. I use "bits of security" to mean "binary log of the number of operations required to attack it", which is only 2^60 for a 120-bit hash. 2^60 is not that huge; MD5CRK was a bruteforce attack on MD5, abandoned when cryptologists found collisions with a better attack (but the Wikipedia page says it'd take 3 weeks on a supercomputer). Apparently there's also a new preimage attack on MD5, but it still requires more than 2^120 work.
tc.
2010-08-23 02:15:35
+3
A:
Thirty characters (bytes) is 240 bits.
If you can't move the goal-post to allow 32 characters, then you will probably end up using SHA-1, which generates 160-bits or 20 bytes. When Base-64 encoded, that will be 28 characters. If you use a hex-encoding, it will be 40 characters, which is nominally out of range. With 32 characters, you could use SHA-256, but Base-64 encoding would increase that size (to 44 characters) and hex-encoding increases the size to 64 characters.
If you must use hex-encoding and can go to 32 bytes, then MD5 - which generates 128 bits - could be used, though it is not recommended for any new systems. With Base-64 encoding, MD5 uses 24 characters. Otherwise, you are using very minimally secure algorithms - not recommended at all.
Jonathan Leffler
2010-08-21 06:43:46