Во-первых, давайте отметим, что SHA-256 не принимает все возможные двоичные строки в качестве входных данных. Как определено FIPS 180-3 , SHA-256 принимает в качестве входных данных любую последовательность битов длиной менее 2 ^ 64 битов (то есть не более 18446744073709551615 битов). Это очень распространено; все хеш-функции так или иначе ограничены формальной длиной ввода. Одна из причин заключается в том, что понятие безопасности определяется в отношении вычислительных затрат; существует предел вычислительной мощности, который может собрать любой злоумышленник. Входные данные, превышающие заданную длину, потребуют больше, чем максимальная вычислительная мощность, чтобы просто оценить функцию. Короче говоря, криптографы очень осторожны с бесконечностью, потому что бесконечность имеет тенденцию препятствовать тому, чтобы безопасность была даже определена, не говоря уже о количественной оценке. Таким образом, ваш входной набор C должен быть ограничен последовательностями до 2 ^ 64-1 бит.
При этом давайте посмотрим, что известно о сюръективности хеш-функции.
Хеш-функции пытаются эмулировать случайный оракул , концептуальный объект, который выбирает выходные данные случайным образом при единственном ограничении, которое он «запоминает» предыдущие входы и выходы, и, если дан уже увиденный вход, возвращает тот же вывод, что и ранее. По определению, случайный оракул может быть доказан сюръективным только путем попытки ввода и исчерпания выходного пространства. Если выход имеет размер n битов, то ожидается, что потребуется около 2 ^ (2n) отдельных входов для исчерпания пространства вывода размера 2 ^ n . Для n = 256 это означает, что должно быть достаточно (в среднем) хеширования около 2 ^ 512 сообщений (например, всех сообщений длиной 512 бит). SHA-256 принимает входные данные намного длиннее, чем 512 бит (действительно, он принимает входные данные до 18446744073709551615 бит), поэтому весьма вероятно , что SHA-256 сюръективен.
Однако , не было доказано, что SHA-256 сюръективен, и это ожидается . Как показано выше, для доказательства сюръективности случайного оракула требуется очень много вычислительной мощности, значительно превышающей простые атаки, такие как прообразы ( 2 ^ n ) и столкновения ( 2 ^ (n / 2) ) ). Следовательно, хорошая хеш-функция «не должна» позволять фактическому доказательству такого свойства, как сюръективность. Это было бы очень подозрительно: безопасность хеш-функции проистекает из неразрушимости их внутренней структуры, и такая неразрывность должна решительно противостоять любой попытке математического анализа.
Как следствие, сюръективность формально не доказана ни для какой приличной хеш-функции, и даже для «сломанных» хеш-функций, таких как MD4. Это только «весьма подозреваемый» (случайный оракул с входными данными, которые намного длиннее выходных, должен быть сюръективным).