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

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

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

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

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

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

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

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

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