Райдужна таблиця

Схема спрощеної райдужної таблиці з ланцюжків довжиною, що дорівнює трьом. R1 R2 R3 — функції редукції, H — функція хешування.

Райдужна таблиця (англ. rainbow table) — спеціальний варіант таблиць пошуку (англ. lookup table) для звернення криптографічних хеш-функцій, які використовують механізм розумного компромісу між часом пошуку таблицею і займаною пам'яттю (англ. time-memory tradeoff). Райдужні таблиці використовуються для розкриття паролів, перетворених за допомогою важкозворотної геш-функції, а також для атак на симетричні шифри на основі відомого відкритого тексту. Використання функції формування ключа з застосуванням солі робить цю атаку неможливою.

Райдужні таблиці є розвитком більш раннього й простого алгоритму, запропонованого Мартіном Геллманом.

Передумови появи

Комп'ютерні системи, які використовують паролі для автентифікації, повинні якимось чином визначати правильність введеного пароля. Найпростішим способом вирішення даної проблеми є зберігання списку всіх допустимих паролів для кожного користувача. Мінусом даного методу є те, що в разі несанкціонованого доступу до списку, зловмисник дізнається всі паролі. Більш поширений підхід полягає у зберіганні значень криптографічної геш-функції від парольної фрази.

Однак більшість гешів швидко обчислюються, тому зловмисник отримавши доступ до гешів, може швидко перевірити список можливих паролів на валідність. Щоб уникнути цього, потрібно використовувати більш довгі паролі, тим самим збільшуючи список паролів, які повинен перевірити зловмисник. Для простих паролів, що не містять сіль, зловмисник може заздалегідь підрахувати значення гешів для всіх поширених і коротких паролів і зберегти їх у таблиці. Тепер можна швидко знайти збіг у заздалегідь отриманій таблиці. Але чим довший пароль, тим більше таблиця, і тим більше пам'яті необхідно для її зберігання.

Альтернативним варіантом є зберігання лише перших елементів ланцюжків гешів. Це потребує більше обчислень для пошуку пароля, але значно зменшить кількість необхідної пам'яті. Райдужні таблиці є поліпшеним варіантом цього методу, які дозволяють уникнути колізій.

Розрахунок ланцюжка гешів

Увага: Ланцюжки хешів, описані в цій статті, відрізняються від описаних у статті Ланцюжок хешів.

Нехай у нас є геш-функція H з довжиною геш n і кінцева множина паролів P. Наша мета — створити структуру даних, яка для будь-якого значення хешу h може знайти такий елемент p з P, що H(p)=h, або визначити, що такого елемента не існує. Найпростіший спосіб зробити це — обчислити H(p) для всіх p з P, але для зберігання такої таблиці потрібно Θ(|P|n) пам'яті, що дуже багато.

Ланцюжки гешів — метод для зменшення цієї вимоги до обсягу пам'яті. Головна ідея — визначення функції редукції R, яка зіставляє значенням геша значення P. Зауважимо, що R не є зверненням геш-функції. Починаючи з вихідного пароля і поперемінно застосовуючи до кожного отриманого значення H і R, ми отримаємо ланцюжок перемежованих паролів і гешів. Наприклад, для набору паролів довжиною в 6 символів і геш-функції, що видає 32-бітні значення, ланцюжок може виглядати так:

$\mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}$

До функції редукції висувається єдина вимога: повертати значення з того ж алфавіту, що і паролі.

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

Для кожного гешу h, значення якого ми хочемо обернути (знайти відповідний йому пароль), обчислюємо послідовність R(…R(H(R(h)))…). Якщо якесь з проміжних значень зійдеться з яким-небудь кінцем будь-якого ланцюжка, ми беремо початок цього ланцюжка і відновлюємо його повністю. З високою ймовірністю повний ланцюжок буде містити значення гешу h, а передуючий йому пароль буде шуканим.

Для прикладу, зазначеного вище, якщо у нас є геш 920ECF10, він породить наступну послідовність:

$\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}$

Оскільки kiebgt є кінцем ланцюжка з нашої таблиці, ми беремо відповідний початковий пароль aaaaaa і обчислюємо ланцюжок, поки не знайдемо хеш 920ECF10:

$\mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10}$

Таким чином, шуканий пароль — sgfnyd.

Варто зауважити, що відновлений ланцюжок не завжди містить шукане значення гешу h. Таке можливо при виникненні колізії функції H або R. Наприклад, нехай дано хеш FB107E70, який на певному етапі породжує пароль kiebgt:

$\mathrm {FB107E70} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {bvtdll} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {0EE80890} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}$

Але FB107E70 не з'являється в ланцюжку, породженої паролем aaaaaa. Це називається помилковим спрацюванням. У цьому випадку, ми ігноруємо збіг і продовжуємо визначати послідовність, породжену h. Якщо згенерована послідовність досягає довжини k без хороших збігів, це означає, що шуканий пароль ніколи не зустрічався в підготовлених ланцюжках.

Вміст таблиці, не залежить від значення досліджуваного гешу, вона обчислюється заздалегідь і використовується лише для швидкого пошуку. Збільшення довжини ланцюжка зменшує розмір таблиці, але збільшує час пошуку потрібного елемента в ланцюжку.

Прості ланцюжки гешів мають декілька недоліків. Найсерйозніший — можливість злиття двох ланцюжків в один (генерація одного і того ж значення в різних ланцюжках). Всі значення, згенеровані після злиття, будуть однаковими в обох ланцюжках, що звужує кількість охоплюваних паролів. Оскільки перегенеровані ланцюжки зберігаються не повністю, неможливо ефективно порівнювати всі згенеровані значення між собою. Як правило, про відсутність колізій геш-функції H піклується сторона, що забезпечує шифрування паролів, тому що основна проблема криється у функції редукції R.

Інша серйозна проблема — підбір такої функції R, яка буде генерувати паролі з необхідним покриттям і розподілом. Обмеження вихідного алфавіту є серйозним обмеженням для вибору такої функції.

Райдужні таблиці

Райдужні таблиці є розвитком ідеї таблиці геш-ланцюгів. Вони ефективно вирішують проблему колізій шляхом введення послідовності функцій редукції R₁, R₂, …, R_k. Функції редукції застосовуються по черзі, перемежаючись з функцією гешування: H, R₁, H, R₂, …, H, R_k.

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

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

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

• перший ланцюжок будується на припущенні, що шуканий геш зустрінеться на останній позиції в табличному ланцюжку, тому складається з єдиного значення R_k(h);
• другий ланцюжок будується на припущенні, що шуканий геш зустрінеться на передостанній позиції в табличному ланцюжку, тому виглядає так: R_k(H(R_k-1(h)));
• аналогічно, нарощуючи довжину ланцюжка і застосовуючи функції редукції з меншими номерами, отримуємо інші ланцюжки. Останній ланцюжок буде мати довжину k і містити всі функції редукції: R_k(H(R_k-1(H(…H(R₁(h))…))))

Також зміниться і визначення помилкового спрацювання: якщо ми неправильно «вгадаємо» позицію шуканого гешу, це буде відкидати тільки один з k згенерованих ланцюжків; при цьому все ще може залишатися можливість знайти вірний геш для даного табличного ланцюжка, але на іншій позиції.

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

Приклад

Є геш (re3xes), який треба обернути (відновити пароль), і райдужна таблиця отримана з використанням трьох функцій редукції.

1. Обчислюємо ланцюжок довжини 1 від початкового гешу: R₃(«re3xes»)="rambo". Цей пароль не є кінцем жодного табличного ланцюжка.
2. Обчислюємо ланцюжок довжини 2: R₃(H(R₂(«re3xes»)))="linux23".
3. Даний пароль знайдений в таблиці. Беремо початок знайденого ланцюжка (пароль passwd).
4. Відновлюємо табличний ланцюжок до тих пір, поки не отримаємо вихідний геш re3xes.
5. Шуканий геш знайдений в ланцюжку, атака успішна. Передуючий даному значенню гешу пароль culture є шуканим.

Час і використання пам'яті

Райдужна таблиця створюється побудовою ланцюжків можливих паролів. Створення таких таблиць вимагає більше часу, ніж потрібно для створення звичайних таблиць пошуку, але значно менше пам'яті (аж до сотень гігабайт, при обсязі для звичайних таблиць N слів для райдужних потрібно всього порядку N^2/3).

При цьому хоч вони і вимагають більше часу (порівняно з простими методами на кшталт атаки по словнику) на відновлення вихідного пароля, але на практиці більше реалізовуються (для побудови звичайної таблиці для 6-символьного пароля з байтовими символами потрібно 256⁶ = 281 474 976 710 656 блоків пам'яті, в той час як для райдужної — всього 256^6·⅔ = 4 294 967 296 блоків).

Таблиці можуть зламувати тільки ту геш-функцію, для якої вони створювалися, тобто таблиці для MD5 можуть зламати тільки геш MD5. Теорія даної технології була розроблена Philippe Oechslin як більш швидкий варіант time-memory tradeoff. Вперше технологія використана в програмі Ophcrack для злому гешів LanMan (LM-геш), які використовуються в Microsoft Windows. Пізніше була розроблена більш досконала програма RainbowCrack, яка може працювати з великою кількістю гешів, наприклад, LanMan, MD5, SHA1 та іншими.

Наступним кроком було створення програми The UDC, яка дозволяє будувати Hybrid Rainbow таблиці не по набору символів, а по набору словників, що дозволяє відновлювати довші паролі (фактично необмеженої довжини).

Застосування

При генерації таблиць важливо знайти найкраще співвідношення взаємопов'язаних параметрів:

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

Вищеназвані параметри залежать від налаштувань, заданих при генерації таблиць:

• допустимий набір символів;
• довжина пароля;
• довжина ланцюжка;
• кількість таблиць.

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

Хоча застосування райдужних таблиць полегшує використання повного перебору (тобто методу грубої сили — bruteforce) для підбору паролів, в деяких випадках необхідні для їх генерації/використання обчислювальні потужності не дозволяють окремому користувачу досягти бажаних результатів за прийнятний час. Наприклад, для паролів довжиною не більше 8 символів, що складаються з літер, цифр і спеціальних символів !@#$%^&*()-_+=, загешованих алгоритмом MD5, можуть бути згенеровані таблиці з наступними параметрами:

• довжина ланцюжка — 1400
• кількість ланцюжків — 50 000 000
• кількість таблиць — 800

При цьому ймовірність знаходження пароля за допомогою даних таблиць складе 0,7542 (75,42 %), самі таблиці займуть 596 ГіБ, генерація їх на комп'ютері рівня Пентіум-3 1 ГГц займе 3 роки, а пошук 1 пароля по готових таблицях — не більше 22 хвилин.

Проте процес генерації таблиць можливо розпаралелити, наприклад, розрахунок однієї таблиці з вищенаведеними параметрами займає приблизно 33 години. У такому випадку, якщо в нашому розпорядженні є 100 комп'ютерів, усі таблиці можна згенерувати через 11 діб.

Захист від райдужних таблиць

Один з поширених методів захисту від злому за допомогою райдужних таблиць — використання необоротних геш-функцій, які включають salt («сіль», «модифікатор»). Існує безліч можливих схем змішування затравки і пароля. Наприклад, розглянемо таку функцію для створення геш від пароля:

геш = MD5( пароль + сіль )

Для такого відновлення пароля зловмиснику необхідні таблиці для всіх можливих значень солі. При використанні такої схеми, сіль повинна бути досить довгою (6-8 символів), інакше зловмисник може обчислити таблиці для кожного значення солі, випадкової і різною для кожного пароля. Таким чином два однакових пароля будуть мати різні значення гешів, якщо тільки не буде використовуватися однакова сіль.

По суті, сіль збільшує довжину і, можливо, складність пароля. Якщо таблиця розрахована на деяку довжину або на деякий обмежений набір символів, то сіль може запобігти відновленню пароля. Наприклад, у старих Unix-паролях використовувалася сіль, розмір якої становив лише 12 біт. Для злому таких паролів зловмисникові потрібно було порахувати всього 4096 таблиць, які можна вільно зберігати на терабайтних жорстких дисках. Тому в сучасних програмах намагаються використовувати більш довгу сіль. Наприклад, в алгоритмі хешування bcrypt використовується сіль розміром 128 біт. Така довжина солі робить попередні обчислення просто безглуздими. Іншим можливим способом боротьби проти атак, що використовують попередні обчислення, є розтягнення ключа(англ. key stretching). Наприклад:

ключ = геш (пароль + сіль)
for 1 to 65536 do
ключ = геш(ключ + пароль + сіль)

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

Даний метод застосовується в наступних алгоритмах хешування: MD5, в якому використовується 1000 повторень, і bcrypt. Альтернативним варіантом є використання посилення ключа (англ. key strengthening), який часто приймають за розтягнення ключа. Застосовуючи даний метод, ми збільшуємо розмір ключа за рахунок додавання випадкової солі, яка потім спокійно видаляється, на відміну від розтягування ключа, коли сіль зберігається і використовується в наступних ітераціях.

Використання

Практично всі дистрибутиви ОС Unix, GNU/Linux і BSD використовують геші з сіллю для зберігання системних паролів, хоча багато програм, наприклад, інтернет-скрипти, використовують простий геш (зазвичай MD5) без «солі». ОС Microsoft Windows і Windows NT використовують геші LM-геш і NTLM, які також не використовують «сіль», що робить їх найбільш популярними для створення райдужних таблиць.

Посилання

• Сторінка Ophcrack Оригінальна дослідна робота з демонстрацією
• Проект RainbowCrack
• oxid.it Містить winrtgen — графічну оболонку для rtgen (утиліти створення таблиць)
• Створення райдужних таблиць для A5/1 (використовується в GSM мережах, поки тільки для відеокарт з CUDA)
• Великі райдужні таблиці від групи Shmoo Group, творців AirSnort