книги / Практическая криптография

равным 0, для второго — 1 и т.д. Но это не совсем удачная идея. Как уже от­ мечалось, в реальной жизни многие сообщения начинаются примерно одина­ ково. Если первые блоки сообщений будут иметь простые отличия, использо­ вание в качестве вектора инициализации простого счетчика может нейтрали­ зовать эти различия с помощью операции XOR и вновь привести к генерации одинаковых блоков шифрованного текста. В частности, значения 0 и 1 отли­ чаются друг от друга ровно одним битом. Если начальные блоки открытого текста первых двух сообщений будут различаться только этим битом (что происходит гораздо чаще, чем можно было ожидать), то начальные блоки шифрованного текста обоих сообщений будут одинаковы. В этом случае зло­ умышленник сможет сразу же сделать определенные выводы относительно различий между сообщениями, чего никогда не должна допускать безопасная схема шифрования.

5.3.3Случайный вектор инициализации

Все проблемы с режимом ЕСВ, а также с использованием фиксированных векторов инициализации или счетчиков в режиме СВС связаны с тем, что ре­ альные сообщения обладают высокой степенью неслучайности. Большинство сообщений имеют фиксированный заголовок или стандартную, легко пред­ сказуемую структуру. В режиме СВС для внесения "элемента случайности”

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

Применение случайного вектора инициализации связано с определенной проблемой. Получатель сообщения должен знать значение вектора инициа­ лизации. Обычно для этого выбирают случайное значение IV и посылают его

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

Со := случайное значение блока,

С{ := Е(К, Pi ф C j-i) для г = 1 ,..., к

при условии, что (дополненный) открытый текст P i,..., Р* преобразуется в шифрованный текст С о,.. . , С&. Обратите внимание, что шифрованный текст начинается с блока Со, а не Си шифрованный текст на один блок длиннее, чем открытый. Из приведенных выше формул легко вывести соответствую­ щую процедуру дешифрования:

Pi := D (K ,C i) ФС,_1 для i = l,...,fc .

Использование случайного вектора инициализации имеет два недостат­ ка. Прежде всего алгоритм шифрования должен иметь доступ к источнику

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

5.3.4Оказия

Существует еще одно — и, пожалуй, наилучшее — решение проблемы вы­ бора вектора инициализации. Оно состоит из двух шагов. Вначале каждому сообщению, которое должно быть зашифровано с помощью заданного клю­ ча, присваивается уникальное число, называемое оказией (попсе). Название этого термина происходит от фразы “number used once” — “число, используе­ мое только один раз”. Основным свойством оказии является ее уникальность. Не допускается использовать одну и ту же оказию дважды с одним и тем же ключом. Обычно оказия представляет собой номер сообщения, присвоен­ ный ему по некоторому принципу и, возможно, скомбинированный с какойнибудь другой информацией. Большинство современных систем уже приме­ няют нумерацию сообщений, чтобы сохранять сообщения в правильном по­ рядке, распознавать повторяющиеся сообщения и т.п. Оказию не обязательно сохранять в секрете, но она может быть использована только один раз. Это особенно важно для получателя сообщений, который получает оказию вместе с каждым сообщением и должен убедиться в том, что ее текущее значение не повторяется дважды.

Вектор инициализации, необходимый для шифрования первого блока тек­ ста в режиме СВС, генерируется путем шифрования оказии.

Обычно отправитель последовательно нумерует свои сообщения и пере­ сылает их вместе с соответствующим номером. В этом случае для отправки сообщения выполните приведенную ниже последовательность действий.

1.Присвойте сообщению номер. Обычно для нумерации сообщений ис­ пользуется счетчик, начинающийся с 0. Обратите внимание: значение счетчика никогда не должно вернуться к нулю, так как это нарушит свойство уникальности.

2.Используйте номер сообщения для построения уникальной оказии. Для заданного ключа оказия должна быть уникальной по всей системе, а не только в рамках текущего компьютера. Например, если один и тот же ключ используется для шифрования трафика в двух направлениях, ока­ зия должна представлять собой сочетание номера сообщения и инди­ катора направления, в котором отсылается сообщение. Размер оказии должен быть равен размеру блока используемого блочного шифра.

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

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

5.Добавьте к шифрованному тексту достаточно информации, чтобы по­ лучатель мог воссоздать значение оказии. Обычно для этого к началу шифрованного текста добавляется номер сообщения. Значение самого вектора инициализации (в наших обозначениях это Со) пересылать не нужно.

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

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

5.4Обратная связь по выходу (OFB)

До сих пор все рассмотренные режимы принимали на вход сообщение и шифровали его путем применения блочного шифра к блокам самого сооб­ щения. Режим обрат ной связи по вы ходу (output feedback — O FB) отличается тем, что в качестве входных данных для блочного шифра не используется само сообщение. Вместо этого блочный шифр применяется для генерации псевдослучайного потока байтов (называемого ключевым потоком), который с помощью операции XOR складывается с открытым текстом для получе­ ния шифрованного текста. Схема шифрования, которая генерирует подобный ключевой поток, называется пот очным шифром (stream cipher). Некоторым почему-то кажется, что поточные шифры очень слабы. Ни в коем случае! Они не только весьма полезны, но и работают безотказно. Просто необхо­ димо внимательно к ним относиться. Злоупотребление поточным шифром (как правило, в форме повторного использования оказии) легко нарушает безопасность системы. В этом смысле надежнее использовать режим наподо­ бие СВС — последний даже при повторном использовании оказии остается относительно безопасным. Тем не менее преимущества поточных шифров за­ частую перевешивают их недостатки.

94 Глава 5. Режимы работы блочных шифров

Схема шифрования в режиме OFB определяется следующим образом:

KQ := IV

К{ := Е (К ,1 Ь -1) для г = 1 ,..., fc,

C i P i Ф К{.

Как видите, здесь также фигурирует вектор инициализации Ко, который применяется для генерации ключевого потока K \ ,...,K k путем постоянного шифрования предыдущего значения К{. Затем ключевой поток с помощью операции XOR складывается с открытым текстом сообщения для получения шифрованного текста.

Значение вектора инициализации должно быть случайным. Как и в ре­ жиме СВС, оно может быть выбрано случайным образом и передано вместе с самим шифрованным текстом (см. раздел 5.3.3) или же сгенерировано на основе оказии (см. раздел 5.3.4).

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

Второе преимущество режима OFB — отсутствие необходимости в допол­ нении. Поскольку ключевой поток может быть представлен в виде беско­ нечной последовательности байтов, мы можем использовать столько байтов, сколько содержит наше сообщение. Другими словами, если последний блок открытого текста неполный, мы посылаем только те байты шифрованного текста, которые соответствуют реальным байтам открытого текста. Отсут­ ствие дополнения сокращает расходы на пересылку, что особенно важно для большого количества коротких сообщений.

Помимо этого, режим OFB наглядно демонстрирует одну из проблем ис­ пользования поточных шифров. Если вы когда-нибудь используете один и тот же вектор инициализации для двух разных сообщений, последние будут за­ шифрованы с помощью одного и того же ключевого потока. Это очень и очень плохо. Предположим, что два открытых текста Р и Р' были зашифрованы с помощью одного и того же ключевого потока. Обозначим полученные шиф­ рованные тексты как С к С' соответственно. Получив в свое распоряжение шифрованные тексты, злоумышленник сможет подсчитать значение выра­ жения Ci ф С[ = Pi ф Ki ф Р( ф Ki = Р{ ф Р(. Другими словами, он сможет определить различие между двумя открытыми текстами. Предположим, что злоумышленник уже знает один из открытых текстов. (В реальной жизни это случается сплошь и рядом.) Тогда задача вычисления второго открытого текста становится тривиальной. Существует даже несколько атак, которые

восстанавливают информацию о двух неизвестных открытых текстах исходя из различия между ними [44].

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

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

5.5 Счетчик (CTR)

Наш любимый режим шифрования с использованием блочных шифров носит название счетчика (counter — CTR). Хотя данный режим известен уже напротяжении многих лет, он не был стандартизирован как официальный ре­ жим работы шифра DES [68], а потому игнорируется авторами большинства учебников по криптографии. Недавно режим CTR был стандартизирован ор­ ганизацией NIST [26]. Как и OFB, режим счетчика основан на применении поточного шифра. Он определяется следующим образом:

Ki := E(K,Nonce\\i) дляг = l,..,,fe,

С{ := Pi ф Ki.

Как и в любом другом поточном шифре, в режиме CTR следует исполь­ зовать оказию того или иного вида (в формуле она обозначена как Nonce). Большинство систем образуют значение оказии на основе номера сообщения и некоторых дополнительных данных, чтобы гарантировать ее уникальность.

но простой метод. Он состоит в конкатенации значения оказии со значением счетчика и в последующем шифровании полученного значения для формиро­ вания одного блока ключевого потока. Данный метод требует, чтобы оказия и счетчик в совокупности умещались в рамки одного блока, однако в со­ временных шифрах со 128-битовыми блоками это не составляет проблемы. Очевидно, размер оказии должен быть меньше размера одного блока, чтобы оставить место для значения счетчика i. Типичный 128-битовый блок может состоять из 48-битового номера сообщения, 16 бит дополнительной информа­ ции, входящей в оказию, а также 64 бит для счетчика г. Такая конструкция позволяет зашифровать с помощью одного ключа не более 248 сообщений, а также ограничивает размер каждого сообщения до 268 байт.

Как и в режиме OFB, в режиме счетчика необходимо гарантировать, что каждая конкретная комбинация “ключ-оказия” никогда не будет использова­ на во второй раз. Данное требование принято относить к недостаткам режима CTR, однако оно же свойственно и режиму СВС. Если один и тот же вектор инициализации будет использован дважды, это приведет к утечке информа­ ции об открытых текстах. В этом плане режим СВС несколько надежнее, так как он с большей вероятностью ограничивает объем данных, которые может получить злоумышленник. Тем не менее, любая утечка информации нарушает требования к безопасности, а при использовании модульной архи­ тектуры нельзя рассчитывать на то, что остальные части системы ограничат размер ущерба, даже если объем утечки весьма невелик. Таким образом, при использовании и СВС и CTR необходимо гарантировать, что оказия или век­ тор инициализации являются уникальными.

За исключением описанных факторов, режим CTR очень прост в ис­ пользовании. Требуется только реализовать функцию шифрования блочного шифра, поскольку функции шифрования и дешифрования CTR одинаковы. Режим CTR позволяет легко осуществлять доступ к произвольным частям открытого текста, поскольку любой блок ключевого потока может быть под­ считан мгновенно, независимо от других блоков. В высокоскоростных при­ ложениях вычисление блоков ключевого потока может выполняться с любой степенью параллелизма. Более того, безопасность режима CTR тривиаль­ ным образом связана с безопасностью блочного шифра. Любое слабое место режима CTR позволяет моментально осуществить атаку с избранным откры­ тым текстом на соответствующий блочный шифр. Из этого следует и обрат­ ное утверждение: если не существует атак на блочный шифр, не существует и атак на режим CTR (кроме утечки информации, о которой вскоре пой­ дет речь).

5.6 Новые режимы

Все рассмотренные режимы работы блочных шифров появились в 70-х либо начале 80-х годов прошлого века. В последние годы криптографическо­ му сообществу было предложено еще несколько новых режимов. Наиболее известным из них, пожалуй, является режим шифровальной книги со сдви­ гом (offset codebook)t или ОСВ [82, 83]. Этот и другие новые режимы сочетают в себе как шифрование, так и аутентификацию. Хотя данные режимы очень привлекательны, мы не можем рекомендовать их по двум причинам.

Во-первых, эти режимы еще слишком новы, а ко всему новому в крип­ тографии относятся с подозрением. Большинство новых режимов, включая и ОСВ, обладают доказательствами своей безопасности. Однако доверять этим доказательствам можно не больше чем любому другому продукту чело­ веческих рук. В доказательствах безопасности уже не раз встречались ошиб­ ки. Они будут встречаться и в будущем. Зачастую подобные доказательства очень сложны, и думать, что они не содержат ошибок, могут только самые закоренелые оптимисты. (Мы еще никогда не видели попыток доказать пра­ вильность самих доказательств.)

В действительности доказательство безопасности отнюдь не доказывает, что система является безопасной. Оно обеспечивает лишь приведение безопас­ ности (security reduction) режима работы блочного шифра к безопасности самого блочного шифра. Доказательство может, например, утверждать, что если шифрование в режиме ОСВ можно взломать за время X, то соответ­ ствующий блочный шифр может быть взломан за время У. Это очень цен­ ный результат, который хорошо укладывается в нашу концепцию модульного дизайна криптографических систем. Тем не менее он доказывает лишь без­ опасность блочного шифра, а не безопасность шифрования с использованием режима работы блочного шифра. В этом нет ничего плохого: гораздо лучше иметь такое доказательство безопасности, чем не иметь его вообще, однако оно не является абсолютным доказательством, как нам зачастую пытаются внушить.

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

5.7Какой режим выбрать

Итак, мы рассмотрели несколько режимов работы блочных шифров. Од­ нако для практического использования стоит рекомендовать лишь два из них: СВС и CTR. Как уже отмечалось, режим ЕСВ недостаточно безопасен. Режим OFB неплох, однако в определенных аспектах уступает режиму CTR, который к тому же лишен проблемы циклических повторений ключевых бло­ ков. Поэтому отдавать предпочтение OFB, а не CTR нет смысла.

Так какой же режим выбрать — СВС или CTR? Давайте проведем неболь­ шое сравнение.

•Дополнение. Режим СВС требует дополнения сообщений, a CTR — нет.

•Скорость. Оба режима предполагают один и тот же объем вычисле­ ний. Тем не менее режим CTR допускает параллельный подсчет любого количества ключевых блоков, в результате чего реализации CTR могут достигать более высоких скоростей.

•Реализация. Работая в режиме CTR, достаточно реализовать только функцию шифрования блочного шифра. Режиму СВС требуются обе функции — шифрования и дешифрования.

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

•Оказия. В режиме СВС можно использовать случайный вектор ини­ циализации или оказию. В режиме CTR для генерации ключевых бло­ ков требуется уникальная оказия. На практике, однако, в режиме СВС практически всегда используют оказию, поэтому в данном аспекте ре­ жимы СВС и CTR можно считать эквивалентными.

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

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

которого обеспечивается другими частями системы. Разве мы не противоре­ чим сами себе? И да и нет. В идеале было бы предпочтительнее использовать режим работы блочного шифра, который не зависит от остальных частей си­ стемы. К сожалению, ни один из рассмотренных режимов такими свойствами не обладает. Все они в той или иной степени зависят от остальных частей си­ стемы. Это легко объяснить. Режим работы блочного шифра не является ни завершенной системой шифрования, ни независимым структурным модулем. Блочный шифр — это модуль, который при необходимости можно заменить другим подходящим блочным шифром. Режим работы блочного шифра — это всего лишь метод, который используется в модуле следующего уровня, а именно модуле шифрования и аутентификации сообщения (он рассматри­ вается в главе 8, “Безопасный канал общения”). Поскольку режим работы блочного шифра не является отдельным модулем, мы не можем гарантиро­ вать его безопасность независимо от других частей системы.

Не забывайте, что режим работы блочного шифра обеспечивает только конфиденциальность. Другими словами, злоумышленник не может получить никакой информации о данных, которыми вы обмениваетесь с собеседником, кроме информации о том, что вы обмениваетесь данными, а также когда, в каком объеме и с кем вы обмениваетесь данными1. Шифрование данных ни в коей мере не помешает злоумышленнику изменить эти данные.

5.8 Утечка информации

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

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

Начнем с режима ЕСВ. Если для блоков открытого текста Р{ и Pj выпол­ няется равенство Pi = Pj, тогда для соответствующих блоков шифрованного текста справедливо С{ — Cj. Случайные блоки открытого текста редко бы­ вают равны друг другу, однако на практике открытый текст не является*

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

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

А что же режим СВС? В этом случае одинаковые блоки открытого тек­ ста не будут преобразованы в одинаковые блоки шифрованного текста, по­ скольку перед шифрованием каждый блок открытого текста складывается с помощью операции XOR с предыдущим блоком шифрованного текста. Все блоки шифрованного текста можно представить себе в виде случайных зна­ чений; в конце концов, они были получены посредством блочного шифра, генерирующего случайные выходные данные по заданным входным данным. Но что, если у нас окажется два одинаковых блока шифрованного текста? Рассмотрим следующее равенство:

Ci = Ch

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

Аналогичная ситуация случается и тогда, когда два блока шифрованно­ го текста не равны друг другу. Зная, что С{ ф Cj, получаем, что Р{ © Pj ф Ci—1ф Cj—i, поэтому неравенство блоков шифрованного текста означает нера­ венство блоков открытого текста.

Подобными свойствами обладает и режим CTR. Известно, что все блоки Ki неодинаковы, так как получены путем применения шифрования к конкате­ нации значений оказии и счетчика. Поскольку все значения такого открытого текста будут разными, значения шифрованного текста (которые формируют ключевые блоки) тоже будут разными. Для двух любых блоков шифрован­ ного текста Q и Cj можно сказать, что Pi®Pj ф C iQCj, так как в противном случае два ключевых блока были бы одинаковыми. Другими словами, режим CTR обеспечивает неравенство открытого текста для каждой пары блоков шифрованного текста.