The security level in hash function

Question

What is the difference in security between using part of message digest hash function or all the message digest hash function? and is there any equation can calculate the security for part or whole message digest?

Answer 1

There are three main characteristics which are looked for in a hash function:

• Resistance to preimages: given x, it shall be hard to find m such that h(m) = x.
• Resistance to second preimages: given m and h(m), it shall be hard to find m' (distinct from m) such that h(m) = h(m').
• Resistance to collisions: it shall be hard to find m and m', distinct from each other, such that h(m) = h(m').

For any hash function, regardless of its cryptographic strength, there is a generic attack which always works, and is called luck. To find a preimage (or a second preimage), just try random messages until a match is found. To find a collision, hash many random messages until two of them yield the same hash value. For a n-bit output, luck works with average effort 2ⁿ for preimages and second preimages, 2^n/2 for collisions (thus is it substantially easier to find collisions than preimages).

What you actually need in a hash function depends on the protocol. For instance, digital signature algorithms (the true ones, like RSA or DSA) begin by a hash function invocation, and the hash value is then used in the algorithm proper. Digital signatures work on preimage and second preimage resistance -- unless you are in a setup where a potential attacker can choose the data of some messages to sign, in which case you need resistance to collisions as well.

As a general rule, stick to n-bit output such that 2^n/2 invocations of the hash function is too big an effort. This means n = 160 or so. Using a hash function with only 128 bits of output means that one may find collisions with effort 2⁶⁴, which is quite expensive but technologically feasible (such an effort was done at least once but it took four years and thousands of contributors).

For some protocols it is safe to dismiss collisions (which would gain nothing to the attacker) and thus reduce the output to 80 bits (or so). And example is when the hash function is used as part of HMAC for integrity checks, but only as long as the underlying hash function is robust. Indeed, HMAC relies on some internal properties of the hash function which are not directly linked with resistance to preimages or collisions. If the hash function is SHA-256, things are fine; HMAC/SHA-256 truncated to 96 bits (you truncate the output of HMAC, not the internal hash function) will offer security up to 2⁹⁶, which is more than enough. If you hash function is MD5 or SHA-1, then... things are less clear.

It takes a trained cryptographer to tell you which usage of a hash function tolerates truncation, and which does not. This depends on the hash function itself, how it is used, and in what context. Many trained cryptographers will answer "don't do it" in most cases, anyway, because a big part of cryptography training is about realizing that a single human will never be able to think of everything. I am a trained cryptographer and thus I tell you: don't do it.

Answer 2

Only using part of the digest means you are reducing the size of the digest-space. What this means in practice depends on what you are using the digest for.

For web-based password hashing, I would be tempted to say that it will not have any major impact until you start using a really small subset of the digest. This is due to the fact that even 16 bits is probably larger than the password space 99% of users will reside in. It is also due to the fact that although using a subset of the digest makes collisions more likely in theory, it does not make them any easier to create in practice. If your hash function still has unbroken second-preimage resistance, such as the SHA2 family, then collisions will not be a worry - again until you get down to really small digest subsets at which point collisions become easily brute-forcable.

That said, it does not sound like a good idea. And I would certainly not advocate it in anything other than a very slow password-checking environment such as remote web authentication.

As for a formal definition of how secure it is, it really depends on your application. If we stay with password hashing, and assume you are doing everything else right - salting, using a slow hash method, defending your database server appropriately - then your only worry starts when the length of the digest you are using approaches (from above) the peak password-entropy of your user base, including salt. At that point you start hurting the strength of user passwords, which is a bad scenario.

Answer 3

A cryptographic hash function has two major sources of security:

• If you know H(x) it is computationally infeasible to deduce any information about x.
• It is computationally infeasible to find a collision such that H(x) = H(y) where x and y are not equal.

By reducing the size of the output of the function H, you reduce the amount of effort required to find a collision. For example, a perfect cryptographic hash function with an 8-bit output has a 1-in-256 (0.391%) chance of collision between any two randomly selected plaintexts. For a 32-bit output, that drops to 1-in-2³², or 0.0000000233%.

In order to guarantee a collision, you have to compute 2ⁿ+1 hashes, where n is the number of bits in the output. The expected number of hashes before a collision is found is 2^n-1, since that's when half of all possible hash outputs have been computed sqrt(2ⁿ), which would mean 2⁶⁴ operations for a 128-bit hash (thanks to Thomas for this correction). Modern hash functions tend to use anywhere between 160 and 512 bits, which results in expensive brute-force collision finding.

However, if you truncate the hash output to a lesser number of bits, you lose some of that collision resistance. For every byte you snip off, the cost of the attack drops by a factor of 256. Now, this isn't such a big deal if you just snip a couple of bytes off the end of a SHA256 hash, but if you use SHA1 and only check half the hash, you're reducing a 2¹⁶⁰ space down to 2⁸⁰, the latter of which is nearing the realms of feasibility in terms of brute-force collision finding.

The biggest question is why you would want to do this. I can see only two reasons, one of which being misguided:

• You want to increase the first security property of the hash, i.e. you can't deduce any information about x if you only know H(x). This isn't a good idea, since any modern cryptographic hash will have been designed to be maximally secure in this area already. There's no reason to truncate for this.
• You have very limited space to store your data, e.g. on a microcontroller or SoC EEPROM. In this case, you should be OK if you're using a decent hash algorithm and aren't truncating to less than ~128 bits (16 bytes) per hash. You'll lose some security against accidental collisions, but it's currently far outside the realms of being practically vulnerable.

Answer 4

The short answers to your questions are "a lot" and "yes".

Very simply, a hash digest theoretically has an amount of unpredictability, or entropy, equal to its length in binary digits. Each one of those bits could be 1 or zero, independent of any other with no apparent pattern. A "128-bit hash function", for instance, produces message digests 128 bits long and thus theoretically having 128 bits of entropy. For our purposes we will label the number of bits of entropy as B.

Given the hash function H, any arbitrary message M, and the resulting digest D = H(M) that is B bits in length, the ideal secure hash (which our real-world crypto hashes attempt to be) has the following fundamental behaviors:

• The complexity (average number of operations) of finding M given only H and D is 2^B. This is called finding a "preimage".
• The complexity of finding a second message M₂ that differs from M but produces the same D is also 2^B; this is called finding a "collision" or "second preimage".
• The complexity of finding any two messages M₁ and M₂ that produce the same D is 2^B/2; by the "birthday problem", as the number of messages whose digests have been calculated and remembered increases, the probability that the next message's digest will be unique decreases; with a relatively small number of known values, you start getting a relatively large chance to collide with each new message.

For instance, given a 128-bit hash function, finding a message that would produce a given hash digest would require 2¹²⁸ = 3.4*10³⁸ hash calculations. That's a lot of work; more than any currently-available coordinated computing system could produce in our lifetime. However, finding any two messages that produced the same digest, no matter what the messages or the digest were, is on the order of 2⁶⁴ = 1.8*10¹⁹. That, believe it or not, is well within the realm of possibility; the distributed.net cluster was able to traverse the 64-bit keyspace in about 5 years to crack a 64-bit cipher, which is equivalent in complexity to finding a 128-bit collision.

The upshot of all of this is that using a smaller hash digest, including using a portion of a larger hash digest, will reduce the number of bits of entropy, exponentially reducing the difficulty of finding a collision or a preimage. if you took, say, half of this 128-bit hash, you reduce the complexity of breaking it by an exponential amount; 2¹²⁸ = 2⁶⁴ * 2⁶⁴, so by using just half of the hash value you have reduced the complexity, and thus the security of the algorithm, to about one quadrillionth of the security that the full hash has.

Answer 5

You're question is a little bit vague. If you're asking if it's secure to check part of the digest, then no. If the hash of message X is "abcdefg", and hash(Y) is "ppppefg", and you only verify a "part" of it (the last 3 chars, "efg"), then you'll have the same value - and your hash functionality fails.

If you mean to hash a part of the message, then you can only provide data integrity for that part, not the entire message. Could be done for performance maybe, but not a good security practice.