Свойства криптографической хэш-функции

В течение 1-й лекции курса биткойн-курсера обсуждается 3 свойства криптографических хеш-функций:

Сопротивление столкновению: хеш-функция H называется устойчивой к столкновению, если невозможно найти два значения x и y, такие, что x!= y, но H (x) = H (y).

Скрытие: хэш-функция H скрывается, если: когда секретное значение r выбрано из распределения вероятностей с высокой энтропией, то при H (r ‖ x) невозможно найти x. ‖ Означает конкатенацию двух строк.

Головоломка. Хеш-функция H называется головоломной, если для любого возможного n-битового выходного значения y, если k выбрано из распределения с высокой энтропией, то невозможно найти x такое, что H (k ‖ x) = y во времени значительно меньше 2 ^ п.

Дружелюбие с голосом, похоже, более подробное описание скрытия. Есть ли существенные различия между 2? Имеются ли хеш-функции с 1 свойствами, но не оба?

Ответ 1

У меня была такая же мысль, и разница действительно тонкая. Мне пришлось подумать об этом некоторое время.

Предположим, у вас был хэш, BadHash. Вы выбираете x 'и случайный nonce r', вычисляете y '= BadHash (r' | x ') и даете мне y'. Оказывается, если x 'является английским текстом, кодированным UTF8, я могу рассказать вам, что такое x', и (хотя и не обязательно), я могу даже сказать вам r '. Если x 'оказался просто случайной битовой строкой, мне было бы не повезло. Но неважно, это явно не скрывающий хеш.

Теперь головоломка: я даю вам значение Y 'и случайное выбранное значение R' (скажем, "11110011... 100" ) и попросите вас найти x, чтобы BadHash (R '| x) = Y ". Хорошие новости: получается, что Y '= BadHash (00101... 0001 | UTF8 (" биткойн дефляционный ")). Поэтому, поскольку BadHash не скрывается (плюс), вы можете определить R (а именно 00101... 0001) и x (а именно UTF8 (" биткойн - дефляционный ")), так что BadHash (R | x) = Y" Но это вам не поможет, потому что головоломка указала, что вам нужен x, который работает с другим R, а именно "11110011... 100". Поэтому вы не решили головоломку.

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

Ответ 2

Реструктуризация определений немного упростила мне.

Столкновение сопротивления:

Учитывая: x и h (x)

Трудно найти: y, отличное от x и такое, что h (y) = h (x).

Скрытие

Учитывая: h (r | x)

Секрет: x и крайне маловероятный и случайный выбор r

Трудно найти: y такое, что h (y) = h (r | x).

Это отличается от сопротивления столкновения тем, что не имеет значения, является ли y = r | x.

Головоломка-дружелюбие:

Учитывая: z и крайне маловероятно-случайно выбранный r

Трудно найти: x такое, что h (r | x) = z (но оно должно существовать).

Это отличается от сопротивления столкновений тем, что даже если у нас есть алгоритм поиска столкновения y, то ограничение, которое должно начинаться с r, может сделать y не решением.

Это отличается от скрытия, аналогично, потому что r является ограничением для решения для удобства головоломки, но не является ограничением в свойстве скрытия, поскольку в этом случае y не требуется равным r | x. Кроме того, для удобства головоломки х не известно никому заранее (даже не голосующему).

Ответ 3

Этот курс чрезвычайно запутан и плохо написан.

В задаче скрытия вы пытаетесь найти x, зная значение H (r | x) (и, естественно, H). Но вы не знаете r! Например, набор для x может быть {0,1}, но вы не можете выбирать между 0 или 1, потому что добавление секретности r в x смешивает все возможные хэши.

В дружественной головоломке задаче k (или r)! Проблема здесь состоит в том, чтобы попробовать все возможные x, пока не найдете тот, который дает правильный хэш. Таким образом, вы в конечном итоге найдете один, но это займет время. (Причина того, что k (или r) в определении путается, это просто означает, что мы не можем обманывать, изменив H раньше).

В проблеме сокрытия, даже если вы попробуете все возможные r и x для H раньше. Это не сработает, потому что вы могли бы найти r ', x', r '', x '', для которых H (r '| x') = H (r '' | x ''). И так как вы не знаете, какое значение r является правильным, тогда невозможно найти x.

Ответ 4

Рассмотрим этот алгоритм: возьмите любой текстовый файл и предположите a = 1, b = 2, c = 3 и т.д. и вычислите сумму для всех букв, и если чистая сумма меньше 5, вы получаете награду. Допустим, вы не выиграли в первый раз, поэтому добавляете какой-то произвольный текст в конец этого файла (nonce) и делаете это вычисление снова, пока не выиграете.

Это algo - головоломка, но не хороша для скрытия, так как вы можете легко догадаться, какое влияние на выход будет у nonce.

Ответ 5

Предположим, что x является результатом броска монеты, т.е. x равно 0 или 1. Если H (x) не может найти x, но... Атакующий может легко найти x, учитывая y = H (x), так как существует только два возможных значения хэша. Он вычисляет H (0) и H (1) и проверяет, какой из них равен y.

Теперь предположим, что вы добавили большой случайный ключ к x и вы вычислили H (k x). Если ключ секретный, злоумышленник не может легко найти x, так как ему придется попробовать множество возможных секретных ключей.

Это действительно на слайдах курса:-), но на самом деле не объяснено словами.

Ответ 6

Пусть есть: y = H(x|r). Здесь вывод y, а входы - r и x.

Свойство скрытия:

Учитывая выход хэш-функции (y), невозможно найти вход (x). Обратите внимание: r не указывается.

Удобная для головоломки собственность:

Учитывая выход хэш-функции (y) и части входа (r), трудно найти вход (x).