19-10-2023
Перебор по словарю (англ. dictionary attack) — атака на систему защиты, использующая метод полного перебора (англ. brute-force) предполагаемых паролей, используемых для аутентификации, осуществляемого путем последовательного пересмотра всех слов (паролей в чистом виде или их зашифрованных образов) определенного вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации.[1] Данное мероприятие, в большинстве случаев, имеет негативный характер, противоречащий моральным и законодательным нормам.
Содержание |
С точки зрения теории вероятности, выбор пароля детерминирован и закономерен. В качестве пароля могут выступать: дата рождения, имя, предмет, набор цифр, последовательность близко расположенных на клавиатуре букв. В общем случае происходит конкатенация вышеперечисленного.
Результатом данных допущений становится тот факт, что предопределенность в выборе пароля играет ключевую роль в выборе алгоритмов, на которых основан метод перебора по словарю.
Различают два вида атак:
Возможно вычислить оценку надежности пароля, в частности, определить долю успешных атак по словарю. Вероятностная оценка успеха может определяться как отношение количества взломаных паролей при атаке по словарю к общему числу попыток.
Использование Интернет-червя (англ. Internet Worm) в 1988 г. предоставляет хорошо документированный случай взлома паролей.[2] Интернет-червь пытался взломать пароли, работая с серией словарей. На первом этапе атаки было использовано множество слов, содержащее имена пользователей, взятых из файла паролей системы Unix. Если это не имело успеха, использовался внутренний словарь 432 общепринятых, используемых в Интернет-жаргоне, слов. Если второй этап не имел успеха, использовался Unix словарь, состоящий из 24474 слов. Червь также проверял на пустой пароль. Сайты, на которые производилась атака, сообщили, что окола 50 % паролей было успешно взломано, используя данную стратегию.
Следующим шагом стала работа Даниэля Кляйна (англ. Daniel Klein).[3] Чтобы предоставить свои результаты, он собрал шифрованные файлы паролей системы Unix. Эта коллекция содержала примерно 15000 различных пар имя пользователя/пароль (англ. login/password). Кляйн сконструировал серию словарей и набор механизмов, позволяющих осуществлять перестановки. Предоставленный им словарь состоял из приблизительно 60000 пунктов. Этот лист включал в себя имена, места, вымышленные ссылки, библейские термины, выражения из поэм У. Шекспира и т. д. После применения стратегии перестановки (использование заглавных букв, очевидные замены, перестановки цифр), он получил пространство паролей, более чем из 3.3 млн возможностей. Использование этого словаря помогло Кляйну взломать 24,2 % всех паролей на определенных серверах.
В 1991—1992 гг. Евгению Спаффорду (англ.)русск. (англ. Eugene Spafford) удалось построить, основываясь на статистике, словарь, с помощью которого поддались взлому 20 % паролей на выбранных серверах.[4]
В 2000 г. команда исследователей из университета Кембридж провела исследование, в ходе которого была произведена атака на 195 хешированных паролей, из которых 35 % были успешно взломаны.[5]
Исследователь(и) / проект | Время | Паролей проверено | Процент нахождения, [%] |
---|---|---|---|
Интернет-червь[2] | 1988 | тысячи | ~50 |
Исследование Кляйна[3] | 1990 | 15000 | 24.2 |
Исследование Спаффорда (англ.)русск.[4] | 1992 | 13787 | 20.0 |
Исследователи из университета Кембридж[5] | 2000 | 195 | 35.0 |
В большинстве паролей наблюдается фонетическое сходство со словами естественного (английского) языка; причина этому заключается в простоте запоминания такого рода информации о данном пароле. Это свойство учитывается в «Марковских фильтрах», основанных на цепи Маркова, которая является стандартной техникой в обработке естественного языка. Наличие неалфавитных символов в пароле можно интерпретировать как применение конечного автомата к определенному набору элементов.
Алфавитный пароль, cгенерированный человеком, неравномерно распределен в пространстве алфавитных последовательностей. Данное условие может быть учтено с большой точностью в «Марковских фильтрах» нулевого и первого порядка:[6]
Математически,
нулевой порядок модели Маркова:
первый порядок модели Маркова:
где — вероятность распределения последовательности символов, — символ данной последовательности, — частота индивидуального символа или диграммы в тексте.
Для устранения маловероятных строк в словаре применяется дискретизация вероятностей — вводится двухуровневая система с порогом :
нулевой порядок модели Маркова:
первый порядок модели Маркова:
Замечания
Для создания конечных автоматов вводятся некоторые ограничения и предположения по отношению к взламываемому паролю:
Детерминированные конечные автоматы являются идеальными средствами для выражений с предложенными ограничениями.[6]
Первым этапом построения словаря, основанного на конечных автоматах, является создание последовательности регулярных выражений (\"нижний регистр", \"заглавная буква расположена перед строчными", \"все заглавные расположены перед строчными" и т. д.). Словарь определяется как множество слов, которые соответствуют Марковским фильтрам и конечному числу регулярных выражений, примененных к ним
Используемый для построения словаря алгоритм немного отличается от Марковского фильтра нулевого уровня (в данном случае для разных длин слов в словаре будет использоваться различный порог ).[6]
Модифицированный словарь определяется как
Перепишем фильтр (словарь) в аддитивный форме
где .
Пусть . Тогда определим частичные словари . Заметим, что определен, так как , поэтому не зависит от выбора .
Для любого префикса, частичный словарь содержит все возможные последовательности символов, которые могут прилагаться к этому префиксу, поэтому результирующая строка удовлетворяет всем Марковским свойствам.
В общем виде частичный словарь можно записать
Рекурсивный алгоритм для подсчета размера частичного словаря[6]
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 }
Рекурсивный алгоритм нахождения ключа по словарю (берет в качестве входа индекс в пространстве ключей и возвращает соответствующий ключ)[6]
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_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 атакам по словарю:
Замечания
Предполагается, что ввод верной комбинации login/password производится пользователем данной учетной записи, в то время как атака по словарю производится автоматической программой. Требуется, чтобы попытка ввода правильного пароля была «вычислительно простой» для человека, и «вычислительно сложной» для машин.
Протокол представляет собой тест, позволяющий серверу отличить человека от бота. Он был впервые предложен М. Наором (англ. Moni Naor) и называется обратный тест Тьюринга (англ. Reverse Turing test (RTT)), другое название для него CAPTCHA. Обратный Тест Тьюринга должен удовлетворять следующим условиям:[7]
Тест с использованием изображений удовлетворяет всем вышеперечисленным условиям.
Протокол 1 (комбинация обратного теста Тьюринга с любой системой проверки подлинности)[8]
Пользователя просят ответить на RTT-сообщение перед началом проверки подлинности (перед вводом login/password).
Замечание
Этот метод не оптимален для больших систем, так как ввод пользователем ответа на RTT-тест каждый раз перед аутентификацией достаточно раздражительная и психологически трудная задача.[8]
Протокол 2 (пользовательский протокол входа в систему, модифицированная версия протокола 1)[8]
Если пользователь успешно вошел в систему, то сервер посылает в пользовательский компьютер cookie, которые содержат запись об аутентификации пользователя и срок валидности этого сообщения (подразумевается невозможность изменить информацию в cookie, при этом не оповестив об этом сервер. Это может быть гарантированно добавлением MAC (англ. message authentication code), который вычисляется, используя ключ, известный только серверу).
- 1. пользователь вводит login/password. Если его компьютер содержит cookie, предоставленные данным сервером, cookie извлекается сервером;
- 2. проверка подлинности login/password;
- 3. если login/password истинные, тогда
- b. в противном случае сервер генерирует RTT-тест и отправляет его пользователю. Пользователь получает доступ к серверу только после правильного ответа на RTT-запрос;
- 4. если пара login/password некорректна, то
- a. с вероятностью (где это системный параметр, например ), пользователю предлагают пройти RTT-тест и не зависимо от ответа, доступ к серверу блокируется;
- b. с вероятностью , немедленно блокируется соединение.
Замечания
Offline атаки по словарю могут быть предотвращены, в большинстве случаев, добавлением известной величины — соли (англ. salt).
Trusted Platform Module (TPM) — представляет собой аппаратный чип, позволяющий компьютерам сохранять безопасность данных. Владение секретной информацией (далее — authData) необходимо для доступа и использования TPM-ключей.
В процессе атаки, криптоаналитик может узнать:[9]
Составление словарей, основанных на полученных сведениях, используется в offline атаке по словарю, с целью определить authData.
Методы борьбы — использование модифицированного криптографического метода SPEKE (англ.)русск. (Simple Password Exponential Key Exchange), который основан на алгоритме обмена ключами Диффи-Хеллмана (позволяет двум сторонам создать общий секрет (англ.)русск. (англ. strong shared secret), основываясь на слабом общем секрете (англ.)русск. (англ. weak secret), который они разделяют).
Протокол (модифицированный криптографический метод SPEKE)
1. пользователь исполняет команду , необходимую для авторизации с authData;
2. пользовательский процесс и TPM включаются в SPEKE-протокол (англ.)русск., используя как слабый общий секрет (англ.)русск. ;
3. пользовательский процесс выбирает случайный и отправляет к TPM, где — хеш-функция;
4. TPM выбирает случайный и отправляет пользовательскому процессу;
5. каждый из них высчитывает секрет ;
6. заменяется на как HMAC-ключ.
Замечания
Перебор по словарю.