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

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

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

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

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

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

${\displaystyle P(\alpha )=\prod _{x\in \alpha }\nu (x),}$

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

${\displaystyle P(x_{1}x_{2}\ldots x_{n})=\nu (x_{1})\prod _{i=1}^{n-1}\nu (x_{i+1}\mid x_{i}),}$

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

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

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

${\displaystyle D_{\nu ,\theta }=\{\alpha$ :\prod _{x\in \alpha }\nu (x)\geq \theta \},}

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

${\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. в алфавітному паролі кількість маленьких літер переважає над кількістю великих.

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

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

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

${\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 }$).

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

${\displaystyle D_{\nu ,\theta ,l}=\{\alpha$ :|\alpha |=l,\prod _{x\in \alpha }\nu (x)\geq \theta \}.}

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

${\displaystyle D_{\nu ,\theta ,l}=\{\alpha$ :|\alpha |=l,\sum _{x\in \alpha }\mu (x)\geq \lambda \},}

где ${\displaystyle \mu (x)=\log \nu (x),\,\lambda =\log \theta }$.

Пусть ${\displaystyle \{\alpha$ :|\alpha |=l',\prod _{x\in \alpha }\nu (x)=\theta '\}} . Тоді визначимо часткові словники ${\displaystyle D_{\nu ,\theta ,l,\theta ',l'}=\{\beta$ :\alpha \beta \in D_{\nu ,\theta ,l}\}} . Заметим, что ${\displaystyle D_{\nu ,\theta ,l,\theta ',l'}}$ определен, так как ${\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 }$.

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

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

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

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

b. з імовірністю ${\displaystyle }$негайно блокується з'єднання.

Зауваження

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

2. процесс входа в систему использует веб-браузер и cookie необходимы;

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

4. ймовірність ${\displaystyle }$- є функція пари login/password. Можливі випадки, коли для фіксованих значень login/password будуть відбуватися або тільки блокування облікового запису або тільки генерації RTT-повідомлень при багаторазовій помилці.

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), який вони поділяють).${\displaystyle }$${\displaystyle }$

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

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

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

3. призначений для користувача процес вибирає випадковий ${\displaystyle x}$ посилає ${\displaystyle H(d)^{x}}$TPM, де ${\displaystyle H}$ — хеш-функція;

4. TPM обирає випадковий ${\displaystyle y}$ посилає ${\displaystyle H(d)^{y}}$ користувальницькому процесу;

5. кожен з них обчислює секрет ${\displaystyle s=H(d)^{xy}}$;

6. ${\displaystyle w}$ замінюється на ${\displaystyle s}$к HMAC-ключ.

Зауваження

1. обмеження, що накладаються на вибір ${\displaystyle }$ описані в алгоритмі обміну ключами Діффі-Геллмана;

2. вибір хеш-функції ${\displaystyle }$ визначається методом шифрування в криптопроцесорі (чип TPM).

3. протокол допускає покращення.[11]