Рейтинг:3

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

флаг tr

Я наткнулся на много мнений, поэтому спрашиваю о них сам.

Позволять $Ч(х)$ и $Ф(х)$ быть хеш-функциями.

  • является $ Н (Ф (х)) $ или же $F(Н(х))$ безопаснее, чем $Ч(х)$ или же $Ф(х)$
  • является $ Н (Ф (х)) $ или же $F(Н(х))$ безопасно, когда $Ч(х)$ или же $Ф(х)$ становится уязвимым
  • является $ Н (Н (х)) $ безопаснее, чем $Ч(х)$

Задний план

Проведя собственное исследование, я нашел утверждения, предполагающие, что объединение ЧАС и Ф является обычной практикой оставаться в безопасности, когда один из них становится небезопасным, но мнения разделились, когда речь заходит о том, является ли такая комбинация такой же безопасной, как МАКС(Ч, Ф) или же МИН(Ч, Ф) с точки зрения безопасности, почти никто не предполагал, что безопасность будет выше или ниже этого.

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

У меня также есть некоторые личные мысли по этому поводу, происходящие из школьной математики. Мне кажется очевидным, что если е: А -> Б и очень |А| > |Б| и г: Б -> С и очень |Б| > |С| тогда г (е (х)) должно иметь гораздо больше столкновений, чем ф или же г. Но также тот факт, что мы объединяем две сложные функции, должно быть несколько сложнее «сломать».

Итак, моя собственная интуиция такова, что г (е (х)) имеет больше столкновений, но сложнее найти метод, чтобы найти столкновение намеренно и в случае таких функций, как ША или же БЛЕЙК увеличение количества столкновений не является проблемой, но польза от безопасности того стоит.

poncho avatar
флаг my
На практике, если мы хотим полагаться на несколько хеш-функций (и ищем устойчивость к коллизиям или вторым прообразам), мы используем $F(x) | H(x)$ (где $|$ — конкатенация); легко показать, что (предполагая, что $F$ или $H$ имеет вывод фиксированной длины) результат устойчив к коллизиям/второму прообразу, если либо $F$, либо $H$ устойчивы к коллизиям/второму прообразу
kelalaka avatar
флаг in
Все для этого? [Как безопасно хэшировать пароли?](https://security.stackexchange.com/questions/211/how-to-securely-hash-passwords)
Kuba Chrabański avatar
флаг tr
Я полагаю, что вы все еще пытаетесь понять смысл моих вопросов в целом, когда их нет. У меня есть несколько дел, совершенно отдельных, которые я разбил на небольшие подвопросы, которые затем перекомпоновал в несколько более крупных вопросов.
Kuba Chrabański avatar
флаг tr
Я спрашиваю о конкретных случаях, чтобы построить некоторую интуицию, которая может в будущем уменьшить набор решений для тестирования.
kelalaka avatar
флаг in
Криптография не разделяет, решает и комбинирует, особенно для начинающих. Дьявол в деталях и сочетание двух безопасных систем могут привести к ненадежным проектам. Я просто говорю, что остановитесь, не торопитесь и определите свою настоящую проблему, включая то, что вы нашли там и здесь, в сообщении с вопросом.
Рейтинг:7
флаг ru

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

Для сопротивления столкновению, обнаружение столкновения на $ Н (Ф (Х)) $ не сложнее, чем найти столкновение $Ф(Х)$ и так если $F$ столкновение скомпрометировано, то так $ Н (Ф (Х)) $. Чтобы увидеть это, пусть $m_1$ и $m_2$ относиться к двум различным входам таким, что $F(m_1)=F(m_2)$ тогда потому что $Ч$ это функция у нас есть $Ч(Ф(м_1))=Ч(Ф(м_2))$. В частном случае $F=H$, $ Н (Н (Х)) $ не более устойчив к столкновениям, чем $Н(Х)$.

Точно так же, если $Н(Х)$ столкновение скомпрометировано и $Ф(Х)$ предварительное изображение скомпрометировано (чрезвычайно скомпрометировано, так что предварительные изображения занимают меньше времени, чем работа на день рождения), мы можем скомпрометировать коллизию $ Н (Ф (Х)) $ обнаружив столкновение на $Ч$ а затем найти прообразы для обоих конфликтующих сообщений.

Обратите внимание на разницу во внутренних и внешних функциях. В настоящее время мы можем найти сообщения $m_1$ и $m_2$ такой, что $\mathrm{SHA3}(\mathrm{SHA1}(m_1))=\mathrm{SHA3}(\mathrm{SHA1}(m_2))$, но не можем найти $m_3$ и $m_4$ такой, что $\mathrm{SHA1}(\mathrm{SHA3}(m_3))=\mathrm{SHA1}(\mathrm{SHA3}(m_4))$.

Аналогично для сопротивления второму прообразу: если внутренняя функция второго прообраза нарушена, то и композиция нарушена.

Для полной устойчивости к прообразу мы, безусловно, можем найти полный прообраз для композиции, если мы сможем найти полные прообразы для обоих $Ч$ и $F$. Компрометации одной хэш-функции до изображения недостаточно: рассмотрим линейный хэш $L(Х)$ который тривиально сломан перед изображением. Для цели $Y$, мы не можем найти ни $Х$ такой, что $\mathrm{SHA3}(L(X))=Y$ ни $ L (\ mathrm {SHA3} (X)) = Y $.

Рейтинг:6
флаг cn

Общая мудрость

Как правило, комбинирование криптографических примитивов редко приводит к прямой победе. Это может усилить некоторые свойства, если все сделано правильно, но ослабить другие свойства.Поэтому это следует делать только в том случае, если это усиливает свойства, которые вам важны, и не ослабляет свойства, которые вам важны.

сочетание 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$ по крайней мере так же хорош, как более сильный из двух, как случайный оракул. Я не уверен с самого начала, есть ли разумное условие, которое давало бы какую-либо гарантию сопротивления столкновению.

Kuba Chrabański avatar
флаг tr
«Сопротивление прообразу является проблемой для функций хеширования паролей». Это то, что я ожидал, хорошо, но имеет ли здесь значение сопротивление второму прообразу? Я считаю, что нет, по крайней мере, не так прямо, как: «отсутствие сопротивления прообраза подразумевает отсутствие сопротивления второго прообраза», и это применимо в одном направлении.
Gilles 'SO- stop being evil' avatar
флаг cn
@KubaChrabaÅski Действительно, для пароля сопротивление второму прообразу так же не имеет значения, как и сопротивление столкновению. Если противник знает один прообраз, его работа выполнена.
Kuba Chrabański avatar
флаг tr
Хорошо, спасибо, очень хороший и исчерпывающий ответ!
Рейтинг:4
флаг in

Целевой безопасностью криптографических хеш-функций, таких как SHAx, BLAKE и т. д., является устойчивость к коллизиям. Классическая общая стоимость атаки столкновений составляет $\mathcal{O}(2^{n/2})$-время из-за нападения на день рождения.

Теперь взгляните на свои хэш-композиции более подробно;

  • является $ Н (Ф (х)) $ или же $F(Н(х))$ безопаснее, чем $Ч(х)$ или же $Ф(х)$
  • Атака удлинения длины;

Двойное хэширование предложено Брюсом Шнайером для смягчения атака удлинения длины хеш-функций на основе MD. Атака на расширение длины выполняется против секретного префикса $H(секрет||сообщение)$. Двойное хеширование разработано как $ Н (Н (х)) $ и Биткойн использует SHA256d для медленного майнинга. Ваш случай отличается, однако эта атака работает только в том случае, если вы хотите использовать этот хэш для создания MAC с префиксно-секретной конструкцией. При двойном хэшировании злоумышленники не могут расширить внутренний хэш, поэтому расширение длины безопасно, даже если одиночные хэши не защищены. Однако использование SHA3, SHA-512/256, BLAKE2, Shake, которые уже защищены таким образом, требует много времени даже для возможного криптографического квантового компьютера.

Любая криптографическая хеш-функция с атакой на расширение длины не является Random Oracle. Поэтому SHA3 и BLAKE2 больше похожи на случайные оракулы.

  • **

  • Столкновение

сопротивление**

Если внутренние хэши $Ч$ или же $F$ не устойчив к коллизиям, то комбинированные хэши $ Н (Ф (х)) $ или же $F(Н(х))$ не будет устойчивым к столкновениям. Данный $х,у$ с $х\neq у$, если $Н(х)=Н(у)$ тогда $F((H(x))=F(H(y))$ есть столкновение для композиции, и аналогично для $ Н (F (\ cdot)) $ кейс.

Если вы хотите смягчить атаку коллизии внутренней хэш-функции, простой ответ; не используйте его.

  • Предварительное сопротивление изображения

    У первого и второго сопротивления предварительного изображения есть одна и та же проблема, пропущенная здесь.

  • является $ Н (Ф (х)) $ или же $F(Н(х))$ безопасно, когда $Ч(х)$ или же $Ф(х)$ становится уязвимым

Когда $Ф(х)$ имеет столкновение тогда $ Н (Ф (х)) $ имеет ответ на тривиальное столкновение в первой части.

Позволять $Ф(х)$ безопасный (без коллизий, без расширения длины, без предварительного изображения), но не $Ч(х)$ тогда как насчет $ Н (Ф (х)) $? Это немного сложно, использовать атаку столкновения $Ч$ нам нужно найти прообразы $F$ так это более безопасно.

  • является $ Н (Н (х)) $ безопаснее, чем $Ч(х)$

Немного да; $ Н (Н (х)) $ защищен от атак с увеличением длины. Если произошло столкновение $Ч$, $Н(х)=Н(у)$ с $x \neq у$ тогда это столкновение для двойника $H(H(x)) = H(H(y))$, тоже.

Я также обнаружил, что некоторые алгоритмы, использующие пароли, используют SHA256d, который по сути является SHA256(SHA256(x)), и что теоретически использование большего количества раундов повысит безопасность хеширования, что не так далеко от объединения хеша с самим собой.

Кто использует SHA256d для хэширования паролей, тот ничего о них не знает. Хеширование паролей требует времени, памяти и потребления потоков, чтобы смягчить массовые поиски с использованием ЦП, графического процессора или ASIC.

SHA256d используется в биткойнах для медленный майнинг. Любая вновь разработанная система для хеширования паролей должна использовать по крайней мере Scrypt или лучше Argon2, а старые системы должны быть перенесены как можно скорее.


Для академического подробного результата по хеш-комбайнерам начните читать с

И даже они могут генерировать множественные столкновения;

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.