Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
2.5. Российский стандарт криптографической защиты В данном разделе в качестве примера блочного итерационно- го шифра приведено краткое описание алгоритма криптографи- ческого преобразования данных ГОСТ 28147-89 [5 – 8], в даль- нейшем изложении – просто ГОСТ. γ i E AB Регистр n n s i s 0 Генератор ПСЧ t Рис. 2.9. Модифицированный генератор ПСЧ для режимов шифрования, подобных OFB Достоинства ГОСТа: удобство программной реализации на 32-разрядных процес- сорах; регулярная структура устройства (реализующего алгоритм), облегчающая его интегральное исполнение; 88 криптостойкость, приемлемая для подавляющего числа при- ложений; оригинальный качественный генератор ПСЧ (генератор гаммы); большой запас «прочности» за счет значительного объема ключевой информации. ГОСТ является классическим итерационным блочным шиф- ром Фейстеля с разрядностью блоков данных, равным 64 битам. Чтобы разобраться в ГОСТе, необходимо понять: характер используемой при шифровании ключевой инфор- мации, структуру раундовой функции шифрования (так называемо- го основного шага криптопреобразования), алгоритмы зашифрования k E (базовые циклы 32-З и 16-З) и расшифрования k D (базовый цикл 32-Р), рекомендуемые режимы использования. Ключевая информация ГОСТа. Ключевая информация представляет собой два массива данных: собственно к люч k и таблицу замен H (рис. 2.10). Ключ – это массив из восьми 32-разрядных элементов 7 , 0 , m k k m Таким образом, размер ключа составляет 256 32 8 битов или 32 байта. Таблица замен – набор из восьми одномерных массивов 7 , 0 , m H H m , так называемых узлов замены, каждый из которых определяет логику работы четырехразрядного блока подстановок (S-блока) и по этой причине содержит шестна- дцать 4-разрядных двоичных наборов (от 0 до 15), располо- женных в произвольном порядке. Элемент m-го узла замен j S m = m j H , – 4-разрядный код на выходе соответствующего m-го S-блока при поступлении на его вход двоичного кода числа j. Таким образом, объем таблицы замен равен 512 4 16 8 битов или 64 байта. Ключ должен быть масси- вом статистически независимых битов, принимающих с ра в- ной вероятностью значения 0 и 1. Если для генерации ключ е- вой информации используется генератор ПСЧ, то он должен обладать криптостойкостью, не меньшей, чем у самого ГОСТа. Таблица замен H (в отличие от ключа k) – долговре- 89 менный ключевой элемент. Она, например, может быть о б- щей для всех процедур шифрования в рамках одной системы криптографической защиты. Таблица замен H Узел замен H 7 0 1 j 15 S 7 (0) Адрес ячейки S 7 (1) S 7 (j) S 7 (15) S m (0) S m (1) S m (j) S m (15) S 1 (0) S 1 (1) S 1 (j) S 1 (15) S 0 (0) S 0 (1) S 0 (j) S 0 (15) Узел замен H m Узел замен H 1 Узел замен H 0 Рис. 2.10. Таблица замен ГОСТ 28147-89 Раундовая функция шифрования ГОСТа. Структура основ- ного шага криптопреобразования показана на рис. 2.11, где t d – входной блок, 1 t d – выходной блок, x – шаговый ключ. В каче- стве исходных данных шаг получает 64-разрядный блок данных d = (L, R) и 32-разрядный раундовый ключ x, в качестве которого используется один из элементов ключа m k . В ходе выполнения шага левая (L) и правая (R) половины блока данных рассматрива- ются как отдельные 32-разрядные элементы данных, в качестве которых они подвергаются следующим преобразованиям: 1) сложению по модулю 32 2 полублока R и элемента ключа x; 2) разбиению результата s на восемь четырехбитовых бло- ков, поблочной замене по таблице замен, формированию из получившихся блоков нового значения s; 3) циклическому сдвигу результата s на 11 разрядов влево; 4) поразрядному сложению по модулю два (XOR) результа- та s и полублока L; 90 5) элемент R cтановится новым значением элемента L, зна- чение результата предыдущей операции становится но- вым значением элемента R. Полученные значения элементов L и R выдаются в качестве результата шага. L R f k i L R d (t) d (t + 1) 64 32 32 32 32 64 а 32 x XOR R x SM 32 32 32 32 4 32 4 4 4 4 4 4 4 4 H H 7 H 0 H 1 S 7 S 1 S 0 <<<11 Сложение по модулю 2 32 Подстановка Циклический сдвиг на 11 разрядов влево б f(R, x) Рис. 2.11. ГОСТ 28147-89: а – схема основного шага криптопреобразования, б – шаговая функция f 91 Базовые циклы ГОСТа. Базовые циклы 32-З, 32-Р (циклы шифрования k E и k D ) и 16-З (цикл выработки имитопристав- ки k E ) отличаются друг от друга только числом повторений основного шага и порядком использования элементов ключа. В обозначении цикла первый элемент – число повторений ос- новного шага (32 или 16), второй элемент – тип функции (З – зашифрование, Р – расшифрование). Кроме того, в конце цик- лов шифрования для взаимной обратимости предусмотрена дополнительная перестановка элементов L и R. Порядок ис- пользования элементов ключа имеет вид: цикл зашифрования 32-З – три раза вперед, один раз назад ( 0 6 7 7 1 0 7 1 0 7 1 0 , , , , , , , , , , , , , , , k k k k k k k k k k k k ); цикл расшифрования 32-Р – один раз вперед, три раза назад ( 0 6 7 0 6 7 0 6 7 7 1 0 , , , , , , , , , , , , , , , k k k k k k k k k k k k ); цикл выработки имитоприставки 16-З – два раза вперед ( 7 1 0 7 1 0 , , , , , , , k k k k k k ). Режимы шифрования ГОСТа. ГОСТ 28147-89 определяет три режима шифрования данных (простая замена, гаммирование и гаммирование с обратной связью) и режим выработки имито- приставки. Простая замена заключается в применении цикла 32-З к бло- кам открытого текста при зашифровании и цикла 32-Р к блокам закрытого текста при расшифровании. Режим простой замены полностью совпадает с режимом ECB, описанным выше. Гаммирование – наложение на открытые данные псевдослу- чайной гаммирующей последовательности. Режим гаммирования аналогичен режиму Counter, описанному выше. Блоки гаммы получаются в результате зашифрования в режиме простой заме- ны элементов выходной последовательности 64-разрядного счетчика. Таким образом, генератор гаммы имеет ярко выражен- ную двухступенчатую структуру, при этом первая ступень, т.е. счетчик, обеспечивает близкий к максимально возможному зна- чению 64 2 период гаммирующей последовательности, а вторая (т.е. функция k E ) – необходимую криптостойкость. Схема счет- чика ГОСТа, являющегося по сути двумя независимо работаю- щими рекуррентными генераторами со взаимно простыми зна- 92 чениями периодов ( 32 2 и 1 2 32 ), формирующими правую и ле- вую половины блоков, обладает следующими свойствами: соседние 64-битовые значения, вырабатываемые генерато- ром, для повышения криптостойкости отличаются друг от друга в каждом байте; генератор легко реализуется как аппаратно, так и на 32- разрядных процессорах программно; синхропосылка (начальное заполнение генератора ПСЧ) пе- ред инициализацией генератора подвергается преобразова- нию по циклу 32-З; период выходной последовательности равен 1 2 2 32 32 Рекуррентные соотношения для старшей ( L Q ) и младшей ( R Q ) частей генератора имеют вид 32 1 2 mod 1 C t Q t Q L L ; 1 1 2 mod 1 1 32 2 C t Q t Q H H , где С 1 = 01010101h, С 2 = 01010104h. Гаммирование с обратной связью полностью совпадает с вы- шеописанным режимом CFB. Его отличительная особенность – способ выработки очередного элемента гаммы. Первый элемент гаммы является результатом шифрования по циклу 32-З синхро- посылки. Любой последующий элемент гаммы вырабатывается как результат преобразования по циклу 32-З предыдущего блока шифротекста, вследствие чего каждый блок шифротекста зави- сит от соответствующего и всех предыдущих блоков открытого текста. Рассмотрим еще раз влияние искажений шифротекста на по- лученные в результате расшифрования открытые данные. В режиме простой замены искажение блока шифротекста приводит при расшифровании к непредсказуемым изменениям соответствующего блока открытого текста. В режиме гаммирования все изменения открытого текста предсказуемы. В режиме гаммирования с обратной связью искажение блока шифротекста после расшифрования приводит к изменениям двух блоков открытого текста, при этом один из них оказывается ис- каженным предсказуемым образом, а другой – непредсказуемым. 93 Непредсказуемые изменения в расшифрованном массиве дан- ных могут быть обнаружены лишь в случае избыточности этих данных. Такая избыточность, к сожалению, имеет место практи- чески только для текстов на естественных или искусственных языках. Поэтому для обнаружения случайных или умышленных искажений информационной последовательности требуется спе- циальный режим, в ГОСТ он назван режимом выработки ими- топриставки. Имитоприставка – это добавляемый к зашифрованным дан- ным контрольный код, зависящий от открытых данных и ключе- вой информации. Для противника вычислительно неразрешимы две задачи: 1) вычисление имитоприставки для заданной незашифро- ванной информационной последовательности; 2) подбор открытых данных под заданную имитоприставку. Схема формирования имитоприставки – зашифрование ин- формации в режиме CFB, при этом k E – функция зашифрования по циклу 16-З. В качестве имитоприставки используется часть последнего зашифрованного блока, обычно его младшие 32 раз- ряда. В общем случае вероятность успешного навязывания лож- ных данных равна N - 2 2.6. Американский стандарт криптографической защиты История конкурса на стандарт криптографической защи- ты ХХI в. – Advanced Encryption Standard (AES). В 1997 г. НИСТ объявил о начале программы по принятию нового стан- дарта криптографической защиты, стандарта ХХI в.,для закры- тия важной информации правительственного уровня, на замену существующему с 1974 г. алгоритму DES, на тот момент самому распространенному криптоалгоритму в мире. DES устарел по многим параметрам: длине ключа, удобству реализации на со- временных процессорах, быстродействию и другим, за исключе- нием самого главного – стойкости. За 25 лет интенсивного крип- тоанализа не было найдено методов вскрытия этого шифра, су- щественно отличающихся по эффективности от полного перебо- ра по ключевому пространству. 94 Требования к кандидатам были следующие: криптоалгоритм должен быть открыто опубликован; криптоалгоритм должен быть симметричным блочным шифром, допускающим размеры ключей в 128, 192 и 256 бит; криптоалгоритм должен быть предназначен как для аппа- ратной, так и программной реализации; криптоалгоритм не должен быть запатентован, в противном случае патентные права должны быть аннулированы; криптоалгоритм подвергается исследованиям по таким па- раметрам, как стойкость, стоимость, гибкость. Стойкость. Это самый важный критерий в оценке алгоритма. Оценивались: способность шифра противостоять различным ме- тодам криптоанализа, статистическая безопасность и относи- тельная защищенность по сравнению с другими кандидатами. Оценивалась стойкость к атаке методом полного перебора с уче- том прогнозируемого роста вычислительных мощностей. Стоимость. Не менее важный критерий, если принимать во внимание одну из основных целей NIST – широкую область ис- пользования и доступность AES. Стоимость зависит от вычисли- тельной эффективности (в первую очередь быстродействия) на различных платформах, удобства программной и аппаратной реализации, низким требованиям к памяти, простоты (простые алгоритмы легче реализовывать, они более прозрачны для ана- лиза) Гибкость. Включает в себя способность алгоритма обрабаты- вать ключи больше оговоренного минимума (128 бит), надеж- ность и эффективность выполнения в разных средах, возмож- ность реализации других криптографических функций. Другими словами, AES должен быть существенно более эф- фективным с точки зрения практической реализации (в первую очередь скорости шифрования и формирования ключей), иметь больший запас прочности, чем TripleDES, при этом не уступая ему в стойкости. Реализуемость в Smart-картах. Важная область использова- ния AES – smart-карты, при этом главной проблемой является небольшой объем доступной памяти. NIST исходил из допуще- ния, что некоторые дешевые карты могут иметь всего 256 байтов 95 RAM (для вычисляемых данных) и 2000 байтов ROM (для хра- нения алгоритмов и констант). Существуют два основных мето- да формирования раундовых ключей: 1) вычисление на начальном этапе работы криптоалго- ритма и хранение в памяти; 2) вычисление раундовых ключей «на лету». Ясно, что второй вариант уменьшает затраты RAM, и поэтому наличие такой возможности в криптоалгоритме является его не- сомненным достоинством. На конкурс были приняты 15 алгоритмов, разработанных криптографами 12 стран – Австралии, Бельгии, Великобрита- нии, Германии, Израиля, Канады, Коста-Рики, Норвегии, США, Франции, Южной Кореи и Японии. В финал конкурса вышли следующие алгоритмы: MARS, RC6, TWOFISH (США), RIJNDAEL(Бельгия), SERPENT (Великобритания, Израиль, Норвегия). По своей структуре TWOFISH– классический шифр Фейстеля; MARS и RC6 мож- но отнести к модифицированным шифрам Фейстеля, в них ис- пользуется новая малоизученная операция циклического «про- кручивания» бит слова на число позиций, изменяющихся в за- висимости от шифруемых данных и секретного ключа; RIJNDAELи SERPENTявляются классическимиSP-сетями. MARS и TWOFISH имеют самую сложную конструкцию, RIJNDAEL и RC6 – самую простую. Финалисты будут описаны по единой схеме, данной в доку- менте NIST. Сначала описываются обнаруженные «слабости» алгоритма (если таковые имеются), затем преимущества и, на- конец, недостатки. MARS выставлен на конкурс фирмой IBM, одним из авторов шифра является Д. Копперсмит, участник разработки DES. В ал- горитме не обнаружено слабостей в защите. Преимущества: высокий уровень защищенности; высокая эффективность на 32-разрядных платформах, осо- бенно поддерживающих операции умножения и цикличе- ского сдвига; потенциально поддерживает размер ключа больше 256 бит. 96 Недостатки: сложность алгоритма, затрудняющая анализ его надежности; снижение эффективности на платформах без необходимых операций; сложность защиты от временного анализа и анализа мощно- сти. RC6 предложен фирмой RSA Lab, один из авторов – Р. Ривест. В алгоритме не обнаружено слабостей в защите. Преимущества: высокая эффективность на 32-разрядных платформах, осо- бенно поддерживающих операции умножения и цикличе- ских сдвигов; простая структура алгоритма, упрощающая анализ его на- дежности; наличие хорошо изученного предшественника – RC5; быстрая процедура формирования ключа; потенциально поддерживает размер ключа больше 256 бит; длина ключа и число раундов могут быть переменными. Недостатки: относительно низкий уровень защищенности; снижение эффективности на платформах, не имеющих не- обходимых операций; сложность защиты от временного анализа и анализа мощно- сти; невозможность генерации раундовых ключей «на лету». TWOFISH основан на широко используемом шифре BLOWFISH; один из авторов разработки – Б. Шнайер. Главная особенность шифра – изменяющиеся в зависимости от секретно- го ключа таблицы замен. В алгоритме не обнаружено слабостей в защите. Преимущества: высокий уровень защищенности; хорошо подходит для реализации в Smart-картах из-за низ- ких требований к памяти; высокая эффективность на любых платформах, в том числе на ожидаемых в будущем 64-разрядных архитектурах фирм Intel и Motorola; поддерживает вычисление раудовых ключей «на лету»; поддерживает распараллеливание на уровне инструкций; 97 допускает произвольную длину ключа до 256 бит. Недостатки: особенности алгоритма затрудняют его анализ; высокая сложность алгоритма; применение операции сложения делает алгоритм уязвимым к анализу мощности и временному анализу. RIJNDAEL, большинством участников конкурса названный лучшим выбором (если будет отвергнут их собственный шифр), основан на шифре SQUARE тех же авторов. В алгоритме не об- наружено слабостей в защите. Преимущества: высокая эффективность на любых платформах; высокий уровень защищенности; хорошо подходит для реализации в Smart-картах из-за низ- ких требований к памяти; быстрая процедура формирования ключа; хорошая поддержка параллелизма на уровне инструкций; поддержка разных длин ключа с шагом 32 бита. Недостаток: уязвимость к анализу мощности. SERPENT – разработка профессиональных криптоаналитиков Р. Андерсона, Э. Бихэма, Л. Кнудсена. Создав шифр, успешно противостоящий всем известным на сегодня атакам, разработчи- ки затем удвоили количество его раундов. В алгоритме не обна- ружено слабостей в защите. Преимущества: высокий уровень защищенности; хорошо подходит для реализации в Smart-картах из-за низ- ких требований к памяти. Недостатки: самый медленный алгоритм среди финалистов; уязвимость к анализу мощности. В октябре 2000 г. конкурс завершился – победителем был признан бельгийский шифр RIJNDAEL,имеющий наилучшее сочетание стойкости, производительности, эффективности реа- лизации, гибкости. Его низкие требования к объему памяти де- лают его идеально подходящим для встроенных систем. Авторы 98 шифра– Joan Daemen и Vincent Rijmen, начальные буквы фами- лий которых и образуют название алгоритма – RIJNDAEL. AES-128. RIJNDAEL – это итеративный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. Рассмотрим версию криптоалгоритма AES-128. Промежуточ- ные результаты преобразований, выполняемых в рамках крипто- алгоритма, называются состояниями (state). Все входные блоки данных, все промежуточные результаты преобразований, все выходные блоки данных, а также ключ шифрования можно представить в виде квадратного массива байтов (рис. 2.12). Этот массив имеет четыре строки и четыре столбца. k 01 k 00 k 02 k 03 k 11 k 10 k 12 k 13 k 21 k 20 k 22 k 23 a 31 a 30 a 32 a 33 a 01 a 00 a 02 a 03 a 11 a 10 a 12 a 13 a 21 a 20 a 22 a 23 a 31 a 30 a 32 a 33 Рис. 2.12. Примерпредставления состояния и ключа шифрования для AES-128 В некоторых случаях ключ шифрования рассматривается как линейный массив 4-байтовых слов. Слова состоят из четырех байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива). Входные данные для шифра обозначаются как байты состоя- ния в порядке a 00 , a 10 , a 20 , a 30 , a 01 , a 11 , a 21 , a 31 , ... . После завер- шения действия шифра выходные данные получаются из байтов состояния в том же порядке. В состав раунда AES-128 входят следующие четыре преоб- разования (рис. 2.13): побайтовая замена байтов состояния с использованием фик- сированной таблицы замен размером 8 256 (SubBytes); побайтовый циклический сдвиг строк результата – i-я строка сдвигается на i байтов влево, 3 , 0 i (ShiftRows); 99 перемешивание столбцов результата (MixColumns); поразрядное сложение по модулю 2 (XOR) результата с ра- ундовым ключом (AddRoundKey). Десятый раунд отличается от остальных – в нем отсутствует предпоследняя операция для более эффективной реализации обратного преобразования. ShiftRows SubBytes MixColumns AddRoundKey Рис. 2.13. Раундовые преобразованияAES-128 Замена байтов (SubBytes). Преобразование представляет со- бой нелинейную замену байтов, выполняемую независимо с каждым байтом состояния. Таблица замены S-блока является инвертируемой. Рис. 2.14 иллюстрирует применение преобра- зования SubBytes к состоянию. a 01 a 00 a 02 a 03 a 11 a 10 a 12 a 21 a 20 a 22 a 23 a 31 a 30 a 32 a 33 b 01 b 00 b 02 b 03 b 11 b 10 b 12 b 13 b 21 b 20 b 22 b 23 b 31 b 30 b 32 b 33 a ij b ij S-блок a 13 Рис. 2.14. SubBytes действует на каждый байт состояния Преобразование сдвига строк (ShiftRows). Последние три строки состояния циклически сдвигаются на различное число байт. Строка 1 сдвигается на один байт, строка 2 – на два байта 100 и строка 3 – на трибайта. Рис. 2.15 показывает влияние преоб- разования на состояние. Без сдвига Циклический сдвиг на 1 байт Циклический сдвиг на 2 байта Циклический сдвиг на 3 байта Рис. 2.15. ShiftRows действует на строки состояния Преобразование перемешивания столбцов (MixColumns). Рис. 2.16 демонстрирует применение преобразования MixColumns к столбцу состояния. Добавление раундового ключа (AddRoundKey).В данной операции раундовый ключ добавляется к состоянию посредст- вом простого поразрядного XOR(рис. 2.17). Раундовый ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Mix a 01 a 00 a 02 a 03 a 11 a 10 a 12 a 21 a 20 a 22 a 23 a 31 a 30 a 32 a 33 a 13 a 00 a 03 a 10 a 20 a 23 a 30 a 33 a 1j a 0j a 3j a 2j b 01 b 00 b 02 b 03 b 11 b 10 b 12 b 13 b 21 b 20 b 22 b 23 b 31 b 30 b 32 b 33 b 03 b 23 b 33 b ij a 03 a 23 a 33 b 1j b 0j b 3j b 2j Рис. 2.16. MixColumns действует на столбцы состояния k 01 k 00 k 02 k 03 k 11 k 10 k 12 k 13 k 21 k 20 k 22 k 23 k 31 k 30 k 32 k 33 a 01 a 00 a 02 a 03 a 11 a 10 a 12 a 13 a 21 a 20 a 22 a 23 a 31 a 30 a 32 a 33 b 01 b 00 b 02 b 03 b 11 b 10 b 12 b 13 b 21 b 20 b 22 b 23 b 31 b 30 b 32 b 33 Рис. 2.17. При добавлении ключа раундовый ключ складывается посредством операции XOR с состоянием 101 Алгоритм выработки ключей (Key Schedule).Раундовые ключи получаются из ключа шифрования посредством алго- ритма выработки ключей. Он содержит два компонента: рас- ширение ключа (Key Expansion) и выбор раундового ключа (Round Key Selection). Основополагающие принципы алгоритма выглядят следующим образом: общее число бит раундовых ключей равно длине блока, умноженной на число раундов плюс 1 (например, для дли- ны блока 128 бит и 10 циклов требуется 1408 бит циклово- го ключа); ключ шифрования расширяется в расширенный ключ (Expanded Key); раундовые ключи берутся из расширенного ключа сле- дующим образом: первый раундовый ключ содержит пер- вые четыре слова, второй – следующие четыре слова и т.д. Расширение ключа (Key Expansion). Расширенный ключ представляет собой линейный массив 4-байтовых слов. Первые четыре слова содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Криптоалгоритм.Шифр AES-128 состоит из: начального добавления раундового ключа; девяти раундов; заключительного раунда. Новая архитектура (рис. 2.18,а), с использованием которой построена функция E k , получила название «Квадрат». Свойства алгоритма иллюстрирует рис. 2.18,б, из которого видно, что два раунда обеспечивают полное рассеивание и перемешивание информации. Видно, что даже незначительные изменения на входе нелинейной функции приводят к существенным измене- ниям на выходе (в среднем изменяется половина бит преобра- зованного блока). 102 Добавление раундового ключа AddRoundKey Сдвиг строк ShiftRows Перемешивание столбцов MixColumns Добавление раундового ключа AddRoundKey Замена байтов SubBytes 1-й раунд 9-й раунд 10-й раунд Добавление раундового ключа AddRoundKey Сдвиг строк ShiftRows Перемешивание столбцов MixColumns Замена байтов SubBytes Сдвиг строк ShiftRows Замена байтов SubBytes Добавление раундового ключа AddRoundKey Входной блок M i Выходной блок C i Входной блок После SubBytes 1-го раунда После MixColumns 1-го раунда После ShiftRows 2-го раунда После MixColumns 2-го раунда Измененный бит Измененный байт а б Рис. 2.18. Шифр AES-128: а – итеративное блочное преобразование (нелинейная функция зашифрования); б – рассеивание и перемешивание информации в процессе двухраундового преобразования Обоснование числа раундов выглядит следующим образом. Авторы криптоалгоритма продемонстрировали эффективнейшую атаку на 4-раундовую версию RIJNDAEL [14]. После добавления 103 5-го раунда атака по-прежнему возможна, но становится сложнее. После добавления 6-го раунда атака по-прежнему возможна, но ее сложность уже сопоставима с атакой полного перебора. К полу- чившейся 6-раундовой функции шифрования, обладающей мини- мальной стойкостью к рассматриваемой атаке, добавляются два начальных раунда, обеспечивающих полное рассеивание и пере- мешивание, и два конечных раунда, обладающих тем же свойст- вом. Таким образом, суммарное число раундов становится рав- ным 10. Основные достоинства AES-128: новая архитектура «Квадрат», обеспечивающая быстрое рас- сеивание и перемешивание информации, при этом за один раунд преобразованию подвергается весь входной блок; байт-ориентированная структура, удобная для реализации на 8-разрядных микроконтроллерах; все раундовые преобразования суть операции в конечных по- лях, допускающие эффективную аппаратную и программную реализацию на различных платформах. Возможные направления совершенствования архитектуры «Квадрат». Можно выделить следующиепути совершенствова- ния архитектуры «Квадрат»: замена раундовой операции сдвига строк ShiftRows на опера- цию перемешивания строк MixRows позволит обеспечить полное рассеивание и перемешивание за один раунд; совместное использование архитектур «Петля Фейстеля» и «Квадрат», например построение раундового преобразования f на основе операций добавления раундового ключа, замены байтов, перемешивания строк и перемешивания столбцов; переход от архитектуры «Квадрат» к архитектуре «Куб» (приложение 3). 2.7. Вероятностное блочное шифрование Одной из функций генераторов ПСЧ в системах криптогра- фической защиты информации может быть внесение неопреде- ленности в работу средств защиты, например, выбор элементов вероятностного пространства R при вероятностном шифровании , : C R M E k 104 где C M k E k , , , – функция зашифрования, секретный ключ, про- странство открытых текстов и пространство шифротекстов соот- ветственно. Главная особенность вероятностного шифрования – один и тот же исходный текст, зашифрованный на одном и том же ключе, может привести к появлению огромного числа раз- личных шифротекстов. Во избежание путаницы следует отметить: термин вероятно- стное шифрование (Probabilistic Encryption) был впервые введен Ш. Гольдвассер и С. Микали. Ими же предложена первая схема такого шифрования, основанная на использовании BBS- генератора ПСЧ в качестве источника ключевой последователь- ности. В настоящем разделе термин «вероятностное шифрова- ние» используется, чтобы подчеркнуть факт внесения неопреде- ленности в работу криптоалгоритма. Представляется, что такое применение термина – более обосновано. Схема одного из возможных вариантов вероятностного блоч- ного шифрования в режиме ECB показана на рис. 2.19, где на вход функции зашифрования k E поступает «расширенный» n-разрядный блок i M' , полученный в результате конкатенации m-разрядного блока открытого текста i M и двоичного набора i R разрядности (n – m) с выхода генератора ПСЧ. В результате за- шифрования получается блок i c закрытого текста, разрядность которого больше разрядности блока i M . В результате при за- шифровании одинаковых блоков на одном и том ключе получа- ются различные блоки шифротекста. При расшифровании часть i R блока, полученного на выходе функции k D , просто отбрасы- вается. Можно выделить следующие достоинства вероятностного шифра: появляется принципиальная возможность увеличения вре- мени жизни сеансовых ключей; использование качественного генератора ПСЧ позволяет при использовании симметричных блочных шифров умень- шить число раундов шифрования, а значит, увеличить быст- родействие криптоалгоритма; 105 отношение длин блока открытого текста i M' и соответст- вующего ему элемента i r вероятностного пространства может выступать в качестве параметра безопасности. M i R i A E k C i Генератор ПСЧ k n n n - m m m M i R i C i D k k n n - m n m а б Рис. 2.19. Пример вероятностного шифрования в режиме ECB: а – зашифрование; б – расшифрование Недостаток у рассматриваемой схемы лишь один – шифро- текст всегда длиннее соответствующего ему открытого текста. Следует отметить, что подобная схема может использовать- ся и в асимметричных криптосистемах (системах с открытым ключом) при этом противник лишается возможности вычислять значение функции шифрования интересующих его текстов и сравнивать их с перехваченным шифротекстом. 2.8. Cинхронные поточные шифры В синхронных поточных шифрах гаммирующая последова- тельность формируется независимо от потока открытого текста при зашифровании и шифротекста при расшифровании. Функ- ционирование генератора гаммы, разворачивающего короткий случайный ключ k в длинную псевдослучайную последователь- ность (ПСП), в общем случае можно описать следующим обра- зом: 106 , , , , 1 k s f k s F s t t t t где t s – состояние элементов памяти генератора гаммы в момент времени t; F – функция обратной связи (перехода); f – функция выхода. Начальное заполнение 0 s может быть функцией от клю- ча и синхропосылки. Существуют два основных режима функционирования син- хронных поточных шифров. В режиме обратной связи по выходу OFB функция выхода f генератора ПСЧ не зависит от ключа и уравнения работы генератора гаммы имеют вид , , 1 t t t t s f k s F s В режиме счетчика функция обратной связи F генератора ПСЧ не зависит от ключа, но гарантированно обеспечивает прохож- дение генератора через все пространство состояний (или боль- шую его часть). Уравнения генератора гаммы в этой ситуации имеют вид , , 1 k s f s F s t t t t Главное свойство синхронного поточного шифра – отсутствие эффекта размножения ошибок. При расшифровании неправиль- ного бита искажается только соответствующий бит открытого текста. Данное свойство ограничивает возможность обнаруже- ния ошибки при расшифровании. Кроме того, противник имеет возможность производить управляемые изменения шифротекста, совершенно точно зная, какие изменения в результате произой- дут в соответствующем открытом тексте. При использовании синхронных поточных шифров необходимо согласование работы устройств на передающей и принимающей стороне, так как в случае потери или вставки элемента зашифрованной последова- тельности на принимающей стороне будет потеряна вся инфор- мация, начиная с того места, где сбилась синхронизация. Обыч- но синхронизация достигается либо вставкой специальных мар- керов, либо переинициализацией передающего и принимающего 107 устройства при некотором заранее согласованном условии [21, 24, 30]. Описание наиболее известных поточных шифров приведено в [24]. ШифрА5 –поточный шифр, используемый в системах GSM (Group Special Mobile) для закрытия связи между абонентом и базовой станцией. Он является европейским стандартом для цифровых сотовых мобильных телефонов. А5 использует три LFSR длиной 19, 22 и 23 с прореженными многочленами обрат- ной связи, т.е. с многочленами, имеющими небольшое число не- нулевых коэффициентов. Выходом генератора гаммы является выход элемента сложения по модулю два М2, на входы которого поступают последовательности с выходов трех LFSR (их на- чальное заполнение – секретный сеансовый ключ). Используется управление синхронизацией LFSR (рис. 2.20). Схема синхронизации ТИ Stop/go Stop/go Stop/go c 1 c 2 c 3 LFSR 1 LFSR 3 LFSR 2 x 1 x 2 x 3 γ M2 Рис. 2.20. Генератор ПСЧ поточного шифра А5 108 Для управления синхронизацией используются биты 3 2 1 , , c c c с выходов LFSR. В каждом такте сдвигаются как минимум два LFSR. Если , = = 3 2 1 c c c сдвигаются все три регистра, в против- ном случае – те два регистра i и j, для которых выполняется ра- венство = j i c c Криптоанализ алгоритма показал, что для определения на- чального заполнения LFSR при известных 64 бит гаммы требу- ется перебор 40 2 вариантов. Кроме того, около 40 % ключей приводят к циклу, длина которого наименьшая из всех возмож- ных и равна 3 4 1 2 23 бит. Алгоритм разрабатывался с нару- шением правила Кирхгофа, поэтому имеет большое число слабо- стей, подробное описание которых приведено в [24]. Шифр RC4 – поточный шифр переменным размером ключа, разработанный Р. Ривестом. Алгоритм работает в режиме OFB, т.е. поток ключевой информации не зависит от открытого текста. Используется 8-разрядный S-блок, таблица замен имеет размер- ность 256 8 и является перестановкой (зависящей от ключа) двоичных чисел от 0 до 255. Применяются два счетчика 1 Q и 2 Q с нулевым начальным состоянием (рис. 2.21). Рассмотрим процедуру генерации очередного байта гаммы. Пусть i S и – содержимое ячейки с адресом i таблицы замен S-блока и очередной байт гаммы. Алгоритм RC4 1. Такт работы первого счетчика: 2 mod 1 8 1 1 Q Q 2. Такт работы второго счетчика: 2 mod 8 2 2 1 Q S Q Q 3. Ячейки таблицы замен S-блока с адресами 1 Q и 2 Q обме- ниваются своим содержимым: 2 1 Q Q S S 109 4. Вычисление суммы содержимого ячеек таблицы замен S-блока с адресами 1 Q и : 2 Q 2 mod 8 2 1 Q Q S S T 5. Считывание содержимого ячейки таблицы замен S-блока с адресом Т: T S γ S-блок S T S Q S Q 8 Q 1 Q 2 1 2 8 8 8 8 8 8 ТИ +1 mod 256 mod 256 Рис. 2.21. Схема генератора ПСЧ RC4 Алгоритм инициализации таблицы замен S-блока 1. Запись в каждую ячейку таблицы замен S-блока ее собст- венного адреса: , 255 , 0 i S i i 2. Заполнение байтами ключа другой 256-байтовой таблицы: 110 255 0, , i k k i 3. Инициализация индекса j: j = 0. 4. Перемешивание таблицы замен S-блока: , 2 mod , 255 , 0 8 j i i i S S k S j j i Число состояний RC4 равно приблизительно 2 1700 256 ! 256 2 Таблица замен S-блока медленно изменяется при использовании, при этом счетчик 1 Q обеспечивает изменение каждого элемента таблицы, а 2 Q гарантирует, что элементы таблицы изменяются случайным образом. Основные достоинства алгоритма: простая и понятная структура шифра; доступность для исчерпывающего анализа, в том числе за счет возможности проведения полного исследования версий шифра меньшей разрядности; универсальный алгоритм перемешивания ключевой табли- цы, имеющий самостоятельное значение, пригодный для создания как S-, так и R-блоков. Наиболее известный пример неудачной реализации шифра – стандарт безопасности Wep, криптоанализ которого приведен в [24]. Шифр PIKE – это модификация взломанного шифра FISH, предложенная Р. Андерсоном. Алгоритм использует три адди- тивных генератора (рис. 2.22): Q i = (Q i – 55 + Q i - 24 ) mod 2 32 , Q i = (Q i – 57 + Q i - 7 ) mod 2 32 , Q i = (Q i – 58 + Q i - 19 ) mod 2 32 Управление синхронизацией осуществляется на основе ана- лиза битов переноса cro 1 , cro 2 , cro 3 на выходах сумматоров Sm. Если все три одинаковы cro 1 = cro 2 = cro 3 (все нули или все еди- ницы), то тактируются все три генератора; в противном случае тактируются те два генератора i и j, для которых выполняется равенство cro i = cro j . Выходом генератора является результат 111 поразрядной операции М2 значений на выходах всех трех гене- раторов. Q 1 Q 19 Q 58 Q 1 Q 7 Q 57 Q 1 Q 24 Q 55 Sm Sm Sm cro 2 cro 1 cro 3 Схема синхронизации ТИ M2 Рис. 2.22. Генератор ПСЧ PIKE Шифр Trivium – синхронный поточный шифр, разработан- ный в 2005 году С. De Canniere и P. Preneel для европейского проекта eSTREAM. Trivium, изначально проектировавшийся для аппаратной реализации, также может успешно применяться и в программ- ном исполнении, где одним из его преимуществ является быст- родействие. Для генерации ключевого потока длиной 2 64 бит требуется 80 бит секретного ключа и 80 бит инициализирующего значе- ния (IV – initial value). Параметры шифра представлены в табл. 2.1. Как и в большинстве поточных шифров, процесс генерации ключевого потока состоит из двух фаз: 1 – внутреннее состояние шифра инициализируется ключом и инициализирующим значе- нием (IV), 2 – состояние неоднократно обновляется и генериру- ется ключевой поток. Сначала рассмотрим вторую. 112 Таблица 2.1 Параметры Trivium Параметр Значение, бит Размер ключа 80 Размер IV 80 Внутреннее состояние 288 Генерация ключевого потока. Шифр состоит из 288 бит внутреннего состояния обозначаемых ) ..., , , ( 288 2 1 s s s . Генерация ключевого потока представляет собой повторяющийся процесс: из внутреннего состояния шифра извлекаются значения 15 опре- деленных битов, с помощью которых обновляются 3 бита внут- реннего состояния и рассчитывается один бит ключевого потока z i , затем внутреннее состояние сдвигается. Процесс повторяется до тех пор, пока требуемое количество битов ( 64 2 N ) ключево- го потока не сгенерируется. Описание этого процесса на псев- докоде имеет следующий вид: do for N i to 1 288 243 3 177 162 2 93 66 1 s s t s s t s s t 3 2 1 t t t z i 69 287 286 3 3 264 176 175 2 2 171 92 91 1 1 s s s t t s s s t t s s s t t 288 179 178 2 288 179 178 176 95 94 1 177 95 94 92 2 1 3 93 2 1 ..., , , , ..., , , ..., , , , ..., , , ..., , , , ..., , , s s s t s s s s s s t s s s s s s t s s s for end 113 Операторы «+» и «·» – операции XOR и AND соответственно. Схема генератора ПСЧ Trivium представлена на рис. 2.23. S 1 S 66 S 94 S 162 S 178 … S 243 ... S 69 … S 171 … S 264 … S 91 S 92 S 93 … S 175 S 176 S 177 … S 286 S 287 S 288 t 1 t 2 t 3 z i Рис. 2.23. Генератор ключевого потока Trivium Инициализация начального состояния ключом и IV. Ал- горитм инициализируется загрузкой 80-битного ключа K и ини- циализирующего значения IV такой же разрядности в 288 бит внутреннего состояния, все остальные биты внутреннего состоя- ния, исключая 288 287 286 , , s s s , обнуляются. Затем полученное внутреннее состояние сдвигается вправо четыре полных цикла похожим способом, как описано выше, но без генерации ключе- вого потока. Этот процесс на псевдокоде можно описать сле- дующим образом: 1 , 1 , 1 , 0 ..., , 0 ..., , , 0 ..., , 0 , ..., , , ..., , , 0 ..., , 0 , ..., , , ..., , , 288 179 178 80 2 1 177 95 94 80 2 1 93 2 1 s s s IV IV IV s s s K K K s s s do for 288 4 to 1 i 114 69 288 287 286 243 3 264 177 176 175 162 2 171 93 92 91 66 1 s s s s s t s s s s s t s s s s s t 288 179 178 2 288 179 178 176 95 94 1 177 95 94 92 2 1 3 93 2 1 ..., , , , ..., , , ..., , , , ..., , , ..., , , , ..., , , s s s t s s s s s s t s s s s s s t s s s for end Несмотря на тот факт, что Trivium проектировался не для программной реализации, шифр довольно успешно может при- меняться на стандартных ПК. 2.9. Самосинхронизирующиеся поточные шифры Самосинхронизирующиеся поточные шифры благодаря свой- ству восстанавливать информацию после нарушения синхрони- зации – это наиболее распространенный метод шифрования в дипломатических, военных и промышленных системах связи. Наиболее распространенный режим функционирования само- синхронизирующихся поточных шифров – режим обратной свя- зи по шифротексту. В шифрах рассматриваемого типа каждый зашифрованный символ (бит при последовательной передаче) зависит от ключа k и только от последних m N символов шифротекста. Память разрядности m N поточного шифра может быть реализована различными способами, простейший из них – использование m N -разрядного регистра сдвига (рис. 2.24). Пусть c F – функция шифрования, G – функция, преобразую- щая на стадии инициализации секретный ключ K и синхропо- сылку S во внутренний ключ k и вектор инициализации IV реги- стра сдвига. Тогда уравнение работы криптосхемы имеет вид 115 ; , ; ; , , 1 - - 0 1 - t t t t N t c t N z M c c c k F z IV c c S K G IV k m m Расшифрование символа закончится успешно, если послед- ние m N символов шифротекста были приняты правильно. Пусть s N – разрядность символа, тогда одиночная ошибка в канале связи вызовет серию из s m N N потенциально неправиль- но расшифрованных бит на принимающей стороне. Самосин- хронизирующееся шифрование имеет смысл применять лишь тогда, когда вероятность битовых ошибок в двоичном канале без памяти значительно меньше величины 1 - s m N N Дополни- тельное достоинство рассматриваемой криптосхемы – возмож- ность реализации поверх любой цифровой коммуникационной системы. G G K S K S k F c F c k M c M IV IV Рис. 2.24. Общая схема самосинхронизирующегося поточного шифра Один из существующих подходов – использование для по- строения самосинхронизирующихся поточных шифров последо- вательной и параллельной композиции простейших функций f шифрования. Параллельная композиция суть побитовый XOR последовательностей с выходов двух блоков f, в последователь- 116 ной композиции выход одного блока f является входом другого. На рис. 2.25 показана схема поточного шифра У. Маурера. Базовый компонент схемы – 3-битовый регистр сдвига с зави- сящей от ключа функцией f выхода. Четыре таких компонента образуют блок следующего уровня – пару параллельно соеди- ненных цепочек из двух базовых компонентов. На следующем уровне четыре таких блока собраны в последовательную компо- зицию. На двух следующих уровнях эта конструкция повторяет- ся. Результирующая последовательностная машина (ПМ) имеет входную память объемом 192 бит и четыре бита-компонента на каждый бит памяти. Внутреннее состояние ПМ служит входом для зависящей от ключа функции шифрования c F Для задания конструкций булевых функций f ключ шифрования «разворачи- вается» в 256 байтов, каждый из которых определяет таблицу истинности соответствующей функции. Основная идея данной конструкции – построение ПМ, коли- чество элементов памяти которой превышает разрядность вход- ной памяти. f i (k) M F c k c Рис. 2.25. Схема Маурера 117 Контрольные вопросы 1. Сформулируйте требования к качественному симметрич- ному шифру. 2. Перечислите недостатки режима шифрования ECB. 3. Укажите области предпочтительного использования ре- жима шифрования ECB. 4. Какие режимы шифрования могут использоваться для формирования контрольного кода целостности информа- ции? 5. Какие режимы шифрования требуют наличия только функции зашифрования AB E ? 6. Сравните генераторы ПСЧ со структурами OFB и Counter. 7. Перечислите основные достоинства Российского стан- дарта криптозащиты. 8. Сколько раундов AES-128 обеспечивают полное рассеи- вание и перемешивание информации? Обоснуйте свой ответ. 9. Сравните архитектуры блочных шифров «Сеть Фейсте- ля» и «Квадрат». 10. Укажите основные различия блочных и поточных шиф- ров (не менее пяти). 11. Укажите способы заполнения таблиц замен S-блоков (не менее трех). 12. Кто является инициатором создания симметричной крип- тосистемы: отправитель или получатель? 13. Укажите два принципиальных недостатка симметричной криптосистемы. 14. Нарисуйте схему вероятностного блочного шифрования: а) в режиме ECB; б) в режиме OFB, в) в режиме CFB. 15. Сформулируйте требования к качественному S-блоку. 16. Перечислите достоинства вероятностного шифрования. |