Рейтинг:2

Учитывая хэш-функцию и хеш-значение, можете ли вы сказать, может ли она создать такое значение?

флаг tr

У меня возник следующий вопрос:

Дана хэш-функция ЧАС() и хэш-значение час который находится в кодовом домене/диапазоне выходов ЧАС(), можете ли вы определить, если час может производиться ЧАС() (т.е. час в образе ЧАС())?

Можно ли ответить на вопрос? Противоречит ли это свойству сопротивления прообраза?

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

Maarten Bodewes avatar
флаг in
Обратите внимание, что заголовок указывает на вопрос, на который [уже был дан ответ] (https://crypto.stackexchange.com/a/41708/1172). Тем не менее, последующие вопросы достаточно интересны, чтобы оставить их открытыми, по моему личному мнению.
Рейтинг:2
флаг ng

Дана хэш-функция $\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\}^*$ следующее:

  1. Преобразование битовой строки $ млн $ в целое число $м$ согласно соглашению с обратным порядком байтов и отслеживайте длину в битах $\ell$ из $ млн $.
  2. Вычислить $$\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$.
  3. Конвертировать $h_1$ в битовую строку $H_1\in\{0,1\}^{512}$, $h_2$ в битовую строку $H_2\in\{0,1\}^{512}$, и $m_1$ в битовую строку $M_1\in\{0,1\}^{\ell}$ согласно соглашению с обратным порядком байтов.
  4. Вычислить и вывести $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-битный хэш.

kelalaka avatar
флаг in
Разве XORing первых 512-бит входных данных к выходным данным SHA3-512 не является более простым способом гарантировать, что весь диапазон представляет собой 512-битное пространство?
fgrieu avatar
флаг ng
@kelalaka: если вы предлагаете $H(m_0\mathbin\|m_1)=m_0\oplus\operatorname{SHA3-512}(m_0\mathbin\|m_1)$ с $m_0\in\{0,1\}^ {512}$, то нет доказательства достижения всего выходного значения, и это, скорее всего, неверно, когда мы ограничиваемся 512-битными сообщениями. Если я правильно вычислю [сборщик купонов](https://en.wikipedia.org/wiki/Coupon_collector%27s_problem), это станет вероятным после того, как мы хэшируем примерно $2^{512+8,5}$ сообщений. Моя функция _демонстративно_ достигает всех выходных значений, но нам нужно решить вариант проблемы DLP, чтобы обратить ее вспять.
kelalaka avatar
флаг in
Да, это неправильно, я должен сказать, что x-or разбивает сообщение на 512-блоки, затем x-or с хэшем, но доказательств нет, только ожидание.
Рейтинг:2
флаг in

Учитывая хеш-функцию H() и хеш-значение h, которое находится в кодовом домене/диапазоне выходов $Ч()$, можете ли вы определить, если $ч$ может производиться $Ч()$ (т.е. $ч$ в образе $Ч()$)?

Вообще, тебе нельзя если вы считаете $Ч$ быть черным ящиком. Я был бы удивлен, если бы были значения, которые не могут быть достигнуты с помощью хеш-функции, такой как SHA-2/3, из-за того, как они построены. Как и в вопросе/ответе, на который я указал, в конце вы захотите взглянуть на внутреннюю работу хеш-функции.

Можно ли ответить на вопрос? Противоречит ли это свойству сопротивления прообраза?

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

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

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

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

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

флаг tr
Спасибо за ваш вклад! Разве не именно потому, что H — это черный ящик, я всегда могу ответить «да» из-за высокой вероятности того, что все изображения сопоставлены? Затем, учитывая искусственный хэш с некоторыми известными значениями, которые он никогда не выведет, я отвечу «да», если h не находится в этих значениях, и «нет» в противном случае. Я всегда могу выиграть?
Maarten Bodewes avatar
флаг in
Нет, потому что если это черный ящик, вы не сможете сказать, какие значения будут исключены из вывода. Как правило, вы ожидаете, что вывод хэша будет хорошо распределен, но если вы просто пропустите несколько, то это будет незначительным и необнаружимым.

Ответить или комментировать

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