Interested Article - Перебор по словарю

tammi
  • 2021-12-08
  • 1

Перебор по словарю ( англ. 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 ( α ) = ∏ x ∈ α ν ( x ) , {\displaystyle P(\alpha)=\prod _{x\in \alpha }\nu (x),}

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

P ( x 1 x 2 … x n ) = ν ( x 1 ) ∏ i = 1 n − 1 ν ( x i + 1 ∣ x i ) , {\displaystyle P(x_{1}x_{2}\ldots x_{n})=\nu (x_{1})\prod _{i=1}^{n-1}\nu (x_{i+1}\mid x_{i}),}

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

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

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

D ν , θ = { α : ∏ x ∈ α ν ( x ) ≥ θ } , {\displaystyle D_{\nu ,\theta }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta \},}

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

D ν , θ = { x 1 x 2 … x n : ν ( x 1 ) ∏ i = 1 n − 1 ν ( x i + 1 ∣ x i ) ≥ θ } . {\displaystyle 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 ν , θ , ⟨ M i ⟩ = { α : ∏ x ∈ α ν ( x ) ≥ θ , ∃ i : M i ∋ α } . {\displaystyle D_{\nu ,\theta ,\left\langle M_{i}\right\rangle }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta ,\,\exists i:M_{i}\ni \alpha \}.}

Алгоритмы

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

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

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

D ν , θ , l = { α : | α | = l , ∏ x ∈ α ν ( x ) ≥ θ } . {\displaystyle D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\prod _{x\in \alpha }\nu (x)\geq \theta \}.}

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

D ν , θ , l = { α : | α | = l , ∑ x ∈ α μ ( x ) ≥ λ } , {\displaystyle D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\sum _{x\in \alpha }\mu (x)\geq \lambda \},}

где μ ( x ) = log ⁡ ν ( x ) , λ = log ⁡ θ {\displaystyle \mu (x)=\log \nu (x),\,\lambda =\log \theta } .

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

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

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

∣ 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 ∣ {\displaystyle \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 производится пользователем данной учетной записи , в то время как атака по словарю производится автоматической программой. Требуется, чтобы попытка ввода правильного пароля была «вычислительно простой» для человека, и «вычислительно сложной» для машин.

Протокол представляет собой тест, позволяющий серверу отличить человека от бота . Он был впервые предложен ( англ. ) и называется обратный тест Тьюринга ( англ. 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 {\displaystyle p} (где 0 ≤ p ≤ 1 {\displaystyle 0\leq p\leq 1} это системный параметр, например p = 0.05 {\displaystyle p=0.05} ), пользователю предлагают пройти RTT-тест и независимо от ответа, доступ к серверу блокируется;
b. с вероятностью 1 − p {\displaystyle 1-p} , немедленно блокируется соединение.

Замечания

  1. предполагается, что пользователь использует малое число компьютеров и, маловероятно, что атака будет произведена с одного из них;
  2. процесс входа в систему использует веб-браузер и cookie необходимы;
  3. алгоритм работы протокола построен так, что процесс генерации RTT-сообщения происходит только в двух случаях: при невалидной записи cookie в компьютере пользователя и при неверной паре login/password. Это позволяет разгрузить серверы, использующие данный протокол;
  4. вероятность p {\displaystyle 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 .

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

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

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

Замечания

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

См. также

Примечания

  1. Shirey R. (англ.) . — August 2007. 19 ноября 2011 года.
  2. ↑ Spafford Eugene. (англ.) . — Communications of the ACM, June 1989. — P. 678—687 . 29 ноября 2010 года.
  3. ↑ Daniel V. Klein. (англ.) // USENIX Association. — 1990. 11 февраля 2014 года.
  4. ↑ Spafford Eugene. (англ.) // USENIX Association. — 31 July 1992. 20 июля 2011 года.
  5. ↑ Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. (англ.) / Markus Kuhn. — September 2000. 19 февраля 2011 года.
  6. ↑ Narayanan Arvind, Shmatikov Vitaly. (англ.) . — November 7–11, 2005. 12 октября 2011 года.
  7. Naor Moni. (англ.) . — September 13th, 1996. 27 сентября 2011 года.
  8. ↑ Pinkas Benny, Sander Tomas. (англ.) . 21 ноября 2011 года.
  9. ↑ Chen Liqun, Ryan Mark. (англ.) . 1 апреля 2011 года.

Ссылки

  • – Internet Security Glossary
  • – Internet Security Glossary, Version 2
  • (англ.) . Дата обращения: 13 ноября 2011. 27 февраля 2012 года.
  • (англ.) . Дата обращения: 13 ноября 2011. 27 февраля 2012 года.
  • (англ.) . Дата обращения: 13 ноября 2011. Архивировано из 27 февраля 2012 года.
  • Oechslin Philippe. (англ.) . Дата обращения: 13 ноября 2011. 27 февраля 2012 года.
  • (англ.) . Дата обращения: 13 ноября 2011. Архивировано из 27 февраля 2012 года.

tammi
  • 2021-12-08
  • 1

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

The title for the last searches