50
$\begingroup$

I am from a web development background (I don't know an awful lot about cryptography or how the algorithms themselves work), so I am asking this question in simple terms.

Consider a hash of the word 'test' using SHA1:

a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

If I were to use SHA512 instead and then simply take the first 40 characters of the output:

ee26b0dd4af7e749aa1a8ee3c10ae9923f618980772e473f8819a5d4940e0db27ac185f8a0e1d5f84f88bc887fd67b143732c304cc5fa9ad8e6f57f50028a8ff

ee26b0dd4af7e749aa1a8ee3c10ae9923f618980

Questions

  1. Are there any security implications for hashing and storing sensitive data like this?

  2. Is it more or less secure than using the full SHA1 hash?

  3. Is there an increased risk of hash collision when using the truncated version?

This is sparked by a debate over somebody doing this, where their reason was that it would be better to use the SHA512 version because it is a more secure algorithm, and by truncating it a potential hacker wouldn't know which algorithm was used in the first place.

My understanding was that SHA1 would always produce a unique value, whereas there is a chance that the first 40 characters of a SHA512 output could appear many times.

$\endgroup$
  • $\begingroup$ Could you indicate if you are OK with changing the title to 160 bits? Hash output is normally given in bits... Don't forget to hit accept on the answer as well, I think it cannot be explained too much better than Reid already did. $\endgroup$ – Maarten Bodewes Aug 6 '13 at 23:47
  • $\begingroup$ @e-sushi I'm working in an environment where a C++ function exists that is called b2a, which stands for "binary to ASCII" which converts byte arrays to a hexadecimal representation. Naming things correctly is pretty important. $\endgroup$ – Maarten Bodewes Aug 6 '13 at 23:50
  • $\begingroup$ Note that the ad-hoc standard for using truncated hashes is to use the leftmost bytes as the hash value (removing bytes from the right). Please use this as default. With regards to security it doesn't matter which bits are used, but it could make a difference with regards to compatibility. $\endgroup$ – Maarten Bodewes Mar 17 '15 at 17:27
56
$\begingroup$

As a general rule, you should not use SHA1; instead, go with one of the hash functions from the SHA-2 family.

As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, SHA-512/256, and SHA-512/384, where SHA-$x$/$y$ denotes a full-length SHA-$x$ truncated to $y$ bits. (Technically the starting algorithm constant is different for the truncated versions, as pointed out by Henno Brandsma, but this is somewhat orthogonal to the point I'm trying to make.)

Are there any security implications for hashing and storing sensitive data like this?

As far as determining the sensitive material from the digest itself, you're safe. All secure modern-day cryptographic hashes have what is called preimage resistance, which essentially means that it is computationally infeasible to "reverse" the hash, if you will. So, your sensitive data's confidentiality won't be compromised by storing the digest. (Note: See Gordon Davisson's comment below about this; there are possible security implications in some scenarios.)

Now, the real question is: why are you wanting to store the hash in the first place? Hopefully you are not using it to detect if the data is maliciously modified; that generally is the purview of a MAC, such as HMAC or CBC-MAC.

Is it more or less secure than using the full SHA1 hash?

Much more secure, actually, if you care about collision resistance. There is an attack on SHA1 that finds collisions in 260 time, whereas truncating SHA-512 to 160 bits requires 280 time to find collisions (see the birthday attack). So, truncating one of the SHA-2 functions to 160 bits is around 220 times stronger when it comes to collision resistance. (Plus, finding collisions is now within the realm of possibility for SHA1. So, if you are reading this, and you are building a new system, you should choose SHA-2 or SHA-3.)

Is there an increased risk of hash collision when using the truncated version?

Increased risk over SHA1? No. Increased risk over using the full SHA-512 output? Yes.

Truncating the output of a hash function always decreases its (theoretical) collision-resistance. In practice, it usually doesn't matter too much; for instance, 280 time is still pretty big. Still, if you used the full output of SHA-256, the same birthday attack would take 2128 time, which is totally out of reach.

by truncating it a potential hacker wouldn't know which algorithm was used in the first place

Always assume the attacker knows everything about your algorithm/cryptosystem except for the secret keys. This is known as Kerckhoffs's principle. Why this is important is well-covered, so you should follow it.

My understanding was that SHA1 would always produce a unique value, whereas there is a chance that the first 40 characters of a SHA512 output could appear many times.

SHA1 doesn't produce unique values. There are infinitely-many possible inputs to SHA1 (it takes a bitstring of any length), yet there are only 160 bits of output. By the pigeonhole principle, there have to be infinitely-many values that map to the same 160 bits of output. In February 2017, a SHA-1 collision was published. However, there have not been any published SHA-256 collisions to date, despite that the pigeonhole principle guarantees they exist.


I should note, if you are going to use the full output of SHA1, SHA-256, or SHA-512, you should be aware of length extension attacks.

$\endgroup$
  • 2
    $\begingroup$ A caveat to the "security implications" section: if the plaintext values are guessable (or chosen from a limited set), an attacker will be able to guess-and-test possible plaintexts. For example, if you hash the State field of an address database, there'll only be 50 distinct hash values, and an attacker won't have much trouble figuring out which is which. Similarly, if you hash the Name field, and the attacker wants to find out if "John Q. Smith" is in your DB, they can hash that and look for a match. $\endgroup$ – Gordon Davisson Jul 27 '13 at 14:49
  • $\begingroup$ @GordonDavisson: Very true. To tell whether or not it's really secure we'd have to know the application. $\endgroup$ – Reid Jul 27 '13 at 15:04
  • 2
    $\begingroup$ Note that SHA-224 is not a simple truncated version of SHA-256: the IV is different. SHA-224 is computed like SHA-256 and then truncated, but as the IV is different, the intermediate 256 bit result of SHA-224 is totally different (in general) than the SHA-256 computation. The same goes for SHA-384 vs SHA-512. $\endgroup$ – Henno Brandsma Aug 13 '13 at 18:07
  • $\begingroup$ In some tests I did, truncated hash functions resulted in far more collisions than hash functions of the same length (although the untruncated version didn't collide, of course). I don't think I used sha512 back then, but for instance aggressively truncating MD5 to 4 bytes resulted in more collisions than using the CRC32 of the original value. $\endgroup$ – Ángel Sep 10 '14 at 19:51
  • 3
    $\begingroup$ @Ángel In general that shouldn't be true. But CRC32 has a special structure so depending on how you created those inputs it might have had far fewer collisions than an ideal hash. For example CRC32 doesn't have any collisions if you hash 4 byte messages, some people don't even consider it a hash. $\endgroup$ – CodesInChaos Sep 30 '15 at 14:47
0
$\begingroup$

A 160 bit (40 hex digit) truncated sha512 is almost certainly far more secure than sha1.

Firstly sha1 has significant known weaknesses, sha512 doesn't.

Secondly a truncated sha512 has far more internal state. What that means is that if someone does find a collision in truncated sha512 but not in full sha512 they can't "extend" that collision like they can with a sha1 collision.


Can you expand on your notion of extended collisions..?

md5/sha1/sha2 operate in roughtly the following way.

  1. Pre-process the input to convert it from a sequence of bytes to a sequence of blocks. Normally this pre-processing consisists of appending padding to the end. Even inputs that are an exact number of blocks in length will have padding appended to avoid the padding process introducing collisions.
  2. Initialise the internal state of the hash function.
  3. For each block in the input sequence perform some processing that takes the old internal state and the input block and produces a new internal state.
  4. Output the result.

For the "full" version of these hash functions the result is the internal state. So a collision in the result is the same thing as a collision in the internal state. For a "truncated" version of the hash function the result is a truncated version of the internal state, so it is possible to have a collision in the final output without having a collision in the internal state.

If we look at the recent collision attacks on SHA1 the strategy for exploiting them goes something like.

  1. Construct a common prefix. This will generally be a header for some sort of rich file format.
  2. Perform the search for collision blocks.
  3. Choose a common suffix which contains conditional logic that depends on the content of the collision blocks.

This strategy relies on the fact that the collision is not merely a collision in the final output, but a collision in the internal state. Therefore whatever suffix the attacker appends they will still have a collision.

If the attacker has a method that finds collisions in the truncated hash but not in the internal state (aka the full hash) then they will not be able to append arbitary suffixes after finding the collision, they will have to change their order of operations to.

  1. Construct a common prefix.
  2. Choose a common suffix.
  3. Perform the search for collision blocks.

This order of operations has two downsides for the attacker.

  1. The attacker has to write their conditional logic before finding their collision. They may end up finding a collision but that collision turning out to be useless because it doesn't trigger the conditional logic in the correct way.
  2. The attacker has to do the work of finding the collision seperately for each victim.
$\endgroup$
  • $\begingroup$ Can you expand on your notion of extended collisions..? $\endgroup$ – Paul Uszak Jun 24 '17 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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