Зачем вам нужно много случайности для эффективного шифрования?

Question

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

Может ли кто-нибудь объяснить, как может быть нарушена безопасность, если не хватает случайности?

Answer 1

Случайность означает неосуществимый ввод. Если вход является предположительным, то выход может быть легко рассчитан. Это плохо.

Например, Debian имел давнюю ошибку в своей реализации SSL, которая не смогла собрать достаточно случайности при создании ключа. Это привело к тому, что программное обеспечение сгенерировало один из 32k возможных ключей. Таким образом, можно легко расшифровать все, что было зашифровано с помощью такого ключа, испробовав все 32 тыс. Возможностей, попробовав их, что очень быстро, учитывая сегодняшние скорости процессора.

Answer 2

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

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

С другой стороны, если у вас есть какая-либо информация о вероятных значениях ключа, ваш исчерпывающий поиск по пространству ключей будет намного проще (или количество выборок, необходимых для криптоанализа, будет намного меньше). Например, (в настоящее время) невозможно выполнить 2 ^ 128 пробных расшифровок, чтобы выяснить, что на самом деле представляет собой 128-битный ключ. Если вы знаете, что материал ключа получен из значения времени, которое, как вы знаете, с точностью до миллиарда тиков, тогда ваш поиск стал в 340282366920938463463374607431 раз проще.

Answer 3

Чтобы расшифровать сообщение, вам нужно знать правильный ключ.

Чем больше ключей вы попробуете, тем сложнее расшифровать сообщение.

Взяв крайний пример, скажем, нет никакой случайности вообще. Когда я сгенерирую ключ для шифрования своих сообщений, я всегда получу тот же ключ. Независимо от того, где и когда я запускаю программу keygen, она всегда дает мне один и тот же ключ.

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

Так что нам нужна некоторая случайность, чтобы сделать непредсказуемым, какой ключ вы в конечном итоге используете. Как упоминает Дэвид Шмитт, в Debian была ошибка, из-за которой он генерировал только небольшое количество уникальных ключей, что означает, что для расшифровки сообщения, зашифрованного реализацией OpenSSL по умолчанию в Debian, мне просто нужно попробовать это меньшее количество возможных ключей. Я могу игнорировать огромное количество других допустимых ключей, потому что реализация SSL в Debian никогда не сгенерирует их.

С другой стороны, если при генерации ключа было достаточно случайности, невозможно угадать что-либо о ключе. Вы должны попробовать все возможные битовые комбинации. (и для 128-битного ключа это много комбинаций.)

Answer 4

Вот аналогия с «карточной игрой»: предположим, мы играем в несколько раундов одной и той же колодой карт. Перетасовка колоды между раундами является основным источником случайности. Если бы мы не перемешали должным образом, вы могли бы пройти игру, предсказав карты.

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

Answer 5

Распространенный шаблон в криптографии следующий (отправка текста от Алисы к Бобу):

Take plaintext p
Generate random k
Encrypt p with k using symmetric encryption, producing crypttext c
Encrypt k with bob's private key, using asymmetric encryption, producing x
Send c+x to bob
Bob reverses the processes, decrypting x using his private key to obtain k

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

Answer 6

Это связано с некоторыми из основных причин криптографии:

• Убедитесь, что сообщение не изменено в пути (неизменяемым)
• Убедитесь, что сообщение не читается при передаче (Защищено)
• Убедитесь, что сообщение от того, от кого оно написано (Подлинный)
• Убедитесь, что сообщение не совпадает с ранее отправленным (без воспроизведения)
• и т.д.

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

Например, если я зашифрую «Слишком много секретов» ключом, может получиться «dWua3hTOeVzO2d9w»

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

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

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

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

-Adam

Answer 7

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

• http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html

Здесь описывается, как в 1995 году реализация SSL в ключе браузера Netscape была уязвима для угадывания ключей SSL из-за проблемы заполнения SENG.

Answer 8

Решите эту проблему от Project Euler, и она действительно поможет понять, что «случайность» сделает для вас. Когда я увидел этот вопрос, это было первое, что пришло мне в голову.

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