Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

For the purpose of fingerprinting data with the least chance of collision will combining the length (as a 32 bit unsigned integer stored in addition to the hash) of the input data and/or sampling a few bytes from the input significantly strengthen the resulting output combined with the hash?

For example:

sha256(data) + length + first_2_bytes_of_data = 304 bits

Note: (updated)

  • The privacy of the input data is not paramount, more the ability to detect if the data has changed.
  • Also I use a 256 bit hash function in this example but the question is less about the final choice of hash function and more about will adding the 6 extra bytes help.
  • The length in bytes of the input data will always be variable but always less than or equal to 2 to the power of 32.
  • The resulting output will be used both for integrity verification and as a dictionary key for up to 2^64 items (if key collision is considered unpractical or impossible)
share|improve this question
If the length of data is equal to 2 to the power of 32 than I think I cannot be encoded in 4 bytes or 32 Bit Integer. Please correct me if I am wrong? – Mohit Sethi Jun 21 '12 at 11:11
2  
I think you meant sha256(data)[256 Bits] + length [32 Bits] + first_2_bytes_of_data [16 Bits] = 304 Bits/38 Bytes – Mohit Sethi Jun 21 '12 at 11:21
I think the logic described shall significantly reduce the chances of hash collision. As far as data privacy is not a concerned, I think it is a great way to reduce the hash collision. – Mohit Sethi Jun 21 '12 at 11:30

4 Answers

up vote 5 down vote accepted

No, adding such side information does not really help to strengthen the resistance to collisions, for a cryptographically secure hash function such as SHA-256 already takes into account the length (through explicit inclusion in the padding, see §5.1.1, page 13 of the FIPS 180-3 standard) as well as every single bit of the input data to compute the digest. There is no known collision for SHA-256 nor is there any publicly known promising method to find one.

share|improve this answer
SHA-256 is not resistant to length extension attacks, despite the inclusion of the length of the padding. As I understand it, the inclusion of the length merely makes looking for the suffix a little more complicated. Source: At the current time, is SHA256 the de facto standard for strong cryptographic hashes? (and others) – Gilles Jun 21 '12 at 17:35
Length-extension attacks allow to build more cheaply several collisions when a first one is already found. I have understood the question with respect to searching this first collision (in an unkeyed context), not the next ones. – cryptopathe Jun 21 '12 at 17:47
@cryptopathe Sorry if this was unclear. The questions has been updated. The intension was to use the resulting output as a key (in addition to message verification) if it is impractical that a key collision will occur. The purpose of adding additional data was to reduce the dataset that may produce the same hash output. – Bernie White Jun 22 '12 at 22:23
up vote 1 down vote

SHA-256 is widely believed to be a secure hash construction, and is the de facto standard for strong cryptographic hashes. You will not add any additional security by adding the length or a few bytes, both can easily be imitated (whereas the SHA-256 hash can't).

Including the length of the message has does have a practical advantage: when you find a message with the wrong hash and you try to investigate if it may be an accidental problem, knowing the length can help steer your investigation towards a truncated message, or certain kinds of typical corruption (for example, a message that should be compressed data and is approximately 1/256th too long may well have had its newlines converted from unix format to Windows format as if it had been text).

Including the first two bytes of the message is almost completely useless. It is useless for security, and it is rarely useful for debugging, except occasionally to detect that you sent the message in the wrong format. It could be useful to verify that the message seems to be in the desired format, but this usually requires a few more bytes, and a MIME type or similar format indication would serve this purpose better.

share|improve this answer
This answer looks wrong to me. 1) The OP's construction is just as vulnerable to length-extension as plan SHA-256 2) "it is possible to find a message E such that M+E has the same hash as M" this isn't a length-extension attack. That's a plain collision, and we know no efficient way to compute that for SHA-256. – CodesInChaos Jun 23 '12 at 13:18
1  
Length extensions aren't about finding collisions. It's about calculating the hash(M || E) when you only know H(M) but not M. This is an issue with the naive MAC Hash(K || M), because you can now calculate a valid MAC for Hash(K || M || E), but this MAC is different from the original MAC. – CodesInChaos Jun 23 '12 at 13:20
@CodeInChaos Oh dear, you're right, what I wrote was complete tripe. Thanks. I've corrected my answer. – Gilles Jun 23 '12 at 21:40
up vote -1 down vote

All hash functions that take an arbitrary-length input have collisions -- that's what a hash function is. In fact, given equal distribution of values within the hash's output and an infinite range of inputs, it's also possible that there are an infinite number of colliding inputs for any given hash value.

Ideally those collisions are rare and seldom seen, but it's significantly less likely that two colliding strings will have the same length.

Therefore it makes perfect sense to use the hash plus length to uniquely identify a string, and you're not the first person to think that either. However, those two elements alone are probably enough. Including any "plaintext" from the content itself probably doesn't add any measurable value.

share|improve this answer
Collisions are purely theoretical for recommended cryptographic hash functions. No one has ever published a same-length collision on SHA-1 or SHA-2, nor is it generally beleived that one will be revealed soon. – Gilles Jun 23 '12 at 7:59
up vote -2 down vote

It looks an excellent way (mechanism) to reduce/minimize the chances of hash collision. Not very sure of the characteristics and specification of hash algorithms; Mathematically there are some concerns:

  1. if 2 data of same size having same length with the first 2 bytes same produces the same hash, than the logic will fail and so shall the detection of data manipulation detection by the receiver. Yeah AFAIK having such a set of data is practically not possible and even if some one finds them such data shall have no business case .
share|improve this answer
1  
“if 2 data of same size having same length with the first 2 bytes same produces the same hash”, then as far as everyone knows, they are the same. Adding the first two bytes brings zero extra security. In many practical circumstances the first two bytes will be always the same anyway, or at least predictable, because they are imposed by the message format. – Gilles Jun 21 '12 at 17:37
@Gilles +1 Yes this is a good point. – Bernie White Jun 22 '12 at 22:24

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.