Рейтинг:2

Есть ли коллизия в шифровании, как в хеш-функциях?

флаг cz

В хеш-функциях $ч(м) = ч(м_1)$ называется коллизией, и очень нежелательно, чтобы их можно было найти, поскольку это подрывает безопасность хеширования. Однако существуют ли аналогичные проблемы в шифровании, такие как блочные шифры (AES-256) или RSA? Если есть пара ключей открытого текста $м,к$ который дает некоторый зашифрованный текст, и существует еще один ключ, пара сообщений $m_1, k_1$ который также дает тот же зашифрованный текст, это по сути аналогичная проблема, как коллизия хэшей? Имея две пары, вы можете затем провести «криптоанализ» и «прорывной» шифр, «узнав», как две пары заканчиваются одним и тем же зашифрованным текстом.

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

corsiKa avatar
флаг us
Я хотел бы сказать, что это хорошо, потому что нутром чувствуется, что если что-то применимо к хэшированию, то оно применимо и к шифрованию, и наоборот. Да, они оба сложны и часто используют одни и те же или похожие алгоритмы, но это два разных инструмента для двух разных задач, и делать предположения об одном на основе другого неразумно — на самом деле, когда речь идет о безопасности, вы должны *всегда* подвергать сомнению ваши предположения!
nimrodel avatar
флаг cz
я не предполагал, что коллизии происходят только при шифровании или даже частично, потому что это происходит при хешировании. скорее я привел хэш просто как пример «как в хэше». мне было интересно, шифрует ли m1xk1 в m2xk2 в первую очередь и есть ли беспокойство о том, что дешифровать, когда может быть несколько вариантов (точно так же, как в хеше). так что это ты предполагаешь, что я предположил.
Рейтинг:4
флаг et

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

Это не относится к шифрованию. Выход шифрования всегда по крайней мере такой же, как размер ввода, поэтому принцип Pigeonhole не применяется.

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

Enc(Plaintext1, key1) никогда не равно Enc(Plaintext2, key1)

ilkkachu avatar
флаг ws
верно, хотя обратите внимание, что там были два разных ключа $k$ и $k_1$. Вопрос не в $E(m_1, k) = E(m_2, k)$, а в $E(m_1, k_1) = E(m_2, k_2)$
kelalaka avatar
флаг in
Это читается неправильно, как я делал раньше. ОП запрашивает коллизии с разными ключами. доказать существование легко, найти по конкретному тексту сложно. Проверьте первую часть моего ответа.
Рейтинг:3
флаг in

Коллизия блочных шифров с разными ключами

Если есть пара ключей открытого текста $м,к$ который дает некоторый зашифрованный текст, и существует еще один ключ, пара сообщений $m_1,k_1$ который также дает тот же зашифрованный текст, это по сути аналогичная проблема, как коллизия хэшей?

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

Если вы используете CTR (любой режим потоковой передачи), то, если у вас есть коллизия зашифрованного текста, это не покажет сообщения, поскольку

$$m_1 \oplus o_1 = c_1 = c_2 = m_2 \oplus o_2$$ так как

$$m_1 m_2 \oplus = o_1 \oplus o_2$$ и это не раскроет сообщения, даже если вы угадаете одно.

И точно так же режим CBC будет противостоять коллизиям под разными ключами.

Возможность коллизии зашифрованного текста

предположим, что мы AES-шифруем «moon» с ключом «morehotquestions», получая «fjydhpdag». и мы шифруем «sun» ключом «hotnetworkquestions», получая также «fjydhpdag». это вообще возможно?

Если учесть, что AES — это PRP, то мы имеем точно такое же состояние, как и атака дня рождения. Вероятность того, что два отдельных блока будут иметь одинаковый зашифрованный текст, равна $1/2^{128}$ для блока ЕЦБ.

Найти один из нас намного проще, так как AES обратим. Рассмотрим ECB для простого случая.Поскольку AES обратим, возьмите зашифрованный текст и расшифруйте его двумя разными ключами. Тогда вы получите два разных сообщения. Конечно, они не обязательно имеют смысл, это простой способ найти/показать это.

Системы подписи, такие как RSA-Sign

Системы подписи используют хэш сообщения для подписи. Один из способов подделки злоумышленника — вторая атака на хеш-функцию с предварительным изображением. Что, если у нас есть злонамеренный подписывающий или злонамеренный секретарь подписывающего? Предположим, что они используют MD5, для которого коллизия неизбежна (не используйте MD5 и SHA-1 для подписи), тогда они могут найти два сообщения с одинаковыми значениями хеш-функции. $ч(м_1) = ч(м_2)$ с $m_1 \neq m_2$ тогда два значения $$\operatorname{RSA-Sign}(h(m_1)) = \operatorname{RSA-Sign}(h(m_2))$$ подобные.

Всегда используйте устойчивые к коллизиям криптографические хеш-функции, такие как SHA-256, SHA-512, SHA-3, BLAKE2 и т. д., чтобы смягчить эту атаку.


Бонусная часть: коллизия блочных шифров с одним и тем же ключом

Да, есть нападки и опасения по этому поводу; как Sweet32;

  • Sweet32: Атаки дня рождения на 64-битные блочные шифры в TLS и OpenVPN

    Короче говоря, для блочного шифра размером $b$, если вы шифруете $2^б$ блоки под тем же ключом можно столкнуться с зашифрованным текстом режима CBC, который $c_i = c_j$ с $i \neqj$. Это;

    $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$

    Затем, используя свойства CBC, мы можем получить

    $$m_i \oplus m_j = c_{1-1} \oplus c_{j-1}.$$

    Как мы видим, это просто x-or блоков открытого текста, которые пассивный злоумышленник может использовать.

Я говорил только о режиме CBC, однако на странице упоминается больше и оставлено исследование, похожее на CBC;

Это особенно важно при использовании обычных режимов работы: мы требуем, чтобы блочные шифры были защищены до $2^n$ запросы, но большинство режимов работы (например, CBC, CTR, GCM, OCB, и т. д.) небезопасны с более чем $2^{n/2}$ блоки сообщений (привязка к дню рождения).

Конечно, мы почти больше не используют 64-битные шифры размером с блок. Однако эта атака возможна даже в том случае, если вы шифруете слишком много данных, используя один и тот же ключ. Можно сказать, что шифрование $2^{64}$ данных слишком много, мы не будем шифровать такой размер. Тогда у нас есть более глубокий аргумент, 50% атаки дня рождения слишком много для преимущества атакующего, это далеко не ничтожно. Они могут искать даже более низкие вероятности, чтобы раскрыть какой-то блок сообщений. Вам следует ограничиться $2^{32}$-блок, чтобы уменьшить преимущество атакующего.

nimrodel avatar
флаг cz
предположим, что мы AES-шифруем «moon» с ключом «morehotquestions», получая «fjydhpdag». и мы шифруем «sun» ключом «hotnetworkquestions», получая также «fjydhpdag». это вообще возможно? я спрашиваю о двух совершенно разных ключах и сообщениях. может ли тогда, если они действительно могут зашифровать один и тот же «fjydhpdag», система дешифрования AES запутаться, то есть она дешифрует оба открытых текста с разными ключами?
kelalaka avatar
флаг in
Разные ключи выбирают разные перестановки и это, в целом, предотвращает возможные атаки. Атака Sweet32 требует того же ключа, которого нет у вас.Вы должны определить свой режим работы, чтобы поговорить об этом подробнее, поскольку дьявол кроется в деталях (пожалуйста, не изменяйте вопрос, так как он получил некоторые ответы)
kelalaka avatar
флаг in
Я написал раздел для вашего конкретного вопроса, который я пропустил, и также ответил на ваш комментарий.

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

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