Райдужна таблиця, Контроль Розуму, FANDOM powered by Wikia

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

Теорія Правити

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

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

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

Таблиці можуть зламувати тільки ту хеш-функцію, на яку вони створювалися, тобто таблиці для MD5 можуть зламати тільки хеш MD5. Теорія даної технології була розроблена Philippe Oechslin [1] як швидкий варіантtime-memory tradeoff[2] . Вперше технологія використана в програмі Ophcrack для злому хешей LanMan, які використовуються в MicrosoftWindows. Пізніше була розроблена більш досконала програма RainbowCrack, яка може працювати з великою кількістю хешів, наприклад LanMan, MD5, SHA1 та ін. Наступним кроком було створення програми The UDC, яка дозволяє будувати Hybrid Rainbow таблиці не за набором символів, а за набором словників, що дозволяє відновлювати довші паролі (фактично необмеженої довжини).

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

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

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

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

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

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

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

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

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

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

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

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

де + означає конкатенацію.

Для відновлення такого пароля зломщику необхідні таблиці для всіх можливих значень затравки.

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

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

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