Перебір за словником () — кібератака, що використовує метод повного перебору (, грубої сили) можливих паролів з якогось великого, вичерпного списку. Наприклад, спроба автентифікації пробуючи кожен пароль, або спроба зашифрування якогось відомого відкритого тексту всіма можливими паролями, щоб дізнатись ключ, яким зашифровано текст.
Атака словником може здійснюватись онлайн та офлайн:https://nordpass.com/blog/what-is-a-dictionary-attack/ При онлайн атаці зловмисник пробує увійти відправляючи запити як будь-який інший користувач, послідовно пробуючи кожен пароль зі списку. Таку атаку може помітити адміністратор сервера, крім того кількість спроб може бути обмежена алгоритмом. У випадку офлайн атаки атакуючий має доступ до зашифрованого файла і може перевірити всі допустимі паролі, не потребуючи при цьому зв'язку з сервером.
Складність пароля З точки зору теорії ймовірностей, вибір пароля детермінований і закономірний. В якості пароля можуть виступати: дата народження, ім'я, предмет, набір цифр, послідовність близько розташованих на клавіатурі букв. В загальному випадку відбувається конкатенація вищепереліченого.
Результатом цих припущень стає той факт, що зумовленість у виборі пароля відіграє ключову роль у виборі алгоритмів, на яких заснований метод перебору за словником.
Історичні відомості Використання Інтернет-хробака () в 1988 р. надає добре документований випадок злому паролів. Інтернет-хробак намагався зламати паролі, працюючи з серією словників. На першому етапі атаки було використано безліч слів, що містить імена користувачів, взятих з файлу паролів системи Unix. Якщо це не мало успіху, використовувався внутрішній словник 432 загальноприйнятих слів, що використовуються в Інтернет-жаргоні. Якщо другий етап не мав успіху, використовувався Unix словник, що складається з 24474 слів. Хробак також перевіряв на порожній пароль. Сайти, на які проводилася атака, повідомили, що близько 50 % паролів було успішно зламано, використовуючи дану стратегію.
Наступним кроком стала робота Даніеля Кляйна (). Щоб надати свої результати, він зібрав зашифровані файли паролів системи Unix. Ця колекція містила приблизно 15000 різних пар ім'я користувача/пароль (). Кляйн сконструював серію словників і набір механізмів, що дозволяють здійснювати перестановки. Наданий ним словник складався з приблизно 60000 пунктів. Цей лист включав в себе імена, місця, вигадані посилання, біблійні терміни, вирази з поем Вільяма Шекспіра і т. д. Після застосування стратегії перестановки (використання великих букв, очевидні заміни, перестановки цифр), він отримав простір паролів, більш ніж 3.3 млн можливостей. Використання цього словника допомогло Кляйну зламати 24,2 % всіх паролів на певних серверах.
У 1991-1992 рр. () вдалося побудувати, ґрунтуючись на статистиці, словник, за допомогою якого піддалися злому 20 % паролів на вибраних серверах.
У 2000 р. команда дослідників з університету Кембриджа провела дослідження, в ході якого була проведена атака на 195 хешованих паролів, з яких 35 % були успішно зламані. + Таблиця: Відсоток паролів знайдених в ході систематичних досліджень Дослідник(и) / проект Час Паролів перевірено Відсоток знаходження, [%] Інтернет-хробак 1988 тисячі ~50 Дослідження Кляйна 1990 15000 24.2 Дослідження 1992 13787 20.0 Дослідники з університету Кембриджа 2000 195 35.0
Основні принципи побудови словника У більшості паролів спостерігається фонетичну схожість зі словами звичайної (англійської) мови; причина цього полягає в простоті запам'ятовування такого роду інформації про даному паролю. Це властивість враховується у Марковських фільтрах», заснованих на ланцюгу Маркова, яка є стандартною технікою в обробці природної мови. Наявність неалфавітних символів в паролі можна інтерпретувати як застосування скінченого автомата до певного набору елементів.
Марківські фільтри Алфавітний пароль, згенерований людиною, нерівномірно розподілений у просторі алфавітних послідовностей. Дана умова може бути враховано з великою точністю у «Марківських фільтрах» нульового і першого порядку: нульовий порядок моделі Маркова: кожен символ генерується у відповідності зі своїм імовірнісним розподілом і незалежно від попередніх символів. перший порядок моделі Маркова: кожній диграмі (впорядкованій парі) символів присвоюється імовірність і кожен символ породжується в умовній залежності від попереднього.
Математично,
нульовий порядок модели Маркова:
перший порядок моделі Маркова:
де — ймовірність розподілу послідовності символів, — символ даної послідовності, — частота індивідуального символу або диграми в тексті.
Для усунення малоймовірних рядків в словнику застосовується дискретизація ймовірностей — запроваджується дворівнева система з порогом :
нульовий порядок моделі Маркова:
перший порядок моделі Маркова:
Зауваження модель Маркова першого порядку демонструє кращі результати (дає більший відсоток злому) порівняно з моделлю Маркова нульового порядку. Винятковими є випадки, коли стратегія вибору пароля використовує скорочення, що складаються з перших літер кожного слова в абстрактному поєднанні; розподіл частот появи літер в паролі залежить від конкретної мови, для якої складається словник (узагальненням даного методу є комбінація передбачуваних мов для створення пароля).
Фільтри, що використовують скінченні автомати Для створення скінченних автоматов вводяться деякі обмеження і припущення по відношенню до пароля, який необхідно зламати: в алфавітно-цифровому паролі всі цифри розташовані в кінці; перша літера в алфавітному паролі, найімовірніше, велика, порівняно з іншими; в алфавітному паролі кількість маленьких літер переважає над кількістю великих.
Детерміновані скінченні автомати є ідеальними засобами для виразів із запропонованими обмеженнями.
Першим етапом побудови словника, побудованого на скінченних автоматах, є створення послідовності регулярних виразів (\"нижній регістр", \"велика літера розташована перед малими", \"усі великі розташовані перед малими" і т. д.). Словник визначається як безліч слів, які відповідають Марківським фільтрам і кінцевого числа регулярних виразів, застосованих до них
Алгоритми
Модифікований словник моделі Маркова нульового порядку Алгоритм, що використовується для побудови словника трохи відрізняється від Марківського фільтра нульового рівня (в даному випадку для різних довжин слів у словнику буде використовуватися різний поріг ).
Модифікований словник визначається як
Перепишемо фільтр (словник) в адитивній формі: </center>где .
Нехай . Тоді визначимо часткові словники . Відзначимо, що визначено, оскільки , тому не залежить від вибору .
Для будь-якого префіксу, частковий словник містить всі можливі послідовності символів, які можуть додаватись до цього префікса, тому результуючий рядок задовольняє всім Марківським властивостями.
У загальному вигляді частковий словник можна записати так:
Рекурсивний алгоритм для підрахунку розміру часткового словника: 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 }
Зауваження partial_size1 обчислюється лише один раз (а не щоразу для кожного ключа); get_key1 обчислюється в процесі криптоаналізу; аби переглянути весь набір ключів, слід запустити 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 }
Зауваження використання гібридних алгоритмів дає кращі результати для криптоаналізу методом перебору за словником.
Основні методи протидії атакам за словником
Протидії online атакам за словником Існує кілька способів протистояти online атакам за словником:
затримка відповіді (): для наданої пари login/password сервер використовує невелику, спеціально згенеровану затримку відповіді Yes/no (наприклад, не частіше одної відповіді на секунду); блокування облікового запису (): обліковий запис блокується після кількох (заздалегідь встановлене число) невдалих спроб введення login/password (для прикладу, обліковий запис блокується на годину після п'яти неправильних спроб введення пароля); використання Proof-of-Work; використання солі і повільних хеш-функцій на стороні клієнта.
Зауваження
переважно такі заходи запобігають атаці по словнику і супутному злому пароля за припустимий час; такі реалізації протидії online атак за словником допускають довготривалі блокування користувальницьких акаунтів при правильному підборі періоду атаки.
Протоколи автентифікації користувачів Передбачається, що введення вірної комбінації login/password здійснюється користувачем даного облікового запису, в той час як атака за словником проводиться автоматичною програмою. Потрібно, щоб спроба введення правильного пароля була «обчислювально простою» для людини, і «обчислювально складною» для машин.
Протокол явліє собою тест, що дозволяє серверу відрізнити людину від бота. Уперше він був запропонований та має назву зворотний тест Тюринга (), або ж CAPTCHA. Зворотний тест Тюринга має відповідати таким умовам:
автоматична генерація; простота виконання для людини; складність для машин; мала ймовірність вгадати відповідь.
Тест з використанням зображень задовольняє всім перерахованим умовам. Протокол 1 (комбінація зворотного тесту Тюрінга з будь-якою системою автентифікації)
Користувача просять відповісти на RTT-повідомлення перед початком перевірки автентичності (перед введенням login/password).
Зауваження
Цей метод не оптимальний для великих систем, так як введення користувачем відповіді на RTT-тест кожен раз перед автентифікацією досить дратівлива і психологічно важка задача. Протокол 2 (користувацький протокол входу в систему, модифікована версія протоколу 1)
Якщо користувач, який успішно увійшов до системи, сервер посилає в комп'ютер користувача cookie, які містять запис про автентифікації користувача і термін валідності цього повідомлення (мається на увазі неможливість змінити інформацію cookie, при цьому не сповістивши про це сервер. Це може бути гарантовано додаванням MAC (), який обчислюється, використовуючи ключ, відомий тільки серверу).
користувач вводить login/password. Якщо його комп'ютер містить cookie, надані даним сервером, cookie витягується сервером; перевірка справжності login/password; якщо login/password справжні, тоді