Чтение выбранного ответа на Разработка хэш-функции на основе первых принципов, а не в зависимости от эвристики очень проницателен.
В разделе «нелинейность» предполагается, что превращение каждого уравнения, участвующего в хеш-функции, в линейное означает, что злоумышленник может легко выяснить реализацию хеш-функции.
Если вы попытаетесь создать криптографическую хэш-функцию, которая использует только исключающее ИЛИ и сдвиг, уравнения будут линейными даже после бесконечного количества раундов, теперь аналитик находится всего в одном исключении Гаусса от его решения, и теперь у них есть возможность создавать произвольные прообразы .
Чтобы избежать этого, вам нужно сделать ваши уравнения нелинейными, используя оператор И. Хэши выполняют всевозможные операции сдвига и XOR, но именно этот нелинейный шаг делает их безопасными.
Но иметь нелинейные термины недостаточно. Вы должны убедиться, что злоумышленник не может эффективно исключить нелинейные члены из ваших уравнений, установив некоторые входные данные на 1 или 0. Также вам нужно убедиться, что члены не будут отменены, если злоумышленники возьмут разность двух уравнений. Если у вас формула ++ для одного и формула ++ для другого бита. Добавление этих двух даст +, который теперь является линейным и позволяет злоумышленнику решить его, чтобы получить отношение между двумя выходными битами. Каждое независимое линейное уравнение, которое может создать злоумышленник, снизит безопасность вашего хэша на 1 бит.
Можете подробнее объяснить, как это будет работать? Учитывая неработающую хэш-функцию, как вы могли бы показать эту ситуацию с линейностью на этой хеш-функции? По сути, скажем, md5 является примером (по какой-то причине небезопасным). Это небезопасно по этой причине линейности? Если да, то что это означает с точки зрения хеш-функции md5? Какие уравнения оказались линейными? Если md5 — плохой пример, то какой хороший? В принципе, как вы ищете линейность в хеш-функции побитно, какие методы использовать?
Я хотел бы знать методы, которые злоумышленник может использовать для «решения» хеш-функции только на основе ввода/вывода (не видя реализации). Но поскольку это, вероятно, слишком общий или слишком сложный вопрос, этот вопрос фокусируется только на этом аспекте линейного уравнения. Какие методы «линейного уравнения» может использовать злоумышленник для решения хеш-функции?
