RainbowCrack

У той час як більшість проектів, пов'язаних з комп'ютерною безпекою, витрачає багато часу для злому пароля шифрувальних систем (простий перебір), RainbowCrack за час, порівнянний з часом злому одного хеша простим перебором, отримує таблиці хешів, за якими з дуже високою ймовірністю можна в тисячі разів швидше зламати будь-який хеш з перевіреного діапазону.[2]

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

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

Стандартний клієнт підтримує наступні алгоритми: LM, NTLM, MD5, SHA1, MYSQLSHA1, HALFLMCHALL, NTLMCHALL, ORACLE-SYSTEM і MD5-HALF, інші алгоритми можуть бути підключені у вигляді плагінів. [4]

У 1982 році була створена основна частина проекту RainbowCrack, але у неї було кілька недоліків, пов'язаних з перетинами ланцюжків. Тому проекти, створені у той час, до цих пір є не настільки ефективними. Для виправлення цих недоліків у початку 90-х років творці UNIX-систем внесли зміни в проект, тим самим надавши великий вплив на розвиток методу. Вони ввели динамічну складову в хеш-функцію, котра створює унікальну функцію для кожної окремої UNIX-системи. У той же час Internet-проекти, системи Windows, бази даних, досі продовжують використовувати статичні хеш-функції, для яких за один повний прохід ключового простору можна розшифрувати всі паролі сервісів і цілого класу програм.

У 2003 році частково вирішена проблема перетинів ланцюжків, у зв'язку з чим проект став працювати ефективніше.

В кінці 2004 року в мережу були викладені вихідні коди програми, яка створює таблиці і підбирає паролі за допомогою нової версії алгоритму:

У 2005 році в BitTorrent з'явилися готові пораховані таблиці (близько 120 ГБ) для основного ключового простору паролів LanMan (авторизація Windows): (вже закритий).

У тому ж 2005 році було запущено кілька проектів: Латвійський , Російський та ін., де всі бажаючі мали можливість використовувати ці таблиці через онлайн-сервіс. Зараз всі ці проекти закриті.

Наприкінці 2005 року був запущений проект . Його можна було поліпшити, збільшуючи розміри ланцюжків, тобто зменшуючи розміри таблиць (чим менше таблиця, тим менше час пошуку по ній) і надавши всім бажаючим доступ до подібного сервісу.[5]

Зараз проект RainbowCrack розширює кількість задіяних серверів.

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

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

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

Програмне забезпечення RainbowCrack складається з наступних частин:

• rtgen — програма для генерації райдужних таблиць.
• rtsort - програма для сортування райдужних таблиць, породжених rtgen.
• rcrack — програма для пошуку райдужних таблиць, упорядкованих за rtsort.

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

rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index

Приклад

hash_algorithm	Lm, NTLM або md5
charset	alpha-numeric = [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789] або loweralpha-numeric = [abcdefghijklmnopqrstuvwxyz0123456789]
plaintext_len_min	1
plaintext_len_max	7
chain_len	3800
chain_num	33554432
key space	${\displaystyle }$ Ключовийе простір — кількість можливих відкритих текстів для кодування, plaintext_len_min і plaintext_len_max вибрані.
table size	3 GB
chain_num	33554432
success rate	0,999 Шанс успіху 99,9 %.
table generation commands	Команди, що використовуються при створенні райдужних таблицьтакі: Для створення NTLM або LM-таблиць, необхідно замінити «md5» на «NTLM» або «LM». Для створення alpha-numeric charset необхідно замінити «loweralpha-numeric» на «alpha-numeric».

У результаті будуть створені наступні файли:

md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt    512 MB
md5_loweralpha-numeric#1-7_1_3800x33554432_0.rt    512 MB
md5_loweralpha-numeric#1-7_2_3800x33554432_0.rt    512 MB
md5_loweralpha-numeric#1-7_3_3800x33554432_0.rt    512 MB
md5_loweralpha-numeric#1-7_4_3800x33554432_0.rt    512 MB
md5_loweralpha-numeric#1-7_5_3800x33554432_0.rt    512 MB

rtsort md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt
rtsort md5_loweralpha-numeric#1-7_1_3800x33554432_0.rt
rtsort md5_loweralpha-numeric#1-7_2_3800x33554432_0.rt
rtsort md5_loweralpha-numeric#1-7_3_3800x33554432_0.rt
rtsort md5_loweralpha-numeric#1-7_4_3800x33554432_0.rt
rtsort md5_loweralpha-numeric#1-7_5_3800x33554432_0.rt

• Велика потужність системи розшифровки паролів.
• Процес розрахунку таблиці може бути продовжений після його некоректного переривання або зависання машини.
• При розрахунках потрібно мало пам'яті (2 МБ).
• Вхідні дані займають мало пам'яті (кілька байт для однієї таблиці).
• В програму, яка дозволяє розшифрувати паролі за отриманими таблицями, можна додавати нові алгоритми хешування. Таким чином, існує можливість створення власного проекту, аналогічного RainbowCrack.

• На даний момент в таблицях ще немає паролів з символів кирилиці.
• У таблицях можуть бути присутні або великі, або тільки малі символи, а паролі виду LanMan (Windows) не розрізняють малі/великі літери.

На даний момент розмір райдужних таблиць перевищує 900 ГБ. Вони дозволяють із заданого хеша за кілька хвилин з дуже високою ймовірністю (близько 99 %) знайти пароль довжиною не більше 7 символів, що складається з букв, цифр і багатьох спеціальних символів. Процес розшифровки паролів реалізується наступними алгоритмами: LanMan, SHA1, NT, MD2, Cisco PIX, MD4, MD5, MySQL 3.23, RIPEMD-160, MySQL SHA1 (бази даних).

• Повний перебір
• Перебір за словником
  
• MD5

• Офіційний сайт