[openssl-users] Truncating A Hash

[Michael Wojcik]

> From: openssl-users [mailto:openssl-users-bounces at openssl.org] On Behalf
> Of Jay Foster
> Sent: Thursday, May 14, 2015 18:09
> To: openssl-users at openssl.org
> Subject: [openssl-users] Truncating A Hash
> 
> What is the down side of truncating a hash?  For example, an SHA-256
> hash is 256 bits.  Is it any less secure if one was to drop the last 128
> bits to make a 128 bit hash or take the MD5 hash of the SHA-256 hash to
> get a 128 bit hash?  It does not seem that such an action would make it
> any easier to brute force reverse the hash, but then again, I am clearly
> not a security expert.

Every bit you remove makes it half as expensive to find a collision by brute force. Discarding 128 bits of an SHA-256 hash makes it 2^128 times easier to "break" the hash.

Precisely how much truncation benefits an attack that's not brute force - that is, an attack on the compression function itself - depends on the attack. But it certainly isn't going to make such an attack more difficult.

Truncation is, broadly speaking, a Bad Idea. Whether it actually poses a credible threat depends on your threat model, but it's something to avoid.

Rehashing with another function that has smaller output (as in your proposal of composing SHA-256 with MD5) is worse than truncation, assuming the initial function is strong, because the result won't be better than truncation and could expose the overall system to other classes of better-than-brute-force attacks.

You're asking the wrong question, by the way, for two reasons. First, there is no "reverse the hash". A hash cannot be reversed, because it's a lossy function with a domain larger than its range; there are many preimages that hash to the same image. Defeating a cryptographic hash by brute force is a matter of finding another preimage that hashes to the same image. (That's oversimplified but good enough for our purposes.) When you discard a bit from the hash, you reduce the total number of possible hash values by a factor of two, so you make it twice as easy to find a collision.

Second, the question isn't "is it safe to truncate the output of a cryptographic hash". It's "I have problem X, under threat model Y; how can I solve X while satisfying Y as much as possible?". You need to tell us your X and explain what you can of your Y.

For example: "I have a legacy system that only allows 8 printable characters for passwords. I want to put a front end on it that lets users enter long passwords. Then I'll hash the password and convert the hash to Base64 and use the first 8 characters as the system password. But that's only using 48 bits of the hash value. Can I do better?"

(Another question would be what this has to do with OpenSSL...)

-- 
Michael Wojcik
Technology Specialist, Micro Focus



This message has been scanned for malware by Websense. www.websense.com