Учитывая алгоритм хеширования, есть ли более эффективный способ «хеширования», кроме брутфорса?

Question

Итак, у меня есть код для функции хеширования, и, судя по всему, нет способа просто его хешировать (множество побитовых AND, OR, Shift и т. Д.). Мой вопрос: если мне нужно выяснить исходное значение перед хэшированием, есть ли более эффективный способ, чем просто грубое форсирование набора возможных значений?

Спасибо!

РЕДАКТИРОВАТЬ: я должен добавить, что в моем случае исходное сообщение никогда не будет длиннее, чем несколько символов, для моих целей.

РЕДАКТИРОВАТЬ2: Из любопытства, есть ли способы сделать это на ходу, без предварительно вычисленных таблиц?

Answer 1

Да; Атаки радужного стола .Это особенно верно для хэшей более коротких строк.то есть хеши небольших строк, таких как «true», «false» и т. д., могут храниться в словаре и использоваться в качестве таблицы сравнения.Это значительно ускоряет процесс взлома.Также, если размер хеша короткий (т.е. MD5), алгоритм становится особенно легко взломать.Конечно, способ обойти эту проблему - комбинировать «криптографические соли» с паролями, прежде чем их хешировать.

Существует два очень хороших источника информации по этому вопросу: Код ужаса: Взлом Rainbow Hash и Википедия: Радужный стол

Редактировать: Таблицы Rainbox могут занимать десятки гигабайт, поэтому для их загрузки (или воспроизведения) могут потребоваться недели, чтобы провести простые тесты.Вместо этого, похоже, есть некоторые онлайн-инструменты для обращения простых хешей: http://www.onlinehashcrack.com/ (то есть попробуйте перевернуть 463C8A7593A8A79078CB5C119424E62A, который является MD5-хэшем слова «crack»)

Answer 2

«Unhashing» называется «атакой с прообразом»: при заданном хеш-выходе найдите соответствующий ввод.

Если хеш-функция «безопасна», то нет лучшей атаки, чем попытка возможных вводов, пока не будет найдено попадание; для хеш-функции с n -битным выходом среднее число вызовов хеш-функции будет примерно равно 2 ⁿ , т.е. слишком много для текущей земли- основанная технология, если n больше 180 или около того. Иначе говоря: если для данной хеш-функции найден метод атаки, более быстрый, чем этот метод грубой силы, то хеш-функция считается непоправимо нарушенной.

MD5 считается нарушенным, но для других недостатков ( - это опубликованный метод для прообразов со стоимостью 2 ^123,4 , который таким образом, примерно в 24 раза быстрее, чем затраты на грубую силу - но это все еще настолько технологически невозможно, что это невозможно подтвердить).

Когда известно, что ввод хеш-функции является частью сравнительно небольшого пространства (например, это «пароль», поэтому он может поместиться в мозгу пользователя-человека), тогда можно оптимизировать атаки прообразом, используя предварительно вычисленные таблицы Злоумышленнику по-прежнему приходится оплачивать стоимость поиска один раз, но он может повторно использовать свои таблицы для атаки на несколько экземпляров. Радужные таблицы - это предварительно вычисленные таблицы с сжатым представлением с эффективным использованием пространства: для радужных таблиц узким местом для злоумышленника является мощность процессора, а не размер его жестких дисков.

Answer 3

Это может звучать тривиально, но если у вас есть код для функции хеширования, вы всегда можете переопределить функцию hash() класса контейнера хеш-таблицы (или аналогичную, в зависимости от вашего языка программирования и среды). Таким образом, вы можете хешировать строки, скажем, 3 символа или меньше, а затем вы можете сохранить хеш как ключ, по которому вы получите исходную строку, которая, кажется, именно то, что вы хотите. Используйте этот метод, чтобы построить свой собственный радужный стол, я полагаю. Если у вас есть код для программной среды, в котором вы хотите найти эти значения, вы всегда можете изменить его для хранения хешей в хеш-таблице.

Answer 4

Исходя из «нормального случая», исходное сообщение будет во много раз длиннее хеша.Следовательно, в принципе абсолютно невозможно получить сообщение из хэша, просто потому, что вы не можете вычислить информацию, которой там нет.

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

Наконец, может и не быть необходимости вообще находить хорошее сообщение, пока можно найти то, которое пройдет.Это предмет известной атаки на MD5.Эта атака позволяет создать другое сообщение с одинаковым хешем.
Независимо от того, является ли это проблемой безопасности или нет, зависит от того, для чего именно вы используете хеш.