Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In terms of security strength, Is there any difference in using the SHA-256 algorithm vs using any random 256 bits of the output of the SHA-512 algorithm?

Similarly, what is the security difference between using SHA-224 and using any random 224 bits of the SHA-256 output?

share|improve this question

migrated from security.stackexchange.com Jul 6 '12 at 10:04

This question came from our site for Information security professionals.

    
This may be a partial dupe, but I think this does get to levels which are better suited over on Crypto. –  Rory Alsop Jul 6 '12 at 10:03
2  
add comment

2 Answers 2

up vote 24 down vote accepted

SHA-512 truncated to 256 bits is as safe as SHA-256 as far as we know. The NIST did basically that with SHA-512/256 introduced March 2012 in FIPS 180-4 (because it is faster than SHA-256 when implemented in software on many 64-bit CPUs). SHA-224 is just as safe as using 224 bits of SHA-256, because that's basically how SHA-224 is constructed. What bits are kept (provided that's fixed) is immaterial to security, but for compliance to NIST specification, the left bits shall be kept.


As stated in this other answer, in the general case of a hash function only assumed to be collision-resistant or preimage-resistant, restricting its output can make it entirely insecure. A trivial example is the 512-bit function obtained by appending 256 zeros to the output of SHA-256, which is both collision-resistant and preimage-resistant, but trivially insecure when restricted to its 256 right bits.

The stated design goal of SHA-2 functions are preimage-resistance and collision-resistance: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest". Therefore, truncation of SHA-2 functions is not playing by the book.

Update: FIPS 180-4, which defines SHA-2 functions SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256, explicitly endorses truncation in its section 7: "Some application may require a hash function with a message digest length different than those provided by the hash functions in this Standard. In such cases, a truncated message digest may be used, whereby a hash function with a larger message digest length is applied to the data to be hashed, and the resulting message digest is truncated by selecting an appropriate number of the leftmost bits".

Truncation of SHA-2 functions is safe. That's the very principle used to construct SHA-224 from a slight variant of SHA-256, as well as SHA-384, SHA-512/224, and SHA-512/256 from a slight variant of SHA-512 (the variant being to change the internal initialization vector, in order to avoid that the output of one function reveals bits of the output of another one).

The reason why SHA-2 functions can be safely truncated is that these functions have another unstated design goal, that they reach as far as we know, which is: being computationally indistinguishable from a random function, except for being that particular function. That strong property is necessary to be able to use the hash with confidence in proofs of protocols made in the Random Oracle Model, and implies collision-resistance and preimage-resistance (the reverse is not true). Truncation (by keeping any fixed subset of their output bits) of a function indistinguishable from a random function also is indistinguishable from a random function (proof sketch: any hypothetical distinguisher for the truncated function is easily converted into a distinguisher for the original function, with the same effort and advantage).

The principle can be extended to any size; e.g. SHA-512 truncated to 128 bits is, as far as we know, as fine a 128-bit hash as can be (regardless of which bits we keep), and unquestionably much preferable security-wise to MD5 (another 128-bit hash, which collision resistance is badly broken). However, collision for an $n$-bit hash can be found in about $2^{(n/2)+0.33}$ hashes, little memory, and efficient parallelization (see Parallel Collision Search with Cryptanalytic Applications). Hence for 80-bit level security (which has sometime been considered an absolute minimum in the early 2000s, and is sometime to be considered insufficient nowadays), when collision resistance is necessary, we should keep at least 160 bits; and when only preimage-resistance is necessary, we should keep at least 80 bits.

share|improve this answer
2  
I'd even say it's more secure, since state collisions become much harder, protecting against a certain class of multi-collisions. It also prevents length-extension. –  CodesInChaos Jul 6 '12 at 13:42
    
@Pacerier: yes we can do further down than 224 bits. See my addition. –  fgrieu Jul 7 '12 at 9:59
2  
@Pacerier: I quoted the NIST prescribing the use of leftmost bits. They most likely did it in order to avoid a multiplication of diverging implementations; but there is no reason to believe we need to do this for security. –  fgrieu Jul 8 '12 at 18:12
1  
The term is common, yes. However it usually does not refer to hash-functions, but to other cryptographic schemes proven secure in the ROM. The hash function (that is used to replace the RO) itself does not even exist in the ROM. It only comes into play, once you try to implement a scheme. –  Maeher Jul 10 '12 at 6:36
1  
@Pacerier: SHA-512/224 and SHA-512/256 differ in output size (the second number, in bits), and initialization value (so that the result of SHA-512/224 is not a subset of the other). –  fgrieu Feb 13 at 5:58
show 8 more comments

If we are talking about collision resistance, then - in general for any hash function - using only part of the output may be a problem.

Given an arbitrary collision resistant hash function $H$, such that $H(m)=x||b$ (where b is only a single bit), we construct the hash function $H'$, such that $H'(m)=x$, i.e. it gives the same output as $H$ but without the last bit.

We can prove, that collision resistance of $H$ does not imply collision resistance of $H'$. To do that, we construct a specific collision resistant hash function $H$, such that $H'$ is not collision resistant.

For that we assume existence of a third collision resistant hash function $H''$ and define $H(m||b)=H''(m)||b$. $H$ is still collision resistant, because any collision under $H$ would also yield a collision under $H''$. However it now holds that for any $m\in \{0,1\}^*$ $H'(m||0)=H''(m)=H'(m||1)$ and $H'$ is therefore not collision resistant.

This may seem a bit counterintuitive and we assume (and hope) that this is not the case for hash functions that are commonly used (such as SHA-512).

So in short: For a hash function like SHA-512 you will probably be ok, but there is absolutely no guarantee. So don't mess with its output unless it's absolutely necessary and you really know what you are doing. Just use a tool that was made for the job.

share|improve this answer
2  
Saying that there is no insurance on the safety of SHA-512 truncated to 256 bits is being overly prudent; the NIST itself used that very technique to build SHA-512/256, part of the March 2012 FIPS 180-4; see my answer. –  fgrieu Jul 6 '12 at 15:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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