Русская Википедия:Перебор по словарю
Перебор по словарю (Шаблон:Lang-en) — атака на систему защиты, использующая метод полного перебора (Шаблон:Lang-en) предполагаемых паролей, используемых для аутентификации, осуществляемого путём последовательного пересмотра всех слов (паролей в чистом виде или их зашифрованных образов) определённого вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации[1].
Перебор по словарю и сложность пароля
С точки зрения теории вероятностей, выбор пароля детерминирован и закономерен. В качестве пароля могут выступать: дата рождения, имя, предмет, набор цифр, последовательность близко расположенных на клавиатуре букв. В общем случае происходит конкатенация вышеперечисленного.
Результатом данных допущений становится тот факт, что предопределенность в выборе пароля играет ключевую роль в выборе алгоритмов, на которых основан метод перебора по словарю.
Различают два вида атак:
- Online: атаки, в которых единственным способом для атакующего проверить, является ли данный пароль корректным, есть взаимодействие с сервером.
- Offline: атаки, когда атакующий имеет возможность проверить все допустимые пароли, не нуждаясь при этом в обратной связи с сервером.
Возможно вычислить оценку надежности пароля, в частности, определить долю успешных атак по словарю. Вероятностная оценка успеха может определяться как отношение количества взломанных паролей при атаке по словарю к общему числу попыток.
Исторические сведения
Использование Интернет-червя (Шаблон:Lang-en) в 1988 г. предоставляет хорошо документированный случай взлома паролей[2]. Интернет-червь пытался взломать пароли, работая с серией словарей. На первом этапе атаки было использовано множество слов, содержащее имена пользователей, взятых из файла паролей системы Unix. Если это не имело успеха, использовался внутренний словарь 432 общепринятых, используемых в Интернет-жаргоне, слов. Если второй этап не имел успеха, использовался Unix словарь, состоящий из 24474 слов. Червь также проверял на пустой пароль. Сайты, на которые производилась атака, сообщили, что около 50 % паролей было успешно взломано, используя данную стратегию.
Следующим шагом стала работа Даниэля Кляйна (Шаблон:Lang-en)[3]. Чтобы предоставить свои результаты, он собрал шифрованные файлы паролей системы Unix. Эта коллекция содержала примерно 15000 различных пар имя пользователя/пароль (Шаблон:Lang-en). Кляйн сконструировал серию словарей и набор механизмов, позволяющих осуществлять перестановки. Предоставленный им словарь состоял из приблизительно 60000 пунктов. Этот лист включал в себя имена, места, вымышленные ссылки, библейские термины, выражения из поэм У. Шекспира и т. д. После применения стратегии перестановки (использование заглавных букв, очевидные замены, перестановки цифр), он получил пространство паролей, более чем из 3.3 млн возможностей. Использование этого словаря помогло Кляйну взломать 24,2 % всех паролей на определённых серверах.
В 1991—1992 гг. Шаблон:Нп3 (Шаблон:Lang-en) удалось построить, основываясь на статистике, словарь, с помощью которого поддались взлому 20 % паролей на выбранных серверах[4].
В 2000 г. команда исследователей из университета Кембридж провела исследование, в ходе которого была произведена атака на 195 хешированных паролей, из которых 35 % были успешно взломаны[5].
Исследователь(и) / проект | Время | Паролей проверено | Процент нахождения, [%] |
---|---|---|---|
Интернет-червь[2] | 1988 | тысячи | ~50 |
Исследование Кляйна[3] | 1990 | 15000 | 24.2 |
Исследование Шаблон:Нп3[4] | 1992 | 13787 | 20.0 |
Исследователи из университета Кембридж[5] | 2000 | 195 | 35.0 |
Основные принципы построения словаря
В большинстве паролей наблюдается фонетическое сходство со словами естественного (английского) языка; причина этому заключается в простоте запоминания такого рода информации о данном пароле. Это свойство учитывается в «Марковских фильтрах», основанных на цепи Маркова, которая является стандартной техникой в обработке естественного языка. Наличие неалфавитных символов в пароле можно интерпретировать как применение конечного автомата к определённому набору элементов.
Марковские фильтры
Алфавитный пароль, сгенерированный человеком, неравномерно распределен в пространстве алфавитных последовательностей. Данное условие может быть учтено с большой точностью в «Марковских фильтрах» нулевого и первого порядка[6]:
- нулевой порядок модели Маркова: каждый символ генерируется в соответствии со своим вероятностным распределением и независимо от предыдущих символов.
- первый порядок модели Маркова: каждой диграмме (упорядоченной паре) символов присваивается вероятность и каждый символ порождается в условной зависимости от предыдущего.
Математически,
нулевой порядок модели Маркова:
первый порядок модели Маркова:
где <math>P(\cdot)</math> — вероятность распределения последовательности символов, <math>x_i</math> — символ данной последовательности, <math>\nu</math> — частота индивидуального символа или диграммы в тексте.
Для устранения маловероятных строк в словаре применяется дискретизация вероятностей — вводится двухуровневая система с порогом <math>\theta</math>:
нулевой порядок модели Маркова:
первый порядок модели Маркова:
Замечания
- модель Маркова первого порядка показывает лучшие результаты (дает больший процент взлома) по отношению к модели Маркова нулевого порядка. Исключение составляют случаи, когда стратегия выбора пароля использует сокращения, состоящие из первых букв каждого слова в абстрактном предложении;
- распределение частот появления букв в пароле зависит от конкретного языка, для которого составляется словарь (обобщением данного метода является комбинация предполагаемых языков для создания пароля).
Фильтры, использующие конечные автоматы
Для создания конечных автоматов вводятся некоторые ограничения и предположения по отношению к взламываемому паролю:
- в алфавитно-цифровом пароле все цифры расположены в конце;
- первая буква в алфавитном пароле наиболее вероятно заглавная, по сравнению с остальными;
- в алфавитном пароле количество строчных букв больше, чем заглавных.
Детерминированные конечные автоматы являются идеальными средствами для выражений с предложенными ограничениями[6].
Первым этапом построения словаря, основанного на конечных автоматах, является создание последовательности регулярных выражений (\"нижний регистр", \"заглавная буква расположена перед строчными", \"все заглавные расположены перед строчными" и т. д.).
Словарь определяется как множество слов, которые соответствуют Марковским фильтрам и конечному числу регулярных выражений, примененных к ним
Алгоритмы
Модифицированный словарь модели Маркова нулевого порядка
Используемый для построения словаря алгоритм немного отличается от Марковского фильтра нулевого уровня (в данном случае для разных длин слов в словаре будет использоваться различный порог <math>\theta</math>)[6].
Модифицированный словарь определяется как
Перепишем фильтр (словарь) в аддитивной форме
где <math>\mu(x) = \log \nu(x),\, \lambda = \log \theta</math>.
Пусть <math>\{ \alpha : |\alpha| = l', \prod_{x \in \alpha} \nu(x) = \theta' \}</math>. Тогда определим частичные словари <math>D_{\nu, \theta, l, \theta', l'} = \{ \beta : \alpha \beta \in D_{\nu, \theta, l} \}</math>. Заметим, что <math>D_{\nu, \theta, l, \theta', l'}</math> определён, так как <math>\prod_{x \in \alpha \beta} \nu(x) = \prod_{x \in \alpha} \nu(x) \prod_{x \in \beta} \nu(x) = \theta' \prod_{x \in \beta} \nu(x)</math>, поэтому не зависит от выбора <math>\alpha</math>.
Для любого префикса, частичный словарь содержит все возможные последовательности символов, которые могут прилагаться к этому префиксу, поэтому результирующая строка удовлетворяет всем Марковским свойствам.
В общем виде частичный словарь можно записать
Рекурсивный алгоритм для подсчета размера частичного словаря[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_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
}
Замечание
- использование гибридных алгоритмов дает лучшие результаты для криптоанализа методом перебора по словарю[6].
Основные противодействия атакам по словарю
Противодействия online атакам по словарю
Существует несколько способов противостоять online атакам по словарю:
- задержка ответа (Шаблон:Lang-en): для предоставленной пары login/password сервер использует небольшую, специально сгенерированную задержку ответа Yes/no (например, не чаще одного ответа в секунду;
- блокировка учетной записи (Шаблон:Lang-en): учетная запись блокируется после нескольких (заранее установленное число) неудачных попыток ввода login/password (для примера, учетная запись блокируется на час после пяти неправильных попыток ввода пароля);
- использование Proof-of-Work;
- использование соли и медленных хеш-функций на стороне клиента.
Замечания
- данные меры, в большинстве случаев, предотвращают атаку по словарю и сопутствующий взлом пароля за допустимое время;
- данные реализации противодействия online атакам по словарю допускают долговременные блокировки пользовательских аккаунтов при правильном подборе периода атаки.
Протоколы проверки подлинности пользователей
Предполагается, что ввод верной комбинации login/password производится пользователем данной учетной записи, в то время как атака по словарю производится автоматической программой. Требуется, чтобы попытка ввода правильного пароля была «вычислительно простой» для человека, и «вычислительно сложной» для машин.
Протокол представляет собой тест, позволяющий серверу отличить человека от бота. Он был впервые предложен Шаблон:Нп2 и называется обратный тест Тьюринга (Шаблон:Lang-en), другое название для него CAPTCHA. Обратный Тест Тьюринга должен удовлетворять следующим условиям[7]:
- автоматическая генерация;
- простота выполнения для человека;
- сложность для машин;
- малая вероятность угадать ответ.
Тест с использованием изображений удовлетворяет всем вышеперечисленным условиям.
Протокол 1 (комбинация обратного теста Тьюринга с любой системой проверки подлинности)[8]
Пользователя просят ответить на RTT-сообщение перед началом проверки подлинности (перед вводом login/password).
Замечание
Этот метод не оптимален для больших систем, так как ввод пользователем ответа на RTT-тест каждый раз перед аутентификацией достаточно раздражительная и психологически трудная задача[8].
Протокол 2 (пользовательский протокол входа в систему, модифицированная версия протокола 1)[8]
Если пользователь успешно вошел в систему, то сервер посылает в пользовательский компьютер cookie, которые содержат запись об аутентификации пользователя и срок валидности этого сообщения (подразумевается невозможность изменить информацию в cookie, при этом не оповестив об этом сервер. Это может быть гарантированно добавлением MAC (Шаблон:Lang-en), который вычисляется, используя ключ, известный только серверу).
- 1. пользователь вводит login/password. Если его компьютер содержит cookie, предоставленные данным сервером, cookie извлекается сервером;
- 2. проверка подлинности login/password;
- 3. если login/password истинные, тогда
- b. в противном случае сервер генерирует RTT-тест и отправляет его пользователю. Пользователь получает доступ к серверу только после правильного ответа на RTT-запрос;
- 4. если пара login/password некорректна, то
- a. с вероятностью <math>p</math> (где <math>0 \le p \le 1</math> это системный параметр, например <math>p = 0.05</math>), пользователю предлагают пройти RTT-тест и независимо от ответа, доступ к серверу блокируется;
- b. с вероятностью <math>1 - p</math>, немедленно блокируется соединение.
Замечания
- предполагается, что пользователь использует малое число компьютеров и, маловероятно, что атака будет произведена с одного из них;
- процесс входа в систему использует веб-браузер и cookie необходимы;
- алгоритм работы протокола построен так, что процесс генерации RTT-сообщения происходит только в двух случаях: при невалидной записи cookie в компьютере пользователя и при неверной паре login/password. Это позволяет разгрузить серверы, использующие данный протокол;
- вероятность <math>p</math>- есть функция пары login/password. Возможны случаи, когда для фиксированных значений login/password будут происходить или только блокировки учетной записи или только генерации RTT-сообщений при многократной ошибке.
Противодействия offline атакам по словарю
Offline атаки по словарю могут быть предотвращены или усложнены следующими способами:
- добавления в хеширование известной величины — соли (Шаблон:Lang-en)
- использование медленной хеш-функции, напр. scrypt
Аппаратная реализация
Trusted Platform Module (TPM) — представляет собой аппаратный чип, позволяющий компьютерам сохранять безопасность данных. Владение секретной информацией (далее — authData) необходимо для доступа и использования TPM-ключей.
В процессе атаки, криптоаналитик может узнать[9]:
- login для authData и ответ TPM на этот запрос;
- Шаблон:Нп3 (Шаблон:Lang-en), ассоциированный с authData и ответ TPM.
Составление словарей, основанных на полученных сведениях, используется в offline атаке по словарю, с целью определить authData.
Методы борьбы — использование модифицированного криптографического метода Шаблон:Нп3 (Simple Password Exponential Key Exchange), который основан на алгоритме обмена ключами Диффи-Хеллмана (позволяет двум сторонам создать Шаблон:Нп3 <math>s</math> (Шаблон:Lang-en), основываясь на слабом Шаблон:Нп3 <math>w</math> (Шаблон:Lang-en), который они разделяют).
Протокол (модифицированный криптографический метод SPEKE)
1. пользователь исполняет команду <math>d</math>, необходимую для авторизации с authData;
2. пользовательский процесс и TPM включаются в Шаблон:Нп3, используя <math>d</math> как слабый Шаблон:Нп3 <math>w</math>;
3. пользовательский процесс выбирает случайный <math>x</math> и отправляет <math>H(d)^x</math> к TPM, где <math>H</math> — хеш-функция;
4. TPM выбирает случайный <math>y</math> и отправляет <math>H(d)^y</math> пользовательскому процессу;
5. каждый из них высчитывает секрет <math>s = H(d)^{xy}</math>;
6. <math>w</math> заменяется на <math>s</math> как HMAC-ключ.
Замечания
- ограничения, накладываемые на выбор <math>d, w, H, x, y</math> описаны в алгоритме обмена ключами Диффи-Хеллмана;
- выбор хеш-функции <math>H</math> определяется методом шифрования в криптопроцессоре (чип TPM).
- протокол допускает улучшения.[9]
См. также
Примечания
Ссылки
- RFC 2828 – Internet Security Glossary
- RFC 4949 – Internet Security Glossary, Version 2
- Шаблон:Cite web
- Шаблон:Cite web
- Шаблон:Cite web
- Шаблон:Cite web
- Шаблон:Cite web