Для решения разнообразных криптографических задач блочные шифры используют в нескольких режимах работы. Рассмотрим этот вопрос на примере шифра DES.
Алгоритм DES может использоваться в следующих четырех режимах:
· режим электронной кодовой книги (ЕСВ – Electronic Code Book);
· режим сцепления блоков (СВС – Cipher Block Chaining);
· режим обратной связи по шифртексту (CFB – Cipher Feed Back);
· режим обратной связи по выходу (OFB – Output Feed Back).
Режим электронной кодовой книги (ЕСВ) отвечает обычному использованию DES как блочного шифра, осуществляющего некоторую простую замену блоков открытого текста. В режиме сцепления блоков (СВС) каждый блок Сi, i ³ 1, шифртекста перед очередным зашифрованием складывается по модулю 2 со следующим блоком открытого текста Мi+1. При этом вектор С0 полагается равным начальному вектору IV (Initial Vector). Начальный вектор меняется ежедневно и хранится в секрете.
В режимах СFB и OFB алгоритм DES функционирует по аналогии с «шифром Вернама», в режиме OFB – как синхронный шифр, в режиме СFB – как шифр с самосинхронизацией.
Кроме перечисленных режимов, DES имеет также "режим т-битовой обратной связи". Этот режим оперирует с т-битовыми блоками.
Указанные режимы имеют свои достоинства и недостатки. Основное достоинство режима ЕСВ – простота реализации. Недостаток – в возможности проведения криптоанализа «со словарем». Дело в том, что вследствие большой избыточности в открытом тексте вполне возможны повторения 64-битовых блоков. Это приводит к тому, что одинаковые блоки открытого текста будут представлены идентичными блоками шифртекста, что дает криптоаналитику возможность при наличии достаточно большого числа пар открытого и шифрованного текста восстанавливать с большой вероятностью блоки отрытого текста по шифртексту.
В режимах ЕСВ и OFB искажение при передаче одного 64-битого блока шифртекста Сi приводит к искажению после расшифрования соответствующего блока Мi открытого текста, но не влияет на следующие блоки. Это свойство используется для шифрования информации, предназначенной для передачи по каналам связи с большим числом искажений. Вместе с тем при использовании режима OFB остается открытым вопрос о периоде получаемой выходной гаммы, который в некоторых предположениях может составлять величину порядка 232.
В режимах СВС и СРВ искажение при передаче одного блока шифртекста Сi приводит к искажению на приеме не более двух блоков открытого текста – Мi, Мi+1. В то же время изменение блока Мi приводит к тому, что Сi, и все последующие блоки шифртекста будут искажены. Это свойство оказывается полезным для целей аутентификации. Такие режимы применяются для выработки кода аутентификации сообщения.
Так, в режиме СВС берется вектор инициализации, состоящий из одних нулей. Затем с помощью ключа k вырабатываются блоки С1,...,Сn шифртекста. Кодом аутентификации сообщения (КАС) служит блок Сn .
Если требуется обеспечить лишь целостность сообщении, отправитель передает блоки М1,...,Мnвместе с Сn. Tогда противнику, желающему изменить сообщение, нужно соответствующим образом изменить и блок Сn . Возможность этого маловероятна, если только противник не располагает секретным ключом k.
Если же нужно обеспечить шифрование и аутентификацию, то отправитель сначала использует ключ k1для выработки КАС, затем шифрует последовательность блоков M1,...,Mn, Мn+1 = КАС на втором ключе k2, и получает последовательность блоков С1,...,Сn,Сn+1. Получатель должен сначала расшифровать С1,...,Сn,Сn+1 на ключе k2, а затем проверить (с помощью k), что Мn+1 — это КАС для M1,...,Mn.
Можно поступить и иначе: сначала использовать k для зашифрования M1,...,Mn, получая С1,...,Сn, а затем k2 для получения КАС. Получатель же будет использовать k2для проверки КАС, а затем k — для расшифрования С1,...,Сn.
Во всех перечисленных режимах вместо алгоритма DЕS может быть использован любой алгоритм блочного шифрования, в частности российский стандарт ГОСТ 28147-89.
В российском стандарте также предусмотрено несколько режимом использования: режим простой замены, режим шифрования с обратной связью и режим гаммирования с обратной связью, которые являются аналогами соответственно режимов ЕСВ, СВС и СFВ. Для того чтобы избавиться от указанной выше проблемы неопределенности длины периода гаммы в режиме OFB, в российском стандарте введен режим гаммирования, при котором блочный шифр используется в качестве узла усложнения некоторой последовательности гарантированного периода. Для выработки этой последовательности обычно применяются линейные регистры сдвига или счетчики по некоторому модулю.
Уравнение шифрования имеет вид
Сi=МiÅF(gi), i=1,2,...,
где F – преобразование, осуществляемое блочным шифром, gi – блоки, сформированные узлом выработки исходной гаммы из начального вектора g1, который передается в начале сообщения в открытом или зашифрованном виде.
Ошибка при передаче, состоящая в искажении символа, приводит при расшифровании к искажению только одного блока, поэтому сохраняются все преимущества шифра гаммирования.
Как было указано выше, алгоритм шифрования DES сегодня уже не является достаточно стойким. Возникает естественный вопрос: нельзя ли использовать его в качестве строительного блока для создания другого алгоритма с более длинным ключом? Уже в 80-х годах была предложена идея многократного шифрования, т.е. использования блочного алгоритма несколько раз с разными ключами для шифрования одного и того же блока открытого текста.
Рассмотрим двукратное шифрование блока открытого текста с помощью двух разных ключей. В этом случае сначала шифруют блок М ключом k1, а затем получившийся шифртекст Еk1(М) шифруют ключом k2. В результате двукратного шифрования получают криптограмму
С = Еk2(Еk1(М)).
Если множество преобразований, реализуемых блочным шифром, является группой (относительно операции композиции преобразований), то всегда найдется такой ключ k, что С = Еk(М). В таком случае двукратное шифрование не дает преимущества по сравнению с однократным шифрованием. В противном случае после двукратного шифрования нужно будет определять оба использованных ключа. Следовательно, трудоемкость перебора ключей по сравнению с однократным шифрованием возводится в квадрат.
Известно, что множество преобразований, реализуемых полной схемой DES, не образует группу. Там же показано, что множество преобразований DES порождает группу подстановок (степени 264), мощность которой превышает число 102499. Поэтому многократное шифрование с помощью DES имеет смысл.
Возможны варианты двойного и тройного шифрования с использованием алгоритма DES. В одном из них предлагается шифровать блок М открытого текста три раза с помощью двух ключей k1 и k2. Уравнение шифрования в этом случае имеет вид С = Еk1(Dk2(Еk1(М))). Введение в такую схему операции расшифрования Dk2 обеспечивает совместимость схемы со схемой однократного использования DES. Для этого достаточно выбрать одинаковые ключи.
При трехкратном шифровании можно применить три различных ключа. Уравнение шифрования в этом случае принимает вид С = Еk3(Dk2(Еk1(М))). При этом возрастает общая длина результирующего ключа и соответственно возрастает стойкость шифра. Следует отметить, что такое возрастание не может быть безграничным, оно происходит до тех пор, пока суммарное число ключей (256-s) не превзойдет общее число преобразований, реализуемых схемой, то есть общее число простых замен, "из которых состоит" данный шифр замены.
6.5. Методы анализа алгоритмов блочного шифрования
Базовым при использовании блочных шифров является режим простой замены. В связи с этим рассмотрим ряд вопросов, связанных с эксплуатацией блочных шифров в этом режиме и влияющих на их криптографическую стойкость. Как отмечалось выше, серьезным недостатком режима простой замены является то, что зашифрование одинаковых блоков исходного текста дает идентичные блоки шифр текста. В результате криптоаналитик лишь на основе шифрованных данных может делать выводы о свойствах исходною текста. Примером таких выводов может служить определение факта рассылки писем с одинаковым содержанием в несколько адресов. Если некоторые блоки открытого текста повторились, то во всех зашифрованных сообщениях, независимо от используемых ключей, на одинаковых местах будут встречаться повторяющиеся блоки шифрованных текстов.
Другой пример – передача ключей в зашифрованном виде по линиям связи. Повторение блоков в одном шифрованном тексте показывает, что часть битов в передаваемом ключе повторились, и что в дальнейшем трудоемкость перебора ключей при их тотальном опробовании может быть сокращена за счет учета повторений.
Показательно, что при случайном выборе блоков открытого текста их повторение является не столь уж редким событием. Напомним известный парадокс "дней рождений", который заключается в том, что если имеется выборка объема, сравнимого с ÖN , из множества из N элементов, то вероятность того, что в ней окажутся два одинаковых элемента, сравнима с 1/2. Этот парадокс показывает, что при случайном выборе блоков открытого текста для получения повтора достаточно взять в среднем порядка ÖN блоков, где N –общее число блоков, которые теоретически могут встретиться в открытом тексте. Применительно к алгоритмам DES и ГОСТ, которые оперируют с двоичными векторами длины 64, это означает, что в среднем, уже среди 232 блоков открытого текста, будут встречаться повторяющиеся. Следует отметить, что при шифровании осмысленных текстов на естественных языках повторения будут появляться еще чаще, поскольку в осмысленных текстах в силу используемой лексики и грамматических правил встречаются далеко не вес сочетания букв и знаков алфавита.
К блочным шифрам, используемым в режиме простой замены, могут быть применены и некоторые методы анализа шифров простой замены в обычных алфавитах. В частности, при достаточно большой длине шифртекста можно применять методы анализа, использующие статистические характеристики открытых текстов. Например, вычисляя частоты появления блоков в шифрованном тексте и проводя опробование часто повторяющихся блоков, начиная с наиболее вероятных сочетаний знаков в открытом тексте, можно составить словарь соответствия между блоками открытого и шифрованного текстов. Далее, развивая текст по смыслу с учетом избыточности открытых текстов, найденные блоки открытого текста можно дополнять соседними блоками. При этом одновременно восстанавливается открытый текст и дополняется словарь соответствия. Этот метод эффективен, когда наблюдается стандартность переписки. Например, всегда стандартны заголовки деловых бумаг, юридических и прочих документов.
Еще одна слабость блочных шифров в режиме простой замены при шифровании осмысленных текстов связана с тем фактом, что в открытом тексте могут появляться не все сочетания знаков, что проявляется в фактическом сокращении числа пользуемых соответствий между блоками открытого и шифрованного текстов. Однако эта слабость легко устранима, если перед шифрованием применить к открытому тексту процедуру сжатия информации, например, использовать стандартные алгоритмы архивации данных.
Следующим моментом, на который следует обратить внимание, является проблема последнего неполного блока данных при шифровании текстов, длины которых не кратны размеру блока. При использовании блочного шифра этот неполный блок должен быть каким-либо образом дополнен до стандартной длины. Если при этом алгоритм дополнения выбран неудачно, например, блок дополняется одними нулями, то при определении соответствующего блока открытого текста у криптоаналитика появляются дополнительные возможности. Эта проблема может показаться надуманной, поскольку относится только к последнему блоку сообщения. Однако именно в конце сообщения обычно ставится подпись и, следовательно, появляются подходы к определению по шифртексту авторства сообщения.
Отдельно остановимся на методах анализа криптографических алгоритмов, основанных на принципе многократного использования блочных шифров. Р.Меркль и М.Хеллмнп на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.
Рассмотрим метод вскрытия блочного шифра при использовании двойного шифрования в общем случае.
Предположим, что известны блок М открытого текста и соответствующий ему блок С шифрованного текста. Алгоритм вскрытия неизвестных ключей k1 и k2 состоит из двух этапов.
На первом этапе перебираются все возможные варианты ключа k1. Для каждого варианта k ключа k1 вычисляются значения ADR(k) =Еk(М), после чего значения k помещаются в память по адресу ADR(k).
На втором этапе опробуются возможные варианты ключа k2. Для опробуемого варианта k' ключа k2 вычисляются значения ADR(k') = Dk’(C) и производится обращение в память по адресу ADR(k'). Если по этому адресу памяти записи отсутствуют, то происходит переход к опробованию следующего варианта k' ключа k2. Если же по адресу ADR(k') в памяти хранится ключ k, то образуется допустимая пара ключей (k,k'), удовлетворяющая равенству С=Еk’(Еk(М)).
Заметим, что в ячейку памяти с номером ADR(k') могут попасть несколько вариантов ключа k (для этого память необходимо соответствующим образом организовать). Для каждого из них пара (k,k') является допустимым ключом. Несложно заметить, что для реализации данного алгоритма требуется 2½К½ опробований и столько же операций обращения к памяти, где ½К½ — общее число ключей шифра. Таким образом, вместо ½К½2 операций, требуемых при полном переборе ключей, затраты метода встречи посередине составляют порядка 4½К½ операций (операции опробования и обращения к памяти для простоты считают приблизительно равносильными по сложности). Заметим, что такой резкий эффект снижения трудоемкости достигается за счет использовании большой (и специальным образом организованной) памяти.
В заключение отметим, что помимо перебора ключей и метода встречи посередине, при исследованиях блочных шифров успешно применяются методы линейного и дифференциального анализа.
Идея метода линейного анализа состоит в линеаризации уравнений шифрования, то есть замене сложных преобразований, описывающих алгоритм шифрования, их приближениями в классе линейных функций. Под приближением в классе линейных функций (или линейным аналогом) понимается линейная функция, значения которой для достаточно большого числа наборов аргументов совпадают со значениями данной функции шифрования. Чем выше вероятность совпадения значений линейного аналога со значениями функции шифрования при случайном и равновероятном выборе аргументов, тем лучше качество аналога.
Таким образом, линейный анализ сводит задачу определения ключей к решению системы линейных уравнений, в которой правые части уравнений известны с некоторой вероятностью. Из общих принципов математической статистики вытекает, что если распределение значений правых частей уравнений системы отлично от равномерного распределения и имеется достаточно большое число уравнений, то решение такой системы линейных уравнений может быть найдено статистическими методами.
Блочные шифры строятся, как правило, по итеративному принципу. Поэтому даже использование на каждой итерации функций, не имеющих хороших аналогов, не гарантирует отсутствия аналогов в результирующем преобразовании. Проблема построения блочных шифров, для которых удается доказать отсутствие линейных аналогов, является весьма сложной задачей современной прикладной криптографии.
Методы дифференциального (или иначе, разностного) анализа строятся в предположении, что криптоаналитик имеет для анализа несколько текстов, зашифрованных на одном ключе, и дополнительно предполагается известной информация о том, как различаются между собой открытые тексты (при этом сами открытые тексты могут быть неизвестны). В этом случае криптоаналитик получает информацию о том, как заданные отличия в открытых текстах проявляются в шифртекстах, или, другими словами, как разность аргументов шифрующего преобразования отражается на изменении его значений. Поскольку шифрующее преобразование однозначно определяется ключом, то информация о зависимостях между разностями значений аргументов и разностями соответствующих значений функции шифрования может быть использована при построении алгебраических и статистическим методов вскрытия ключей алгоритма шифрования.
Заметим, что аналогичная ситуация возникает в случае, когда криптоаналитику удается получить результат зашифрования некоторого сообщения на разных ключах с дополнительной информацией о различиях использованных ключей. В ряде работ некоторые разновидности такого подхода, получившие общее название метода дифференциальных искажений, применялись для вскрытия ключей криптографических алгоритмов, использовавшихся для защиты информации в платежных системах на основе интеллектуальных карт.
6.6. Рекомендации по использованию алгоритмов блочного шифрования
При практическом использовании блочных шифров, помимо чисто криптографических проблем, необходимо учитывать особенности конкретной системы криптографической защиты информации, ее функции и условия эксплуатации. Эти факторы определяют выбор режима шифрования и условий, в которых необходимо оценивать надежность построенной системы защиты.
Основными достоинствами режима простой замены являются простота реализации и тот факт, что изменения одного блока шифртекста вызывают изменения только в одном блоке открытого текста. К недостаткам этого режима, помимо упомянутыx выше, можно отнести также неустойчивость системы защиты перед модификацией сообщения, заключающуюся в перестановке блоков шифртекста. Такое нарушение целостности данных может оказаться незамеченным, поскольку при расшифровании каждого блока будет получен осмысленный результат. В особенности это замечание касается передачи формализованных сообщений.
Вследствие отмеченных недостатков блочные шифры редко используются в режиме простой замены для шифрования длинных сообщений. Режим простой замены применяется в основном в системах передачи ключей и в платежных системах, где сообщения состоят из небольшого числа блоков и, следовательно, вероятность шифрования двух одинаковых блоков открытого текста на одном ключе очень мала.
Для практического использования блочных шифров можно предложить модификацию режима простой замены, заключающуюся в замене части битов блоков открытого текста их порядковыми номерами в сообщении. Такой подход несколько снижает скорость передачи информации, поскольку часть блока перестает нести содержательную информации». Но, с другой стороны, при такой модификации одинаковые блоки открытого текста вследствие различия их порядковых номеров будут представлены различными блоками шифрованного текста.
К достоинствам режима гаммирования следует отнести решение проблемы повторений, возникающих при зашифровании одинаковых блоков сообщения, поскольку в режиме гаммирования одинаковые блоки открытого текста преобразуются в различные блоки шифртекста. Снимается также вопрос о способе дополнения последнего неполного блока данных, так как лишние биты гаммы просто отбрасываются. Перестановка блоков шифртекста также будет обнаружена при расшифровании. Свойство нераспространения ошибок является более выраженным: искажение при передаче одного бита блока приводит при расшифровании в режиме простой замены к искажению всего блока, а в режиме гаммирования - к искажению всего лишь одного бита.
Однако оборотная сторона эффекта нераспространения искажений состоит в том, что появляется возможность целенаправленной модификации шифртекста и открытого текста с точностью до конкретного разряда. Кроме того, необходимо обеспечить уникальность гаммы, что требует для всех сообщений уникальных синхропосылок (иначе возможны повторения используемой гаммы).
Чаще блочные шифры используются в режиме шифрования с обратной связью, когда очередной блок шифртекста зависит не только от ключа, но и от предшествующих блоков шифртекста. Гаммирование с обратной связью устойчиво к перестановкам блоков шифрованного текста и к целенаправленным модификациям шифртекста. В таких системах отсутствует проблема последнего неполного блока данных и одновременно снимается острота проблемы обеспечения уникальности синхропосылки.
Контрольные вопросы
1. Каковы с точки зрения криптографии преимущества и недостатки перехода к шифрованию сообщений в алфавитах большой мощности?
2. Как реализуется предложенный К.Шенноном принцип "перемешивания" при практической реализации алгоритмов блочного шифрования?
3. Каковы основные недостатки алгоритма DES и путиих устранения?
4. Как связан "парадокс дней рождений" с криптографическими качествами блочных шифров в режиме простой замены
5. В каких случаях можно рекомендовать использовать блочный шифр в режиме простой замены?
6. От каких потенциальных слабостей позволяет избавиться использование блочных шифров в режимах шифрования с обратной связью?
