Каковы свойства хэш-функции?

С криптографической точки зрения хэш-функция с выходом фиксированного размера:

• Должна быть детерминированной функцией: одни и те же входные данные всегда должны генерировать одни и те же выходные данные.
• Должен принимать входные сообщения в широком наборе входных данных. В идеале это должна быть произвольная строка битов, но часто это произвольные строки байтов или строки символов, возможно, до некоторого размера.
• Обнажая специальный квалификатор (например, с ключом или же секрет или же случайный), должен быть общедоступным: каждый шаг и константа, необходимые для вычисления результата для любого заданного входа, известны всем.
• Должен вычислить результат за время, полиномиальное с входным размером. Это время должно быть примерно линейным с размером ввода.
• Должен иметь устойчивость к столкновениям: вычислительно невозможно представить два разных сообщения с одним и тем же выводом (это свойство подразумевает второе сопротивление прообраза, то есть при случайных входных данных вычислительно невозможно найти другой вход, дающий такой же результат). Обратите внимание, что если есть $n$ возможных выходов, существуют общие атаки, которые нарушают устойчивость к коллизиям примерно $\кв.п$ оценки функции, таким образом, устойчивость к столкновению подразумевает $n$ большой (скажем, не менее $2^{192}$ Настоящее время); в противном случае определение устойчивости к коллизиям должно быть ослаблено: лучший способ показать два разных сообщения с одним и тем же выводом - это общая атака.
• Должен иметь (первое) сопротивление прообразу: учитывая выходные данные для случайных неизвестных входных данных, вычислительно невозможно найти эти входные данные (или другие входные данные с тем же выходным сигналом) проще, чем путем перебора входных данных. Обратите внимание, что если есть $n$ возможных выходов, существуют общие атаки, которые разрушают сопротивление прообраза примерно с $n$ оценки функции, таким образом, сопротивление прообразу подразумевает $n$ большой (скажем, не менее $2^{96}$ Настоящее время); в противном случае определение сопротивления прообразу должно быть ослаблено.

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

• Для неизвестных случайных входных данных с любой естественной характеристикой (то есть не зависящих от определения хеш-функции; например, входных данных, состоящих из 40 десятичных цифр, сумма которых делится на 10), выходные данные должны быть вычислительно неотличимы от равномерно случайных в выходной набор.
• Устойчивость к атаке с расширением длины: данный вывод для неизвестного ввода $ млн $, должно быть невозможно вычислить вывод для ввода расширения $ млн $ (это $M\mathbin\|E$ для непустого $Е$) проще, чем найти $ млн $ путем попытки ввода. Обратите внимание, что все еще распространенные хэши, такие как SHA-256, не имеют этого более позднего свойства.