Верен ли пример человека, который я привел в своем вопросе выше, в его утверждении - что пример 2 приведет к тому, что столкновения, вероятно, будут происходить реже?
делается несколько утверждений там:
Одно утверждение состоит в том, что функция 1 из пароль + соль уступающий хэш определяется
хэш = sha512 (пароль + соль);
для (я = 0; я < 1000; я ++) {
хэш = sha512 (хэш); // <-- НЕ делайте этого!
}
с большей вероятностью столкнется, чем функция 2 из пароль + соль уступающий хэш определяется
хэш = sha512 (пароль + соль);
для (я = 0; я < 1000; я ++) {
хэш = sha512 (хэш + пароль + соль);
}
Это правильно в теории и будет наблюдаться на практике для узкого хеша, например. 80-бит.
Один из способов увидеть это
- выходной набор фиксированной случайной функции $Ч$ повторяющийся $n$ время имеет тенденцию к сужению, поскольку $n$ растет (аргумент: он никогда не может увеличиваться, когда $n$ делает, и некоторое сужение происходит из-за коллизий повторного хэша, здесь SHA-512);
- вероятность столкновения случайной функции для двух случайных различных входных данных обратно пропорциональна размеру ее выходного набора.
Таким образом, это понятно (хотя повторение случайной функции $n$ раз может не дать случайной функции относительно того, что осталось от выходного набора), что вероятность столкновения $Ч^п(х)$ для двух случайных различных $х$ увеличивается с $n$.
Это ограничивает устойчивость к коллизиям функции 1, которая за цикл повторяется $H: h\mapsto\имя_оператора{SHA-512}(h)$. Принимая во внимание, что в 2 итерируемая функция изменяется, когда вход пароль + соль изменяется, поэтому выходные наборы сокращаются с $n$ зависят от этого ввода. В модели хэша как случайной функции 2 также является случайной функцией, которая потенциально может достигать полного набора, и это вероятность столкновения для разных входных данных. пароль + соль не увеличивается, как $n$ делает.
Также утверждается, что по этой причине на практике следует использовать 2, а не 1, что неверно по ряду причин:
- По крайней мере, для любого хэша, устойчивого к коллизиям, как SHA-512, нам вообще не нужно беспокоиться о коллизиях или циклах.
- В контексте (приложение для хеширования паролей) устойчивость к столкновениям общей итерируемой функции не является проблемой. Сопротивление прообразу является. И даже для SHA-1, которая не является коллизионно-стойкой, и любой реалистичной $n$, нам не нужно беспокоиться о том, что для взлома 1 потребуется значительно меньше вычислений хэша, чем для взлома 2, в том числе с реалистичным предварительным вычислением.
Преимущество 2 заключается в том, что его немного сложнее реализовать на оборудовании, потому что аппаратное обеспечение должно использовать пароль и соль на каждой итерации, которые, следовательно, должны храниться. Таким образом, ASIC для ускорения 2 будет сложнее, чем для 1. Это единственная причина, по которой я вижу, что 2 менее плох, чем 1 на практике. Это все еще плохо, потому что $n=1000$ итерации недостаточно медленны для ASIC или GPU, выполняющих поиск паролей; и потому что все это не использует память, таким образом теряя дополнительную защиту от перебора паролей методом грубой силы, которую современные хэши паролей с жесткой памятью (например, скрипт или же Аргон2) дайте.
Будет ли многократное хеширование более безопасным, чем однократное хеширование?
Это зависит в первую очередь от цели, которая диктует использование хеша.
- Если мы хешируем с целью растяжка ключей, то есть обычно при хешировании пароля или фразы-пароля, да: защита от перебора методом грубой силы растет примерно линейно с количеством раундов. Но опять же, мы должны использовать жесткий хеш пароля.За равное время потрачено даже устаревшее bcrypt даст больше безопасности, чем конструкции, просто итерирующие хэш, например ПБКДФ2 или функции 1 и 2, которые явно не рекомендуются в эпоху ASIC, FPGA и GPU для взлом пароля.
- Если мы хэшируем более одного раза, чтобы усилить некоторую криптографическую хеш-функцию с дефектом (например, ее устойчивость к коллизиям нарушена), возможно, да. Например. функция 2 (с
пароль + соль заменено сообщением в хэш) исправит все известные дефекты безопасности MD5 или же ША-1 помимо их выходной ширины, даже если мы сделаем только один дополнительный раунд, а не 1000. Однако это приводит к огромной цене производительности и удобства использования, потому что нам нужно дважды хешировать сообщение, поэтому в некоторых случаях сохранить его.
- Для других криптографических целей, включая получение подписи и ключа из широкого ключа с использованием современного хэша, нет. Для этих целей мы можем использовать SHA-2 или SHA-3 (чтобы назвать тех, кто в вопросе). Повторное хеширование не требуется и может даже немного снизить устойчивость к коллизиям (если выполняется, как в 1), за одним исключением: если хэш имеет свойство удлинения длины (как у SHA-2, но не у SHA-3), и если это нежелательно, разумно повторно хешировать один раз вывод хэша (что не требует сохранения сообщения дважды).
