Блочный шифр

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

${\displaystyle C_{i}=R_{K_{i}}(C_{i-1})}$,

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

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

Пример SP-сети с 3 раундами.

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

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

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

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

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

${\displaystyle F=F(K_{i},R_{i-1})}$

Шифрование в ячейке Фейстеля

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

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

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

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

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

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

оригинальное изображение

криптограмма в режиме ECB

псевдослучайная последовательность

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

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

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

Чтобы преодолеть эти проблемы, были разработаны иные режимы работы[16][17], установленные международным стандартом ISO/IEC 10116[18] и определеные национальными рекомендациями, такие, как NIST 800-38A[19] и BSI TR-02102[20]

Общая идея заключается в использовании случайного числа, часто называемого вектором инициализации (IV). В популярном режиме сцепления блоков (англ. Cipher Block Chaining, CBC) для безопасности IV должен быть случайным или псевдослучайным. После его определения, он складывается при помощи операции исключающее ИЛИ с первым блоком открытого текста. Следующим шагом шифруется результат и получается первый шифроблок, который используем как IV для второго блока и так далее. В режиме обратной связи по шифротексту (англ. Cipher Feedback, CFB) непосредственному шифрованию подвергается IV, после чего складывается по модулю два (XOR, исключающее ИЛИ) с первым блоком. Полученный шифроблок используется как IV для дальнейшего шифрования. У режима нет особых преимуществ по сравнению с остальными. В отличие от предыдущих режимов, режим обратной связи вывода (англ. Output Feedback, OFB) циклически шифрует IV, формируя поток ключей, складывающихся с блоками сообщения. Преимуществом режима является полное совпадение операций шифрования и расшифрования. Режим счетчика (англ. Counter, CTR) похож на OFB, но позволяет вести параллельное вычисление шифра: IV объединяется с номером блока без единицы и результат шифруется. Полученный блок складывается с соответствующим блоком сообщения.

Следует помнить, что вектор инициализации должен быть разным в разных сеансах. В противном случае приходим к проблеме режима ECB. Можно использовать случайное число, но для этого требуется достаточно хороший генератор случайных чисел. Поэтому обычно задают некоторое число — метку, известную обеим сторонам (например, номер сеанса) и называемое nonce (англ. Number Used Once — однократно используемое число). Секретность этого числа обычно не требуется. Далее IV — результат шифрования nonce. В случае режима счетчика, nonce используется для формирования раундового ключа K_i[3]:

${\displaystyle K_{i}=E_{K}(nonce||i-1),i=1,..,n,}$ где i — номер раунда.

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

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

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

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

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

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

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

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

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

• Усечённый дифференциальный криптоанализ,
• Атака скольжением или сдвигом (англ. Slide attack),
• Атака бумерангом (англ. Boomerang attack),
• XSL-атака (англ. XSL attack, алгебраическая атака),
• Невозможный дифференциальный криптоанализ и так далее.

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

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

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

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

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

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

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

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