Общая мудрость
Как правило, комбинирование криптографических примитивов редко приводит к прямой победе. Это может усилить некоторые свойства, если все сделано правильно, но ослабить другие свойства.Поэтому это следует делать только в том случае, если это усиливает свойства, которые вам важны, и не ослабляет свойства, которые вам важны.
сочетание H и F является обычной практикой, чтобы оставаться в безопасности, когда один из них становится небезопасным, но были разные мнения, когда речь шла о том, является ли такая комбинация такой же безопасной, как MAX(H, F) или MIN(H, F) с точки зрения безопасность, почти никто не предполагал, чем безопасность будет выше или ниже этой.
Вы нашли смешанные мнения, потому что это зависит от того, как вы делаете комбинацию. (Это или потому, что люди были неосведомлены. Бывает.)
У меня также есть некоторые личные мысли по этому поводу, происходящие из школьной математики. Мне кажется очевидным, что если е: А -> Б и очень |А| > |Б| и г: Б -> С и очень |Б| > |С| тогда г (е (х)) должно иметь гораздо больше столкновений, чем f или g.
Подсчет столкновений не имеет значения. Важно то, что их трудно найти. MD5(х)||SHA1(х) представляет собой 288-битный хэш и, вероятно, имеет меньше коллизий в 257-битных строках, чем SHA256(х) на самом деле правдоподобно, что MD5(х)||SHA1(х) вообще не имеет коллизий на 257-битных строках, тогда как SHA256(х) должны иметь коллизии по принципу классификатора. Но мы знаем, как находить коллизии на MD5(х)||SHA1(х) для немного более длинных строк за долгое, но выполнимое время (это лишь немного дороже, чем коллизии SHA1), тогда как мы вообще не знаем, как находить коллизии SHA256.
Но также тот факт, что мы объединяем две сложные функции, должно быть несколько сложнее «сломать».
Нет, это не факт. Это полностью зависит от того, что вы комбинируете и как.
Составление двух хэшей
Касательно хеши и устойчивость к столкновениям, составление двух хэшей снижает безопасность. Другими словами, $H \circ F$ менее устойчив к столкновениям, чем $Ч$ или же $F$ самостоятельно.
Легко видеть, что если $F$ имеет столкновение, то и $H \circ F$: если $F(x_1 = F(x_2)$ с $x_1\ne x_2$ тогда $(H \circ F)(x_1) = H(F(x_1)) = H(F(x_2)) = (H \circ F)(x_2)$. Уже одно это означает, что составление двух хэшей в лучшем случае бесполезно, если вас волнует устойчивость к столкновению: с тем же успехом вы могли бы просто использовать $F$.
Сопротивление столкновению $H \circ F$ может быть лучше, чем у $Ч$ в одиночестве. Если $Ч$ имеет столкновение $Ч(у_1) = Н(у_2)$ с $y_1\ne y_2$, чтобы использовать этот факт, чтобы найти столкновение для $H \circ F$, вам нужно найти прообраз для обоих $y_1$ и $y_2$. Итак, вы уверены, что $F$ устойчив к коллизиям и прообразам, то $H \circ F$ может быть безопаснее, чем $Ч$ по сопротивлению столкновениям. Однако, поскольку это не безопаснее, чем $F$, единственная причина использовать эту конструкцию — если она улучшает какое-то другое свойство.
Если $H \circ F$ имеет столкновение, т. е. если $ Н (F (x_1)) = Н (F (x_2)) $ с $x_1\ne x_2$, то либо $F(x_1) = F(x_2)$ и это столкновение для $F$, или же $F(x_1) \ne F(x_2)$ и это столкновение для $Ч$. Так что состав не хуже худшего из двух, по сопротивлению столкновению.
Составление двух хэшей может повысить устойчивость к прообразам. Чтобы воспользоваться структурой $H \circ F$ при поиске прообраза вы оба должны найти прообраз через $Ч$ а затем прообраз этого через $F$. Однако ни одна криптографическая хеш-функция, которую я бы назвал основной, никогда не нарушала устойчивость к прообразу, так что это не имеет практического значения.
Сопротивление прообразу беспокоит пароль функции хеширования. Но Функции хеширования паролей — это совершенно другой тип криптографических примитивов, отличный от «обычных» хеш-функций.. У них разные параметры и разные цели безопасности. Устойчивость к коллизиям не имеет отношения к хешированию паролей. Составление двух функций хеширования паролей может иметь смысл, но нужно быть осторожным: определенно можно сделать это неправильно.
Составление двух хэшей также может улучшить свойства безопасности, отличные от свойств, определяющих криптографическую хеш-функцию. Хэши часто используются как случайные оракулы, и широко используемые хэши (например, семейство SHA-2), как известно, несовершенны как случайные оракулы из-за атака удлинения длины. Составление двух хэшей, даже одной и той же функции, как в SHA256d(х) = SHA256(SHA256(х)), устраняет атаку расширения длины и не вводит другую известную уязвимость сама по себе. («Сами по себе» важны: если вы смешиваете SHA256d и SHA256 с одними и теми же данными, результаты могут быть катастрофическими.)
Объединение двух хэшей
Еще один простой способ объединить два хэша — объединить их: $Н(х) || Ф(х)$. Это определенное улучшение с точки зрения сопротивления столкновению: если есть столкновение для $Ч || Ф$, это также столкновение для $Ч$ и $F$. Конкатенация также улучшает сопротивление второго прообраза: если ты знаешь $Н(х_1) || Ф(х_1)$ и ты хочешь найти $x_2\ne x_1$ такой, что $Н(х_1) || F(x_1) = H(x_2) || Ф(х_2)$, вам нужно найти второй прообраз для обоих $F$ и $Ч$. Как для сопротивления столкновению, так и для сопротивления второму прообразу конкатенация, по крайней мере, столь же сильна, как и более слабый из двух, а возможно, и сильнее.
Примером использования конкатенации в реальном протоколе являются старые версии протокола. SSL/TLS-протокол, до версии 1.1. Они использовали MD5(х)||SHA1(х) для подписи рукопожатия, где основной проблемой безопасности является сопротивление второму прообразу. TLS 1.2 заменил это одной настраиваемой хеш-функцией (обычно SHA-256 или SHA-384): дополнительная сложность того не стоила (и в любом случае в то время не было разумной популярной хеш-функции для объединения с SHA-256).
Конкатенация не является однозначным выигрышем. Например, уменьшает сопротивление первого прообраза к более слабой из двух функций: если вы знаете $Н(х) || Ф(х)$ тогда вы можете найти $х$ если вы знаете, как это сделать либо через $Ч(х)$ или через $Ф(х)$.
Xoring два хэша
Еще один способ объединить два хэша — это их xor: $H(x) \oplus F(x)$. Защитные свойства результата зависят от выбора функций. Это имеет очевидный потенциал для ужасной ошибки: особый случай $Ч = Ф$ приводит к выводу, что все биты равны нулю. С другой стороны, если $Ч$ и $F$ независимы, то $H \oplus F$ по крайней мере так же хорош, как более сильный из двух, как случайный оракул. Я не уверен с самого начала, есть ли разумное условие, которое давало бы какую-либо гарантию сопротивления столкновению.
