Конечное волокно SHA512

Здесь $y\in\{0,1\}^{512}$ с $\emptyset \neq s^{-1}(\{y\})$ и $s^{-1}(\{у\})$ конечно?

Для SHA-512, как определено на самом деле, тривиально да, поскольку размер ввода ограничен к $2^{128}-1$ кусочек. Что делает $s^{-1}(\{у\})$ верно для любого $y\in\{0,1\}^{512}$. И $у$ хэш пустой битовой строки соответствует условию $\emptyset \neq s^{-1}(\{y\})$. В дальнейшем мы предполагаем это $2^{128}-1$ битрейт снят.

Ставлю на то, что предложение теперь ложно в силу следующего аргумента (не доказательства).

1. Кажется правдоподобным, что каждый 512-битный хэш достигается с помощью SHA-512 для некоторого не более 895-битного сообщения (самое большое блочное сообщение, требующее одного раунда). Аргумент: в идеальной модели блочного шифра для блочного шифра в основе раунда SHA-512 каждый хэш такого сообщения является случайным и независимым в $\{0,1\}^{512}$. Посредством коллекционер купонов связан, мы ожидаем получить все значения примерно после $2^{520.5}$ рисует, и хвостовая оценка существенно исключает (вероятность $<2^{-(2^{384})}$) мы бы не получили их все после $2^{896}-1$ попытки. На самом деле это может потерпеть неудачу только в том случае, если наша модель будет очень плохой.

2. Еще более правдоподобно, что каждый 512-битный хэш достигается с помощью SHA-512 для не более чем 1919-битного сообщения (самое большое блочное сообщение, требующее двух раундов), потому что с двумя раундами количество возможных входных данных в первых раундах достигает $2^{1024}$, что делает его (по аргументу 1) вероятным настолько близким к $2^{512}$ значения могут достигать 512-битного входа состояния второго раунда; и мы получаем $2^{896}-1$ блоки ввода сообщений, как и в первом раунде. Таким образом, мы еще больше преодолели ограничение сборщика купонов, и, что более важно, поскольку у нас есть еще 512 входных битов, которые варьируются, кажется еще более маловероятным, что наша модель может быть настолько плохой.

3. Это рассуждение для второго раунда можно повторить для любого большего количества раундов, что приведет к выводу, что каждое значение в $\{0,1\}^{512}$ скорее всего достигается максимально раунд.

4. Было бы еще более удивительно, если бы мы позволили длине сообщения по модулю $2^{128}$ принимать все возможные значения, любое из $2^{512}$ значения не достигнуты для отсутствия сообщения $2^{128}$ к $2^{129-1}$ бит: у нас есть почти дополнительные 128 бит ввода, которые могут варьироваться.

5. И затем, поскольку длина сообщения может увеличиваться до бесконечности, мы получаем, что, вероятно, любой $у$ имеет бесконечное $s^{-1}(\{у\})$.

6. $\emptyset \neq s^{-1}(\{y\})$ часть предложения делает его еще менее вероятным. Предположим, что 512-битный начальное значение SHA-512 достигается снова (внутренне) после $2^{119}$ раундов по крайней мере для одного (скажем, $w$) принадлежащий $2^{(2^{129})}$ разные сообщения начинаются $2^{129}$ бит, что, вероятно, соответствует слегка измененной версии 3 выше (у нас есть полная свобода для каждого из $2^{119}$ 1024-битные входные блоки $w$). Теперь, если определенный $y\in\{0,1\}^{512}$ является $\operatorname{SHA-512}(х)$, то это тоже $\operatorname{SHA-512}(w\mathbin\|x)$ и вообще $\operatorname{SHA-512}(w\mathbin\|\ldots\mathbin\|w\mathbin\|x)$ таким образом, конструктивно опровергая предложение.