Каковы важные моменты в криптографических хеш-функциях?

Question

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

Тем не менее, единодушный ответ на вопрос Почему хеш-значения MD5 не обратимы? равен Поскольку бесконечное число входных строк будет генерировать один и тот же вывод. Это кажется совершенно противоречивым я.

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

Что происходит, когда размер входных данных меньше фиксированного размера выходных данных (например, хэширование пароля «abc»)?

РЕДАКТИРОВАТЬ:

ОК, дайте мне посмотреть, если у меня есть это прямо:

1. Действительно, очень сложно вывести входные данные из хеша , потому что существует бесконечное количество входных строк, которые будут генерировать один и тот же вывод (необратимое свойство).
2. Тем не менее, поиск даже одного экземпляра нескольких входных строк, генерирующих один и тот же вывод, также действительно очень сложен (свойство устойчивости к столкновениям).

Answer 1

Предупреждение: длинный ответ

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

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

(Несмотря на распространенное мнение о ненадежности MD5, MD5 по-прежнему устойчив к прообразам. Любой, кто не верит мне, волен давать мне все, что хэширует до 2aaddf751bff2121cc51dc709e866f19. Что MD5 не имеет, это сопротивление столкновению , что является чем-то совершенно другим.)

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

Так возникает вопрос: а почему бы и нет? (Или, другими словами, как вы делаете функцию устойчивой к прообразу?)

Ответ заключается в том, что криптографические хеш-функции имитируют хаотические системы. Они принимают ваше сообщение, разбивают его на блоки, смешивают эти блоки вокруг, взаимодействуют между собой некоторые блоки, смешивают эти блоки и повторяют это много раз (ну, одна криптографическая хеш-функция делает это; другие имеют свои собственные методы). Поскольку блоки взаимодействуют друг с другом, блок C должен не только взаимодействовать с блоком D, чтобы создать блок A, но он должен взаимодействовать с блоком E, чтобы создать блок B. Теперь, конечно, вы можете найти значения блоков C, D, E, который произведет блоки A и B в вашем хэш-значении, но когда вы вернетесь дальше, внезапно вам понадобится блок F, который взаимодействует с C, чтобы сделать D, и с E, чтобы сделать B, и ни один такой блок не может сделать оба в в то же время! Вы, должно быть, догадались, неправильные значения для C, D и E.

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

Answer 2

1: Основная цель хэша состоит в том, чтобы сопоставить очень, очень большое пространство с меньшим, но все еще очень большим пространством (например, MD5, которое возьмет «что угодно» и преобразует его в пространство размером 2 ^ 128). - большой, но не такой большой, как алеф-0.)

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

Представьте себе идиотскую хеш-функцию sum (), которая просто добавляет все цифры входного числа: она преуспевает в отображении, но есть куча коллизий (входы с одинаковыми выходными данными, такими как 3 и 12 и 21) на нижнем конце выходного пространства и верхнем конце пространства почти пусто. В результате он очень плохо использует пространство, легко взламывается и т. Д.

Таким образом, хороший хеш, который даже использует пространство назначения, затруднит поиск двух входов с одинаковым выходом, просто по коэффициенту: если бы MD5 был идеальным, вероятность того, что два входа имели бы одинаковый выход, была бы 2 ^ -128. Это довольно приличные шансы: лучшее, что вы можете сделать, не прибегая к большему пространству на выходе. (На самом деле MD5 не идеален, что делает его уязвимым.)

Но все равно будет верно, что огромное количество входных данных будет сопоставляться с любым данным хешем, потому что входное пространство является «бесконечным», а деление бесконечности на 2 ^ 128 все еще дает вам бесконечность.

2: Да, хэши всегда вызывают потерю данных, за исключением случая, когда ваше пространство вывода равно или больше, чем ваше пространство ввода - и в этом случае вам, вероятно, не нужно хешировать!

3: Для меньших входных данных наилучшей практикой является соление входных данных. На самом деле, это хорошая практика для любого криптографического хэширования, потому что в противном случае злоумышленник может передать вам определенные входные данные и попытаться выяснить, какой хеш вы используете. «Соль» - это просто набор дополнительной информации, которую вы добавляете (или добавляете) к своему входу; Затем вы хешируете результат.

edit : В криптографии также важно, чтобы хеш-функция была устойчивой к атакам с прообразом, интуитивно, что трудно угадать ввод для данного вывода, даже зная множество других пар ввода / вывода. Функцию «сумма», вероятно, можно было бы угадать довольно легко (но, поскольку она уничтожает данные, обратное преобразование может быть непростым).

Answer 3

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

Быть устойчивым к прообразу - это другое свойство, чем быть обратимым. Функция является обратимой, если при y = f (x) существует ровно один подходящий x (легко это или нет). Например, определите f (x) = x mod 10. Тогда f не обратимо. Из f (x) = 7 вы не можете определить, было ли x 17, 27 или что-то еще. Но f не является устойчивым к прообразу, так как значения x 'такие, что f (x) = 7, легко найти. x '= 17, 27, 12341237 и т. д. все работают.

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

Answer 4

Это свойства хеш-функций в целом.

Однако, предостережение: MD5 больше не следует использовать из-за найденных в нем уязвимостей. Проверьте раздел «Уязвимости» и внешние ссылки, подробно описывающие эти атаки. http://en.wikipedia.org/wiki/Md5 Вы можете создать коллизию MD5, изменив в сообщении только 128 бит.

SHA-1 безопасен для простого хеширования, хотя есть некоторые атаки, которые могут ослабить его против хорошо финансируемых организаций (правительств, крупных корпораций)

SHA-256 - безопасная отправная точка против технологий на ближайшие пару десятилетий.

Answer 5

И все же единодушный ответ на вопрос "почему значения MD5 не являются обратимыми?" потому что «бесконечное количество входных строк будет генерировать один и тот же вывод».

Это верно для любой хеш-функции, но это не сущность криптографической хеш-функции.

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

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

Answer 6

"почему значения MD5 не являются обратимыми?" потому что «бесконечное количество входных строк> будет генерировать один и тот же вывод»

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

Когда вход меньше размера блока, padding используется для подгонки его под размер блока.