В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 4. Блочные шифры к типу атак с избранным открытым текстом. В разделе 3.6 рассматриваются основные типы атак. Все они применимы и к блочным шифрам. Существует также несколько типов атак, специфичных для блочных шифров. Один из этих типов атак называется атакой со связанным ключом (related- key attack) . Впервые представленная Эли Бихемом в 1993 году [7], атака со связанным ключом предполагает, что злоумышленник имеет доступ к не- скольким функциям шифрования. Все они работают с неизвестными ключа- ми, однако эти ключи связаны определенным отношением, которое известно злоумышленнику. На первый взгляд такая атака выглядит несколько стран- но, однако, как оказалось, она дает весьма неплохие результаты по отноше- нию к реальным системам. Существует множество реальных систем, кото- рые используют разные ключи, связанные известным отношением. В одной закрытой системе для каждого нового сообщения предыдущее значение клю- ча увеличивалось на единицу. Таким образом, сообщения, идущие друг за другом, шифровались с помощью последовательных значений ключей. Ока- зывается, что подобные соотношения между ключами могут использоваться для атак на блочные шифры. Существуют еще более экзотические типы атак. Команда разработчиков блочного шифра Twofish представила концепцию атаки с избранным ключом (chosen key attack) , в которой злоумышленник задает часть ключа и затем выполняет атаку со связанным ключом на оставшуюся часть ключа [85] 1 . Зачем обращать внимание на какие-то неправдоподобные типы атак, та- кие, как атаки со связанным ключом или с избранным ключом? На это есть ряд причин. В своей практике мы видели реальные системы, которые вполне могли подвергнуться атаке со связанным ключом, поэтому данный тип атак вообще нельзя назвать неправдоподобным. Блочные шифры доволь- но часто используются в криптографических системах и потому подвергают- ся всем мыслимым и немыслимым нападениям. Одним из стандартных прие- мов построения функции хэширования для блочного шифра является метод Дэвиса–Мейера [95]. Оказалось, что при использовании функции хэширова- ния Дэвиса–Мейера злоумышленник получает возможность выбирать ключ блочного шифра, что позволяет ему осуществлять атаки со связанным клю- чом и с избранным ключом. Любое определение безопасности блочного шиф- ра, которое не учитывает эти или любые другие типы атак, является непол- ным. Блочный шифр — это модуль, который должен иметь простой интер- фейс. Наиболее простым этот интерфейс будет в том случае, если он включа- ет в себя все свойства, которые кто-либо может ожидать от блочного шифра. 1 Дальнейшие исследования показали, что этот тип атаки не позволяет взломать Twofish [31], однако может оказаться успешным при нападении на другие блочные шифры. 4.3. Идеальный блочный шифр 65 Наличие некоторого несовершенства блочного шифра лишь усложняет ис- пользующую его систему многочисленными перекрестными зависимостями. 4.3 Идеальный блочный шифр Чтобы определить безопасность блочного шифра, необходимо вначале дать определение идеальному блочному шифру. Как должен выглядеть иде- альный блочный шифр? Очевидно, это должна быть случайная перестанов- ка вариантов открытого текста. Немного уточним: для каждого значения ключа блочный шифр должен представлять собой случайную перестановку вариантов открытого текста, причем перестановки для различных вариан- тов ключа должны выбираться независимо друг от друга. Как уже отмеча- лось, 128-битовый блочный шифр (одна перестановка 128-битовых значений) можно представить себе в виде большой таблицы соответствий, содержащей 2 128 элементов по 128 бит в каждом. В идеальном блочном шифре каждому значению ключа соответствует одна из таких таблиц, причем она выбирается случайным образом из набора всех возможных таблиц (т.е. всех возможных перестановок). С формальной точки зрения, данное определение идеального блочного шифра является неполным, поскольку оно не задает соответствия таблиц раз- личным значениям ключей. С другой стороны, как только будет задано соот- ветствие таблиц, идеальный блочный шифр станет фиксированным и больше не будет случайным. Чтобы формализовать это определение, мы не можем говорить об одном конкретном идеальном шифре. Мы должны рассмотреть идеальный шифр как равномерное вероятностное распределение на множе- стве всех возможных блочных шифров. Имея дело с идеальным блочным шифром, необходимо размышлять в терминах вероятностей. Это приводит в восторг математиков, однако существенно усложняет и без того непростые объяснения. Поэтому будем придерживаться неформальной, но в то же время более простой концепции случайно выбранного блочного шифра. 4.4 Определение безопасности блочного шифра В литературе дано множество определений безопасности блочного шиф- ра (например, [52]). Большинство этих определений сформулированы с ма- тематической точки зрения, и ни одно из них не отражает аспектов, кото- рые затронутых в предыдущих разделах. Мы же предпочитаем простое, хотя и неформальное определение. Определение 1 Безопасный блочный шифр — это шифр, для которого не существует атак. |