Как хэш-функции, такие как MD5, уникальны?

Question

Как хэш-функции, такие как MD5, уникальны?

Я знаю, что у MD5 были некоторые коллизии, но это скорее вопрос высокого уровня о функциях хэширования.

Если MD5 хэширует любую произвольную строку в 32-значное шестнадцатеричное значение, то согласно Принцип Pigeonhole конечно, это не может быть уникальным, так как есть более уникальные произвольные строки, чем есть уникальные 32-значные шестнадцатеричные значения.

751 8

hash theory md5 uniqueidentifier

8 ответов:

Comments

Ничего не найдено.

Mike Cargal · Accepted Answer · 2017-11-12 16:48:50

вы правы, что он не может гарантировать уникальность, однако есть приблизительно 3.402823669209387 e+38 различных значений в 32-значном шестнадцатеричном значении (16^32). Это означает, что, предполагая, что математика за алгоритмом дает хорошее распределение, ваши шансы феноменально малы, что будет дубликат. Вы должны иметь в виду, что можно дублировать, когда вы думаете о том, как он будет использоваться. MD5 обычно используется для определения того, было ли что-то изменено (т. е. это контрольная сумма). Было бы смешно маловероятно, что что-то может быть изменено и привести к той же контрольной сумме MD5.

Edit: (учитывая последние новости re: SHA1 хэши) Ответ выше, все еще держится, но вы не должны ожидать, что хэш MD5 будет служить какой-либо проверкой безопасности от манипуляций. SHA-1 хэши как 2^32 (более 4 миллиардов) раз реже сталкиваются, и было продемонстрировано, что можно придумать вход для получения того же значения. (Это было продемонстрировано против MD5 довольно давно). Если вы хотите убедиться, что никто злонамеренно не изменил что-то для получения того же хэш-значения, в эти дни вам нужно в SHA-2 иметь прочную гарантию.

с другой стороны, если это не в контексте проверки безопасности, MD5 все еще имеет свою полезность.

аргумент может быть сделан, что хэш SHA-2 достаточно дешев для вычисления, что вы должны просто использовать его в любом случае.

Ignacio Vazquez-Abrams · Accepted Answer · 2010-03-15 01:46:58

вы абсолютно правы. Но хеши-это не "уникальные", а "достаточно уникальные".

Phil · Accepted Answer · 2010-03-15 02:10:56

как указывали другие, цель хэш-функции, такой как MD5, заключается в том, чтобы легко проверить, эквивалентны ли два объекта, не зная, что они изначально были (пароли) или сравнивая их полностью (большие файлы).

скажем, у вас есть объект O и его хэш h_O. Вы получаете другой объект P и хотите проверить, равен ли он O. Это может быть пароль или загруженный файл (в этом случае вы не будет O но скорее хэш из него h_O пришла с P, скорее всего). Во-первых, вы хэш P для ч_P.

теперь есть 2 возможности:

h_O и h_P разные. Это должно означать, что O и P отличаются, потому что использование одного и того же хэша для 2 значений/объектов должно давать одно и то же значение. Хэши являются детерминированными. нет ложных отрицания.

h_O и h_P равны. Как вы сказали, из-за принципа Pigeonhole это может означает, что разные объекты хэшируются до одного и того же значения, и могут потребоваться дальнейшие действия.

a. поскольку количество возможностей настолько велико, если вы верите в свою хэш-функцию, может быть достаточно сказать: "Ну, был 1 в 2¹²⁸ вероятность столкновения (идеальный случай), так мы можем предположить O = P. Это может работать для паролей, Если вы ограничиваете длину и сложность символов, например. Именно поэтому вы видите хэши паролей, хранящихся в базах данных, а не сами пароли. b. вы можете решить, что только потому, что хэш вышел равным, не означает, что объекты равны, и сделать прямое сравнение O и P. у вас может быть ложно-положительным.

таким образом, хотя вы, возможно, ложные положительные совпадения, у вас не будет ложных негативов. В зависимости от вашего приложения и от того, ожидаете ли вы, что объекты всегда будут равными или всегда будут разными, хэширование может быть излишним шагом.

M.A. Hanin · Accepted Answer · 2010-03-15 02:07:27

криптографические односторонние хэш-функции, по своей природе определения, не Инъективным. С точки зрения хэш-функций, "уникальный" довольно бессмысленно. Эти функции измеряются другими атрибутами, что влияет на их силу, затрудняя создание предварительного образа данного хэша. Например, мы можем заботиться о том, на сколько битов изображения влияет изменение одного бита в предварительном изображении. Мы можем заботиться о том, как трудно провести атаку грубой силы (поиск prie-изображения для данного хэш-образа). Мы можем заботиться о том, как трудно найти столкновение: найти два предварительных изображения, которые имеют один и тот же хэш-образ, который будет использоваться в атака на день рождения.

Alan Plum · Accepted Answer · 2010-03-15 02:34:29

хотя вполне вероятно, что вы получаете коллизии, если хэшируемые значения намного длиннее, чем результирующий хэш, количество коллизий все еще достаточно мало для большинства целей (есть 2¹²⁸ возможные хэши всего, поэтому вероятность двух случайных строк, производящих один и тот же хэш, теоретически близка к 1 из 10³⁸).

MD5 был в первую очередь создан для проверки целостности, поэтому он очень чувствителен к минимальным изменениям. Минор модификация входного сигнала приведет к совершенно другому выходу. Вот почему трудно угадать пароль, основанный только на хэш-значении.

хотя сам хэш не является обратимым, все еще можно найти возможное входное значение с помощью чистой грубой силы. Вот почему вы всегда должны обязательно добавлять соль, если вы используете MD5 для хранения хэшей паролей: Если вы включаете соль во входную строку, соответствующая входная строка должна включать точно такую же соль, чтобы результат в той же выходной строке, потому что в противном случае необработанная входная строка, которая соответствует выходу, не будет соответствовать после автоматического посола (т. е. вы не можете просто "отменить" MD5 и использовать его для входа в систему, потому что обратный хэш MD5, скорее всего, не будет соленой строкой, которая первоначально привела к созданию хэша).

таким образом, хэши не уникальны, но механизм аутентификации может быть сделан, чтобы сделать его достаточно уникальным (что является одним из несколько правдоподобных аргументов для ограничения пароля вместо соления: набор строк, которые приводят к одному и тому же хэшу, вероятно, будет содержать много строк, которые не подчиняются ограничениям пароля, поэтому сложнее отменить хэш грубой силой-очевидно, что соли все еще хорошая идея, тем не менее).

большие хэши означают больший набор возможных хэшей для одного и того же входного набора, поэтому более низкий шанс перекрытия, но до тех пор, пока вычислительная мощность не достигнет достаточного уровня, чтобы сделать грубое принуждение MD5 тривиальным, это еще достойный выбор для большинства целей.

bmargulies · Accepted Answer · 2010-03-15 01:47:30

(Это, кажется, хэш-функция воскресенье.)

криптографические хэш-функции предназначены для очень, очень, очень низких частот дублирования. По очевидной причине вы заявляете, что ставка никогда не может быть равна нулю.

The Википедия страницы является информативным.

Bolster · Accepted Answer · 2010-03-15 02:00:31

Как сказал Майк (и в основном все остальные), он не идеален, но он делает свою работу, и производительность столкновения действительно зависит от algo (что на самом деле довольно хорошо).

Что представляет реальный интерес-это автоматическая манипуляция файлами или данными для сохранения одного и того же хэша с разными данными, см. Это демо

Pinko · Accepted Answer · 2010-03-15 02:01:12

Как ответили другие, хэш-функции по определению не гарантируют возврата уникальных значений, поскольку существует фиксированное число хэшей для бесконечного числа входов. Их ключевое качество заключается в том, что их столкновения непредсказуемой.