Перебор по словарю (англ. 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 |
В большинстве паролей наблюдается фонетическое сходство со словами естественного (английского) языка; причина этому заключается в простоте запоминания такого рода информации о данном пароле. Это свойство учитывается в «Марковских фильтрах», основанных на цепи Маркова, которая является стандартной техникой в обработке естественного языка. Наличие неалфавитных символов в пароле можно интерпретировать как применение конечного автомата к определённому набору элементов.
Алфавитный пароль, сгенерированный человеком, неравномерно распределен в пространстве алфавитных последовательностей. Данное условие может быть учтено с большой точностью в «Марковских фильтрах» нулевого и первого порядка:[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 атаки по словарю могут быть предотвращены или усложнены следующими способами:
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-ключ.
Замечания
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .