RainbowCrack

RainbowCrack

Тип	взлом хешей
Разработчик	Zhu Shuanglei
Операционная система	Windows и Linux
Последняя версия	1.5 (26 августа 2010)
Сайт	http://project-rainbowcrack.com/

RainbowCrack — компьютерная программа для быстрого взлома хешей. Является реализацией техники Филиппа Окслина faster time-memory trade-off.^[1]Она позволяет создать базу предсгенерированных LanManager хешей, с помошью которой можно почти мгновенно взломать практически любой алфавитно-цифровой пароль.

Введение

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

Обычно хэши и алгоритм хэширования известны всем, но обратное преобразование слишком сложно. На этом основывается безопасность многих систем.

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

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

История

В 1982 году была создана основная часть проекта RainbowCrack, но у неё было несколько недостатков, связанных с пересечениями цепочек. Поэтому проекты, созданные в то время, до сих пор являются не столь эффективными. Для исправления этих недостатков, в начале 90-х годов создатели UNIX-систем внесли изменения в данный проект, тем самым оказав большое влияние на развитие метода. Они ввели динамическую составляющую в хэш-функцию, создающую уникальную функцию для каждой отдельной UNIX-систем. В то же время Internet-проекты, системы Windows, базы данных до сих пор продолжают использовать статические хэш-функции, для которых за один полный проход ключевого пространства можно расшифровать все пароли сервисов и целого класса программ.

В 2003 году частично решена проблема пересечений цепочек, в связи с чем проект стал работать эффективнее.

В конце 2004 года в сеть были выложены исходники программы, которая создает таблицы и подбирает пароли по новой версии алгоритма: [1]

В 2005 году в BitTorrent появились готовые посчитанные таблицы (около 120 ГБ) для основного ключевого пространства паролей LanMan (авторизация Windows): [2] (уже закрыт).

В том же 2005 году было запущено несколько проектов: Латышский [3], Русский [4] и др, где все желающие имели возможность использовать эти таблицы через онлайн-сервис. Сейчас все эти проекты закрыты.

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

Сейчас проект RainbowCrack расширяет количество задействованных серверов.

Основная проблема

Размер радужных таблиц слишком большой. Для решения этой проблемы используется следующий способ: хэши располагаются в цепочки по несколько тысяч комбинаций. Зная одну цепочку мы можем получить следующую комбинацию из предыдущей с помощью функции хэширования. В таблицы записываются только начало и конец цепочки. Для нахождения пароля по такой таблице, нужно применить к заданному хэшу функцию хэширования много раз (зависит от длины цепочек) и на очередном цикле получится хэш, который является концом одной из цепочек в радужной таблице. После этого мы прогоняем эту цепочку и заново применяем функцию хэширования от начального до нужного нам хэша. После нескольких цепочек мы находим комбинацию, соответствующую заданному хэшу - это и есть искомый пароль.

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

Описание алгоритма

Программное обеспечение RainbowCrack состоит из следующих частей:

• rtgen — программа для генерации радужных таблиц.

• rtsort- программа для сортировки радужных таблиц, порожденных rtgen.

• rcrack-программа для поиска радужных таблиц, упорядоченных по rtsort.

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

Шаг 1.Использование rtgen для генерации радужных таблиц

Для начала генерации таблиц необходимо определить следующие параметры:

rtgenhash_algorithmcharsetplaintext_len_minplaintext_len_maxtable_indexchain_lenchain_numpart_index

Объяснение этих параметров

Параметр	Смысл
hash_algorithm	Хэш-алгоритм (LM, NTLM, md5 и т.д.).
charset	Кодирование всех открытых текстов в радужной таблице. Все возможные кодировки определены в Charset.txt файле.
plaintext_len_min plaintext_len_max	Эти два параметра определяют возможную длину всех открытых текстов в радужной таблице. Если кодировка является числовой то plaintext_len_min равно 1, и plaintext_len_max равно 5. Тогда текст "12345", скорее всего будет включен в таблицу, а "123456" не будет.
table_index chain_len chain_num part_index	Table_index связан с "reduce function", которая используется в радужной таблице. Chain_len — длина каждой «Радужной цепи» в таблице. «Радужная цепь» размером 16 байт является наименьшей единицей в радужной таблице. Радужная таблица содержит много радужных цепей. Chain_num — число радужных цепочек в таблице. Part_index — параметр, определяющийся, как «startpoint» при генерации каждой радужной цепи. Он должен быть числом (или начинаться с цифры) в RainbowCrack 1,3 и 1,4.

Пример

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	$36 + 36^2 + 36^3 + 36^4 + 36^5 + 36^6 + 36^7 = 80603140212$ Ключевое пространство — количество возможных открытых текстов для кодировки, plaintext_len_min и plaintext_len_max выбраны.
table size	3 GB
chain_num	33554432
success rate	0,999 Шанс успеха 99,9 %.
table generation commands	Команды, использующиеся при создании радужных таблиц такие : rtgen md5 loweralpha-numeric 1 7 0 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 1 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 2 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 3 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 4 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 5 3800 33554432 0 Для создания NTLM или LM-таблиц, необходимо заменить «md5» на «NTLM» или «LM». Для создания alpha-numeric charset, необходимо заменить «loweralpha-numeric» на "alpha-numeric ".

В итоге будут созданы следующие файлы:

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

Шаг 2.Использование rtsort для сортировки радужных таблиц

Радужные таблицы, порожденные программой rtgen, необходимо обработать, для того чтобы поиск по ним стал легче. Программа rtsort используется для сортировки "end point" всех радужных цепочек в радужных таблицах.

Используются следующие команды :

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

Каждая команда выполняется несколько минут. Программа rtsort записывает отсортированые радужные таблицы в исходном файле. Если свободный объем оперативной памяти системы меньше размера отсортированных радужных таблиц, то для хранения оставшихся данных будет выделено место на жестком диске.

Шаг 3.Использование rcrack программы для поиска радужных таблиц

Преимущества

• Большая мощность системы расшифровки паролей.

• Процесс расчёта таблицы может быть продолжен после его некорректного прерывания или зависания машины .

• При расчетах требуется мало памяти (2 МБ).

• Входные данные занимают мало памяти ( несколько байт для одной таблицы ).

• В программу, которая позволяет расшифровать пароли по полученным таблицам, можно добавляться новые алгоритмы хэширования. Таким образом существует возможность создания собственного проекта, аналогичного RainbowCrack.

Недостатки

• На данный момент в таблицах еще нет паролей из символов кириллицы.

• В таблицах могут присутствовать либо только прописные, либо только строчные символы, а пароли вида LanMan (Windows) не различают строчные/прописные символы.

Результаты

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

Примечания

1. ↑ Philippe Oechslin Making a Faster Cryptanalytic Time-Memory Trade-Off // Lecture Notes in Computer Science. — 2003. — Т. 2729. — С. 617-630. — DOI:10.1007/978-3-540-45146-4_36
2. ↑ The Ethical Hacker Network — Tutorial: Rainbow Tables and RainbowCrack
3. ↑ RainbowCrack - Распределённые вычисления
4. ↑ А.В. Аграновский, И.В. Мамай O методах оптимизации алгоритма RainbowCrack в целях аудита информационной безопасности web-систем // Системы управления и информационные технологии. — 2006. — № 4.1 (26). — С. 108-111.
5. ↑ Проект RainbowCrack :: Распределённые вычисления в Интернете

См. также

• Полный перебор
• Перебор
• MD5

Ссылки

• project-rainbowcrack.com — официальный сайт RainbowCrack (англ.)