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

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

Перебір за словником і складність пароля

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

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

Розрізняють два види атак:

Online: атаки, в яких єдиним способом для атакуючого перевірити, чи є даний пароль коректним, є взаємодія з сервером.
Offline: атаки, коли атакуючий має можливість перевірити всі допустимі паролі, не потребуючи при цьому в зворотному зв'язку з сервером.

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

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

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

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

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

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

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

Основні принципи побудови словника

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

Марківські фільтри

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

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

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

Протидії 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. Зворотній тест Тьюринга має відповідати таким умовам:[8]

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

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

Протокол 1 (комбінація зворотного тесту Тюрінга з будь-якою системою автентифікації)[9]


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

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

Протокол 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-ключів.

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

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

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

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

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

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

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

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

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

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

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

Зауваження

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

Дивись також

Примітки

  1. Shirey R. Request for Comments: 4949. — August 2007.
  2. Spafford Eugene. The Internet Worm: Crisis and Aftermath. — Communications of the ACM, June 1989. — С. 678-687.
  3. Daniel V. Klein. A Survey of, and Improvements to, Password Security // USENIX Association. — 1990.
  4. Spafford Eugene. Observing Reusable Password Choices // USENIX Association. — 31 July 1992.
  5. Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. The memorability and security of passwords some empirical results. — September 2000.
  6. Narayanan Arvind, Shmatikov Vitaly. Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff. — November 7–11, 2005.
  7. Naor Moni. Verification of a human in the loop or Identification via the Turing Test. — September 13th, 1996.
  8. Pinkas Benny, Sander Tomas. Securing Passwords Against Dictionary Attacks.
  9. 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.
3. Oechslin Philippe. Making a Faster Cryptanalytic Time-Memory Trade-Off. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.
5. John the Ripper password cracker. Архів оригіналу за 27 лютого 2012. Процитовано 13 листопада 2011.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.