Использование rainbow tables для сверхбыстрого взлома хэшей Эта статья написанна nikitoz(ом) и взята из журнала Хакер я решил выложить, может кто не читал. Ведь материал по этой теме в интернете в основном на английском. В современных системах аутентификации огромную роль играют хэш-функции - специальные отображения, которые по переданной им строке генерируют некоторую сигнатуру, отпечаток, или шифруют эту строку. На страницах нашего журнала мы не раз сталкивались с проблемой, когда нужно было провести обратную операцию: по известному значению хэш-функции восстановить строку-оригинал. Такого рода задачи возникают довольно часто. Если хочешь узнать пользовательский пароль во взломанной системе, подключиться к чужому VPN-серверу, то тебе придется ломать захваченный хэш. Сегодня мы поговорим о наиболее современном и прогрессивном подходе к решению этой проблемы, который позволяет раздраконивать хэши за считанные часы. [начало] В большинстве систем пользовательские пароли не хранятся в открытом виде, размещаются только лишь соответствующие им значения хэш-функций. При этом возникает такая ситуация, что даже сама система не знает пользовательского пароля: она располагает лишь его отпечатком и при аутентификации сравнивает хэш переданной пользователем строки с тем, что хранится внутри системы. Таким образом, даже если взломщику удается захватить хэши пользовательских паролей, обычно ему не удается использовать эти значения для своих темных делишек. К сожалению, сейчас многие проекты страдают довольно странной, на мой взгляд, вещью: они сами предоставляют интерфейс для аутентификации через хэш-пароля, обращая в маразм всю эту затею с шифрованием. За примерами далеко ходить не надо: куча 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. Это довольно здоровое выражение, и само по себе нас мало интересует, нас больше заботит, что оно показывает. Собственно, ничего кардинально нового: при росте размеров таблицы вероятность P* практически перестает увеличиваться. По этой причине для эффективного использования метода необходимо создавать несколько таблиц, сгенерированных независимым образом. В этом случае общая вероятность успеха (P) выражается так: P=1-(1-P*)^l, l - число таблиц. Эту формулу очень легко получить из простейших соображений: (1-P*) - это вероятность того, что мы не найдем ключ в одной из таблиц; (1-P*)^l - вероятность, что вообще не найдем ключ ни в одной из l таблиц. Соответственно, вероятность обратного события - это P=1-(1-P*)^l. Следует отметить, что эта формула верна лишь в том случае, если обеспечена независимость генерации таблиц, то есть для каждой таблицы выбрана собственная, уникальная срезающая функция R. [конкретные вещи] Думаю, то, что я рассказал тебе, будет достаточно для понимания более практических вещей. Давай познакомимся с конкретным софтом, научимся с ним работать и, вообще, понюхаем эти радуги в таблицах. На самом деле, в Сети не так уж и много информации о rainbow tables: если ты поищешь инфу в гугле, то, по существу, увидишь только одну содержательную ссылку - www.antsight.com/zsl/rainbowcrack. Однако смею тебя заверить, ее нам будет предостаточно! Это сайт проекта с говорящим названием RainbowCrack, главная ценность которого находится в разделе Downloads. Там предлагается скачать софтину, с помощью которой можно генерировать цепочки ключей, и взламывать при помощи уже созданных таблиц конкретные хэши. Софтина поставляется в том числе и в исходных кодах, так что при наличии у тебя желания и необходимого опыта, можно будет ознакомиться с конкретной реализацией всего того, о чем мы говорили выше. Мы же в этой статье просто научимся пользоваться этой программой для генерации rainbow-таблиц и взлома хэшей. Под FreeBSD собрать эту программу у меня не получилось, и поэтому я решил все эксперименты проводить на виндовой машине - благо на сайте лежит уже готовый бинарник, и париться с компиляцией не нужно. Последняя версия системы - 1.2, она поддерживает работу с хэшами LanManager, md5, sha1, а также позволяет пользователю легко прикручивать к программе свои собственные алгоритмы, которых нет в базовом списке. Скачав с сайта архив с бинарниками, ты найдешь внутри несколько бинарных файлов. Нас сейчас больше всех интересует rtgen - именно эта программа генерирует цепочки символов. Для запуска софтины необходимо указать все требуемые параметры таким образом: 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/N), где П - произведение по i от 1 до t, длины цепочки; m - число новых элементов в i-ой цепочке. Числа m вычисляются итеративно, каждое последующее значение зависит от предыдущего, и, в конечном итоге, все они зависят от начального. Сам понимаешь, что расчет такой конструкции и ее пересчет при изменении начального условия - задача очень трудоемкая, компьютер возится над ней долго. Рассчитать, как меняется вероятность в зависимости от числа цепочек, их длины и количества таблиц, даже с большим шагом, - все это занимает много времени. Да и построить график функции трех переменных - тоже задачка наркоманская. Поэтому для построения графика вероятности нужно по очереди фиксировать одну из переменных - ну, скажем, число таблиц. Понятно, что разумное число - что-то в районе трех-четырех-пяти. Если зафиксировать этот параметр, то уже можно построить вероятностную поверхность и судить об оптимальных параметрах. На скрине неподалеку отсюда изображен пример такой поверхности, которую я построил в Maple. Там отчетливо видно две оси - Mb и t. Mb - это объем таблиц в мегабайтах, t - длина цепочек. Сама поверхность отображает, как меняется вероятность по этим параметрам. Секущая плоскость соответствует вероятности 0.95. Соответственно, для выполнения этого условия тебе нужно выбирать все точки, лежащие над секущей плоскостью или прямо на линии пересечения поверхностей. При этом у тебя остается выбор, какому из параметров отдать приоритет - занимаемому на диске месту, или времени поиска. Тут следует еще отметить такой факт, что время поиска рассчитывается исходя из того, что вся текущая таблица находится в памяти компьютера, то есть время доступа очень мало по сравнению с вычислением хэш-функции. Это надо иметь в виду, на практике все может быть совершенно по-другому. Что же касается параметров, то, наверное, лучше всего будет взять золотую середину, точку, где и место, и время «съедается» сравнительно мало. Она отмечена крестиком на графике. Итак, с выбором параметров для генерации таблиц мы разобрались. А так ли уж легко их сгенерировать? Ну нет, конечно, совсем нелегко, это опять занимает кучу времени. Ведь для построения цепочки из 2000 элементов нужно вычислить функцию столько же раз. На практике это может занимать сутки, недели и даже года. Однажды, проделав такую работу, сгенерированные таблицы можно будет выгодно сбыть, или использовать для собственных нужд. Разумеется, можно и не заморачиваться над генерацией собственных таблиц, можно их просто купить за 500 долларов. Сейчас я расскажу о том, как использовать уже сгенерированные таблицы. Первым делом, для увеличения скорости поиска, их нужно пересортировать при помощи утилиты rtsort, в качестве параметра ей нужно просто передать имя файла с таблицей. После этого уже можно запускать утилиту rcrack, которая, собственно, и будет ломать твой хэш, отыскивая его в сгенерированных ранее таблицах. Запускается rcrack следующим образом: rcrack *.rt -h 5d41402abc4b2a76b9719d911017c592
2 MegaBits Заипёшься их генерировать, эти таблички... товарищам с инетом от 256кб/с советую качать просто их.....
Тема старая, но все же. Где скачать описываемые программы, указанный сайт уже не работает. Да и готовые таблицы тоже интересно скачать.
Качай: http://project-rainbowcrack.com/ http://rainbowtables.shmoo.com/ Читай: http://en.wikipedia.org/wiki/Rainbow_table
статейка бородатая , дк и щас новые технологии цветут и пахнут и для брута используется наглый перебор , для этого нужно топовое железо , или достаточно проц+графика , и уже будет результат!
да не, для одиночных брутфорс атак по ша или мд5 они пока ещё актуальны. При условии, что не смущает необходимость скачать гигов под 400 этих табл.
