Сервис по реверсу MD5

Передо мной встала задача - реверс md5 хеша 4 произвольных байт. То есть, другими словами, мне надо написать сервис из 1 метода - метод получает 16 байт хеша на входе и возвращает 4 байта на выходе.
Поскольку, насколько я помню, реверс хеша сам по себе неосуществим, я решил пойти другим путем и сгеренировать хеши для всех возможных значений. Я выделил сущность, назовем её запись, которая состоит из 16 байт хеша (назовем ключ) и 4 байт значения. Поскольку значений 4 байт ~4млд, то у меня получается 4млд записей, каждая размером 20 байт - это 80 гигабайт данных.
В качестве первого приближения я сгенерировал 80гиг, разбитых на сортированные отрезки (каждый отрезок - отдельный файл) и реализовал слияние файлов по принципу сортировки слиянием. Таким образом в итоге я получу один большой 80 гиговый файл, где будет 4 млд записей, сортированных по ключу. Я планирую по такому большому файлу создать второй файл - индексный, который запросто влезет в оперативку. После этого поиск записи по ключу будет выглядеть как двоичный поиск в большом файле с небольшой помощью индексного файла. Время поиска в общем случае должно быть логарифмическим, ограниченным максимумом в 32 прыжка.
Плюсы такого решения:
простота развертывания. Просто задеплоил сервис, дождался инициализации, и все работает.
Минусы:
Генерирование файла занимает очень много времени. Время измеряется часами. Генерируемые данные занимают очень много места - 80 гиг
Исходя из минусов, у меня возникло несколько идей:
Первая, конечно, хранить данные в БД. Они там сразу индексирутся и сжимаются. Я пробовал MongoDB и SQL Server, однако скорость вставки и там и там была настолько низкая, что я устал ждать, и оно явно было медленней, чем простая генерация в файл. То есть я и так ради 1 сервиса БД ставить не хотел, и выходит, что это бы мне и не помогло особо. Вторая - попробовать придумать, как лучше сжать данные. Если честно - сжатие хеша не кажется мне чем то элементарным, а сжать значения не получится так как там используется полный набор значений. Была мысль разделить на файлы большой файл по подобию trie - тогда каждый уровень trie экономил бы мне примерно по 4гига + опускать в значениях незначащие нули (но это бы сильно усложнило поиск)
Мне довольно сложно побрать максимально конкретный вопрос в моей ситуации, но я постараюсь: Если ли более общепринятые способы решения подобной задачи? У меня стойкое ощущение, что я делаю что то не так.
UPD Итак, подведу текущие итоги.
Было опробовано несколько подходов.
1. Первоначальный мой вариант был генерацией всех 16 байтных хешей в файл вместе c начальными айдишниками и после искать хеш по файлу.
Время генерации: примерно 3-4 часа. Скорость поиска: не тестировалось. Память - 80гб
2. Второй подход заключался в том факте, что даже если от 16 байтного хеша взять первые 4 байта, то коллизий будет немного. Таким образом, можно было сгенерировать один большой файл айдишников (сортированный по хешу) + небольшой индексный файл. Поиск выглядел так: получаем входящий хеш, берем от него первые 3 байта, по этому адресу в индексном файле (который можно и в память загрузить) находится начальное смещение в большом файле. По этому смещению считываем 400 айдишников - один из них и есть искомый. Считаем 400 хешей, находим нужный id, возвращаем результат.
Время генерации: примерно 2 часа (не делал пока никаких оптимизаций). Индексный файл - 70мб, файл с айдишниками - 16гб. Скорость поиска: около 75-100 запросов в секунду.
3. Третий подход - генерация цепочек хешей. Суть подхода в том, что можно цепочку хешей представить только начальным и конечным значением. Для моей задачи это выглядит так:
Берем 4 байтный id, генерируем от него хеш H (берем первые 4 байта), получаем что то типа id->H. Хеш 4 байтный, значит, где то есть такой id, значит я могу возять хеш от хеша и построить цепочку типа id->H1->H2->Hn. В файл можно писать только начало цепочки и конец. Начало нужно для восстановления цепочки, конец для поиска значения по хешу.
Сам поиск выглядит следующим образом: на входе имеем хеш h. Ищем цепочку с концом h - если находим, то восстанавливаем цепочку, она содержит искомый id. Если нет такой цепочки, то берем хеш от нашего хеша h1, и ищем также цепочку с концом h1. И так повторяем, пока не найдется цепочка.
Подход свиду имеет несколько плюсов - вроде как можно представить данные набором длинных цепочек (храня в памяти только начало и конец). И первая проблема в слове "длинных". Поясню далее.
Итак, минусы:
Очевидно, что если в цепочке попадется id, который уже есть в другой цепочке, то цепочки начнут дублировать информацию.
Выглядит это так:
id1->H1->H2->H3->H4 id2->H5->H1->H2->H3
как видно, идет дублирование информации, если держать длину цепочек постоянной (что увеличит время генерации файла).
Чтобы избавиться от дублирования, я выделил в памяти 2^32 бит (~500 мб), и отмечал уже обработанные айдишники. Таким образом 1 айдишник был только в 1 цепочке. И тут всплыла проблема с длиной цепи. Суть в том, что чтобы цепочка была реально длинной и полезной, надо чтобы все сгенерированные хеши внутри неё равнялись тем айдишникам, которые ещё не обработаны. Когда начинаешь расчитывать эти цепочки (я считал цепочку до тех пор, пока не встречал уже обработанный id) имеют среднюю длину 200 узлов. Но это число очень быстро уменьшается.
Приведу пример: представим, что обработаны 10% всех айдишников, и идет генерация новой цепочки. Предполагая, что хеш функция имеет равномерное распределение, шанс, что первый хеш будет таким id, который ещё не обрабатывался - 0,9. Шанс, что второй хеш будет таким - 0,9*0,9=0,81, и тд, и шанс, что в цепочке будет хотя бы 10 элементов примено 0.35. И это при обработынных 10%. При обработанных 80% шанс иметь хотя бы 2 элементы в цепи (не считая первый id) - 0,64. При обработанных 99% - шансы на длинную цепь, можно сказать, отсутвуют, и типичная цепь будет состоять из начального id и его хеша. Так поучилось и у меня.
Итого, время генерации - примерно час, размер файла - 16гб. Скорость поиска даже не пробвал тестировать.
4. Четвертый подход - радужные таблицы (спасибо @AlexanderPetrov за наводку).
Радужные таблицы, по сути, вариация цепочек хешей. Разница с цепочками в том, что тут применение хеш функции чередуется с применением разных функций (функций редукции). Приведу пример:
id -> H1=H(id) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
В примере видно, что хеш функция чередуется с разными функциями редукции. Плюс этого подхода в том, что даже если какое то значение будет одинаково в 2 цепочках, дублирование будет только в том случае, если значение это будет стоять тем же по счету от начала цепи, например
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4) id2 -> H6=H(id2) -> H7=R1(H6) -> H3=H(H7) -> H4=R2(H3) -> H5=H(H4)
Но если это значение будет в разных местах цепочек, то оно даст разный результат, так как обработается разными функциями редукции
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4) id2 -> H6=H(id2) -> H7=R1(H6) -> H2=H(H7) -> H8=R2(H2) -> H9=H(H8)
И вроде бы все прекрасно, можно генерировать цепочки произвольной длины. Так я думал, когда начинал генерировать цепи длины 3000 элементов. И я очень быстро посчитал 30% всех значений. За терпимое время посчитал 50%. Но тут вступают те же правила с теорией вероятности, что я описал в предыдущем примере. Представим, что я посчитал 95% всех айдишников. Таким образом, новая цепочка из 3000 элементов, будет содержать 150 новых элементов и 2850 уже посчитанных. Таким образом скорость расчетов цепочек драматически падает, так в каждой новая цепочке вхолостую считаются 95% элементов. Я ждал примерно 30 часов, и не вытерпел, прекратил это безумие - примерно 98% всех Id заняли порядка 240 мегабайт. Но меня не устраивала точность 98%, мне, конечно, надо 100%.
Из за введения функции редукции, поиск id по хешу немного отличается от поиска в предыдущем варианте. Если в предыдущем варианте я просто брал хеш от хеша, то тут на основе входящего хеша надо строить новую цепь. Пример: Допустим, есть цепочка
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
И нам на вход пришел хеш H1. Цепочек, которые бы оканчивались на H1 у нас нет, потому мы считаем:
H(H1) - нет совпадений R2(H(H1)) - нет совпадений H(R2(H(H1))) - нет совпадений R1(H(R2(H(H1)))) - на этом этапе результат выражения будет равен H5 элементу цепочки.
После того, как цепочка найдена, восстанавливаем её и находим искомый id. Из практики - я ждал, когда найдется хотя бы 1 id по хешу минут 10, не дождался. Но подозреваю, что дело не в алгоритме, а я просто рукожоп. Вполне допускаю, что если надо реверсить хеш с какой то погрешностью, то, в принципе, вариант рабочий.
Итого, время генерации - очень долго, 98% за 30 часов, причем 98й процент считался часов 5-6, размер файла - 240 мб. Скорость поиска N/A.
Как текущий итог, я пока остановился на варианте 2) - 16 гиговый файл + индекс. Подозреваю, что этот вариант будет самым быстрым. Но другие варианты тоже не буду пока списывать со счетов.
UPD 2 Выложил исходники моих мытарств. Второй подход полностью реализован, вся генерация занимает 25 минут, поиск по 1 ключу за раз - примерно 180 запросов в секунду, поиск пачки входящих реальных данных с реальной программы - ~1000 запросов в секунду (проверял на 75 тыс имеющихся хешей).
Всем спасибо за помощь!

Ответ

Оценим минимальный размер возможного индекса. При любом способе индексации ключ должен вывести нас на 4 байта значения. Для хранения самих значений необходимо 16 ГБайт. Учитывая, что в индексе значения расположены в порядке следования ключей то можно считать их набором случайных данных с полным использованием всех возможных бит. Без потерь сжать такие данные не способен ни один алгоритм.
Дополнительный индекс вообще не нужен !!! Нам нужен только 16 Гб словарь, в котором будут лежать сами искомые значения, отсортированные в порядке следования их MD5-хешей. При поиске мы на основе первых 4х байт хеша прикидываем примерный регион файла, в котором должно находиться искомое значение. После построения словаря и сбора статистики удалось установить, что можно прочитать прицельно блок размером 128Кб и искомое значение точно будет в нем. Точные координаты блока в файле получаются так:
const int bufSize=1024*128; long offs = (((long)hash[0] << 24 | (long)hash[1] << 16 | (long)hash[2] << 8 | hash[3]) << 2) - bufSize/2; if (offs < 0) offs = 0; if (offs >= 0x400000000 - bufSize) offs = 0x400000000 - bufSize;
После чтения этого блока стаем в его середину, вычисляем MD5 от найденного значения и сверяем с искомым. Далее двигаемся прыжками в том или ином направлении по региону словаря, двоичным поиском, но не по хранимым данным, а по вычисляемым на лету MD5 суммам. Мы дойдем до необходимого значения максимум за 20 "прыжков".

Дополнение: Алгоритм построения словаря при недостатке памяти
Если вам доступно менее 4 Гб памяти и вы даже не можете сходу посчитать количества 4х байтных ключей, то достаточно быстрым решением будет следующее:
Всю обработку разбиваем на 2 этапа. На первом этапе открываем 256 файлов от 00 до FF. Рассчитываем MD5 всех возможных чисел и пишем в файл, совпадающий по номеру с первым байтом хеша, само значение (4 байта) и 4 байта хеша, начиная со второго (так как первый мы знаем по файлу). При выделении буферов записи в 1 мегабайт программа на этом этапе требует порядка 280 Мб оперативной памяти. Этап у меня, при реализации на C#, без особой оптимизации, занял порядка 2.5 часов при работе на 1 ядре. Все время занимает собственно расчет MD5 и от этого не уйти, не задействуя несколько ядер или GPU.
Второй этап - сортировка каждого файла в отдельности и слияние значений из них в итоговый файл словаря. При этом мы идем по порядку номеров файлов и следовательно данные изначально сами собой сортируются по первому байту хеша. Никакого сравнения строк между файлами не требуется, прочитали файл, отсортировали, записали в выходной, перешли к следующему. Как называется метод сортировки, примененный мной я не знаю, но работает от так: Читаем все 128 Мб файла в память. Создаем выходной буфер в 64 Мб, буфер выходных ключей в 64 Мб, так же 16 Мб массив байтов счетчиков ключей, 64 Мб массив смещений и еще рабочий массив текущих смещений в блоке. Итого программа требует порядка 370 Мб памяти. Сортируем в 2 прохода, сначала считаем количество вхождений каждого 3х байтного ключа (максимум бывает 11 повторений одного ключа, так как 4й байт ключа совпадает так как он в имени файла). На основе этого вычисляем сложением и пишем в массив смещений начало каждого списка значений. Далее делаем второй проход по входному массиву, при этом переписываем значения в массив значений и ключи в отдельный массив. При вставке элементов в точки, где может быть более 1 значения на ключ используем сортировку вставкой, т.е. находим значение, большее данного и отодвигаем его и все последующие назад. Учитывая, что максимально в одном списке бывает всего 11 значений (и то таких ситуаций порядка 20 штук на файл, т.е. из 16 млн.) - это быстро. В случае если все 4 байта ключа из файла (плюс 5й из названия файла) одинаковы, сейчас алгоритм заново вычисляет MD5 и сравнивает полные хеши. Таких ситуаций порядка 32000 на 16 млн записей. Если это место тормозит, можно сохранять большую часть ключа на первом этапе (но при этом файлы вырастут в объеме и потребуют больше памяти и больше дисковый ввод-вывод). Данный этап у меня прошел за 25 минут. Опять же при полном отсутствии оптимизации.
Итоговый код. Просьба сильно не пинать, первый раз пишу на C# (он мне скоро возможно будет нужен, данная задача была удобна в качестве "Hellow World"), могу не знать элементарных вещей. Замечания, предложения и т.п. (особенно: "Это же делается гораздо проще") приветствуются :)
Дополнение 2: Собственный расчет MD5
Переделав C исходники процедуры расчета блока MD5 из этой статьи. Сделав версию заточенную строго под расчет хеша для 4х байт. Вернее считается минимальный блок в 64 байта, как положено по алгоритму MD5, но в готовом блоке меняется только 4 начальные байта. Я получил следующее. Время стадии 1 алгоритма, рассчитывающей 4 миллиарда MD5 сумм, уменьшилось с 2 часов 40 минут до 17 минут (но одном ядре Core i7-2600). А после введения многопоточности приложение начало упираться в скорость диска, при этом стадия 1 проходит за 10 минут, стадия 2 за 12 минут. Итого полное время построения, готового к поиску, словаря составляет 22 минуты.