Перебір за словником

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

Атака словником може здійснюватись онлайн та офлайн:

• При онлайн атаці зловмисник пробує увійти відправляючи запити як будь-який інший користувач, послідовно пробуючи кожен пароль зі списку. Таку атаку може помітити адміністратор сервера, крім того кількість спроб може бути обмежена алгоритмом.
• У випадку офлайн атаки атакуючий має доступ до зашифрованого файла і може перевірити всі допустимі паролі, не потребуючи при цьому зв'язку з сервером.

Складність пароля

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

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

Історичні відомості

Використання Інтернет-хробака (англ. 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 здійснюється користувачем даного облікового запису, в той час як атака за словником проводиться автоматичною програмою. Потрібно, щоб спроба введення правильного пароля була «обчислювально простою» для людини, і «обчислювально складною» для машин.

Протокол явліє собою тест, що дозволяє серверу відрізнити людину від бота. Уперше він був запропонований М. Наором та має назву зворотний тест Тюринга (англ. 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. протокол допускає покращення.

Дивись також

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

Посилання

1. The Strong Password Dilemma. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.
2. Dictionaries. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.
3. CAPTCHA. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.
4. Oechslin Philippe. Making a Faster Cryptanalytic Time-Memory Trade-Off (PDF). Архів оригіналу (PDF) за 27 лютого 2012. Процитовано 13 листопада 2011.
5. John the Ripper password cracker. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.