Угадай хеш-функцию?

Question

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

Ввод: любая строка
Вывод: 5 шестнадцатеричных символов (0-F)

У меня есть доступ к столько ключей и результатов, сколько я хочу, но я не знаю, как именно я мог бы использовать это для атаки на функцию. Есть ли способ? Если бы я знал какие-либо функции, которые для начала были преобразованы в 5-символьные, я мог бы использовать грубую силу для соли или чего-то еще.

Я знаю, например, что:
а = 06a07
б = bfbb5
с = 63447
(если вы что-то имеете в виду)

При обычном использовании он преобразует случайные 32-символьные строки в 5-символьные.

Answer 1

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

Практически не имеет значения, что ваша функция преобразует 32-символьные строки в 5-символьные хэши; вывод, вероятно, усечен. Для забавы вот несколько вполне законных примеров, последние три из которых криптографически ужасны:

• Используйте алгоритм хеширования MD5 , который генерирует 16-символьный хэш, и используйте от 10 ^th до 14 ^th символов.
• Используйте алгоритм SHA-1 и введите последние 5 символов.
• Если входная строка буквенная, используйте простую подстановку A=1, B=2, C=3, ... и возьмите первые 5 цифр.
• Найдите каждый символ на клавиатуре, измерьте его расстояние от левого края в миллиметрах и используйте все остальные цифры в обратном порядке, начиная с последнего.
• Создайте пользователя stackoverflow , имя которого является 32-битной строкой, разделите 113 на соответствующий идентификационный номер пользователя и возьмите первые 5 цифр после десятичной дроби. (Но не говорите им, что я сказал вам сделать это!)

Answer 2

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

Answer 3

Исходя из только что сделанного мною комментария к Понту Гаггу, предположим, что алгоритм хеширования выглядит следующим образом:

• Добавить некоторую длинную постоянную строку для ввода
• Вычислить хэш SHA-256 результата
• Выведите последние 5 символов хэша.

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

Тем не менее, если бы я знал какие-либо опубликованные 20-битные хеш-функции, то я бы сначала проверил их. Но я не знаю ничего: все обычные нешифрующие строковые хеш-функции являются 32-битными, потому что это ожидаемый размер целочисленного типа. Возможно, вам следует сравнить свои результаты с результатами хэша CRC, PJW и BUZ для одних и тех же строк, а также с некоторыми вариантами хеша DJB с разными простыми числами и любыми хеш-функциями, встроенными в известные языки программирования, такие как java.lang.String.hashCode. Возможно, что 5 выходных символов выбраны из 8 шестнадцатеричных символов, сгенерированных одним из них.

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

Answer 4

Это звучит слегка незаконно.

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

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