Аномалии выхода хэш-криптографической функции - PullRequest
Новая
       28

Аномалии выхода хэш-криптографической функции

0 голосов
/ 06 декабря 2011

Кто-нибудь знает, есть ли у MD5, Whirlpool, SHA [n] и т. Д. Какие-либо «специальные» входные данные, которые могут привести к выводу hexdigest для выравнивания в:

  • Все цифры
  • Все буквенные символы
  • Все одинаковые символы / шаблоны повторяются последовательно или полностью

Пример на python: 

>>> from hashlib import sha1
>>> hash = sha1('magic_word').hexdigest()
>>> hash
4040404040404040404040404040404040404040
>>> hash = sha1('^3&#b d   *#"').hexdigest()
aedefeebadcdccebefadcedddcbeadaedcbdeadc

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

Но иногда я задаюсь вопросом, когда при тестировании на столкновения могут возникать подобные случаи ...

Ответы [ 3 ]

3 голосов
/ 06 декабря 2011

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

Выбрасывая 16-стороннюю кость 40 раз (для каждого входа), мы получаем достаточно вывода для оракула, подобного SHA-1. (Для MD5 нам нужно всего 32 раза.)

Таким образом, мы можем вычислить вероятность «40 раз только буквы» как (6/16) ^ 40 ≈ 9,15 · 10 ^ -18, «40 раз только цифры» имеет вероятность (10/16) ^ 40 ≈ 6,8 · 10 ^ -9.

Поскольку «количество попыток, необходимых до первого успеха» распределено геометрически, нам нужно в среднем 1 / р попыток, то есть около 10 ^ 17 попыток «только букв» и 1,5 · 10 ^ 8 попыток «только цифр» ».

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

1 голос
/ 06 декабря 2011

Я уверен, что при правильном вводе возможны такие выходы. Почему это имеет значение? Просто любопытно?

0 голосов
/ 06 декабря 2011

Да, это возможно.При правильном вводе любой желаемый битовый шаблон может быть выведен.Тем не менее, может потребоваться несколько миллионов лет, чтобы найти правильный вход.

Для достаточно широкой цели, такой как весь гекс 0-9 или весь гекс после, это должно быть относительно легко.Расчет доли приемлемых выходов во всех возможных выходах поможет вам получить оценку времени работы.Грубая сила или случайный поиск в конечном итоге найдут то, что попадает в цель.Для сломанного хеша, такого как MD4, вы можете сократить время ожидания.

...