Радуга в таблицах

Никита Кислицин

Хакер, номер #082, стр. 082-050-4

Скачав с сайта архив с бинарниками, ты найдешь внутри несколько бинарных файлов. Нас сейчас больше всех интересует 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[i]/N), где П - произведение по i от 1 до t, длины цепочки; m[i] - число новых элементов в i-ой цепочке. Числа m[i] вычисляются итеративно, каждое последующее значение зависит от предыдущего, и, в конечном итоге, все они зависят от начального. Сам понимаешь, что расчет такой конструкции и ее пересчет при изменении начального условия - задача очень трудоемкая, компьютер возится над ней долго. Рассчитать, как меняется вероятность в зависимости от числа цепочек, их длины и количества таблиц, даже с большим шагом, - все это занимает много времени. Да и построить график функции трех переменных - тоже задачка наркоманская. Поэтому для построения графика вероятности нужно по очереди фиксировать одну из переменных - ну, скажем, число таблиц. Понятно, что разумное число - что-то в районе трех-четырех-пяти. Если зафиксировать этот параметр, то уже можно построить вероятностную поверхность и судить об оптимальных параметрах. На скрине неподалеку отсюда изображен пример такой поверхности, которую я построил в Maple. Там отчетливо видно две оси - Mb и t. Mb - это объем таблиц в мегабайтах, t - длина цепочек. Сама поверхность отображает, как меняется вероятность по этим параметрам. Секущая плоскость соответствует вероятности 0.95. Соответственно, для выполнения этого условия тебе нужно выбирать все точки, лежащие над секущей плоскостью или прямо на линии пересечения поверхностей. При этом у тебя остается выбор, какому из параметров отдать приоритет - занимаемому на диске месту, или времени поиска. Тут следует еще отметить такой факт, что время поиска рассчитывается исходя из того, что вся текущая таблица находится в памяти компьютера, то есть время доступа очень мало по сравнению с вычислением хэш-функции. Это надо иметь в виду, на практике все может быть совершенно по-другому. Что же касается параметров, то, наверное, лучше всего будет взять золотую середину, точку, где и место, и время «съедается» сравнительно мало. Она отмечена крестиком на графике.