3

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.

  • For the sake of clarity: Do you have the values of stringA and stringB and what is the length of the string data you are referring to? – DA12C 917 Jan 23 '14 at 7:25
  • these are unknowns the attacker is trying to find, but assume the attacker knows the algorithm / code / everything else. – pacifist Jan 23 '14 at 7:28
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.

  • yeah - I'm aware you can't go from the hash to the source, but in the question I was skipping the pedantics in that if you find a string that gives the same hash in an expected short format (like a password with a fixed format) whilst you can't be sure it's not a collision, much of the time you've actually found the original. – pacifist Jan 23 '14 at 7:26
  • Sorry for the pedantics, I usually prefer adding the basic information if I am not sure if the reader know them. So, are we talking about passwords? has this "BString" something to do with the so called "salt and pepper"? – kiBytes Jan 23 '14 at 7:30
  • nah that's cool. Assume they can be passwords, but of particular formats, somewhat limiting the range of what the input could've been. – pacifist Jan 23 '14 at 7:34
  • As to salts - you can assume they're salted & that the attacker knows the salts, and that they're say, pre-pended to the start before the strings. – pacifist Jan 23 '14 at 7:36
  • Ok, have a look to the edit response, maybe it will give you more insight. – kiBytes Jan 23 '14 at 7:41
1

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.

  • I've upvoted for plenty of detail, and yes, I know about avalache effect, thanks, but I still don't think we've established that birthday attacks on hashA and hashB aren't reduced by an attacker knowing part of the inputs are overlap (i.e. attacker knows precise portions that overlap, this is different to pre-image), and as a result they won't need to try the ordinary number of permutations of both to know working solutions for both hashes. I see references that when parts of hashes are known difficulty decreases from exponential to polynomial, mostly after eprint.iacr.org/2008/075.pdf – pacifist Jan 27 '14 at 23:11

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.