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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

Складність пароля[ред. | ред. код]

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

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

Історичні відомості[ред. | ред. код]

Використання Інтернет-хробака (англ. Internet Worm) в 1988 р. надає добре документований випадок злому паролів.[3] Інтернет-хробак намагався зламати паролі, працюючи з серією словників. На першому етапі атаки було використано безліч слів, що містить імена користувачів, взятих з файлу паролів системи Unix. Якщо це не мало успіху, використовувався внутрішній словник 432 загальноприйнятих слів, що використовуються в Інтернет-жаргоні. Якщо другий етап не мав успіху, використовувався Unix словник, що складається з 24474 слів. Хробак також перевіряв на порожній пароль. Сайти, на які проводилася атака, повідомили, що близько 50 % паролів було успішно зламано, використовуючи дану стратегію.

Наступним кроком стала робота Даніеля Кляйна (англ. Daniel Klein).[4] Щоб надати свої результати, він зібрав зашифровані файли паролів системи Unix. Ця колекція містила приблизно 15000 різних пар ім'я користувача/пароль (англ. login/password). Кляйн сконструював серію словників і набір механізмів, що дозволяють здійснювати перестановки. Наданий ним словник складався з приблизно 60000 пунктів. Цей лист включав в себе імена, місця, вигадані посилання, біблійні терміни, вирази з поем Вільяма Шекспіра і т. д. Після застосування стратегії перестановки (використання великих букв, очевидні заміни, перестановки цифр), він отримав простір паролів, більш ніж 3.3 млн можливостей. Використання цього словника допомогло Кляйну зламати 24,2 % всіх паролів на певних серверах.

У 1991-1992 рр. Юджину Спаффорду[en] (англ. Eugene Spafford) вдалося побудувати, ґрунтуючись на статистиці, словник, за допомогою якого піддалися злому 20 % паролів на вибраних серверах.[5]

У 2000 р. команда дослідників з університету Кембриджа провела дослідження, в ході якого була проведена атака на 195 хешованих паролів, з яких 35 % були успішно зламані.[6]

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

Основні принципи побудови словника[ред. | ред. код]

У більшості паролів спостерігається фонетичну схожість зі словами звичайної (англійської) мови; причина цього полягає в простоті запам'ятовування такого роду інформації про даному паролю. Це властивість враховується у Марковських фільтрах», заснованих на ланцюгу Маркова, яка є стандартною технікою в обробці природної мови. Наявність неалфавітных символів в паролі можна інтерпретувати як застосування скінченого автомата до певного набору елементів.

Марківські фільтри[ред. | ред. код]

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

1. нульовий порядок моделі Маркова: кожен символ генерується у відповідності зі своїм імовірнісним розподілом і незалежно від попередніх символів.
2. перший порядок моделі Маркова: кожній диграмі (впорядкованій парі) символів присвоюється імовірність і кожен символ породжується в умовній залежності від попереднього.

Математично,

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

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

де — ймовірність розподілу послідовності символів, — символ даної послідовності, — частота індивідуального символу або діграми в тексті.

Для усунення малоймовірних рядків в словнику застосовується дискретизація ймовірностей — запроваджується дворівнева система з порогом :

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

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

Зауваження

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

Фільтри, що використовують скінченні автомати[ред. | ред. код]

Для створення скінченних автоматов вводяться деякі обмеження і припущення по відношенню до пароля, який необхідно зламати:

1. в алфавітно-цифровому паролі всі цифри розташовані в кінці;
2. перша літера в алфавітному паролі, найімовірніше, велика, порівняно з іншими;
3. в алфавітному паролі кількість маленьких літер переважає над кількістю великих.

Детерміновані скінченні автомати є ідеальними засобами для виразів із запропонованими обмеженнями.

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

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

Алгоритми[ред. | ред. код]

Модифікований словник моделі Маркова нульового порядку[ред. | ред. код]

Алгоритм, що використовується для побудови словника трохи відрізняється від Марківського фільтра нульового рівня (в даному випадку для різних довжин слів у словнику буде використовуватися різний поріг ).

Модифікований словник визначається як

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

где .

Пусть . Тоді визначимо часткові словники . Заметим, что определен, так как , тоді не залежить від вибору .

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

У загальному вигляді частковий словник можна записати так:

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

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. використання гібридних алгоритмів дає кращі результати для криптоаналізу методом перебору за словником.Помилка цитування: Відкривальний тег <ref> неправильний або містить хибну назву.

Основні методи протидії атакам за словником[ред. | ред. код]

Протидії online атак за словником[ред. | ред. код]

Існує кілька способів протистояти online атакам за словником:

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

Зауваження

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

Протоколи автентифікації користувачів[ред. | ред. код]

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

Протокол явліє собою тест, що дозволяє серверу відрізнити людину від бота. Уперше він був запропонований М. Наором[en] та має назву зворотній тест Тьюринга (англ. Reverse Turing test (RTT)), або ж CAPTCHA. Зворотній тест Тьюринга має відповідати таким умовам:[8]

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

Тест з використанням зображень задовольняє всім перерахованим умовам.

Протокол 1 (комбінація зворотного тесту Тюрінга з будь-якою системою автентифікації)Помилка цитування: Відкривальний тег <ref> неправильний або містить хибну назву.


Користувача просять відповісти на RTT-повідомлення перед початком перевірки автентичності (перед введенням login/password).

Зауваження Цей метод не оптимальний для великих систем, так як введення користувачем відповіді на RTT-тест кожен раз перед автентифікацією досить дратівлива і психологічно важка задача.[9]

Протокол 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. з імовірністю (де це системний параметр, наприклад ), користувачеві пропонують пройти RTT-тест і незалежно від відповіді, доступ до сервера блокується;
b. з імовірністю негайно блокується з'єднання.

Зауваження

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

Протидії offline атакам за словником[ред. | ред. код]

Offline атаки за словником можуть бути відвернені або ускладнені наступними способами:

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

Апаратна реалізація[ред. | ред. код]

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

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

1. login для authData і відповідь TPM на цей запит;
2. спільний секрет[en] (англ. shared secret), асоційований з authData і відповідь TPM.

Складання словників, заснованих на отриманих відомостях, використовується в offline атаках за словником, з метою визначити authData.

Методи боротьби — використання модифікованого криптографічного методу SPEKE[en] (Simple Password Exponential Key Exchange), який заснований на алгоритмі обміну ключами Діффі-Геллмана (дозволяє двом сторонам створити общий секрет[en] (англ. strong shared secret), ґрунтуючись на слабкому спільному секреті[en] (англ. weak secret), який вони поділяють).

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

1. користувач виконує команду , необхідну для авторизації з authData;

2. призначений для користувача процес і TPM включаються в SPEKE-протокол[en], використовуючи ;

3. призначений для користувача процес вибирає випадковий  посилає TPM, де  — хеш-функція;

4. TPM обирає випадковий  посилає  користувальницькому процесу;

5. кожен з них обчислює секрет ;

6. замінюється на к HMAC-ключ.

Зауваження

1. обмеження, що накладаються на вибір описані в алгоритмі обміну ключами Діффі-Геллмана;
2. вибір хеш-функції визначається методом шифрування в криптопроцесорі (чип TPM).
3. протокол допускає покращення.[10]

Дивись також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. RFC 4949, Internet Security Glossary, Version 2
  2. https://nordpass.com/blog/what-is-a-dictionary-attack/
  3. Spafford Eugene. The Internet Worm: Crisis and Aftermath. — Communications of the ACM, June 1989. — С. 678-687.
  4. Daniel V. Klein. A Survey of, and Improvements to, Password Security // USENIX Association. — 1990.
  5. Spafford Eugene. Observing Reusable Password Choices : [арх. 20 липня 2011] // USENIX Association. — 31 July 1992.
  6. Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. The memorability and security of passwords some empirical results. — September 2000.
  7. Narayanan Arvind, Shmatikov Vitaly. Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff. — November 7–11, 2005.
  8. Naor Moni. Verification of a human in the loop or Identification via the Turing Test. — September 13th, 1996.
  9. Pinkas Benny, Sander Tomas. Securing Passwords Against Dictionary Attacks.
  10. а б Chen Liqun, Ryan Mark. .

Посилання[ред. | ред. код]

  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. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011. 
  5. John the Ripper password cracker. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.