“SHA-256” vs “any 256 bits of SHA-512”, which is more secure?

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?

-

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
– Gilles Jul 6 '12 at 21:43

2 Answers

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 (often considered an absolute minimum 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.

-

1
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
Can we take it furthur than 224? Or is 224 the absolute minimum? Also, does this mean that SHA-224 is just as secure as SHA-256, or SHA-256 is still more secure than SHA-224? – Pacerier Jul 7 '12 at 9:15
@Pacerier: yes we can do further down than 224 bits. See my addition. – fgrieu Jul 7 '12 at 9:59

1
@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
show 4 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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9255377650260925, "perplexity_flag": "middle"}