Hash attack: find strings of length 2^N with same hashCode()

Andreas' and Glains' answers are both correct, but they aren't quite what you need if your goal is to produce 2^N distinct strings of length 2N.

Rather, a simpler approach is to build strings consisting solely of concatenated sequences of Aa and BB. For length 2×1 you have { Aa, BB }; for length 2×2 you have { AaAa, AaBB, BBAa, BBBB }, for length 2×3 you have { AaAaAa, AAaaBB, AaBBAa, AaBBBB, BBAaAa, BBAaBB, BBBBAa, BBBBBB }; and so on.

(Note: you've quoted the text as saying the strings should have length 2^N. I'm guessing that you misquoted, and it's actually asking for length 2N; but if it is indeed asking for length 2^N, then you can simply drop elements as you proceed.)

"Strong hint" explained.

Strong hint: Aa and BB have the same value.

In ASCII / Unicode, B has a value 1 higher than A. Since those are the second last characters, the value is multiplied by 31, so hash code is increased by 31 when you change xxxxAa to xxxxBa.

To offset that, you need last character to offset by -31. Since lowercase letters are 32 higher than uppercase letters, changing a to A is -32 and changing one letter up to B is then -31.

So, it get same hash code, change second-last letter to next letter (e.g. A to B), and change last letter from lowercase to next uppercase (e.g. a to B).

You can now use that hint to generate up to 26 strings with the same hash code.

Lets take a look at the hashCode() implementation and the given hint:

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++)
        hash = (hash * 31) + charAt(i);
    return hash;
}

We know that Aa and BB produce the same hash and we can easily verify that:

• (65 * 31) + 97 = 2112
• (66 * 31) + 66 = 2112

From here on, hash is the same for both inputs. That said, we can easily append any amount of characters to both strings and you will always receive the same value.

One example could be:

• hashCode("AaTest") = 1953079538
• hashCode("BBTest") = 1953079538

So, you can generate enough hash values by just appending the same sequence of characters to both strings, more formally:

hashCode("Aa" + x") = hashCode("BB" + x)

Another note on your idea to generate all possible strings and search for duplicates. Have a look at the bithday paradox and you will note that it will take much less to find duplicate hash values for different inputs.

• It will be very difficult to find the original hashed value (indeed, you would have to try out all possible inputs if the hash algorithm is good).
• Duplicate hash values are rare (there have to be duplicates since the hash has a fixed length). If a duplicate is found, the duplicate should be meaningless (random characters), so it cannot be abused by an attacker.

Taking a closer look at the hash function, it works like a number system (e.g. Hexadecimal) where the weight of the digits is 31. That is, think of it as converting a number to base 31 and that makes your final hash code something like hashCode = (31^n) * first-char + (31^n-1) * second-char + ..... + (31^0) * last-char

The second observation is that the ASCII distance between the capital and the small letter is 32. Explained in terms of the hash function, it means that when you replace a capital letter by a small one, it means you are adding 1 more to the higher digit and 1 to your current digit. For example:

BB = (31)(B) + (31^0)B which also equals (31)*(B - 1) + (31^0)*(31 + B) notice that I have just taken one unit from the higher digit and added to the lower digit without changing the overall value. The last equation equals to (31)*(A) + (a) == Aa

So, to generate all of the possible String of a given hash code, start with the initial String and shift the character from right to left by replacing a small character by the capital one while decreasing one from the higher location (where applicable). You can run this in O(1)

Hope this helps.