А.Винокуров. Серия выпусков по криптографии для электронного журнала "iNFUSED BYTES Online".

Выпуск 7. Режимы шифрования (начало).

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

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

T = (T₁,T₂,...,T_n),
T'_i = E_K(T_i),
T' = (T'₁,T'₂,...,T'_n),
где |T'_i| = |T_i| = N.

Этот режим шифрования, то есть способ использования шифра в отечественной литературе и ряде зарубежных источников называется режимом простой замены, в другой части зарубежных источников, включая нормативные документы США он называется режимом электронной кодовой книги (Electronic Code Book, сокращенно ECB).

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

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

T_i = T_jE_K(T_i) = E_K(T_j).

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

E_K(T_i) = E_K(T_j)T_i = T_j.

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

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

T'_i = f(T₁,T₂,...,T_i,T'₁,T'₂,...,T'_i_-1,S).

Понятно, что при вычислении функции f должно использоваться криптографическое преобразование E_K и приведенное выше соотношение должно быть разрешимо относительно шифруемого блока T_i, чего требует обратимость процедуры шифрования. Как мы с вами выяснили в предыдущих выпусках, обратимость преобразования в сочетании с его криптостойкостью в ситуациях, когда один блок данных модифицируется с использованием одного или нескольких дополнительных блоков данных легче всего обеспечить за счет применения обратимых бинарных операций. Напомню, что бинарная операция "" называется обратимой, если существует обратная ей операция "", такая, что каковы бы не были два блока данных X и Y, составляющие пару допустимых аргументов первой операции, справедливо следующее соотношение:

(XY)Y = X.

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

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

T'_i = E_K(T_if(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S)).

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

T_i = D_K(T'_i)f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S),

где через D_K обозначена обратная E_K процедура расшифрования в режиме простой замены, а через "" - бинарная операция, обратная операции "".

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

T'_i = T_iE_K(f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S)).

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

T_i = T'_iE_K(f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S)).

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

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

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

1. Блочные режимы:

зашифрование:
T'_i = E_K(T_if(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S));
расшифрование:
T_i = D_K(T'_i)f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S).

2. Потоковые режимы:

зашифрование:
T'_i = T_iE_K(f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S));
расшифрование:
T_i = T'_iE_K(f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S)).

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

В блочных режимах зашифрование осуществляется применением криптографического преобразования непосредственно к шифруемому блоку, модифицированному значением рандомизирующей функции f, - в уравнении зашифрования шифруемый блок T_i стоит внутри скобок криптографического преобразования E_K(...), тогда как в потоковых режимах зашифрование осуществляется точно так же, как в потоковых шифрах, наложением на шифруемый блок некоторого кода с помощью обратимой бинарной операции, и шифруемый блок T_i не фигурирует в выражении для аргумента преобразования E_K.
При расшифровании в блочном режиме используется криптографическое преобразование D_K, обратное тому преобразованию E_K, которое применяется для зашифрования, тогда как при расшифровании в потоковом режиме используется то же самое шифрующее преобразование, что и при зашифровании. Из этого следует, вообще говоря, весьма интересный вывод: для организации блочных режимов шифрования необходимо обратимое криптографическое преобразование, тогда как для организации потоковых режимов шифрования обратимость используемого криптопреобразования не требуется, достаточно его криптографической стойкости. Это позволяет реализовать такие режимы на базе вычислительно необратимых функций.

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

T'_i = E_K(T_iF_i) в "блочных" режимах,
T'_i = T_iE_K(F_i) в "потоковых" режимах,
где F_i = f(T₁,T₂,...,T_i_-1,T'₁,T'₂,...,T'_i_-1,S) для обоих типов режимов.

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

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

если T'_i = V'_i для i = 1,2,...,m,
то T_i = V_i для i = 1,2,...,m.

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

T'_i = V'_iT_i = V_i для любого i.

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

T'_i = V'_jT_i = V_j для любых i,j,

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

T'_i = T'_jT_i = T_j для любых i,j.

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

В потоковых шифрах это же самое приводит к катастрофической потере стойкости. Предположим, что два массива данных, T = (T₁,T₂,...,T_n), и V = (V₁,V₂,...,V_n), зашифрованы в потоковом режиме на одном и том же ключе K с использованием одного и того же параметра инициализации S. Тогда

T'₁ = T₁E_K(f(S)),
V'₁ = V₁E_K(f(S)),

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

T'₁V'₁ = (T₁E_K(f(S)))(V₁E_K(f(S))) = T₁V₁.

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

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

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

T_i = V_i для i = 1,2,...,m.

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

T'_i₊₁V'_i₊₁ = T_i₊₁V_i₊₁.

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

T'_i = T_iE_K(f(i,S)),
V'_i = V_iE_K(f(i,S)),

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

T'_iV'_i = T_iV_i

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

[Оглавление] [Предыдущий выпуск] [Следующий выпуск]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]