Hashes of overlapping data - does it make them easier to crack even when neither is cracked

Question

Say I have strings: stringA, StringB, stringC.

And I make two hashes: HashA = sha256(stringA + stringB) HashB = sha256(stringB + stringC)

For the sake of the argument I'm suggesting sha256 but answering the question generically is just as good.

I'm not a strong mathematician, but suppose I were, and am trying to reverse the above hashes, and knew from an algorithm in code that there is a stringB (still unknown to me) that is the later part of the string going into HashA and the earlier part of HashB.

Can I reduce the number of permutations required, in order to figure out what stringB might have been, since in order for the two hashes to give the answers they do, from overlapping input, should it not reduce the input-space I need to bruteforce?

i.e. are the hashes weaker because of this behaviour of having the data within them overlap.

For clarity: If stringA, stringB, stringC, and stringD are secrets.

And an attacker gets all the code / algorthm etc except for the strings, and has:

case A: hashA=sha256(stringA+stringB) and hashB=(stringB+stringC)

or case B: hashC=sha256(stringA+stringB) and hashD=(stringC+stringD)

I have a suspicion that in case A it's easier to construct source data to match the hashes than in caseB, but I don't know enough maths to back up my suspicion.

Further clarity: Assume the strings are salted, though with the same salt per record and hashes for that record, and that the attacker knows the salts. The salts can be assumed prepended before the 'stringx+stringY' throughtout my text if you like.

Thanks.

Answer 1

I will try to put it in simple words.

Ok, first is first, hashing is a one way only algorithm. You can only go from the source to the hash and never from the hash to the source. I mean, the hash string does not have all the original information so we can't extract it. The only way to guess if an information coincide with a hash is hashing the information and comparing it against the original hash. And even in this way we will never be sure since two hash strings may collide.

[Edit after your clarification] The CaseB is clearly more secure:

1. Consider than in CaseA you will only need to brute force the full space once, the second time you will need to brute force only half of the space (just the StringC part).
2. In CaseB you will need to brute force two times.

The full space in CaseB is N^(length(a)+length(b))+N^(length(c)+length(d), the full space in case A is N^(length(a)+length(b)+N^(length(c)) where N is the number of valid chars.

But there will be no shortcuts to find "StringB" in the case A just because it is used when computing all the hashes. You will have to bruteforce it along the StringA or along with StringB (and then you will need to know the exact length of each string and so on...)

Just as a side note... I am thinking that you may be referring to a problem with ECB block cipher mode encryption, that will be a different problem and you will have a very different response. Consider having a look to this wikipedia page.

Answer 2

From your previous answer to my question:

1. We don't know string length.
2. We don't have value of any string literal.
3. We want to deduce the string values from known Hash values, algorithm and fact that stringB overlaps.

Fact:

1. We have to resort to Brute-Force attack method to compute Hash for test values of stringA, stringB and stringC to compare with known Hash values.

Assumptions:

Since you mentioned keywords "password" & "salt" lets assume the following:

1. Password limit is 8 characters.
2. 52 English alphabets (both upper and lower case), 0-9 digits and '!','@','#','$','%','^','&','*','(',')' are permissible values.
3. Salt value contains 43 characters.
4. 52 English alphabets (both upper and lower case), 0-9 digits are permissible values.
5. stringA and stringC are passwords whereas stringB is salt.

Deduction:

1. To Brute-Force hashA
   • For 8 character password with (52+10+10)=72 possible repetitive values, we will have 72^8 permutations.
   • For 43 character salt with (52+10)= 62 possible repetitive values, we will have 62^43 permutations.
   • Total possibilities = (62^43) X (72^8)

2.Now lets Brute Force the hashB

• For 8 character password with (52+10+10)=72 possible repetitive values, we will have 72^8 permutations.
• For 43 character salt with (52+10)= 62 possible repetitive values, we will have 62^43 permutations.
• Total possibilities = (62^43) X (72^8)

But hey, wait a minute... Didn't we know that stringB overlaps ! Yes we did, but it does not make much of the difference as in any case we have to test for each value of stringB with stringC to brute-force hashB.

Conclusion:

Knowing the hash values and fact that part of the string overlaps in different source strings does not make life easier for the simple reason that we will have to perform brute-force on individual source data - resultant hash value pair.

'Avalanche Effect' ... does it ring any bell ? No ... ?

Proof:

Please go through this link

Even though the input 2 and input 3 differ by a single character the resultant hash value sticks to property of defense against preimage attack and does not reveal anything about the apparent similarity between source data.

As a result the attacker will have to try all possible character values for each character place.

Hope this helps!

PS: Pardon the pedantic approach, but I have tried to keep scenario as simplistic and theoretical as possible. And goes without saying that if you find the answer incorrect by any means hesitate not to bring to notice.