Русская Википедия:Блочный шифр

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Файл:Block cipher.png
Общая схема работы блочного шифра

История

Современная модель блочных шифров основана на идее итеративных блочных шифров, предложенной в публикации 1949 года Клода Шеннона «Теория связи в секретных системах». Данная концепция позволяет достичь определённого уровня безопасности комбинированием простых в исполнении операций подстановки (Шаблон:Lang-en) и перестановки (Шаблон:Lang-en)[2].

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

Стали появляться опасения, связанные со стойкостью данного алгоритма. Тем не менее, принципы, выработанные при построении «Люцифера», (SP-сеть и сеть Фейстеля, названная так в честь одного из разработчиков) легли в основу конструирования блочных шифров.

В 1973 году Национальный институт стандартов и технологий (Шаблон:Lang-en) объявил конкурс с целью разработать стандарт шифрования данных, победителем которого в 1974 году стал шифр DES (Data Encryption Standard), являющийся, фактически, улучшенной версией «Люцифер». Публикация шифра в 1977 году была основополагающей в общественном понимании современной модели блочного шифра. В то же время, она дала начало развитию криптоаналитических атак.

После одобрения Американским национальным институтом стандартов в 1981 году, алгоритм долгое время использовался в гражданском секторе и даже вышел за пределы США. Однако шифр имел существенный недостаток — маленькую длину ключа, породившую множество связанных с параллельным перебором атак, и приближающаяся возможность её реализации. Отсутствие достойной защиты от атак шифра DES породило множество алгоритмов, являющихся как более сложной версией DES (3DES), так и совершенно иных схем (NewDES, FEAL, IDEA).

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

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

Определение

Блочный шифр состоит из двух парных алгоритмов: шифрования и расшифрования.[3] Оба алгоритма можно представить в виде функций. Функция шифрования E (Шаблон:Lang-en — шифрование) на вход получает блок данных M (Шаблон:Lang-en — сообщение) размером n бит и ключ K (Шаблон:Lang-en — ключ) размером k бит и на выходе отдает блок шифротекста C (Шаблон:Lang-en — шифр) размером n бит:

<math>E_K(M) := E(K,M) : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n.</math>

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

<math>D_K(C) := D(K,C) : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n,</math>

являясь, при этом, обратной к функции шифрования:

<math>D = E^{-1},</math>
<math>\forall K: D_K(E_K(M)) = M</math> и
<math>E_K(D_K(C)) = C.</math>

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

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

Шаблон:Начало цитаты «Проектировать блочный шифр нетрудно. Трудность состоит в проектировании блочного шифра, который не только безопасен, но также может быть легко описан и просто реализован.»

Брюс Шнайер, криптограф и специалист по компьютерной безопасности.

Шаблон:Конец цитаты

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

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

Большинство блочных шифров являются итеративными. Это означает, что данный шифр преобразует блоки открытого текста (Шаблон:Lang-en) постоянной длины в блоки шифротекста (Шаблон:Lang-en) той же длины посредством циклически повторяющихся обратимых функций, известных как раундовые функции.[4] Это связано с простотой и скоростью исполнения как программных, так и аппаратных реализаций. Обычно раундовые функции используют различные ключи, полученные из первоначального ключа:

<math>C_i = R_{K_i}(C_{i-1})</math>,

где Ci — значение блока после i-го раунда, C0 = M — открытый текст, Ki — ключ, используемый в i-м раунде и полученный из первоначального ключа K.

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

SP-сети

Файл:SubstitutionPermutationNetwork2.png
Пример SP-сети с 3 раундами.

Шаблон:Main

SP-сеть (Шаблон:Lang-en) — один из важнейших типов итеративных блочных шифров. Шифр на основе SP-сети получает на вход блок и ключ и совершает несколько чередующихся раундов, состоящих из чередующихся стадий подстановки (Шаблон:Lang-en) и стадий перестановки (Шаблон:Lang-en)[5]. Для достижения безопасности достаточно одного S-блока, но такой блок будет требовать большого объёма памяти. Поэтому используются маленькие S-блоки, смешанные с P-блокамиШаблон:Sfn. Нелинейная стадия подстановки перемешивает биты ключа с битами открытого текста, создавая Шаблон:Iw Шеннона. Линейная стадия перестановки распределяет избыточность по всей структуре данных, порождая диффузию[6][7].

S-блок (Шаблон:Lang-en) замещает маленький блок входных бит на другой блок выходных бит. Эта замена должна быть взаимно однозначной, чтобы гарантировать обратимость. Назначение S-блока заключается в нелинейном преобразовании, что препятствует проведению линейного криптоанализа. Одним из свойств S-блока является лавинный эффект, то есть изменение одного бита на входе приводит к изменению всех бит на выходе[8].

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

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

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

Шаблон:Main

Сеть Фейстеля — это общий метод преобразования произвольной функции F в перестановку на множестве блоков.Шаблон:Sfn Она состоит из циклически повторяющихся ячеек — раундов. Внутри каждого раунда блок открытого текста разделяется на две равные части. Раундовая функция

<math>F = F(K_i,R_{i-1})</math>
Файл:Feistel encryption.png
Шифрование в ячейке Фейстеля

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

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

  • её работа должна приводить к лавинному эффекту
  • должна быть нелинейна по отношению к операции XOR

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

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

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

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

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

Шаблон:Main

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

Шифрование независимыми блоками

Файл:Tux.svg
оригинальное изображение
Файл:Tux ecb.jpg
криптограмма в режиме ECB
Файл:Tux secure.jpg
псевдослучайная последовательность

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

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

Шифрование, зависящее от предыдущих блоков

Файл:CBC Encryption ru.svg
Шифрование в режиме сцепления блоков шифротекста

Чтобы преодолеть эти проблемы, были разработаны иные режимы работы[9]Шаблон:Sfn, установленные международным стандартом ISO/IEC 10116[10] и определеные национальными рекомендациями, такие, как NIST 800-38A[11] и BSI TR-02102[12]

Общая идея заключается в использовании случайного числа, часто называемого Шаблон:Iw (IV). В популярном режиме сцепления блоков (Шаблон:Lang-en) для безопасности IV должен быть случайным или псевдослучайным. После его определения, он складывается при помощи операции исключающее ИЛИ с первым блоком открытого текста. Следующим шагом шифруется результат и получается первый шифроблок, который используем как IV для второго блока и так далее. В режиме обратной связи по шифротексту (Шаблон:Lang-en) непосредственному шифрованию подвергается IV, после чего складывается по модулю два (XOR, исключающее ИЛИ) с первым блоком. Полученный шифроблок используется как IV для дальнейшего шифрования. У режима нет особых преимуществ по сравнению с остальными. В отличие от предыдущих режимов, режим обратной связи вывода (Шаблон:Lang-en) циклически шифрует IV, формируя поток ключей, складывающихся с блоками сообщения. Преимуществом режима является полное совпадение операций шифрования и расшифрования. Режим счетчика (Шаблон:Lang-en) похож на OFB, но позволяет вести параллельное вычисление шифра: IV объединяется с номером блока без единицы и результат шифруется. Полученный блок складывается с соответствующим блоком сообщения.

Следует помнить, что вектор инициализации должен быть разным в разных сеансах. В противном случае приходим к проблеме режима ECB. Можно использовать случайное число, но для этого требуется достаточно хороший генератор случайных чисел. Поэтому обычно задают некоторое число — метку, известную обеим сторонам (например, номер сеанса) и называемое nonce (Шаблон:Lang-en). Секретность этого числа обычно не требуется. Далее IV — результат шифрования nonce. В случае режима счетчика, nonce используется для формирования раундового ключа KiШаблон:Sfn:

<math>K_i = E_K(nonce||i-1), i = 1,..,n ,</math> где i — номер раунда.

Дополнение до целого блока

Как уже упоминалось выше, в случае, если длина самого сообщения, либо последнего блока, меньше длины блока, то он нуждается в дополнении. Простое дополнение нулевыми битами не решает проблемы, так как получатель не сможет найти конец полезных данных. К тому же, такой вариант приводит к Шаблон:Iw[13].

Поэтому на практике применимо решение, стандартизованное как «Метод дополнения 2» (Дополнение битами) в ISO/IEC 9797-1, добавляющее единичный бит в конец сообщения и заполняющее оставшееся место нулями[14]. В этом случае была доказана стойкость к подобным атакам[15].

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

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

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

Шаблон:Main

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

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

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

Файл:Differential cryptanalysis.png
Рис.1 Схема взлома дифференциальным криптоанализом

Шаблон:Main

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

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

Шаблон:Main

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

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

Шаблон:Main

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

Другие типы атак

Помимо описанных выше, существуют другие типы атак:

Любой новый шифр должен продемонстрировать стойкость ко всем известным видам атак.

Практическая оценка

На практике блочный шифр оценивают по множеству критериевШаблон:Sfn[18]:

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

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

Lucifer / DES

Шаблон:Main Шифр Lucifer в целом рассматривается в качестве первого блочного шифра. Алгоритм разработан компанией IBM в 1970-х годах для собственных нужд и основан на работе Хорста Фейстеля (Шаблон:Lang-en). Доработанная версия была принята как американский правительственный федеральный стандарт обработки информации: FIPS PUB 46 Data Encryption Standard (DES) — стандарт шифрования данных.

DES имеет размер блока 64 бит и ключ 56 бит. Впоследствии 64-битные блоки стали общепринятыми при построении шифра. Длина ключа зависела от нескольких факторов, в том числе от правительственных ограничений, и в результате стала очевидным недостатком алгоритма — её оказалось недостаточно, чтобы противостоять атакам полным перебором. В 1993 году Майкл Винер спроектировал машину стоимостью 1 миллион долларов, способную взломать DES за 3,5 часа грубой силой, и в 1998 году Шаблон:Iw, способная к взлому, была построена. К тому же, для ключей алгоритма существует ряд значений, считающимися слабымиШаблон:Sfn.

Существует улучшенная версия алгоритма, называемая Triple DES или 3DES. Скорость алгоритма снизилась трижды, но система оказалась значительно более устойчива к полному перебору за счёт утроенной длины ключа (168 бит и 112 секретных бит). Опционально можно выбрать удвоенный ключ (112 бит и 80 секретных бит). По состоянию на 2011 год трехключевая система сохраняет свою безопасность, однако двуключевая версия с 80-битным уровнем безопасности больше не удовлетворяет современным требованиям[19].

ГОСТ 28147-89

Файл:Feistel function GOST.png
Вид функции, используемой в сети Фейстеля алгоритма шифрования ГОСТ 28147-89.

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

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

AES / Rijndael

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

Связь с другими криптографическими примитивами

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

См. также

Примечания

Шаблон:Примечания

Литература

Внешние ссылки

  1. ↑ Block Ciphers — Introduction and overview — http://cacr.uwaterloo.ca/hac/about/chap7.pdf Шаблон:Wayback
  2. ↑ Шаблон:Source
  3. ↑ Шаблон:Книга
  4. ↑ Шаблон:Книга
  5. ↑ Шаблон:Книга
  6. ↑ Шаблон:Книга
  7. ↑ Шаблон:Книга
  8. ↑ Шаблон:Книга, pages 166—167.
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite web
  11. ↑ Шаблон:Citation Шаблон:Cite web
  12. ↑ Шаблон:Citation
  13. ↑ Шаблон:Статья
  14. ↑ Шаблон:Citation Шаблон:Cite web
  15. ↑ Шаблон:Статья
  16. ↑ Шаблон:Книга
  17. ↑ Шаблон:Книга
  18. ↑ Шаблон:Citation Шаблон:Cite web
  19. ↑ Шаблон:Cite web
  20. ↑ Nicolas T. Courtois. Security Evaluation of GOST 28147-89 In View Of International Standardisation Шаблон:Wayback. Cryptology ePrint Archive: Report 2011/211
  21. ↑ Шаблон:Cite web
  22. ↑ Шаблон:Cite web
  23. ↑ Шаблон:Cite web

Шаблон:Выбор языка Шаблон:Симметричные криптоалгоритмы

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Блочный_шифр&oldid=9203170