Данный материал любезно предоставлен и взят с разрешения создателя программы UDC - sic57005 Линк на исходный материал - __http://the-udc.com/rus/rus_hrainbow.html Hybrid Rainbow - Новый сверхмощный метод, комбинирующий гибридную атаку с популярной техникой предвычисления. Сочетая в себе гибкость гибридной атаки, удобство и скорость табличного криптоаналза, он позволит с легкость восстанавливать те пароли, которые раньше считали "стойкими" и даже "недоступными для восстановления". Теперь, для любой хеш-функции, единожды посчитав гибридную таблицу по качественному словарю или комбинации словарей, можно за секунды восстанавливать пароли из 12 символов, да и из 13, да даже и из 20... Хотя, в общем-то, длина пароля более не имеет значения. Оглавление 1. Предпосылки 2. Новые рубежи 3. Параметры генератора 4. Параметры предвычислителя 5. Работа с HR из UDC 6. Статистика и примеры 7. Справка по UDC 1. Предпосылки к созданию метода Еще в 2003 году, Philippe Oechslin анонсировал новый метод, названный Rainbow Attack ("Making a Faster Cryptanalytic Time-Memory Trade-Off"), который позволил предвычислять Прямой Перебор. Единожды сгенерировав таблицу для определенного набора символов и определенной длинны пароля (например, 7 латинских символов) и сохранив ее на диск, мы сможем обращаться к таблице сколько угодно раз, и искать пароли для соответствующего набора символов уже не Прямым Перебором, а, выбирая нужные хеш-значения из таблицы, что на порядки сокращает время атаки. Например, после создания таблицы для 7 алфавитно-цифровых символов (на это потребуется больше недели), можно восстановить почти любой пароль из 7 алфавитно-цифровых символов за 20-30 секунд. А вот Прямой Перебор по тому же диапазону займет более суток. Более того, таблицы можно просто скачать из Интернета, при этом даже не придется тратить время на их генерацию. Таблицы, предложенные Philippe Oechslin имеют вероятностный характер - то есть любая таблица по определенному диапазону, не гарантирует 100% вероятность нахождения любого пароля из этого диапазона. И чем больше размер таблицы - тем выше эта вероятность восстановления (Success Rate). И тут мы подходим к основной проблеме Rainbow таблиц. Если мы хотим получить высокую Success Rate для большого диапазона перебора - объем таблицы может быть слишком велик. В частности, таблицы для восстановления всех 8 символьных паролей с вероятностью 99% занимают более 1.5Тб (1500 Гигабайт). А время криптоанализа по ним, никак не меньше времени загрузки их с диска, что уже само по себе довольно ощутимо (порядка 4-5 часов). Конечно же, мы можем сильно уменьшить объем таблиц за счет уменьшения Success Rate; например, для 90% вероятности восстановления того же диапазона объем таблицы уменьшится более чем в 2 раза (700 Гигабайт), а при 1% Success Rate таблица вообще поместится на компакт-диск. Но только вот, что мы сможем восстановить по этим таблицам? Таблица с 1% Success Rate вообще не даст никаких результатов, более эффективно в таком случае использовать Прямой Перебор. А таблица с 90% Success Rate, возможно, не будет содержать как раз самые релевантные комбинации (которые могли бы быть реальными паролями), навроде "password", "testpass" или "qwertyui". Но при этом, сами релевантные комбинации, возможно c легкостью уместить и в 1% исходного диапазона для перебора. Но для этого надо научиться генерировать таблицы так, чтобы они состояли именно из релевантных комбинаций, а не разнообразного "мусора" (т.е. строк, у которых вероятность быть паролем очень низка - "qpdfvlpr", например)... Таблицы, которые предложил Philippe Oechslin, являлись демонстрацией успешности его техники предвычисления, а не специальным средством для восстановления паролей, о чем он и утверждал в abstract'e своей работы. Однако, многие онлайн сервисы, а также новички или любители, сразу же вооружились его методом, в первоначальном виде. И уже в таком виде метод давал неплохие результаты. Однако за 4 года, барьер в 8 символов так и не был преодолен. Обычными Rainbow таблицами нельзя восстановить пароль из 12 символов, например, для MD5, как бы мы ни старались. Да что там 12, огромные сложности возникают уже и с 9 символами. А ведь на многих веб-порталах предлагают ставить пароли не короче 6-10 символов. Как раз для того чтобы их нельзя было подобрать при помощи таблиц... 2. Новые рубежи А теперь представим, что у нас есть генератор, который строит таблицы из релевантных комбинаций, любой заданной длины и в любом количестве. Например, миллиард релевантных слов из 9 букв. Чем поможет такая таблица? С одной строны, реальное заполнение диапазона из 9 букв составит меньше одной сотой процента. И по отношению к случайной строке из 9 букв ее Success Rate будет такой же (0.01%). Но с другой, стороны, каждая из релевантных комбинаций должна быть проверена в первую очередь, по причине большей реальной вероятности успеха. Возможно, по отношению к паролям, придуманным человеком, такая таблица будет иметь до 10% Success Rate (а может и больше). И в этом случае, мы получаем выигрыш КПД по отношению к классическим Rainbow таблицам до 10%/0.01% = 1000 раз. Здесь я говорю "возможно", потому что реальная вероятность успеха полностью зависит от параметров генератора, которые пользователь устанавливает самостоятельно. Самым примитивным способом предвычисления является текстовой словарь, состоящий целиком из релевантных комбинаций. По разным источникам, его Success Rate меняется от 5% до 90% (в зависимости от словаря и от исходной выборки хеш-значений). Но это уже в тысячи раз лучше, чем для Rainbow таблиц аналогичного размера. Теперь посмотрим в сторону пользователя, который пытается придумать сложный для восстановления пароль. Пусть он даже знает, что у нас есть таблица из 100 миллиардов релевантных слов разной длины (такая таблица может занимать пару Гигабайт), но он не знает что это за таблица и какие слова в ней содержатся. Как выбрать пароль, который не восстановят? Ведь мы можем восстановить всего-то 100 миллиардов разных слов, а он может выбрать любой из практически неогранниченного количества. Может быть, он возьмет пароль "H@rdPas$word", которого наверняка нету в нашей таблице. Только вот откуда ему знать это. Возможно, у нас не будет пароля "peopmmssrl", но а если он у нас есть? Таким образом, граница "невозможности восстановления" стирается, уже благодаря одной сравнительно небольшой таблице. А если у каждого криптоаналитика будет по своей большой таблице релевантных слов?... Также теряет смысл и отношение "быть более надежным" для паролей. Будет ли пароль "testpassword" более надежным чем "326"? В одной таблице не будет первого, в другой не будет второго, а в третьей будут оба. 3. Основные параметры генератора Из чего мы будем генерировать наши таблицы? Для первого приближения Hybrid Rainbow ответ прост - из словарей. Возьмем один словарь D1. Какие слова мы можем получить из него? Например, добавим к каждому слову строку "2007". Или удвоим каждое слово. Или запишем в обратном порядке. Каждое такое действие назовем операцией. Назовем правилом последовательность операций. Например, удвоить слово, и записать результат в обратном порядке. Каждое правило "добавляет" в наш словарь еще одно слово, получаемое применением правила к исходному слову словаря. Значит, имея N правил, мы получим в N раз больше слов, чем в исходном словаре. Достоинство такого метода - его скорость, а также отсутствие необходимости держать на диске что-то кроме исходных слов и списка правил. А есть и другой способ. Возьмем из словаря D1 какое-то слово W и добавим это слово к каждому слову из исходного словаря D1 (включая и W). Получим новый словарь, с количеством слов равным исходному. Теперь возьмем другое слово V и проделаем ту же операцию. Да и вообще, проделаем ее для всех слов из D1. Если в D1 было ровно M слов, то мы получим M новых словарей по M слов. Объединим их вместе и получим словарь из M^2 (M квадрат) слов. Такой словарь назовем "Декартовым квадратом D1" и обозначим за D1*D1. Например, если D1 = {test, pass, 1} (три слова), то D1*D1 будет равен {testtest, testpass, test1, passtest, passpass, pass1, 1test, 1pass, 11} (девять слов). Чем этот способ хорош? В первом приближении, он позволяет строить по набору слов всевозможные фразы, из этих слов составленные. Копнем немного глубже. Будем строить словарь не из слов языка, а из кусочков слов. Например, по четырехбуквенным комбинациям. Причем не будем включать в словарь те комбинации, которые редко встречаются в реальных словах (паролях), навроде "pzla" или "qmzo", а оставим только те, которые являются вероятными, например, "test" или "qqqq". Построим D1*D1. Самое удивительное, что он будет состоять в основном из релевантных слов! Хотя их там будет в квадрат раз больше, чем в исходном словаре. То есть для 1000 релевантных кусочков, мы получим 1 000 000 более-менее релевантных комбинаций из 8 символов. Данное обстоятельство позволяет, с одной стороны, упростить анализ релевантности, с другой стороны, автоматизировать процесс генерации словарей. Теперь обобщим эту технику. Будем строить, не декартов квадрат, а декартово мультипроизведение. По набору словарей D1, D2, ... Dk построим словарь D1*D2*...*Dk, состоящий из всевозможных "фраз", где первое слово берется из первого словаря (D1), второе - из второго (D2), ..., а последнее - из последнего (Dk). Такой словарь будет иметь размер, равный произведению длин всех словарей, участвующих в построении, кроме того, он тоже в некоторой степени сохраняет релевантность. Можно создать обобщенный словарь, который учитывает особенности морфологии. Например, все английские слова можно получить, перемножив prefixes.txt * stems.txt * suffixes.txt (префиксы * основы * суффиксы). Конечно, полученный словарь будет включать не только английские слова, но и "странные" словоформы (например "reasker" или "premainy"), но даже у них релевантность будет выше, чем у случайных наборов символов. Самое главное, что эти три файла с частями слов вместе занимают куда меньше места, чем даже сравнительно небольшой словарь английских слов. Так вот, в Hybrid Rainbow используется именно декартово мультипроизведение, как основной способ генерации релевантных комбинаций. Значит, до начала генерации, необходимо определить все словари с "частичками", в порядке их произведения. Это и является первым параметром метода ( D = {D1, D2, D3, ... Dk} ). 4. Параметризация предвычислителя После того как мы определили нужные нам словари ( D = {D1, D2, D3, ... Dk} ), необходимо задать способ, которым полученное произведение R = D1*D2*...*Dk будет сохранено на диск. Объем полученного словаря |R| будет составлять |D1|*|D2|*...*|Dk|, то есть просто произведение объемов всех словарей. Пусть мы возьмем два словаря на 100 000 и 500 000 слов, и перемножим, получим словарь на 50 000 000 000 слов. Скорее всего, его уже не удастся записать в текстовом виде на диск. При средней длине слова в 9 символов, такой словарь потребует 480 Гб дискового пространства. Для того чтобы сократить этот объем, можно пользоваться параметром длина цепочки. Как и в оригинальном методе Philippe Oechslin, установка длина цепочки в L сокращает объем словаря в L/16 раз. То есть, если в вышерассмотренном примере положить длину цепочки равной 2048, то объем файла на диске сократится до 380 Мб (50 000 000 000 * 16/2048 байт). Однако, при увеличении длины цепочки, время криптоанализа (т.е. подбора пароля по готовой таблице) увеличивается. И если при длине цепочки равной 2048, в среднем на одно хеш-значение потребуется пара секнуд, то уже при длине цепочки равной 10 000, на один хеш придется потратить до пары минут. В общем случае, время криптоанализа зависит от длины цепочки квадратично. Обычно для цепочки, длиннее 100 000 криптоанализ перестает быть эффективным. Один диапазон для предвычисления (R) не обязан быть предвычислен на одном компьютере за один раз. Естественно, метод поддерживает возобновление вычисления после остановки. А для того чтобы эффективней генерировать несколько таблиц по одному диапазону, введен параметр номер таблицы. Таблицы с разными именами и номерами, даже по одному диапазону (R) никогда не будут одинаковыми. Также, следует отметить, что оптимальным образом криптоанализ происходит, если таблица целиком умещается в оперативную память компьютера. Для этого имеет смысл сделать несколько маленьких табличек с разными номерами таблицы, вместо одной большой. А как сделать "маленькую" таблицу? Для этого поможет параметр под именем "Фактор выполнения". Установка в 100% предполагает где-то 45-55% покрытие R (т.е. Success Rate), что является обычно недостаточным. Для 90% Success Rate необходимо поставить фактор выполнения минимум на 300%. При этом время предвычисления будет в 3 (=300%/100%) больше чем время перебора по тому же диапазону. Мы видим, что за то же время, что Прямой Перебор справляется с диапазоном, предвычисления (с фактором выполнения = 100%) покрывают лишь половину диапазона. Это неизбежная плата за уменьшение объема файла-таблицы и увеличение скорости криптоанализа. Маленькие таблицы получаются, за счет установки фактора выполнения на небольшое значение 1% - 25%. У каждой такой таблицы будет свой небольшой Success Rate, но сложив все таблицы вместе мы получим общий Success Rate больше чем у одной таблицы того же объема. Подобный эффект подробно описан в работе Philippe Oechslin.
5. Работа с Hybrid Rainbow из UDC Теперь перейдем к практике. На сегодняшний день, единственной программой, которая поддерживает Hybrid Rainbow, является The UDC, поэтому мы рассмотрим методы, которые The UDC предоставляет для работы с Гибридными Таблицами. Все параметры, связанные с Hybrid Rainbow собраны на одной вкладке под названием "HRainbow атака". Вкладка делится на две части, левая посвящена атаке по готовым табличным файлам, а правая - генерации новых таблиц. Целевая хеш-функция определяется на вкладке "Прогресс", там же и хеш-значения, для которых нужно выполнить перебор. Для начала посмотрим на часть, связанную с атакой, то есть с криптоанализом. В списке слева, отражены уже установленные таблицы. Каждую из них можно либо разрешить (стоит флажок) либо запретить (убрать флажок). Таблицы без флажка будут попросту пропущенны в момент криптоанализа. Нужно это для того, чтобы сэкономить врмя, убирая однозначно неподходящие таблицы (если таковые имеются). Текущий номер указывает на таблицу, с которой начнется криптоанализ. Нумерация идет только по отмеченным таблицам, первая таблица имеет номер ноль. После отметки нужных таблиц, остается только запустить атаку, воспользовавшись соответствующим пунктом главного меню "Восстановление -> Локальное -> HRainbow атака". Вот, собственно, и все. После запуска, можно наблюдать за процессом криптоанализа на вкладке "Консоль", туда будет выводиться детальный отчет о совершаемых действиях. Теперь рассмотрим метод генерации новых таблиц. Для начала, необходимо указать имя файла для сохранения новой таблицы без префиксов и расширений, например, "TestTable01". Чуть ниже - самое главное - список словарей, для произведения. Кнопка сверху слева позволяет добавить словарь вниз списка. Центральная слева кнопка убирает выделенный словарь из списка. Нижняя - очищает спсок полностью. Правая верхняя кнопка позволяет переместить выделенный словарь на одну строчку выше, правая нижняя - на строчку ниже. Порядок словарей в списке отражает порядок следования слов в целевой фразе. Если бы верхний словарь был всего из одного слова "test", а нижний из двух "pass" и "word", то в таком порядке мы бы получили две комбинации: "testpass" и "testword". Поменяв словари местами, получим: "passtest" и "wordtest". Старайтесь не выбирать огромные словари, для большинства целей нужны маленькие (до 50кб) словари релевантных слов. Всего можно указать до восьми словарей. Далее идут параметры предвычислителя, в том же порядке, что они были описаны выше. Затем идет индикатор вероятности успеха обновляемый автоматически, при изменении других параметров. Еще ниже находится полезная ссылка "Оценить объем, время и другое", которая предоставляет информацию о таблице, которую мы хотим сгенерировать: из какого рода строк она будет состоять, какой размер будет иметь файл, за какое время таблица будет создана, сколько времени будет длиться криптоанализ по этой таблице. Установив необходимые параметры, просто запускаем генератор из главного меню: "Дополнительно -> Генератор HRainbow". Генерация, разумеется, поддерживает продолжение после остановки, и пишет таблицу на диск сразу же, по мере вычисления. 6. Примеры и статистика Пример #1."Числа". Наверное, ни для кого не будет секретом, что довольно большая часть паролей являются исключительно числовыми. Попробуем предвычислить их, для ускорения процесса восстановления. На первый взгляд, все цифры в пароле имеют примерно одинаковую вероятность появления. Но если мы рассмотрим группы цифр, то для каждой такой группы, вероятности появления уже не будут равными. В частности, строка "123" входит в средний пароль куда чаще, чем "294". Не воспользоваться этим обстоятельством было бы довольно глупо. Поэтому, для начала, необходимо выявить самые частые комбинации чисел. Для этого, возьмем реальную выборку паролей и посчитаем на ней для каждой комбинации ее частоту. Чем больше выборка - тем точнее статистика. В нашем примере, рассматривается исходная выборка из 50 тысяч цифровых паролей. Обсчет вероятностей проводился очень несложной программой, которая для всех чисел от 100 до 9999 проверяла, сколько раз каждое число встретилось в исходной выборке паролей, как подстрока. Например, пароль "123123321" содержит по три раза подстроки "1", "2", "3"; по два раза подстроки "12", "23", "123"; а остальные подстроки - по одному разу. Затем, N самых частых подстрок были записаны в словарь. Кроме того, к ним добавили все недостающие строки из набора от 0 до 9 (т.е. по одной цифре) и 00 до 99 (т.е. по две цифры). Мы взяли N равным 500. Возможны и другие варианты, которые могут давать лучшие результаты. Полученный словарь из 610 (500 + 110) строк сохраним и возведем в четвертую степень. Такой словарь, с одной стороны, будет содержать все числа от 0000 до 99999999 (четыре двухзначных числа). С другой стороны, и самые релевантные комбинации длиной до 16 знаков (четыре четырехзначных числа), например - 1234123412341234 или 0000111122223333. 610^4 = 138 458 410 000. Для того, чтобы уменьшить занимаемый объем, и повысить скорость поиска, прибегаем к технике предвычислений. Ставим длину цепочки = 5000, фактор выполнения = 300%, четыре раза добавляем наш словарь в список словарей. А значения остальных параметров, в данном случае, не важны. Такая таблица будет занимать 610^4/(5000/16) = 443066912 байт. То есть, чуть меньше чем 450 мегабайт. Время генерации (однократный процесс) этой таблицы для MD5 на компьютере Athlon 3000+ составит около суток. Время криптоанализа, то есть время восстановления пароля для каждого хеш-значения будет составлять 30 секунд в худшем случае. Важно заметить, что Hybrid Rainbow таблицы имеют вероятностный характер, и в данном случае, могут быть восстановлены примерно 87% паролей из тех, которые можно получить гибридной атакой по тому же словарю. Ниже - сравнение Hybrid Rainbow и Гибридной Атаки. Сравнивать Hybrid Rainbow с классическими rainbow таблицами, или прямым перебором бессмысленно, т.к. последние вообще не могут восстанавливать пароли из 16 символов за разумное (меньше года) время. Из таблицы становится ясно, что использовать Hybrid Rainbow для однократного восстановления пароля бессмысленно. Для реализации схемы "восстановил и забыл", куда быстрее использовать Гибридную Атаку. Однако, при наличии соответствующих гибридных таблиц, использование других техник восстановления теряет смысл. Более того, если часто нужно восстанавливать пароли, по известному диапазону - генерация Hybrid Rainbow таблиц является целесообразной. Пример #2."Частые пароли". Аналогично, можно предвычислять не только цифровые пароли, но и составленные из любых символов. Здесь мы выбирали 14 000 самых частоиспользуемых комбинаций до четырех символов на исходной коллекции из 150 тысяч реальных паролей. Этот словарик мы возводим в третью степень. 14000^3 = 2 744 000 000 000. Для сохранения таблиц потребуется около 16Гб места на диске, процесс генерации (для MD5) требует чуть меньше месяца процессорного времени. А вот так выглядят параметеры генератора: Криптоанализ по полученным 20 таблицам (каждая на 830мб) длится до 10 минут на одно хеш-значение (без учета времени загрузки таблиц с диска). Однако, по проведенным исследованиям, выяснилось, что таких таблиц достаточно для восстановления примерно 85% паролей с любого реального форума (в среднем). Максимальная длина восстанавливаемого пароля по таким таблицам составляет 12 символов (3 четырехсимвольные комбинации), что куда выше, чем 8 символов, на которых остановились классические rainbow таблицы.
1. Возможна генерация в бесплатной версии? 2. Являются-ли таблицы полным аналогом сгенерированых по диапозону или у них есть какие-либо отличия? 3. ППро перебирает по этим таблицам? 4. Если в первом вопросе ответ отрицательный, то может ключ есть?
Выглядят так же как классические Rainbow таблицы - т.е. набор "почти случайных байт". Общий параметр с классическими таблицами - только длина цепочки, все остальные параметры другие и описаны в статье выше.
