Обратите внимание, что новости можно получать по RSS.
X
-

Информационные технологии, Infused Bytes - архив

8 мая 1999, 00:00 (6626 дней назад, №6054)Режимы шифрования (окончание)
(Андрей Винокуров)

< К оглавлению

 

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

T = (T1,T2,...,Tn) - массив открытых данных,
T' = (T'1,T'2,...,T'n) - массив зашифрованных данных,

поделенные на блоки одинакового размера |T'i| = |Ti| = N. Кроме того, мы будем подразумевать, что в блочных режимах последний блок уже дополнен каким-либо образом до полного, и что в потоковых режимах при модификации последнего неполного блока используется лишь часть гаммирующего блока. Кроме того, мы не будем здесь упоминать о проблемах, общих для всех режимов одного типа - они были подробно рассмотрены в предыдущих выпусках.

А. Блочные режимы шифрования.

1. Режим простой замены (электронной кодовой книги).

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

T'i = EK(Ti),
Ti = DK(T'i),

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

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

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

2. Режим простой замены (электронной кодовой книги) с рандомизацией шифруемых данных.

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

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

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

1. Если у противника есть возможность криптоанализа на основе произвольного выбранного открытого текста, то он может обнаружить все априорно известные "шаблонные" блоки (v), просто зашифровав массив из таких блоков и сравнив результат с перехваченным шифротекстом:

V'i = EK(v f(i,S)),
если T'i = V'i, то Ti = v.

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

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

1. При необходимости любой фрагмент шифротекста может быть расшифрован независимо от остального шифротекста.

2. При модификации исходных данных нет необходимости шифровать весь массив заново, достаточно зашифровать только изменившиеся блоки, причем при этом может быть использован тот же самый параметр инициализации S.

3. Режим сцепления блоков шифротекста.

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

T'i = EK(Ti T'i-1),
Ti = DK(T'i) T'i-1,
где полагаем T'0 = S.

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

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

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

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

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

4. Режим сцепления блоков.

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

T'i = EK(Ti Fi),
Ti = DK(T'i) Fi,
где Fi+1 = Fi T'i, F1 = S.

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

T'i = EK(Ti S T'1 ... T'i-1),
Ti = DK(T'i) S T'1 ... T'i-1.

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

5. Режим сцепления блоков шифротекста с распространением ошибки.

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

T'i = EK(Ti T'i-1 Ti-1),
Ti = DK(T'i) T'i-1 Ti-1,

где полагают T0 T'0 = S.

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

6. Режим сцепления блоков шифротекста с контрольной суммой.

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

T'i = EK(Ti Ti-1 ... T1 T'i-1),
Ti = DK(T'i) T'i-1 Ti-1 ... T1,
где полагают T0 T'0 = S.

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

7. Режим сцепления блоков открытого текста.

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

T'i = EK(Ti Ti-1),
Ti = DK(T'i) Ti-1,

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

Б. Потоковые режимы шифрования.

8. Режим гаммирования (потоковый режим).

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

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

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

1. При любом значении параметра инициализации S обеспечивать максимальный или близкий к максимальному начальный отрезок последовательности элементов, в котором вырабатываемые элементы не повторяются. Обычно используется рекуррентный генератор элементов Xi+1 = W(Xi), X0 = S, f(i,S) = Xi, обеспечивающий достаточно большой период повторения вырабатываемой последовательности.

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

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

Источник последовательности элементов для выработки гаммы является настолько важным компонентом шифра, что разработчики российского стандарта шифрования сочли необходимым определить его явным образом. Стандартный источник состоит из двух независимых рекуррентных генераторов 32-битовых элементов с периодами 232 и 232-1, в результате чего период повторения всей последовательности равен 232 · (232-1) ~ 264. Кроме того, соседние элементы последовательности отличаются по крайней мере на один бит в каждом байте.

9. Режим обратной связи по выходу генератора элементов гаммы.

Как и во всех остальных режимах данного класса, в режиме обратной связи по выходу вырабатывается последовательность элементов гаммы, которая используется для шифрования данных путем наложения на них с помощью операции побитового исключающего ИЛИ. Генератор гаммы организован в виде блока криптопреобразования EK, часть выходных двоичных разрядов которого подается опять на вход, образуя тем самым петлю обратной связи. Элементы гаммы в этом случае вырабатываются блоками размера (L), меньшего или равного размеру блока используемого криптоалгоритма (N), L N. За- и расшифрование данных выполняется по следующим уравнениям:

T'i = Ti HiL(EK(Xi)),
Ti = T'i HiL(EK(Xi)),
где X1 = S, Xi+1 = LoN-L(Xi) || HiL(EK(Xi)).

Через HiL(X) и LoL(X) в вышеприведенных уравнениях обозначены операции извлечения L соответственно старших или младших битов блока X. Естественно, размер шифруемого блока для этого режима равен размеру элемента гаммы и не превышает размера блока данных используемого криптоалгоритма: |T'i| = |Ti| = L N.
Однако режим обратной связи по выходу при L < N обладает следующими недостатками:

1. С точки зрения криптостойкости - было показано, что при L < N средний период повторения последовательности вырабатываемых элементов составляет приблизительно 2N/2, что для наиболее распространенного на практике размера блока 64 бита даст 232 - конечно, этого явно недостаточно. При L = N период вырабатываемой последовательности элементов равен 2N, т.е. достигает возможного максимума для заданного размера блока.

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

T'i = Ti Xi,
Ti = T'i Xi,
где X1 = EK(S), Xi+1 = EK(Xi).

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

10. Режим обратной связи по шифротексту.

Этот режим напоминает предыдущий, за исключением того, что для обратной связи в нем берется не элемент гаммы, а шифротекст. Точно так же шифрованию подвергаются блоки размера L, меньшего или равного размеру блока используемого криптоалгоритма (N), L N. Уравнения за- и расшифрования в режиме обратной связи по шифротексту следующие:

T'i = Ti HiL(EK(Xi)),
Ti = T'i HiL(EK(Xi)),

где X1 = S, Xi+1 = LoN-L(Xi) || T'i.

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

T'i = Ti EK(T'i-1),
Ti = T'i EK(T'i-1),

где полагаем T'0 = S.

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

11. Режим обратной связи по открытому тексту.

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

T'i = Ti HiL(EK(Xi)),
Ti = T'i HiL(EK(Xi)),
где X1 = S, Xi+1 = LoN-L(Xi) || Ti.

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

T'i = Ti EK(Ti-1),
Ti = T'i EK(Ti-1),
где полагаем T0 = S.

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

Подведем итог нашего рассмотрения:

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

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

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

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

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


Опубликовано: Андрей Винокуров

Случайная заметка

6530 дней назад, 15:0012 августа 1999 Закончилась Paradox'99 demo party (Ростов-на-Дону, 7-8 августа). Один из ее организаторов Warhawk сообщает: В среднем было около 100-150 человек. Первый день прошел не так как планировали, из-за проблем с zx-spectrum'ом , да и работ навезли на саму party больше чем было залито, пришлось работы принимать даже с винтов. Второй день прошел на ура, задержки ...далее

Избранное

54 дня назад, 01:575 мая 2017 Часть 1: От четырёх до восьми Я люблю читать воспоминания людей, заставших первые шаги вычислительной техники в их стране. В них всегда есть какая-то романтика, причём какого она рода — сильно зависит от того, с каких компьютеров люди начали. Обычно это определяется обстоятельствами — местом работы, учёбы, а иногда и вовсе — ...далее

1559 дней назад, 00:5922 марта 2013 Прочёл тут книжку - iWoz ( ссылка ) , 2006 года. Это автобиография Стива Возняка. Похоже, что на русский её не переводили (в отличие от книг про Стива Джобса). В этой парочке, как известно, Возняк был инженером (собственно, и спроектировавшим Apple I и II), а Джобс - скорее предпринимателем. В книге есть довольно интересные ...далее

663 дня назад, 23:404 сентября 2015 Небольшое видео про CC'2015 ( версия без фоновой музыки здесь: ссылка )

1031 день назад, 03:121 сентября 2014 Мой семинар на Chaos Constructions'2014 (слайды можно в виде PDF скачать здесь: ссылка ) и несколько интервью с разными людьми: Вячеслав Славинский (svo) о Vectrex: ссылка Вячеслав Славинский (svo) о 3D Imager для Vectrex: ссылка Вячеслав Славинский (svo) о световом пере для Vectrex: ссылка ...далее