Режимы шифрования (начало)

🕛 02.04.2009, 13:15

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

Итак, предположим, что в нашем распоряжении имеется симметричный блочный шифр, содержащий два зависящих от ключа K преобразования за- и расшифрования N-битовых блоков, EK и DK соответственно. Простейший способ использовать эти преобразования - разбить шифруемый массив T на N-битовые блоки и шифровать их независимо друг от друга:

T = (T1,T2,...,Tn),
T'i = EK(Ti),
T' = (T'1,T'2,..., T'n),
где |T'i| = |Ti| = N.

Этот режим шифрования, то есть способ использования криптографического преобразования для шифрования данных, в отечественной литературе и части зарубежных источников называется режимом простой замены, в другой части зарубежных источников, тяготеющей к англосаксонской криптографической терминологии, он называется режимом электронной кодовой книги (Electronic Code Book, сокращенно ECB). Использование данного простейшего режима шифрования сопряжено с рядом трудностей. Первая, чисто техническая трудность называется проблемой последнего блока и заключается в том, что размер шифруемого текста может быть не кратен размеру блока используемого шифра. В этом случае последний блок будет неполным (|Tn| < N), и его необходимо как-либо дополнить до размера в N бит, так как криптографическому преобразованию может быть подвергнут только блок полного размера. При этом все полученные биты блока шифротекста будут значащими, их нельзя отбрасывать без потери информации, что приводит к увеличению размера шифротекста по сравнению с открытым текстом, а это не во всех случаях допустимо.

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

Ti = Tj -> EK(Ti) = EK(Tj).

Обратное также верно: если два блока шифротекста совпадают, то соответствующие им блоки открытого текста идентичны:

EK(Ti) = EK(Tj) ->Ti = Tj.

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

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

T'i = F(T1,T2,...,Ti,T'1,T'2,...,T'i-1,S).

Понятно, что при вычислении функции F должно использоваться криптографическое преобразование EK и приведенное выше соотношение должно быть разрешимо относительно шифруемого блока Ti, чего требует обратимость процедуры шифрования. Как мы с вами выяснили в предыдущих выпусках, обратимость преобразования в сочетании с его криптостойкостью в ситуациях, когда один блок данных модифицируется с использованием одного или нескольких дополнительных блоков данных легче всего обеспечить за счет применения обратимых бинарных операций. Напомню, что бинарная операция “° ” называется обратимой, если существует обратная ей операция “· ”, такая, что каковы бы не были два блока данных X и Y, составляющие пару допустимых аргументов первой операции, справедливо следующее соотношение:

(X ° Y) · Y = X.

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

В блочных режимах шифруемый блок первоначально модифицируется путем наложения на него с помощью бинарной операции (“° ”) значения функции f, зависящей от всех предыдущих блоков открытого (Ti) и шифрованного (T'i ) текста, и, возможно, от параметра инициализации (S), после чего полученное значение модифицируется с помощью криптографического преобразования (EK ). Таким образом, зашифрование в блочных режимах выполняется в соответствии со следующим уравнением:

T'i = EK(Ti ° f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S)).

Тогда расшифрование в режимах этого типа выполняется по следующему уравнению:

Ti = DK(T'i) · f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S) ,

где через DK обозначена обратная EK процедура расшифрования в режиме простой замены, а через “· ” - бинарная операция, обратная операции “° ”.

В потоковых режимах шифруемый блок модифицируется путем наложения на него с помощью бинарной операции (“° ”) результата криптографического преобразования EK значения функции f , зависящей от всех предыдущих блоков открытого (Ti) и шифрованного (T'i) текста, и, возможно, от параметра инициализации (S). Таким образом, зашифрование в потоковых режимах выполняется в соответствии со следующим уравнением:

T'i = Ti ° EK(f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S)).

Тогда расшифрование в режимах этого типа выполняется по следующему уравнению:

Ti = T'i · EK(f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S)).

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

Fi = f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S) и

Fj = f(T1,T2,...,Tj-1,T'1,T'2,...,T'j-1,S), то

i <> j -> Fi <> Fj.

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

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

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

1.Блочные режимы:
* зашифрование:
T'i = EK(Ti (+) f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S));
* расшифрование:
Ti = DK(Ti) (+) f(T1,T2,...,Ti-1,T'1,T'2,...,Ti-1,S);

2.Потоковые режимы:
* зашифрование:
T'i = Ti (+) EK(f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S));
* расшифрование:
Ti = T'i (+) EK(f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S)).

Теперь сравним оба типа режимов, сравнение начнем с двух фундаментальных фактов, которые, собственно, и определяют их свойства:
1. В блочных режимах зашифрование осуществляется применением криптографического преобразования непосредственно к шифруемому блоку, модифицированному значением рандомизирующей функции f, - в уравнении зашифрования шифруемый блок Ti стоит внутри скобок криптографического преобразования EK(...), тогда как в потоковых режимах зашифрование осуществляется точно так же, как в потоковых шифрах, наложением на шифруемый блок некоторого кода с помощью обратимой бинарной операции, и шифруемый блок Ti не фигурирует в выражении для аргумента преобразования EK. 1. Для расшифрования в блочных режимах применяется криптографическое преобразование DK, обратное преобразованию EK, использованному для зашифрования, тогда как при расшифровании в потоковом режиме используется то же самое преобразование, что и при зашифровании. Из этого следует, вообще говоря, весьма интересный вывод: для построения блочных режимов шифрования необходимо обратимое криптографическое преобразование, тогда как для построения потоковых режимов обратимость используемого криптопреобразования не требуется, достаточно его стойкости. Это, в частности, позволяет реализовать такие режимы на базе вычислительно необратимых функций, например, на базе MD5 и аналогичных алгоритмов.

Из сказанного выше становится понятным, что названия “блочные” и “потоковые” режимы имеет вполне простой и понятный смысл: шифр в блочном режиме ведет себя как обычный блочный шифр: шифрованию могут подвергаться только полные блоки данных. Если шифруемый массив данных содержит нецелое число блоков, это создает для такой схемы определенные трудности - данный вопрос будет подробно рассмотрен ниже. Шифры же в потоковом режиме являются в полном смысле слова потоковыми шифрами, и для них, в частности, отсутствует проблема последнего блока. По своей сути потоковый режим есть не что иное, как способ построения потокового шифра на базе блочного криптографического алгоритма. В этом, собственно, и заключается фундаментальная разница между указанными типами режимов, хотя, на первый взгляд, различия между ними могут показаться незначительными, и их уравнения зашифрования похожи друг на друга:
T'i = EK(Ti (+) Fi) в “блочных” режимах,
T'i = Ti (+) EK(Fi) в “потоковых” режимах,

где Fi = f(T1,T2,...,Ti-1,T'1,T'2,...,T'i-1,S) для обоих типов режимов.

Теперь поговорим о роли параметра инициализации S, называемого в отечественной криптографии синхропосылкой. Дело в том, что при определенных условиях шифрование двух сообщений или массивов данных на одном и том же ключе может привести к катастрофической потере стойкости. Вместе с тем, не всегда технически возможно обеспечить смену ключа перед началом шифрования каждого нового сообщения. Особенно это было актуально для первых систем шифрования, использовавших потоковые шифры и обслуживавших каналы связи с высоким трафиком. Чтобы примирить указанные обстоятельства, в системах обеспечения секретности стали использовать понятие “начального состояния” шифратора. При шифровании одного и того же сообщения дважды на одном и том же ключе, но с различными начальными состояниями шифратора получаются две совершенно различные выходные последовательности. В этом случае шифрование двух сообщений на одном и том же ключе уже не грозит критической потерей стойкости - необходимо лишь обеспечить, чтобы начальные состояния шифратора при этом были различны. Элементом данных, определяющим это начальное состояние, как раз и является синхропосылка. Понятно, что она должна передаваться или храниться вместе с зашифрованными данными и не может быть секретной. Собственно, поэтому она и называется синхропосылкой или синхронизирующей посылкой, то есть посылкой элемента данных, предназначенного для синхронизации шифрующего устройства получателя с шифрующим устройством отправителя.

В блочных режимах шифрование двух различных массивов информации на одном и том же ключе с одним и тем же параметром инициализации S допустимо и не ведет к потере криптографической стойкости. Собственно, по большому счету, в режимах этого типа вполне можно обойтись и вовсе без синхропосылки. Конечно, если при этом два массива данных T = (T1,T2,...,Tn), и V = (V1,V2,...,Vn) дают при зашифровании массивы шифротекста, начальные отрезки которых совпадают, это говорит о том, что соответствующие начальные отрезки исходных массивов также идентичны:

если T'i = V'i для i = 1,2,...,m,

то Ti = Vi для i = 1,2,...,m.

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

T'i = V'i -> Ti = Vi для любого i.

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

T'i = V'j -> Ti = Vj для любых i,j,

и, в частности,

T'i = T'j -> Ti = Tj для любых i,j.

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

В потоковых шифрах то же самое приводит к катастрофической потере стойкости. Предположим, что два массива данных, T = (T1,T2,...,Tn), и V = (V1,V2,...,Vn), зашифрованы в потоковом режиме на одном и том же ключе K с использованием одного и того же параметра инициализации S. Для простоты предположим, что для модификации шифруемых данных используется операция побитового исключающего ИЛИ. Тогда

T'1 = T1 (+) EK(f(S)),

V'1 = V1 (+) EK(f(S)), откуда следует, что

T'1 (+) V'1 = (T1 (+) EK(f(S))) (+) (V1 (+) EK(f(S))) = T1 (+) V1.

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

T'i = V'i для i = 1,2,...,m.

Точно также, как и в случае блочных режимов, это позволяет установить тождественность соответствующих отрезков открытого текста:

Ti = Vi для i = 1,2,...,m.

Однако помимо этого будет также выполняться и приведенное выше соотношение, но сформулированное не для первых блоков, а для первых несовпадающих блоков соответствующих массивов данных:

T'm+1 (+) V'm+1 = Tm+1 (+) Vm+1.

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

T'i = Ti (+) EK(f(i,S)),

V'i = Vi (+) EK(f(i,S)),

откуда следует, что

T'i (+) V'i = Ti (+) Vi

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