Перебор по словарю

Перебор по словарю (Шаблон: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]:

нулевой порядок модели Маркова: каждый символ генерируется в соответствии со своим вероятностным распределением и независимо от предыдущих символов.
первый порядок модели Маркова: каждой диграмме (упорядоченной паре) символов присваивается вероятность и каждый символ порождается в условной зависимости от предыдущего.

Математически,

нулевой порядок модели Маркова:

P (α) = \prod_{x \in α} ν (x),

первый порядок модели Маркова:

P (x_{1} x_{2} \dots x_{n}) = ν (x_{1}) \prod_{i = 1}^{n - 1} ν (x_{i + 1} ∣ x_{i}),

где $P (\cdot)$ — вероятность распределения последовательности символов, $x_{i}$ — символ данной последовательности, $ν$ — частота индивидуального символа или диграммы в тексте.

Для устранения маловероятных строк в словаре применяется дискретизация вероятностей — вводится двухуровневая система с порогом $θ$ :

нулевой порядок модели Маркова:

D_{ν, θ} = {α : \prod_{x \in α} ν (x) \geq θ},

первый порядок модели Маркова:

D_{ν, θ} = {x_{1} x_{2} \dots x_{n} : ν (x_{1}) \prod_{i = 1}^{n - 1} ν (x_{i + 1} ∣ x_{i}) \geq θ} .

Замечания

модель Маркова первого порядка показывает лучшие результаты (дает больший процент взлома) по отношению к модели Маркова нулевого порядка. Исключение составляют случаи, когда стратегия выбора пароля использует сокращения, состоящие из первых букв каждого слова в абстрактном предложении;
распределение частот появления букв в пароле зависит от конкретного языка, для которого составляется словарь (обобщением данного метода является комбинация предполагаемых языков для создания пароля).

Фильтры, использующие конечные автоматы

Для создания конечных автоматов вводятся некоторые ограничения и предположения по отношению к взламываемому паролю:

в алфавитно-цифровом пароле все цифры расположены в конце;
первая буква в алфавитном пароле наиболее вероятно заглавная, по сравнению с остальными;
в алфавитном пароле количество строчных букв больше, чем заглавных.

Детерминированные конечные автоматы являются идеальными средствами для выражений с предложенными ограничениями^[6].

Первым этапом построения словаря, основанного на конечных автоматах, является создание последовательности регулярных выражений (\"нижний регистр", \"заглавная буква расположена перед строчными", \"все заглавные расположены перед строчными" и т. д.).

Словарь определяется как множество слов, которые соответствуют Марковским фильтрам и конечному числу регулярных выражений, примененных к ним

D_{ν, θ, ⟨ M_{i} ⟩} = {α : \prod_{x \in α} ν (x) \geq θ, \exists i : M_{i} ∋ α} .

Алгоритмы

Модифицированный словарь модели Маркова нулевого порядка

Используемый для построения словаря алгоритм немного отличается от Марковского фильтра нулевого уровня (в данном случае для разных длин слов в словаре будет использоваться различный порог $θ$ )^[6].

Модифицированный словарь определяется как

D_{ν, θ, l} = {α : | α | = l, \prod_{x \in α} ν (x) \geq θ} .

Перепишем фильтр (словарь) в аддитивной форме

D_{ν, θ, l} = {α : | α | = l, \sum_{x \in α} μ (x) \geq λ},

где $μ (x) = \log ν (x), λ = \log θ$ .

Пусть ${α : | α | = l^{'}, \prod_{x \in α} ν (x) = θ^{'}}$ . Тогда определим частичные словари $D_{ν, θ, l, θ^{'}, l^{'}} = {β : α β \in D_{ν, θ, l}}$ . Заметим, что $D_{ν, θ, l, θ^{'}, l^{'}}$ определён, так как $\prod_{x \in α β} ν (x) = \prod_{x \in α} ν (x) \prod_{x \in β} ν (x) = θ^{'} \prod_{x \in β} ν (x)$ , поэтому не зависит от выбора $α$ .

Для любого префикса, частичный словарь содержит все возможные последовательности символов, которые могут прилагаться к этому префиксу, поэтому результирующая строка удовлетворяет всем Марковским свойствам.

В общем виде частичный словарь можно записать

∣ D_{ν, t h r e s h o l d, t o t a l l e n g t h, l e v e l, c u r r e n t l e n g t h} ∣

Рекурсивный алгоритм для подсчета размера частичного словаря^[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 истинные, тогда
a. если cookie находится в состоянии валидности (проверяется по дате изменения сервером) и запись, идентифицирующая пользователя (и хранящаяся в cookie) согласуется с введенным login, то пользователь получает доступ к серверу;

b. в противном случае сервер генерирует RTT-тест и отправляет его пользователю. Пользователь получает доступ к серверу только после правильного ответа на RTT-запрос;

4. если пара login/password некорректна, то
a. с вероятностью $p$ (где $0 \leq p \leq 1$ это системный параметр, например $p = 0.05$ ), пользователю предлагают пройти RTT-тест и независимо от ответа, доступ к серверу блокируется;

b. с вероятностью $1 - p$ , немедленно блокируется соединение.

Замечания

предполагается, что пользователь использует малое число компьютеров и, маловероятно, что атака будет произведена с одного из них;
процесс входа в систему использует веб-браузер и cookie необходимы;
алгоритм работы протокола построен так, что процесс генерации RTT-сообщения происходит только в двух случаях: при невалидной записи cookie в компьютере пользователя и при неверной паре login/password. Это позволяет разгрузить серверы, использующие данный протокол;
вероятность $p$ - есть функция пары 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 $s$ (Шаблон:Lang-en), основываясь на слабом Шаблон:Нп3 $w$ (Шаблон:Lang-en), который они разделяют).

Протокол (модифицированный криптографический метод SPEKE)

1. пользователь исполняет команду $d$ , необходимую для авторизации с authData;
2. пользовательский процесс и TPM включаются в Шаблон:Нп3, используя $d$ как слабый Шаблон:Нп3 $w$ ;
3. пользовательский процесс выбирает случайный $x$ и отправляет $H (d)^{x}$ к TPM, где $H$ — хеш-функция;
4. TPM выбирает случайный $y$ и отправляет $H (d)^{y}$ пользовательскому процессу;
5. каждый из них высчитывает секрет $s = H (d)^{x y}$ ;
6. $w$ заменяется на $s$ как HMAC-ключ.

Замечания

ограничения, накладываемые на выбор $d, w, H, x, y$ описаны в алгоритме обмена ключами Диффи-Хеллмана;
выбор хеш-функции $H$ определяется методом шифрования в криптопроцессоре (чип TPM).
протокол допускает улучшения.^[9]

См. также

Примечания

Шаблон:Примечания

Ссылки

RFC 2828 – Internet Security Glossary
RFC 4949 – Internet Security Glossary, Version 2
Шаблон:Cite web
Шаблон:Cite web
Шаблон:Cite web
Шаблон:Cite web
Шаблон:Cite web

↑ Шаблон:Статья
↑ ^2,0 ^2,1 Шаблон:Статья
↑ ^3,0 ^3,1 Шаблон:Статья
↑ ^4,0 ^4,1 Шаблон:Статья
↑ ^5,0 ^5,1 Шаблон:Статья
↑ ^6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 Шаблон:Статья
↑ Шаблон:Статья
↑ ^8,0 ^8,1 ^8,2 Шаблон:Статья
↑ ^9,0 ^9,1 Шаблон:Статья

[RFC-1] Шаблон:Статья

[InternetWorm-2] 2,0 ^2,1 Шаблон:Статья

[Klein-3] 3,0 ^3,1 Шаблон:Статья

[Spafford-4] 4,0 ^4,1 Шаблон:Статья

[JianxinAlanRossAlasdair-5] 5,0 ^5,1 Шаблон:Статья

[NarayananShmatikov-6] 6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 Шаблон:Статья

[7] Шаблон:Статья

[PinkasSander-8] 8,0 ^8,1 ^8,2 Шаблон:Статья

[ChenRyan-9] 9,0 ^9,1 Шаблон:Статья

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Перебор по словарю

Содержание