Дана хэш-функция $\mathcalH()$ и хэш-значение $Ч$ который находится в кодовом домене/диапазоне выходов $\mathcalH()$, можете ли вы определить, если $Ч$ может производиться $\mathcalH()$ (т.е. $Ч$ в образе $\mathcalH()$)?
Я предполагаю, что «кодовый домен/диапазон выходных данных» определяется без ссылки на то, что на самом деле выводит хэш (а не как набор фактических выходных данных хэша, что сделало бы все это достигнутым по определению).
Если хэш-функция $\mathcal H$ была такова, что для значительной части данного $Ч$ в его домене можно экспонат вход $ млн $ такой, что $Ч(М)=Ч$, то эта функция не будет устойчивой к прообразам. Таким образом, указанная выставка должна быть вычислительно невозможна для случайного $Ч$.
Если мы моделируем хэш как случайную функцию $\{0,1\}^*\к\{0,1\}^n$, то согласно коллекционер купонов проблема, ожидаемое количество хэшей случайных сообщений для достижения всех значений равно $E=2^n\,(n\,\ln(2)+\gamma)+1/2+o(1)$. В криптопрактике $n\ge128$ таким образом $\log_2(E)\приблизительно n+\log_2(n)-0,53$. Таким образом, в среднем нам нужно будет хешировать меньше, чем все сообщения размером ровно 33 байта, чтобы получить все значения для идеального 256-битного хэша, но нужно хешировать больше, чем все сообщения размером ровно 65 байт, чтобы получить все значения для идеального 512-битного хэша. бит хэш. Сделать столько хэшей невозможно.
Для обычных хэш-функций, таких как SHA-1, SHA-256, SHA-512 и, я думаю, SHA-3, как указано в этом другой ответ, у нас нет математического доказательства того, что каждое выходное значение может быть достигнуто. Лучшее, что мы можем сказать, это то, что это, вероятно, имеет место (даже если ограничиться сообщениями, которые помещаются в один блок, и тем более, если их больше), но было бы удивительно, если бы это можно было либо доказать, либо опровергнуть.
Но я думаю, что мы можем построить хеш-функцию, которая доказуемо достигает всего своего выходного пространства, но в значительной степени обладает свойствами, ожидаемыми от криптографического хэша. Вот хэш-кандидат произвольной битовой строки, явно достигающий всего $\{0,1\}^{512}$.
Я буду использовать 3072-битный безопасный премьер $р$, то есть такое, что $q=(p-1)/2$ также является простым; и генератор $г$ мультипликативной группы $\mathbb Z_p^*$, это $г\в[2,р-2]$ с $g^q\equiv-1\pmod p$. Мы можем использовать $p=2^{3072}-2^{3008}+2^{64}\,(\left\lfloor2^{2942}\,\pi\right\rfloor+1690314)-1$ принадлежащий 3072-битная группа MODP, и $g=\left\lfloor 2^{3070}\,e\right\rfloor$.
Вычислить хэш $H(M)\in\{0,1\}^{512}$ входного сообщения $M\in\{0,1\}^*$ следующее:
- Преобразование битовой строки $ млн $ в целое число $м$ согласно соглашению с обратным порядком байтов и отслеживайте длину в битах $\ell$ из $ млн $.
- Вычислить
$$\begin{выравнивание}
m_0&=m\bmod(p-1)\
h_0&=(g^{m_0}\bmod p)-1\
h_1&=\left\lfloor h_0/2^{1024}\right\rfloor\bmod2^{512}\
h_2&=\left\lfloor h_0/2^{1664}\right\rfloor\bmod2^{512}\
m_1&=\слева\lэтаж м/(p-1)\справа\rэтаж\
\end{выравнивание}$$
Примечание: константы 1024 и 1664 выбирают положение двух произвольных непересекающихся 512-битных сегментов в двоичном представлении $h_0$.
- Конвертировать $h_1$ в битовую строку $H_1\in\{0,1\}^{512}$, $h_2$ в битовую строку $H_2\in\{0,1\}^{512}$, и $m_1$ в битовую строку $M_1\in\{0,1\}^{\ell}$ согласно соглашению с обратным порядком байтов.
- Вычислить и вывести $H=H_1\oplus H_2\oplus\имя_оператора{SHA3-512}(M_1)$.
Преобразование между $m_0$ и $h_0$ является биекцией $[0,p-2]$. Если следует, мы могли бы доказуемо найти прообраз $ млн $ любой $H\in\{0,1\}^{512}$ если бы мы могли решить ДЛП в мультипликативной группе $\mathbb Z_p^*$: мы исправляем $M_1=0^{3072}$ (таким образом $\ell=3072$ и $м_0=м$), $h_0=2^{640}\,h_1$ (таким образом $H_2=0^{512}$), что позволяет вычислить $H_1=H\oplus\имя_оператора{SHA3-512}(M_1)$, тогда $h_1$, тогда $h_0=2^{640}\,h_1$. Решаем проблему DLP $(g^{m_0}\bmod p)=h_0+1$ получить $m_0$, тогда $м$, то 3072-битный $ млн $.
Мой аргумент в пользу того, что хэш устойчив к коллизиям и прообразам, заключается в том, что $M\mapsto(M_1,m_0)$ инъективен, $m_0\mapsto H_1\oplus H_2$ кажется, довольно сложно инвертировать или столкнуться, и выполнить операцию XOR с хорошим несвязанным хэшем $M_1$ менее чем в два раза снижает сопротивление столкновению.
Есть ли какая-то польза, о которой вы можете подумать?
я ничего не вижу фактическое техническое преимущество хеш-функции, которая очевидно достигает всего своего кодового домена, поскольку мы не можем экспериментально определить разницу с хорошей стандартной хэш-функцией без этого свойства. С другой стороны, это было бы интеллектуально удовлетворительно. Проблема в том, что все, что я могу придумать (например, кандидат выше), медленнее и менее безопасно при заданной ширине вывода, чем стандартный хеш, и это практическое рассмотрение взвешивает неосязаемое преимущество уверенности в том, что все выходные значения могут быть достигнуты.
Я не вижу никакой выгоды от хеш-функции, которая явно не может достичь части своего выходного пространства, и при этом вычислительно невозможно показать такое выходное значение или невозможно определить, достижимо ли заданное значение выходного пространства.
Я могу представить приложения для хэшей, которые, вероятно, не могут достичь нескольких известен значения в их выходном пространстве (например, одно такое значение может быть зарезервировано как индикатор особого случая). С другой стороны, мы можем легко построить такие хэши из стандартных примитивов. Например, для 256-битного хэша, который не может достичь $0^{256}$, мы можем использовать (с обычными преобразованиями между битовыми строками и целыми числами) $M\mapsto(\operatorname{SHAKE128}(M,416)\bmod(2^{256}-1))+1$. И на практике мы могли бы также использовать любой стандартный 256-битный хэш.
