Если у меня есть похожие данные с ограничением размера (например, номера социального страхования) с использованием алгоритма хеширования с большим размером байта, чем данные (например, sha-256), хэш гарантирует тот же уровень уникальности как исходные данные?Существуют ли случаи, когда алгоритм хеширования может быть гарантирован уникальным?
Если вы используете криптографический хеш, такой как SHA, то короткий ответ - да.
Вы всегда можете создать индивидуальный хеш, который гарантирует уникальность. Для данных в известном домене (например, SSN) упражнение относительно простое.
Если ваше целевое значение hash имеет больше доступных битов, чем то, что вы хешируете, хэш просто отображает входные значения в одно из доступных выходных значений. Это будет простое линейное отображение от входного значения в виде многобайтового целого числа к выходу в виде многобайтового целого числа.
Когда целевое значение хэша имеет меньшее количество бит, чем то, что хэшируется, тогда уникальность не может быть гарантирована.
Спасибо. Я рассматриваю хэширование ssn и идентификатор учетной записи, который может варьироваться в зависимости от каждой реализации. Поэтому, если я могу использовать хэш-функцию вместо предварительно сгенерированной, было бы предпочтительнее. – matt
Если маскирование номеров социального обеспечения является целью, то реализация одной-единственной функции линейного сопоставления не будет достаточной, так как было бы довольно просто рассчитать исходный ввод из некоторых выборок вывода. Кроме того, длина входной строки определенно не влияет на эффективность криптографически защищенной хеш-функции, поэтому использование известного алгоритма хеширования - это путь –
Ключевой особенностью cryptographically secure hash function является то, что вы можете избежать столкновений вне разумных сомнений независимо от ввода. Это также справедливо для ввода короче размера вывода, что является тем же самым длинным сообщением с небольшой энтропией. Таким образом, вы можете использовать SHA-2, не беспокоясь о столкновениях.
Вероятность столкновения хэшей не имеет никакого отношения к размеру входной строки (за исключением того, что она указывает, сколько входных данных требуется для сохранения уникальности). Возможно, вы столкнулись с хеш-столкновением, когда вы используете hash 0 и 1, используя идеальный алгоритм хеширования, хотя вероятность 1/(2 бит длины). Что в случае SHA-256 фактически равно нулю.
Конфликты Хэша - проблема парадоксального дня рождения. В случае 256-битного хеша вероятность столкновения между двумя входами зависит от количества входов и составляет:
Правда. Однако я не ставил под сомнение последствия для безопасности. Я прошу вероятность уникальности из хеша, когда размер данных меньше размера хеша. (Мне нужно, чтобы результирующее значение было детерминированным/повторяемым, поэтому выполнение случайной соли x байтов для меня не работает. Я могу «солить», добавив постоянные символы для каждой реализации - например, я мог бы добавить символы типа «593jra», к ssn перед хэшированием). – matt
Разве это не парадокс дня рождения, основанный на принципе голубины? Если это так, то в теории у меня нет сценария. – matt
Принцип «голубиная скважина» - это простое представление о том, что когда у вас есть больше предметов, чем у ящиков, у вас гарантировано столкновение. Парадокс дня рождения просто говорит, что вы действительно действительно можете столкнуться, если ваше отношение предметов к голубям «велико». Где «высокий» определяется приведенной выше формулой. –
Другие указали, что столкновения не должны вызывать беспокойства; то есть весь смысл криптографически защищенных хеш-функций. Я хотел бы добавить следующее:
Спасибо. Я так и думал, но я не мог найти ссылку, чтобы поддержать его, и я недостаточно умен, чтобы вникать в математику и заключать одно или другое! – matt
Как отмечалось выше, криптографический хеш просто говорит, что столкновения необычайно маловероятны, а не невозможны. – Novelocrat
@Novelcrat, * короткий * ответ на оригинальный вопрос есть. Теоретически возможен столкновение, среднее время нахождения столкновения значительно дольше, чем время, когда солнце превратится в красного гиганта и уничтожит землю. –