В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 5. Режимы работы блочных шифров случайным, наоборот — он высоко структурирован. В таком тексте одинако- вые блоки встречаются довольно часто, а соответствующие одинаковые блоки шифрованного текста хорошо воспроизводят эту структуру для злоумышлен- ника. Вот почему мы не рекомендуем использовать режим ECB. А что же режим CBC? В этом случае одинаковые блоки открытого тек- ста не будут преобразованы в одинаковые блоки шифрованного текста, по- скольку перед шифрованием каждый блок открытого текста складывается с помощью операции XOR с предыдущим блоком шифрованного текста. Все блоки шифрованного текста можно представить себе в виде случайных зна- чений; в конце концов, они были получены посредством блочного шифра, генерирующего случайные выходные данные по заданным входным данным. Но что, если у нас окажется два одинаковых блока шифрованного текста? Рассмотрим следующее равенство: C i = C j , E ( K, P i ⊕ C i − 1 ) = E ( K, P j ⊕ C j − 1 ) — из спецификации режима CBC , P i ⊕ C i − 1 = P j ⊕ C j − 1 — расшифруем обе стороны , P i ⊕ P j = C i − 1 ⊕ C j − 1 — один из фундаментальных законов алгебры . Последнее равенство показывает, что разница между блоками открыто- го текста равна сумме XOR соответствующих блоков шифрованного текста, которые, как можно было предположить, известны злоумышленнику. Разу- меется, это совсем не то, чего мы ожидали от совершенной системы шифрова- ния. А если открытый текст многословен (как, например, обычный текст на английском языке), он, вероятно, содержит достаточно информации, чтобы злоумышленник мог восстановить оба блока открытого текста. Аналогичная ситуация случается и тогда, когда два блока шифрованно- го текста не равны друг другу. Зная, что C i 6 = C j , получаем, что P i ⊕ P j 6 = C i − 1 ⊕ C j − 1 , поэтому неравенство блоков шифрованного текста означает нера- венство блоков открытого текста. Подобными свойствами обладает и режим CTR. Известно, что все блоки K i неодинаковы, так как получены путем применения шифрования к конкате- нации значений оказии и счетчика. Поскольку все значения такого открытого текста будут разными, значения шифрованного текста (которые формируют ключевые блоки) тоже будут разными. Для двух любых блоков шифрован- ного текста C i и C j можно сказать, что P i ⊕ P j 6 = C i ⊕ C j , так как в противном случае два ключевых блока были бы одинаковыми. Другими словами, режим CTR обеспечивает неравенство открытого текста для каждой пары блоков шифрованного текста. 5.8. Утечка информации 101 В режиме CTR нет проблем с коллизиями. Два ключевых блока никогда не будут одинаковыми, а равенство блоков открытого или шифрованного тек- ста не означает ровным счетом ничего. Единственное, что отличает CTR от идеального поточного шифра, — это отсутствие коллизий ключевых блоков. Режим OFB хуже, чем CBC или CTR. Пока между блоками ключевого потока не возникает коллизий, режим OFB приводит к утечке такого же объ- ема информации, как и режим CTR. Тем не менее, если между ключевыми блоками режима OFB когда-нибудь возникнет коллизия, она приведет к кол- лизии всех последующих ключевых блоков. Это катастрофа с точки зрения безопасности, а также основная причина того, почему CTR предпочтительнее режима OFB. 5.8.1 Вероятность коллизии Итак, какова же вероятность того, что два блока шифрованного текста окажутся равными? Предположим, мы зашифровали M блоков открытого текста. То, как именно они были организованы — в несколько больших со- общений или в большое количество коротких сообщений, не имеет значения. Нас интересует только общее количество блоков. Из полученных блоков по довольно грубой оценке можно сформировать примерно M ( M − 1) / 2 пар бло- ков. Вероятность того, что значения блоков в паре совпадут, равна 2 − n , где n — это размер блока используемого блочного шифра. Итак, ожидаемое ко- личество пар одинаковых блоков шифрованного текста равняется M ( M − 1) / 2 n +1 , что приближается к единице при M ≈ 2 n/ 2 . Другими словами, ко- гда будет зашифровано около 2 n/ 2 блоков текста, можно ожидать появления двух одинаковых блоков шифрованного текста 2 . Если размер блока равен 128 бит, ожидать первого повторения блока шифрованного текста можно, за- шифровав около 2 64 блоков. Это и есть парадокс задачи о днях рождения, о котором идет речь в разделе 3.6.6. На сегодняшний момент 2 64 блоков — это большое количество данных, однако не забывайте, что мы разрабаты- ваем системы с расчетом на 30 лет службы. Возможно, в будущем кому-то понадобится шифровать сообщения и такой длины. Меньшие объемы данных тоже подвергаются риску. Если обработать 2 40 блоков текста (около 16 Тбайт данных), вероятность коллизии блоков шиф- рованного текста будет равна 2 − 48 . Это действительно очень малая вероят- ность, но давайте посмотрим на нее с точки зрения злоумышленника. Для конкретного ключа шифрования он собирает 2 40 блоков шифрованного тек- ста и проверяет, нет ли среди них повторений. Поскольку вероятность найти 2 В действительности количество блоков, которые следует зашифровать прежде, чем ожидать первого повторения, близко к √ π 2 n − 1 = 2 n/ 2 p π/ 2 , однако доказательство этого факта достаточно громоздко, а в нашей ситуации такой уровень точности не нужен. |