Дизайн для максимального размера хэша, учитывая N-значный числовой ввод и цель, связанную с коллизиями
Предположим, что хакер получает набор данных из хэшей, солей, перца и алгоритма и имеет доступ к неограниченным вычислительным ресурсам. Я хочу определить максимальный размер хеша, чтобы достоверность определения исходной входной строки была номинально равна некоторому целевому проценту достоверности.
Ограничения:
Входная строка ограничена ровно 8 числовыми символами, равномерно распределенными. Не существует межзначного отношения, такого как контрольная сумма.
Целевой номинальный процент уверенности составляет 1%.
Предположим, что функция хеширования является равномерной.
Каков максимальный размер хеша в байтах, поэтому есть номинально 100 (то есть 1% достоверности) 8-значных значений, которые будут вычисляться для того же хеша? Должно быть возможно обобщить до N числовых цифр и X% от принятого ответа.
Пожалуйста, укажите, есть ли проблемы с использованием первых N байтов стандартного 20-байтового SHA1 в качестве приемлемой реализации.
Признано, что этот подход значительно увеличит восприимчивость к атаке методом грубой силы за счет увеличения возможных "правильных" ответов, что приводит к компромиссу проекта и могут потребоваться некоторые дополнительные меры (временные задержки, несколько этапов проверки и т. Д.).
1 ответ
Похоже, что вы хотите гарантировать коллизии, имея в виду, что если хакер получил все, так что предполагается, что он может грубо форсировать все хэшированные значения, то они не получат исходные значения, а только набор возможных исходных значений. для каждого хешированного значения.
Этого можно достичь, выполнив шаг предвестника перед обычным криптографическим хешированием. Этот шаг предшественника просто сворачивает ваш набор возможных значений в меньший набор возможных значений. Это может быть достигнуто различными способами. По сути, вы применяете начальную хеш-функцию к вашим входным значениям. Использование арифметики по модулю, как описано ниже, представляет собой простую разновидность хеш-функции. Но могут быть использованы другие типы хеш-функций.
Если у вас есть 8-значные исходные строки, есть 100 000 000 возможных значений: 00000000 - 99999999. Чтобы гарантировать, что 100 исходных значений хэшируют одно и то же, вам просто нужно отобразить их в пространство из 1 000 000 значений. Самый простой способ сделать это - преобразовать ваши строки в целые числа, выполнить операцию по модулю 1 000 000 и преобразовать обратно в строку. Сделав это, следующие значения будут хэшировать один и тот же сегмент: 00000000, 01000000, 02000000,....
Проблема в том, что хакер не только знает, какие 100 значений могут быть хэшированными, но и с уверенностью знает, что такое 6 из 8 цифр. Если реальная изменчивость цифр в хешируемых фактических значениях не одинакова по всем позициям, то хакер может использовать это, чтобы обойти то, что вы пытаетесь сделать.
В связи с этим было бы лучше выбрать значение по модулю так, чтобы полный диапазон цифр был представлен достаточно равномерно для каждой позиции символа в наборе значений, которые отображаются на одно и то же хешированное значение.
Если разные регионы исходной строки имеют большую изменчивость, чем другие регионы, то вам нужно это отрегулировать, так как статические регионы легче угадать в любом случае. Часть, которую захочет хакер, - это очень изменчивая часть, которую они не могут угадать. Разбивая 8 цифр на регионы, вы можете выполнить этот предварительный хэш отдельно для каждого региона, выбрав значения по модулю для изменения степени столкновений в каждом регионе.
В качестве примера вы можете разбить 8 цифр, таким образом 000-000-00. Предварительный хеш преобразует каждую область в отдельное значение, выполняет для каждого из них модуль, объединяет их обратно в 8-значную строку и затем выполняет обычное хеширование. В этом примере, учитывая ввод "12345678", вы должны сделать 123 % 139, 456 % 149 и 78 % 47, что дает 123 009 31. Существует 139*149*47 = 973 417 возможных результатов из этого предварительного хэша. Таким образом, будет примерно 103 исходных значения, которые будут сопоставлены с каждым выходным значением. Чтобы дать представление о том, как это работает, следующие 3-значные исходные значения в первой области будут отображаться в одно и то же значение 000: 000, 139, 278, 417, 556, 695, 834, 973. Я сделал это на лету в качестве примера, поэтому я специально не рекомендую эти варианты выбора регионов и значения по модулю.
Если хакер получит все, в том числе исходный код, и все перебор заставит, он получит значения, созданные предварительным хешем. Таким образом, для любого конкретного хэшированного значения он будет знать, что это одно из 100 возможных значений. Он знал бы все эти возможные значения, но он не знал бы, какое из них было НАСТОЯЩИМ значением, которое произвело хэшированное значение.
Вы должны хорошо подумать, прежде чем идти по этому пути. Я опасаюсь всего, что выходит за рамки стандартных, принятых криптографических рекомендаций.