Для чего используют блочные шифры

Блочные шифры и их криптоанализ

Блочный шифр — разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками, характерный размер которых меняется в пределах 64 — 256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Фактически, блочный шифр представляет собой подстановку на алфавите блоков, которая, как следствие, может быть моно- или полиалфавитной. Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты данных, передаваемых по сети.

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

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

Contents

История

Современная модель блочных шифров основана на идее итеративных блочных шифров, предложенной в публикации 1949 года Клода Шеннона «Теория связи в секретных системах». Данная концепция позволяет достичь определенного уровня безопасности комбинированием простых в исполнении операций подстановки и замены.

До 70-х годов криптография была уделом военных и практически не существовало каких-либо публикаций. Первопроходцем явился шифр «Люцифер», разработанный в 1970 году компанией IBM и основанный на SP-сети. Идея шифра заключалась в использовании комбинаций простых, а следовательно, быстро вычисляемых как аппаратно, так и программно операций. Однако, схема получилась неудачной: она была слишком громоздкой, что привело к низкой скорости шифрования в программной реализации (около 8 кбайт/с) и в аппаратной (97 кбайт/с). Стали появляться опасения, связанные со стойкостью данного алгоритма. Тем не менее, принципы, выработанные при построении «Люцифера», (SP-сеть и сеть Фейстеля, названная так в честь одного из разработчиков) легли в основу конструирования блочных шифров.

В 1973 году Национальный институт стандартов и технологий объявил конкурс с целью разработать стандарт шифрования данных, победителем которого в 1974 году стал шифр DES (Data Encryption Standart), являющийся, фактически, улучшенной версией «Люцифер». Публикация шифра в 1977 году была основополагающей в общественном понимании современной модели блочного шифра. В то же время, она дала начало развитию криптоаналитических атак. После одобрения Американским национальным институтом стандартов в 1981 году, алгоритм долгое время использовался в гражданском секторе и даже вышел за пределы США. Однако шифр имел существенный недостаток — маленькую длину ключа, породившую множество связанных с параллельным перебором атак, и приближающаяся возможность её реализации. Отсутствие достойной защиты от атак шифра DES породило множество алгоритмов, являющихся как более сложной версией DES (3DES), так и совершенно иных схем (NewDES, FEAL, IDEA).

В 1997 году стал годом начала программы по принятию AES (Advanced Encryption Standart). Конкурс состоял из трех этапов, окончательным победителем которого стал алгоритм RIJNDAEL, разработанный бельгийцами J. Daemen и V. Rijmen. AES, как и его предшественники, также построен с использованием SP-сети.

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

Определение

Блочный шифр состоит из двух парных алгоритмов: шифрования и расшифрования. Оба алгоритма можно представить в виде функций. Функция шифрования E на вход получает блок данных M размером n бит и ключ K размером k бит и на выходе отдает блок шифротекста C размером n бит:

Для любого ключа K, является биективной функцией (перестановкой) на множестве n-битных блоков. Функция расшифрования D на вход получает шифр C, ключ K и на выходе отдает M: являясь, при этом, обратной к функции шифрования: и

Заметим, что ключ, необходимый для шифрования и дешифрования, один и тот же — следствие симметричности блочного шифра.

Построение блочного шифра

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

Итеративные блочные шифры

Большинство блочных шифров являются итеративными. Это означает, что данный шифр преобразует блоки открытого текста постоянной длины в блоки шифротекста той же длины посредством циклически повторяющихся обратимых функций, известных как раундовые функциии. Это связано с простотой и скоростью исполнения как программных, так и аппаратных реализаций. Обычно раундовые функции используют различные ключи, полученные из первоначального ключа: , где C_i — значение блока после i-го раунда, C₀ = M — открытый текст, K_i — ключ, используемый в i-м раунде и полученный из первоначального ключа K.

Размер блока n — это фиксированный параметр блочного шифра, обычно равный 64 или 128 битам, хотя некоторые шифры допускают несколько различных значений. Длина 64 бита была приемлема до середины 90-х годов, затем использовалась длина 128 бит, что примерно соответствует размеру машинного слова и позволяет эффективную реализацию на большинстве распространённых вычислительных платформ. Различные схемы шифрования позволяют зашифровывать открытый текст произвольной длины. Каждая имеет определенные характеристики: вероятность ошибки, простота доступа, уязвимость к атакам. По состоянию на 2006 год 80-битный ключ способен был предотвратить атаку грубой силой.

SP-сети

SP-сеть (англ. substitution-permutation network, SPN) — один из важнейших типов итеративных блочных шифров. Шифр на основе SP-сети получает на вход блок и ключ и совершает несколько чередующихся раундов, состоящих из чередующихся стадий подстановки и стадий перестановки. Для достижения безопасности достаточно одного S-блока, но такой блок будет требовать большого объёма памяти. Поэтому используются маленькие S-блоки, смешанные с P-блоками. Нелинейная стадия подстановки перемешивает биты ключа с битами открытого текста, создавая конфузию Шеннона. Линейная стадия перестановки распределяет избыточность по всей структуре данных, порождая диффузию.

S-блок (англ. substitution box or S-box) замещает маленький блок входных бит на другой блок выходных бит. Эта замена должна быть взаимно однозначной, чтобы гарантировать обратимость. Назначение S-блока заключается в нелинейном преобразовании, что препятствует проведению линейного криптоанализа. Одним из свойств S-блока является лавинный эффект, т.е. изменение одного бита на входе приводит к изменению всех бит на выходе.

P-блок (англ. permutation box or P-box) — перестановка всех бит: блок получает на вход вывод S-блока, меняет местами все биты и подает результат S-блоку следующего раунда. Важным качеством P-блока является возможность распределить вывод одного S-блока между входами как можно больших S-блоков.

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

Сеть Фейстеля

Сеть Фейстеля — это общий метод преобразования произвольной функции F в перестановку на множестве блоков. Она состоит из циклически повторяющихся ячеек — раундов. Внутри каждого раунда блок открытого текста разделяется на две равные части. Раундовая функция берет одну половину (на рис. правую), преобразует её с использованием ключа Ki и объединяет результат с второй половиной посредством операции исключающее ИЛИ (XOR). Этот ключ задаётся первоначальным ключом K и различен для каждого раунда. Далее половинки меняются местами (иначе будет преобразовываться только одна половина блока) и подаются на следующий раунд. Преобразование сети Фейстеля является обратимой операцией.

Для функции F существуют определенные требования:

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

Формирование группы

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

Режимы работы блочного шифра

Криптоанализ

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

Атака полным перебором

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

Не менее важную роль играет размер ключа. Ранний шифр DES характеризовался размером ключа в 56 бит, что, как показала практика, явно не достаточно для надежной пересылки данных. Именно атакой полным перебором впервые был вскрыт DES. Более современные алгоритмы, такие как AES и ГОСТ 28147-89 имеют размер ключа в 128 бит и 256 бит соответственно, что делает бессмысленным подобные атаки.

Дифференциальный криптоанализ

В 1990 году Эли Бихам (Eli Biham) и Ади Шамир (Adi Shamir) определили идею дифференциального криптоанализа. С помощью этого метода удалось взломать шифр DES. Подобной атаке подвержены шифры с постоянным S-блоком и шифрование в режиме кодовой электронной книги. Данный метод работает с парами шифротекстов, для которых известно различие соответствующих открытых текстов, и рассматривает эволюцию этих различий. Наряду с линейным является самым распространенным при атаках на блочный шифр.

Линейный криптоанализ

Линейный криптоанализ — метод вскрытия шифра, основанный на поиске аффинных приближений для работы алгоритма. Разработан японским математиком Мицуру Мацуи (Mitsuru Matsui), первым применивший эту технику для атаки на DES и FEAL. Метод основан на применении операции исключающему ИЛИ (XOR) к блокам открытого текста, шифротекста и к их результату, что позволяет получить результат применения XOR для битов ключа. Структура S-блока оказывает сильное влияние на стойкость к линейным атакам. Когда метод был разработан, оказалось, что DES имеет слабость к нему, так как никто не предполагал подобных атак при его разработке.

Интегральный криптоанализ

Интегральный криптоанализ — вид атак, особенно применимый к блочный шифрам, построенным на SP-сети. В отличие от дифференциального криптоанализа, использующего пару выбранного открытого текста с фиксированным разницей, вычисленной при помощи операции XOR, интегральный криптоанализ использует множества открытых текстов, в которых одни части удерживаются постоянными, в то время как другие варьируются среди всевозможных значений. Подобное множество с необходимостью имеет сумму по модулю 2 (XOR), равной 0, в то время, как соответствующая сумма шифротекста содержит информацию об операциях шифра.

Атака на основе связанных ключей

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

Национальные стандарты шифрования

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

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

Схема шифрования алгоритма DES

Исходный текст — блок 64 бит. Процесс шифрования состоит из начальной перестановки, 16 циклов шифрования и конечной перестановки.

Исходный текст (блок 64 бит) преобразуется c помощью начальной перестановки .

Начальная перестановка IP

58	50	42	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

По таблице первые 3 бита результирующего блока после начальной перестановки являются битами 58, 50, 42 входного блока , а его 3 последние бита являются битами 23, 15, 7 входного блока.

Полученный после начальной перестановки 64-битовый блок IP(T) участвует в 16-циклах преобразования Фейстеля.

— 16 циклов преобразования Фейстеля:

Разбить IP(T) на две части , где — соответственно 32 старших битов и 32 младших битов блока T₀, =.

Пусть результат (i-1) итерации, тогда результат i-ой итерации определяется:

Левая половина равна правой половине предыдущего вектора . А правая половина — это битовое сложение и по модулю 2.

В 16-циклах преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

Основная функция шифрования (функция Фейстеля)

Аргументами функции f являются 32-битовый вектор R_i-1 и 48-битовый ключ k_i, который является результатом преобразования 56-битового исходного ключа шифра k

Для вычисления функции f последовательно используются

Функция E расширяет 32-битовый вектор R_i-1 до 48-битового вектора E(R_i-1) путём дублирования некоторых битов из R_i-1

Первые три бита вектора E(R_i-1) являются битами 32, 1, 2 вектора R_i-1. По таблице 2 видно, что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 бита вектора E(R_i-1) — это биты 31, 32, 1 вектора R_i-1. Полученный после перестановки блок E(R_i-1) складывается по модулю 2 с ключами k_i и затем представляется в виде восьми последовательных блоков B₁,B₂,B₃. B₈

Каждый B_j является 6-битовым блоком. Далее каждый из блоков B_j трансформируется в 4-битовый блок B_j с помощью преобразований S_j.

Схема расшифрования

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

Схема расшифрования указана на рисунке.

Режимы использования DES

DES может использоваться в четырёх режимах.

ГОСТ 28147-89

ГОСТ 28147-89 — российский стандарт шифрования, введенный в 1990 году, также является стандартом СНГ. Шифр основан на 32-раундовой сети Фейстеля c 256-битным ключом. В мае 2011 года краптоаналитиком Николя Куртуа была предпринята попытка атаки, снижающая время взлома в 28 (256) раз, но требующая 264 пар открытого/шифрованного текста, что не может рассматриваться как успешная атака, так как при наличии такого количества открытого текста нет необходимости в знании шифротекста.

Из-за наличия большого количества раундов, атаки на основе дифференциального и линейного криптоанализа не состоятельны, так как последние чувствительны к числу раундов. Полный перебор при такой длине ключа полностью лишен смысла. Для достижения лавинного эффекта ГОСТу требуется 8 раундов, что может быть слабостью алгоритма, но при 32 раундах это не имеет столь сильного значения. Вопрос о безопасности ГОСТа остается открытым.

Описание алгоритма

Выделяют четыре режима работы ГОСТ 28147-89:

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Его S-блоки могут быть секретными, и они содержат примерно 354 (log₂(16! 8 )) бит секретной информации, так что эффективный размер ключа может быть увеличен до 610 бит.

Подключи выбираются в предварительно заданном порядке. Ключевое расписание очень простое: разбивается 256-битный ключ на восемь 32-битных подключей, и каждый подключ используется четыре раза в алгоритме, первые 24 раунда используются ключи по порядку, а последние 8 раундов они используются в обратном порядке.

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

Данный набор S-блоков используется в криптографических приложениях ЦБ РФ:

#	S-Box
1	4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3
2	14 11 4 12 6 13 15 10 2 3 8 1 0 7 5 9
3	5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11
4	7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3
5	6 12 7 1 5 15 13 8 4 10 9 14 0 3 11 2
6	4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14
7	13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12
8	1 15 13 0 5 7 10 4 9 2 3 14 6 11 8 12

Криптоанализ

Считается, что ГОСТ устойчив к таким широко применяемым методам, как линейный и дифференциальный криптоанализ. Обратный порядок использования ключей в последних восьми раундах обеспечивает защиту от атак скольжения (slide attack) и отражения (reflection attack). Ростовцев А.Г., Маховенко Е.Б., Филиппов А.С., Чечулин А.А. в своей работе описали вид криптоанализа, который сводится к построению алгебраической целевой функции и нахождению ее экстремума. Были выделены классы слабых ключей, в частности, показано, что разреженные ключи (со значительным преобладанием 0 или 1) являются слабыми. По мнению авторов, их метод в любом случае лучше, чем полный перебор, однако без численных оценок.

В мае 2011 года известный криптоаналитик Николя Куртуа доказал существование атаки на данный шифр, имеющей сложность в 2 8 (256) раз меньше сложности прямого перебора ключей при условии наличия 2 64 пар открытый текст/закрытый текст. Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности. Более того, знание 2 64 пар открытый текст/закрытый текст, очевидно, позволяет читать зашифрованные тексты, даже не вычисляя ключа. В большинстве других работ также описываются атаки, применимые только при некоторых предположениях, таких как определенный вид ключей или таблиц замен, некоторая модификация исходного алгоритма, или же требующие все еще недостижимых объемов памяти или вычислений. Вопрос о наличии применимых на практике атак без использования слабости отдельных ключей или таблиц замены остается открытым.

AES, принятый NIST в 2001 году после 5-летнего общественного конкурса, заменил собой шифр DES как федеральный стандарт соединенных штатов. Шифр разработан двумя бельгийскими криптографами Дайменом Йоаном и Рэйменом Винсентом. Размер блока составляет 128 бит и размер ключа 128, 192 и 256 бит, несмотря на то, что размер блока может быть определен любым числом бит, кратным 32, с минимальным значением 128 бит. Максимальный размер блока равен 256 бит, при этом размер ключа не имеет теоретического предела. Поддержка данного шифра введена компанией Intel в семейство процессоров x86.

Шифрование

Для AES длина input(блока входных данных) и State(состояния) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. Для обозначения выбранных длин input, State и Cipher Key в 32-битных словах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

В начале шифрования input копируется в массив State по правилу , для и . После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу , для и . Отдельные трансформации SubBytes(), ShiftRows(), MixColumns(), и AddRoundKey() — обрабатывают State. Массив w[] — содержит key schedule.

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

, где , и где b_i есть i-ый бит b, а c_i— i-ый бит константы . Таким образом, обеспечивается защита от атак, основанных на простых алгебраических свойствах.

ShiftRows работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали, в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1 Б и т. д. Таким образом каждая колонка выходного состояния после применения процедуры ShiftRows состоит из байтов из каждой колонки начального состояния. Для алгоритма AES смещения строк для 128- и 192-битных строк одинаково. Однако для блока размером 256 бит отличается от предыдущих тем, что 2, 3, и 4-е строки смещаются на 1, 3, и 4 байта, соответственно.

В процедуре AddRoundKey, RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey используя процедуру KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey.

Источник