Хэш-атака: найти строки длиной 2 ^ N с таким же hashCode () - PullRequest
Новая
       40

Хэш-атака: найти строки длиной 2 ^ N с таким же hashCode ()

0 голосов
/ 23 декабря 2018

Чтение алгоритмов четвертого издания Роберта Седжвика и Кевина Уэйна. Я нашел следующий вопрос:

Хеш-атака: найдите 2 ^ N строк, каждая длиной 2 ^ N, которые имеют одинаковый hashCode (), предполагая, что реализация hashCode () для String имеет следующий вид: 

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

Сильная подсказка: Aa и BB имеют одинаковое значение.

Что мне приходит в голову - это генерировать все возможные строки длиной 2 ^ N и сравнивать их хэш-коды.Это, однако, очень дорого для большого N, и я сомневаюсь, что это правильное решение.Можете ли вы дать мне подсказки, что я скучаю по всей картине?

Ответы [ 4 ]

0 голосов
/ 24 декабря 2018

Если присмотреться к хэш-функции, она работает как система счисления (например, шестнадцатеричная), где вес цифр равен 31. То есть, думайте, что это преобразование числа в основание 31, и это делает ваш окончательный хешкод наподобие hashCode = (31^n) * first-char + (31^n-1) * second-char + ..... + (31^0) * last-char

Второе наблюдение состоит в том, что расстояние ASCII между заглавной и строчной буквой равно 32. Объясняется в терминах хэш-функции, это означает, что когда вы заменяете заглавную букву маленькойодин, это означает, что вы добавляете еще 1 к старшей цифре и 1 к вашей текущей цифре.Например:

BB = (31)(B) + (31^0)B, что также равно (31)*(B - 1) + (31^0)*(31 + B), обратите внимание, что я только что взял одну единицу из старшей цифры и добавил к младшей цифре без изменения общего значения.Последнее уравнение равно (31)*(A) + (a) == Aa

Итак, чтобы сгенерировать всю возможную строку заданного хеш-кода, начните с начальной строки и сдвиньте символ справа налево, заменив маленький символ на заглавнуюодин, уменьшая один из более высокого местоположения (где применимо).Вы можете запустить это в O (1)

Надеюсь, это поможет.

0 голосов
/ 23 декабря 2018

Давайте посмотрим на реализацию hashCode() и данный намек: 

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

Мы знаем, что Aa и BB производят одинаковые hash, и мы можем легко проверить, что:

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

С этого момента hash одинаково для обоих входов.Тем не менее, мы можем легко добавить любое количество символов в обе строки, и вы всегда получите одно и то же значение.

Один из примеров может быть:

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

Итак, вы можете сгенерировать достаточно хеш-значений, просто добавив одну и ту же последовательность символов к обеим строкам, более формально: 

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

Еще одна заметка на вашемИдея генерировать все возможные строки и искать дубликаты.Взгляните на парадокс bithday , и вы заметите, что найти дублирующиеся хеш-значения для разных входных данных будет гораздо меньше.

  • Будет очень трудно найти исходное хэшированное значение (действительно, вам придется попробовать все возможные входные данные, если алгоритм хеширования хорош).
  • Дублирующиеся хеш-значенияредко (должны быть дубликаты, поскольку хеш имеет фиксированную длину).Если дубликат найден, он должен быть бессмысленным (случайные символы), поэтому злоумышленник не может его использовать.
0 голосов
/ 23 декабря 2018

Ответы Андреаса и Глейнса верны, но они не совсем то, что вам нужно, если ваша цель - создать 2 N отдельных строк длиной 2 N .

Скорее, более простой подход заключается в построении строк, состоящих исключительно из сцепленных последовательностей Aa и BB.Для длины 2 × 1 у вас есть {Aa, BB};для длины 2 × 2 у вас есть {AaAa, AaBB, BBAa, BBBB}, для длины 2 × 3 у вас есть {AaAaAa, AAaaBB, AaBBAa, AaBBBB, BBAaAa, BBAaBB, BBBBAa, BBBBBB};и т. д.

(Примечание: вы процитировали текст, в котором говорилось, что строки должны иметь длину 2 N . Я предполагаю, что вы неправильно процитировали, ина самом деле он запрашивает длину 2 N , но если он действительно запрашивает длину 2 N , тогда вы можете просто отбросить элементы по мере продвижения.)

0 голосов
/ 23 декабря 2018

Объяснен «Сильный намек».

Сильный намек: Aa и BB имеют одинаковое значение.

В ASCII / Unicode, B имеет значение 1выше A.Так как это вторые последние символы, значение умножается на 31, поэтому хеш-код увеличивается на 31 при изменении xxxxAa на xxxxBa.

Чтобы сместить это, вам нужно последнийсмещение символа на -31.Поскольку строчные буквы на 32 больше заглавных, изменение a на A равно -32, а изменение одной буквы на B означает -31.

Таким образом, он получает тот же хэш-кодизмените вторую последнюю букву на следующую букву (например, A на B) и измените последнюю букву с строчной на следующую заглавную (например, a на B).

Теперь вы можете использоватьэтот совет для генерации до 26 строк с одинаковым хеш-кодом.

...