То есть, для массового взлома даже прямой перебор выгоднее таблиц!
Если вернуться к цифрам, то прямой перебор с подобной оптимизацией займет около месяца на том же железе, или несколько дней на видеокартах.
При переборе, считаем от полученного значения свертку == j, смотрим checkup[j], если там 0, то смысла искать такое значение в наборе нет (это проверяется за O(1)). Иначе используем двоичный поиск, который справляется уже за O(log(N)).
В основе поиска лежит простая фильтрация, не пытаться искать те хеши, которые мы заведомо не найдем. Создаем массив битовых значений (checkup) размером SIZE, где-то сотню мегабайт и строим функцию, которая отображает хеш-значение в индекс этого массива. Как ни странно, такой объект тоже называется хеш-функцией, только не криптографической, и частенько его называют сверткой. Для каждого хеша из LinkedIn мы вычисляем свертку, и записываем «1» в соответствующие биты массива checkup.
И поиск операция, которую в данном случае довольно оптимизировать. Забегая вперед, в своей программе я добился O(1) поиска даже на таких больших базах.
Нужно взять каждую строчку из набора {a..z0..9}^8, посчитать ее хеш, и поискать в базе хеш-значений, которые в данном случае LinkedIn заботливо нам предоставил.
Прямой перебор же несколько отличается от радужных таблиц для массового взлома он легко оптимизируется на предмет поиска перебираемых значений в больших наборах хеш-значений.
Однако хороший набор радужных таблиц поможет восстановить пароль к одному хеш-значению за минуты (при учете тех же скромных ограничений в 8-9 символов длины).
Это где-то 10 лет. Поэтому, наш божественный дар в данном случае нельзя считать и скромным подарком.
Возможности оптимально искать сразу несколько паролей к разным хеш-значениям не существует; для каждого хеша требуется строить отдельную радужную цепочку и искать ее в таблице. Таким образом, нам понадобится примерно 5.7 миллионов минут на поиск.
Время, необходимое на поиск пароля к одному хеш-значению по таким таблицам около минуты. За это время необходимо выполнить chain_length по тем самым 100Gb.
Почему? Возьмем набор хиленьких радужных таблиц размером в , которые способны с вероятностью в 98% восстановить любой пароль до 8 алфавитно-цифровых символов одного регистра. К слову, такие таблицы можно сгенерить где-то за пару месяцев на довольно-таки мощной машине, но пусть они у нас уже будут, как некий божественный дар.
Небольшой ликбез. Многие верят в чудесные свойства радужных таблиц, якобы они «что-то способное сломать все и сразу». Это огромное заблуждение, более того, для массового аудита (тысячи или миллионы хешей) они непригодны вовсе. Поэтому забудьте фразу «взломщик же может сгенерировать радужную таблицу!».
Частотный анализ.
Атака по словарям (с правилами);
Но начнем по порядку. Представьте, что вам попадается база из 6.5 миллионов хешей (уникальных всего 5 787 239), какие способы восстановить максимальное количество паролей за разумное (скажем 7 дней) время существуют?
И так, за час удалось «восстановить» около 2.5 миллионов паролей на средней рабочей конфигурации, без специальных словарей и радужных таблиц. Среди найденных паролей присутствуют 16-символьные алфавитно-цифровые комбинации, и далеко не в единственном экземпляре.
Неделю назад , для других это событие может быть примечательным само по себе, но для меня, в первую очередь, это означает возможность провести анализ современных возможностей взлома паролей. И я не собираюсь рассказывать о том сколько раз слово «password» было встречено среди паролей и о том, сколько времени занимает перебор шестисимвольных комбинаций. Скорее буду пугать пользователей тем, насколько сложные пароли можно «взломать» за несколько часов. А программистам расскажу как это возможно эффективно реализовать, и в качестве небольшого подарка приложу программу, которую я написал для массового аудита. Присутствует и некоторый ликбез по использованию радужных таблиц с простыми выводами.
Анализ возможностей массового аудита на основе утечки хешей из LinkedIn
Анализ возможностей массового аудита на основе утечки хешей из LinkedIn / Хабрахабр
Комментариев нет:
Отправить комментарий