SHA and "Bits of Security"

Question

I've researched several forms of encryption/hashing and have often come across the term "bits of security". For example, at least one source claimed SHA-256 = AES128 = ECC256 = 128 bits of security.

My question is, if this is true, can I take a 256-bit SHA-256 digest and compress it down to 128 bits without loss of security? (For example, by just taking the XOR of the upper 128 bits and lower 128 bits of the digest)

In my particular case, it's important that the digest be small. Thanks in advance for any responses.

Answer 1

Cryptographic hash functions must have several properties:

• Resistance to preimages: given x, it should be infeasible to find m such that h(m) = x.
• Resistance to second-preimages: given m, it should be infeasible to find m' such that h(m) = h(m').
• Resistance to collisions: it should be infeasible to find m and m' such that m ≠ m' and h(m) = h(m').

These properties are not equivalent to each other, and you do not necessarily need all of them. It depends on the protocol in which you are using the hash function. For instance, hash functions are used at the initial step of digital signatures, for which collisions are not a problem -- unless the attacker is in position to choose an exact message to be signed. Details can be subtle.

If the hash function has an output of n bits, then there exist generic attacks which find preimages, second-preimages and collisions with cost, repsectively, 2ⁿ, 2ⁿ and 2^n/2. A "generic" attack means that it works for all hash functions, regardless of how perfect they may be. This sets the maximum achievable security level.

If you "compress" SHA-256 output to 128 bits (whatever compression procedure you may want to use, even a simple truncation), then you are actually defining a new hash function with a 128-bit output. As such, the resistance to preimages and second-preimages of that function will be at best 2¹²⁸, and resistance to collisions will be at best 2⁶⁴. Therefore, your truncated SHA-256 will offer "128-bit security" only in usage contexts where collisions are not an issue. But since it can be quite hard to ascertain that collisions are indeed not a problem, "compressing" hash function output is not recommended.

In general, we prefer to be safe than sorry; thus, when we want "128-bit security" we use a 256-bit hash function. That way, we don't have to worry about whether collisions could be leveraged into an actual attack or not. SHA-256 collisions are not feasible with existing technology.

Answer 2

The assessment of any strong 256 bit cryptographic hash as having a security level of either 128 or 256 bit depends entirely on how it is used. In an application where an attacker can succeed simply by finding any hash collision, the security level cannot exceed 128 bit since a simple birthday attack will (probabilistically) succeed after 2^128 random attempts. If you shorten the hash to a 128 bit hash, then you reduce its security level in this context to 64 bits.

However, applications are conceivable where a successful attack would have to find a collision to one (or very few) given hashes, such as for forging a digitally signed message not by forging the signature itself, but by finding a different message that yields the same hash (which is what signature schemes tend to actually sign). In the extreme case that only one real signature exists, SHA256 would arguably permit a security level of 256 bits when used only as in this example.

Answer 3

No. In the context of a hash, "bits of security" is a measure of how many possible outputs a hash function has, and thus, how hard it is to find an input with a given output. It's on a logarithmic scale, so each additional bit doubles the security.

You can't compare the security of SHA-256, AES-128, and ECC-256. They're totally different things: SHA-256 is a cryptographic hash function, AES-128 is a symmetric block cypher, and ECC-256 is a public-key cypher.

Your proposed modification to SHA-256 will greatly reduce security, essentially turning it into a 128-bit hash function. Doing so is, however, more secure than any of the standard 128-bit hash functions because all of them have known collision attacks, and some of them have preimage or second preimage attacks. 128 bits may be enough security for your purposes.