Перебор по словарю () — атака на систему защиты, использующая метод полного перебора () предполагаемых паролей, используемых для аутентификации, осуществляемого путём последовательного пересмотра всех слов (паролей в чистом виде или их зашифрованных образов) определённого вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации.
Перебор по словарю и сложность пароля С точки зрения теории вероятностей, выбор пароля детерминирован и закономерен. В качестве пароля могут выступать: дата рождения, имя, предмет, набор цифр, последовательность близко расположенных на клавиатуре букв. В общем случае происходит конкатенация вышеперечисленного.
Результатом данных допущений становится тот факт, что предопределенность в выборе пароля играет ключевую роль в выборе алгоритмов, на которых основан метод перебора по словарю.
Различают два вида атак:
Online: атаки, в которых единственным способом для атакующего проверить, является ли данный пароль корректным, есть взаимодействие с сервером. Offline: атаки, когда атакующий имеет возможность проверить все допустимые пароли, не нуждаясь при этом в обратной связи с сервером.
Возможно вычислить оценку надежности пароля, в частности, определить долю успешных атак по словарю. Вероятностная оценка успеха может определяться как отношение количества взломанных паролей при атаке по словарю к общему числу попыток.
Исторические сведения Использование Интернет-червя () в 1988 г. предоставляет хорошо документированный случай взлома паролей. Интернет-червь пытался взломать пароли, работая с серией словарей. На первом этапе атаки было использовано множество слов, содержащее имена пользователей, взятых из файла паролей системы Unix. Если это не имело успеха, использовался внутренний словарь 432 общепринятых, используемых в Интернет-жаргоне, слов. Если второй этап не имел успеха, использовался Unix словарь, состоящий из 24474 слов. Червь также проверял на пустой пароль. Сайты, на которые производилась атака, сообщили, что около 50 % паролей было успешно взломано, используя данную стратегию.
Следующим шагом стала работа Даниэля Кляйна (). Чтобы предоставить свои результаты, он собрал шифрованные файлы паролей системы Unix. Эта коллекция содержала примерно 15000 различных пар имя пользователя/пароль (). Кляйн сконструировал серию словарей и набор механизмов, позволяющих осуществлять перестановки. Предоставленный им словарь состоял из приблизительно 60000 пунктов. Этот лист включал в себя имена, места, вымышленные ссылки, библейские термины, выражения из поэм У. Шекспира и т. д. После применения стратегии перестановки (использование заглавных букв, очевидные замены, перестановки цифр), он получил пространство паролей, более чем из 3.3 млн возможностей. Использование этого словаря помогло Кляйну взломать 24,2 % всех паролей на определённых серверах.
В 1991—1992 гг. () удалось построить, основываясь на статистике, словарь, с помощью которого поддались взлому 20 % паролей на выбранных серверах.
В 2000 г. команда исследователей из университета Кембридж провела исследование, в ходе которого была произведена атака на 195 хешированных паролей, из которых 35 % были успешно взломаны.
+ Таблица: Процент паролей найденных в ходе систематических исследований Исследователь(и) / проект Время Паролей проверено Процент нахождения, [%] Интернет-червь 1988 тысячи ~50 Исследование Кляйна 1990 15000 24.2 Исследование 1992 13787 20.0 Исследователи из университета Кембридж 2000 195 35.0
Основные принципы построения словаря В большинстве паролей наблюдается фонетическое сходство со словами естественного (английского) языка; причина этому заключается в простоте запоминания такого рода информации о данном пароле. Это свойство учитывается в «Марковских фильтрах», основанных на цепи Маркова, которая является стандартной техникой в обработке естественного языка. Наличие неалфавитных символов в пароле можно интерпретировать как применение конечного автомата к определённому набору элементов.
Марковские фильтры Алфавитный пароль, сгенерированный человеком, неравномерно распределен в пространстве алфавитных последовательностей. Данное условие может быть учтено с большой точностью в «Марковских фильтрах» нулевого и первого порядка:
нулевой порядок модели Маркова: каждый символ генерируется в соответствии со своим вероятностным распределением и независимо от предыдущих символов. первый порядок модели Маркова: каждой диграмме (упорядоченной паре) символов присваивается вероятность и каждый символ порождается в условной зависимости от предыдущего.
Математически,
нулевой порядок модели Маркова:
первый порядок модели Маркова:
где — вероятность распределения последовательности символов, — символ данной последовательности, — частота индивидуального символа или диграммы в тексте.
Для устранения маловероятных строк в словаре применяется дискретизация вероятностей — вводится двухуровневая система с порогом :
нулевой порядок модели Маркова:
первый порядок модели Маркова:
Замечания
модель Маркова первого порядка показывает лучшие результаты (дает больший процент взлома) по отношению к модели Маркова нулевого порядка. Исключение составляют случаи, когда стратегия выбора пароля использует сокращения, состоящие из первых букв каждого слова в абстрактном предложении; распределение частот появления букв в пароле зависит от конкретного языка, для которого составляется словарь (обобщением данного метода является комбинация предполагаемых языков для создания пароля).
Фильтры, использующие конечные автоматы Для создания конечных автоматов вводятся некоторые ограничения и предположения по отношению к взламываемому паролю:
в алфавитно-цифровом пароле все цифры расположены в конце; первая буква в алфавитном пароле наиболее вероятно заглавная, по сравнению с остальными; в алфавитном пароле количество строчных букв больше, чем заглавных.
Детерминированные конечные автоматы являются идеальными средствами для выражений с предложенными ограничениями.
Первым этапом построения словаря, основанного на конечных автоматах, является создание последовательности регулярных выражений (\"нижний регистр", \"заглавная буква расположена перед строчными", \"все заглавные расположены перед строчными" и т. д.).
Словарь определяется как множество слов, которые соответствуют Марковским фильтрам и конечному числу регулярных выражений, примененных к ним
Алгоритмы
Модифицированный словарь модели Маркова нулевого порядка Используемый для построения словаря алгоритм немного отличается от Марковского фильтра нулевого уровня (в данном случае для разных длин слов в словаре будет использоваться различный порог ).
Модифицированный словарь определяется как
Перепишем фильтр (словарь) в аддитивной форме
где .
Пусть . Тогда определим частичные словари . Заметим, что определён, так как , поэтому не зависит от выбора .
Для любого префикса, частичный словарь содержит все возможные последовательности символов, которые могут прилагаться к этому префиксу, поэтому результирующая строка удовлетворяет всем Марковским свойствам.
В общем виде частичный словарь можно записать
Рекурсивный алгоритм для подсчета размера частичного словаря:
partial_size1(current_length, level) { if level >= threshold: return 0 if total_length = current_length: return 1
sum = 0 for each char in alphabet sum = sum + partial_size1(current_length+1, level+mu(char)) return sum }
Рекурсивный алгоритм нахождения ключа по словарю (берет в качестве входа индекс в пространстве ключей и возвращает соответствующий ключ):
get_key1(current_length, index, level) { if total_length = current_length: return ""
sum = 0 for each char in alphabet new_level = level + mu(char) // looked up from precomputed array size = partial_size1[current_length+1][new_level] if sum + size > index // ’|’ refers to string concatenation return char | get_key1(current_length+1, index-sum, new_level)
sum = sum + size
// control cannot reach here print "index larger than keyspace size"; exit }
Замечания
partial_size1 вычисляется только один раз (а не один раз для каждого ключа); get_key1 вычисляется в процессе криптоанализа; чтобы просмотреть все пространство ключей, необходимо запустить get_key1 с current_length = 0, и level = 0.
Словарь модели Маркова первого порядка Как и в случае метода нулевого порядка, определяются частичные словари.
После просмотра строки в частичном словаре, необходимо побеспокоиться о последнем символе (учет диграммы и её распределения)
partial_size2(current_length, prev_char, level) { if level >= threshold: return 0 if total_length = current_length: return 1
sum = 0 for each char in alphabet if current_length = 0 new_level = mu(char) else new_level = level + mu(prev_char, char)
sum = sum + partial_size2(current_length+1, char, new_level)
get_key2(current_length, index, prev_char, level) { if total_length = current_length: return ""
sum = 0 for char in alphabet if current_length = 0 new_level = mu(char) else new_level = level + mu(prev_char, char)
size = partial_size2(current_length+1, char, new_level) if sum + size > index return char | get_key2(current_length+1, index-sum, char, new_level)
sum = sum + size // control cannot reach here print "index larger than keyspace size"; exit }
Замечание
использование гибридных алгоритмов дает лучшие результаты для криптоанализа методом перебора по словарю.
Основные противодействия атакам по словарю
Противодействия online атакам по словарю Существует несколько способов противостоять online атакам по словарю: задержка ответа (): для предоставленной пары login/password сервер использует небольшую, специально сгенерированную задержку ответа Yes/no (например, не чаще одного ответа в секунду; блокировка учетной записи (): учетная запись блокируется после нескольких (заранее установленное число) неудачных попыток ввода login/password (для примера, учетная запись блокируется на час после пяти неправильных попыток ввода пароля); использование Proof-of-Work; использование соли и медленных хеш-функций на стороне клиента.
Замечания
данные меры, в большинстве случаев, предотвращают атаку по словарю и сопутствующий взлом пароля за допустимое время; данные реализации противодействия online атакам по словарю допускают долговременные блокировки пользовательских аккаунтов при правильном подборе периода атаки.
Протоколы проверки подлинности пользователей Предполагается, что ввод верной комбинации login/password производится пользователем данной учетной записи, в то время как атака по словарю производится автоматической программой. Требуется, чтобы попытка ввода правильного пароля была «вычислительно простой» для человека, и «вычислительно сложной» для машин.
Протокол представляет собой тест, позволяющий серверу отличить человека от бота. Он был впервые предложен и называется обратный тест Тьюринга (), другое название для него CAPTCHA. Обратный Тест Тьюринга должен удовлетворять следующим условиям:
автоматическая генерация; простота выполнения для человека; сложность для машин; малая вероятность угадать ответ.
Тест с использованием изображений удовлетворяет всем вышеперечисленным условиям.
Протокол 1 (комбинация обратного теста Тьюринга с любой системой проверки подлинности)
Пользователя просят ответить на RTT-сообщение перед началом проверки подлинности (перед вводом login/password).
Замечание
Этот метод не оптимален для больших систем, так как ввод пользователем ответа на RTT-тест каждый раз перед аутентификацией достаточно раздражительная и психологически трудная задача.
Протокол 2 (пользовательский протокол входа в систему, модифицированная версия протокола 1)