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

Перебор по словарю (англ. dictionary attack) — атака на систему защиты, использующая метод полного перебора (англ. brute-force) предполагаемых паролей, используемых для аутентификации, осуществляемого путём последовательного пересмотра всех слов (паролей в чистом виде или их зашифрованных образов) определённого вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации.

Перебор по словарю и сложность пароля

С точки зрения теории вероятностей, выбор пароля детерминирован и закономерен. В качестве пароля могут выступать: дата рождения, имя, предмет, набор цифр, последовательность близко расположенных на клавиатуре букв. В общем случае происходит конкатенация вышеперечисленного.

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

Различают два вида атак:

• Online: атаки, в которых единственным способом для атакующего проверить, является ли данный пароль корректным, есть взаимодействие с сервером.
• Offline: атаки, когда атакующий имеет возможность проверить все допустимые пароли, не нуждаясь при этом в обратной связи с сервером.

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

Исторические сведения

Использование Интернет-червя (англ. Internet Worm) в 1988 г. предоставляет хорошо документированный случай взлома паролей. Интернет-червь пытался взломать пароли, работая с серией словарей. На первом этапе атаки было использовано множество слов, содержащее имена пользователей, взятых из файла паролей системы Unix. Если это не имело успеха, использовался внутренний словарь 432 общепринятых, используемых в Интернет-жаргоне, слов. Если второй этап не имел успеха, использовался Unix словарь, состоящий из 24474 слов. Червь также проверял на пустой пароль. Сайты, на которые производилась атака, сообщили, что около 50 % паролей было успешно взломано, используя данную стратегию.

Следующим шагом стала работа Даниэля Кляйна (англ. Daniel Klein). Чтобы предоставить свои результаты, он собрал шифрованные файлы паролей системы Unix. Эта коллекция содержала примерно 15000 различных пар имя пользователя/пароль (англ. login/password). Кляйн сконструировал серию словарей и набор механизмов, позволяющих осуществлять перестановки. Предоставленный им словарь состоял из приблизительно 60000 пунктов. Этот лист включал в себя имена, места, вымышленные ссылки, библейские термины, выражения из поэм У. Шекспира и т. д. После применения стратегии перестановки (использование заглавных букв, очевидные замены, перестановки цифр), он получил пространство паролей, более чем из 3.3 млн возможностей. Использование этого словаря помогло Кляйну взломать 24,2 % всех паролей на определённых серверах.

В 1991—1992 гг. Евгению Спаффорду (англ. Eugene Spafford) удалось построить, основываясь на статистике, словарь, с помощью которого поддались взлому 20 % паролей на выбранных серверах.

В 2000 г. команда исследователей из университета Кембридж провела исследование, в ходе которого была произведена атака на 195 хешированных паролей, из которых 35 % были успешно взломаны.

Таблица: Процент паролей найденных в ходе систематических исследований

Исследователь(и) / проект	Время	Паролей проверено	Процент нахождения, [%]
Интернет-червь	1988	тысячи	~50
Исследование Кляйна	1990	15000	24.2
Исследование Спаффорда	1992	13787	20.0
Исследователи из университета Кембридж	2000	195	35.0

Основные принципы построения словаря

В большинстве паролей наблюдается фонетическое сходство со словами естественного (английского) языка; причина этому заключается в простоте запоминания такого рода информации о данном пароле. Это свойство учитывается в «Марковских фильтрах», основанных на цепи Маркова, которая является стандартной техникой в обработке естественного языка. Наличие неалфавитных символов в пароле можно интерпретировать как применение конечного автомата к определённому набору элементов.

Марковские фильтры

Алфавитный пароль, сгенерированный человеком, неравномерно распределен в пространстве алфавитных последовательностей. Данное условие может быть учтено с большой точностью в «Марковских фильтрах» нулевого и первого порядка:

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

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

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

$P(\alpha )=\prod _{x\in \alpha }\nu (x),$

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

$P(x_{1}x_{2}\ldots x_{n})=\nu (x_{1})\prod _{i=1}^{n-1}\nu (x_{i+1}\mid x_{i}),$

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

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

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

$D_{\nu ,\theta }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta \},$

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

$D_{\nu ,\theta }=\{x_{1}x_{2}\ldots x_{n}:\nu (x_{1})\prod _{i=1}^{n-1}\nu (x_{i+1}\mid x_{i})\geq \theta \}.$

Замечания

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

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

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

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

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

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

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

$D_{\nu ,\theta ,\left\langle M_{i}\right\rangle }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta ,\,\exists i:M_{i}\ni \alpha \}.$

Алгоритмы

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

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

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

$D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\prod _{x\in \alpha }\nu (x)\geq \theta \}.$

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

$D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\sum _{x\in \alpha }\mu (x)\geq \lambda \},$

где $\mu (x)=\log \nu (x),\,\lambda =\log \theta$.

Пусть $\{\alpha :|\alpha |=l',\prod _{x\in \alpha }\nu (x)=\theta '\}$. Тогда определим частичные словари $D_{\nu ,\theta ,l,\theta ',l'}=\{\beta :\alpha \beta \in D_{\nu ,\theta ,l}\}$. Заметим, что $D_{\nu ,\theta ,l,\theta ',l'}$ определён, так как $\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)$, поэтому не зависит от выбора $\alpha$.

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

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

$\mid D_{\nu ,\,threshold,\,total\,length,\,level,\,current\,length}\mid$

Рекурсивный алгоритм для подсчета размера частичного словаря:

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 
}

Замечания

1. partial_size1 вычисляется только один раз (а не один раз для каждого ключа);
2. get_key1 вычисляется в процессе криптоанализа;
3. чтобы просмотреть все пространство ключей, необходимо запустить 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 
}

Замечание

1. использование гибридных алгоритмов дает лучшие результаты для криптоанализа методом перебора по словарю.

Основные противодействия атакам по словарю

Противодействия online атакам по словарю

Существует несколько способов противостоять online атакам по словарю:

1. задержка ответа (англ. delayed response): для предоставленной пары login/password сервер использует небольшую, специально сгенерированную задержку ответа Yes/no (например, не чаще одного ответа в секунду;
2. блокировка учетной записи (англ. account locking): учетная запись блокируется после нескольких (заранее установленное число) неудачных попыток ввода login/password (для примера, учетная запись блокируется на час после пяти неправильных попыток ввода пароля);
3. использование Proof-of-Work;
4. использование соли и медленных хеш-функций на стороне клиента.

Замечания

1. данные меры, в большинстве случаев, предотвращают атаку по словарю и сопутствующий взлом пароля за допустимое время;
2. данные реализации противодействия online атакам по словарю допускают долговременные блокировки пользовательских аккаунтов при правильном подборе периода атаки.

Протоколы проверки подлинности пользователей

Предполагается, что ввод верной комбинации login/password производится пользователем данной учетной записи, в то время как атака по словарю производится автоматической программой. Требуется, чтобы попытка ввода правильного пароля была «вычислительно простой» для человека, и «вычислительно сложной» для машин.

Протокол представляет собой тест, позволяющий серверу отличить человека от бота. Он был впервые предложен М. Наором (англ. Moni Naor) и называется обратный тест Тьюринга (англ. Reverse Turing test (RTT)), другое название для него CAPTCHA. Обратный Тест Тьюринга должен удовлетворять следующим условиям:

1. автоматическая генерация;
2. простота выполнения для человека;
3. сложность для машин;
4. малая вероятность угадать ответ.

Тест с использованием изображений удовлетворяет всем вышеперечисленным условиям.

Протокол 1 (комбинация обратного теста Тьюринга с любой системой проверки подлинности)

Пользователя просят ответить на RTT-сообщение перед началом проверки подлинности (перед вводом login/password).

Замечание

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

Протокол 2 (пользовательский протокол входа в систему, модифицированная версия протокола 1)

Если пользователь успешно вошел в систему, то сервер посылает в пользовательский компьютер cookie, которые содержат запись об аутентификации пользователя и срок валидности этого сообщения (подразумевается невозможность изменить информацию в cookie, при этом не оповестив об этом сервер. Это может быть гарантированно добавлением MAC (англ. message authentication code), который вычисляется, используя ключ, известный только серверу).

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$, немедленно блокируется соединение.

Замечания

1. предполагается, что пользователь использует малое число компьютеров и, маловероятно, что атака будет произведена с одного из них;
2. процесс входа в систему использует веб-браузер и cookie необходимы;
3. алгоритм работы протокола построен так, что процесс генерации RTT-сообщения происходит только в двух случаях: при невалидной записи cookie в компьютере пользователя и при неверной паре login/password. Это позволяет разгрузить серверы, использующие данный протокол;
4. вероятность $p$- есть функция пары login/password. Возможны случаи, когда для фиксированных значений login/password будут происходить или только блокировки учетной записи или только генерации RTT-сообщений при многократной ошибке.

Противодействия offline атакам по словарю

Offline атаки по словарю могут быть предотвращены или усложнены следующими способами:

• добавления в хеширование известной величины — соли (англ. salt)
• использование медленной хеш-функции, напр. scrypt

Аппаратная реализация

Trusted Platform Module (TPM) — представляет собой аппаратный чип, позволяющий компьютерам сохранять безопасность данных. Владение секретной информацией (далее — authData) необходимо для доступа и использования TPM-ключей.

В процессе атаки, криптоаналитик может узнать:

1. login для authData и ответ TPM на этот запрос;
2. общий секрет (англ. shared secret), ассоциированный с authData и ответ TPM.

Составление словарей, основанных на полученных сведениях, используется в offline атаке по словарю, с целью определить authData.

Методы борьбы — использование модифицированного криптографического метода SPEKE (Simple Password Exponential Key Exchange), который основан на алгоритме обмена ключами Диффи-Хеллмана (позволяет двум сторонам создать общий секрет $s$ (англ. strong shared secret), основываясь на слабом общем секрете $w$ (англ. weak secret), который они разделяют).

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

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

Замечания

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

См. также

• Сложность пароля
• Радужная таблица
• Разделение секрета

Ссылки

• RFC 2828 – Internet Security Glossary
• RFC 4949 – Internet Security Glossary, Version 2
• The Strong Password Dilemma (англ.). Дата обращения: 13 ноября 2011. Архивировано 27 февраля 2012 года.
• Dictionaries (англ.). Дата обращения: 13 ноября 2011. Архивировано 27 февраля 2012 года.
• CAPTCHA (англ.). Дата обращения: 13 ноября 2011. Архивировано из оригинала 27 февраля 2012 года.
• Oechslin Philippe. Making a Faster Cryptanalytic Time-Memory Trade-Off (англ.). Дата обращения: 13 ноября 2011. Архивировано 27 февраля 2012 года.
• John the Ripper password cracker (англ.). Дата обращения: 13 ноября 2011. Архивировано из оригинала 27 февраля 2012 года.