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

Теоретические исследования

Сети Фейстеля были широко изучены криптографами в силу их обширного распространения. В 1988 году Майкл Люби }} и провели исследования сети Фейстеля и доказали, что если раундовая функция является криптостойкой псевдослучайной, и используемые ключи независимы в каждом раунде, то 3 раундов будет достаточно для того, чтобы блочный шифр являлся псевдослучайной перестановкой, тогда как четырёх раундов будет достаточно для того, чтобы сделать сильную псевдослучайную перестановку.

«Псевдослучайной перестановкой» Люби и Ракофф назвали такую, которая устойчива к атаке с адаптивным выбором открытого текста, а «сильной псевдослучайной перестановкой» — псевдослучайную перестановку, устойчивую к атаке с использованием выбранного шифрованного текста.

Иногда в западной литературе сеть Фейстеля называют «Luby-Rackoff block cipher» в честь Люби и Ракоффа, которые проделали большой объём теоретических исследований в этой области.

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

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

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

DES – блочный алгоритм, то есть при шифровании исходное сообщение переводится в двоичный код, а затем разбивается на блоки и каждый блок отдельно зашифровывается (расшифровывается). По стандарту (принят в 1977 году) размер блока DES равен 64 бита, то есть используя 8-ми битовую кодировку ASCII, применяемую в те времена, получим в одном блоке – 8 символов.

Теперь же в основном используется 16-ти битная кодировка Юникода (UTF-16), поэтому, чтобы сохранить длину блока равную 8-ми символам, увеличим размер блока DES до 128 бит.

Алгоритм DES. Шаги

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

• довести исходное сообщение до такого размера (в битах), чтобы оно нацело делилось на размер блока (sizeOfBlock = 128 бит);
• разделить исходное сообщение на блоки;
• довести длину ключа до длины половины блока;
• перевести ключ в бинарный формат (в нули и единицы);
• провести над каждым блоком прямое преобразование сетью Фейстеля в течении 16-ти раундов. После каждого раунда необходимо выполнять циклический сдвиг ключа на заданное количество символов;
• соединить все блоки вместе; таким образом получим сообщение, зашифрованное алгоритмом DES.

Расшифровка DES производится по аналогии. Используется обратное преобразование сетью Фейстеля.

Алгоритм DES. Сеть Фейстеля

Сеть Фейстеля используется в алгоритме DES для зашифровывания (прямое преобразование сетью) и расшифровывания (обратное преобразование). Эти преобразования изображены на рисунках 1 и 2 соответственно.

Рисунок 1. Прямое преобразование сетью Фейстеля

Рисунок 2. Обратное преобразование сетью Фейстеля

Чтобы вам было понятнее, давайте рассмотрим один раунд прямого преобразования сетью Фейстеля.

На i-й итерации исходный блок делится пополам – левая часть обозначается L, правая R. Над R и ключом k_i вычисляется какая-либо выбранная логическая функция f (мы будем использовать XOR). Затем выполняется вычисление логической операции “исключающее или” над L и вычисленным ранее значением функции (L xor f). Старое значение R переносится в левую часть блока, а в правую часть заносится значение L xor f. И последняя операция раунда – нужно выполнить циклический сдвиг ключа: key_i+1 = key_i >> shiftKey (при расшифровке key_i-1 = key_i << shiftKey); shiftKey – количество символов, на которое необходимо циклически сдвинуть ключ.

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

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

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

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

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

Не менее важную роль играет размер ключа. Ранний шифр 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 с известной константой: или более сложная связь вида , где – произвольная функция, выбранная атакующим. В реальной жизни такие зависимости могут возникнуть при сбоях в аппаратном обеспечении или плохо спроектированных протоколах безопасности.

Модификации сети Фейстеля[править | править код]

При большом размере блоков шифрования (128 бит и более) реализация такой конструкции Фейстеля на 32-разрядных архитектурах может вызвать затруднения, поэтому применяются модифицированные варианты этой конструкции. Обычно используются сети с четырьмя ветвями. На рисунке показаны наиболее распространённые модификации. Также существуют схемы, в которых длины половинок L{\displaystyle L_{0}} и R{\displaystyle R_{0}} не совпадают. Такие сети называются несбалансированными.

Алгоритм IDEAправить | править код

Основная статья: IDEA

Источник :

Схема одной итерацииполного раунда алгоритма IDEA

В алгоритме IDEA используется глубоко модифицированная сеть Фейстеля. В нём 64-битные входные блоки данных (обозначим за X{\displaystyle X_{0}}) делятся на 4 подблока длиной 16 бит X={X()X(1)X(2)X(3)}{\displaystyle X_{0}=\{X^{(0)}X^{(1)}X^{(2)}X^{(3)}\}}. На каждом этапе используется 6 16-битных ключей. Всего используется 8 основных этапов и 1 укороченный.

Формулы для вычисления значения подблоков на i-м раунде (для раундов c 1-го по 8-й):

предварительные вычисления:

Ai=((Xi−1()∗Ki(1))⊕(Xi−1(2)+Ki(3)))∗Ki(5);{\displaystyle A_{i}=((X_{i-1}^{(0)}*K_{i}^{(1)})\oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)};}

Bi=(((Xi−1(1)+Ki(2))⊕(Xi−1(3)∗Ki(4))+Ai)∗Ki(6));{\displaystyle B_{i}=(((X_{i-1}^{(1)}+K_{i}^{(2)})\oplus (X_{i-1}^{(3)}*K_{i}^{(4)})+A_{i})*K_{i}^{(6)});}

Ci=((Xi−1(1)+Ki(2))⊕(Xi−1(3)∗Ki(4))+((Xi−1()∗Ki(1))⊕(Xi−1(2)+Ki(3)))∗Ki(5))∗Ki(6);{\displaystyle C_{i}=((X_{i-1}^{(1)}+K_{i}^{(2)})\oplus (X_{i-1}^{(3)}*K_{i}^{(4)})+((X_{i-1}^{(0)}*K_{i}^{(1)})\oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)})*K_{i}^{(6)};}

финальные вычисления:

Xi() = (Xi−1()∗Ki(1))⊕Bi;{\displaystyle X_{i}^{(0)}\ =\ (X_{i-1}^{(0)}*K_{i}^{(1)})\oplus B_{i};}

Xi(1) = (Xi−1(2)+Ki(3))⊕Bi;{\displaystyle X_{i}^{(1)}\ =\ (X_{i-1}^{(2)}+K_{i}^{(3)})\oplus B_{i};}

Xi(2) = (Xi−1(1)+Ki(2))⊕(Ai+Ci);{\displaystyle X_{i}^{(2)}\ =\ (X_{i-1}^{(1)}+K_{i}^{(2)})\oplus (A_{i}+C_{i});}

Xi(3) = (Xi−1(3)∗Ki(4))⊕(Ai+Ci),{\displaystyle X_{i}^{(3)}\ =\ (X_{i-1}^{(3)}*K_{i}^{(4)})\oplus (A_{i}+C_{i}),}

где Ki(j){\displaystyle K_{i}^{(j)}} — j-й ключ на i-м раунде.

Формула для вычисления 9-го раунда:

X9() = X8()∗K9(1);{\displaystyle X_{9}^{(0)}\ =\ X_{8}^{(0)}*K_{9}^{(1)};}

X9(1) = X8(2)+K9(2);{\displaystyle X_{9}^{(1)}\ =\ X_{8}^{(2)}+K_{9}^{(2)};}

X9(2) = X8(1)+K9(3);{\displaystyle X_{9}^{(2)}\ =\ X_{8}^{(1)}+K_{9}^{(3)};}

X9(3) = X8(3)∗K9(4).{\displaystyle X_{9}^{(3)}\ =\ X_{8}^{(3)}*K_{9}^{(4)}.}

Выходом функции будет

Y={X9()X9(1)X9(2)X9(3)}.{\displaystyle Y=\{X_{9}^{(0)}X_{9}^{(1)}X_{9}^{(2)}X_{9}^{(3)}\}.}

Можно заметить, что s- и p-блоки в чистом виде не используются. В качестве основных операций используются:

• умножение по модулю 216+1=65537{\displaystyle 2^{16}+1=65537};
• сложение по модулю 216=65536{\displaystyle 2^{16}=65536}.

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

Основная статья: Режим шифрования

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

1. Режим электронной кодовой книги (ECB — Electronic Codebook): обычное использование DES как блочного шифра. Шифруемый текст разбивается на блоки, при этом каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.7).

   Рис.7 Режим электронной кодовой книги — ECB

2. Режим сцепления блоков шифротекста (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок Mi{\displaystyle M_{i}} i>=1, перед зашифровыванием складывается по модулю 2 с предыдущим блоком зашифрованного текста Ci−1{\displaystyle C_{i-1}}. Вектор C{\displaystyle C_{0}} — начальный вектор, он меняется ежедневно и хранится в секрете.

   Рис.8 Режим сцепления блоков — СВС

3. Режим обратной связи по шифротексту (Cipher Feedback) (см. Рис.9). В режиме CFB вырабатывается блочная «гамма» Z,Z1,…{\displaystyle Z_{0},Z_{1},…}Zi=DESk(Ci−1){\displaystyle Z_{i}=DES_{k}(C_{i-1})} Ci=Mi⊕Zi{\displaystyle C_{i}=M_{i}\oplus Z_{i}}. Начальный вектор C{\displaystyle C_{0}} является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом.

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

4. Режим обратной связи по выходу (OFB — Output Feedback) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z,Z1,…{\displaystyle Z_{0},Z_{1},…} Zi=DESk(Zi−1)Ci=Mi⊕Zi{\displaystyle Z_{i}=DES_{k}(Z_{i-1})C_{i}=M_{i}\oplus Z_{i}}, i>=1

   Рис.10 Режим обратной связи по выходу — OFB

Достоинства и недостатки режимов:

В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста Ci{\displaystyle C_{i}} приводит к искажению после расшифрования только соответствующего открытого блока Mi{\displaystyle M_{i}}, поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

ГОСТ 28147-89

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

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

Схема работы ГОСТ 28147-89

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

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

• простой замены
• гаммирование
• гаммирование с обратной связью
• режим выработки имитовставки

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

Основа алгоритма шифра — сеть Фейстеля с 32 циклами преобразования. Его раундовая функция очень простая: складывается 32-разрядный подключ по модулю 232, результат проходит через слой S-блоков, и этот результат сдвигается влево на 11 бит. В результате получается выход раундовой функции. На рисунке справа, одна строка представляет 32 бита.

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

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

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

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

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

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

Определения и вспомогательные процедуры

Современное использование

Общие принципы

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

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

Электронная почта

Одним из первых стандартов для асинхронного обмена сообщениями является протокол SMTP. Этот протокол, изначально используемый только для передачи электронной почты, в первоначальной своей реализации не обеспечивал конфиденциальности переписки при помощи сквозного шифрования. В 1991 году Филиппом Циммерманом был создан пакет программного обеспечения для шифрования электронной почты PGP. Библиотека получила широкое распространение по всему миру, поэтому у многих компаний возникло желание создавать собственное ПО, совместимое с PGP. После этого в 1997 году IETF окончательно определила набор стандартов для сквозного шифрования электронной почты, который назвали OpenPGP. OpenPGP реализован в программном обеспечении систем с открытым исходным кодом, таких как Enigmail для Thunderbird, а также в мобильных приложениях, таких как IPGMail для iOS и в системе управления ключами Openkeychain для Android и других.

В 1999 году Фондом свободного программного обеспечения была разработана реализация OpenPGP, которая получила название GnuPG. Она соответствует стандартам спецификации OpenPGP, выступая в качестве основы свободного программного обеспечения для большинства современных приложений с поддержкой PGP.

Мессенджеры и чаты

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

В 1998 году Джереми Миллером началась разработка проекта Jabber, который впоследствии получил название XMPP. XMPP предоставляет технологию для асинхронного обмена структурированными данными в распределенной сети с участием клиентов и серверов, поддерживающую уведомления о присутствии. Чтобы повысить уровень безопасности, в новых спецификациях протокола будет добавлена поддержка сквозного шифрования, так как сейчас информация, переданная посредством XMPP, по умолчанию не шифруется, хотя в нем и используются встроенные протоколы SASL и TLS Первоначально именно открытый стандарт протокола XMPP, разработанный IETF, использовался в большинстве систем мгновенного обмена сообщениями, таких как Google Talk..

Протокол OTR, выпущенный в 2004 году, является расширением XMPP с целью обеспечить сквозное шифрование. Он также обеспечивает оповещение пользователей, в отличие от PGP, которое впоследствии может быть использовано в качестве записи об установке соединения и идентификации участников. OTR в каком-то смысле можно считать обновлением безопасности по PGP, так как он не хранит долгосрочных открытых ключей, которые могут быть скомпрометированы. К недостаткам OTR можно отнести отсутствие поддержки групповых чатов и асинхронного обмена сообщений, так как он предназначен для синхронного обмена сообщениями между двумя людьми.

Несколько современных мессенджеров используют для шифрования Signal Protocol.

Примечания

1. Horst Feistel. Cryptography and Computer Privacy — www.prism.net/user/dcowley/docs.html  (англ.)
2. Хорст Файстель. Криптография и компьютерная безопасность. Перевод Андрея Винокурова — www.enlight.ru/crypto/articles/feistel/feist_i.htm
3. ↑ 12 А. Винокуров. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86 — www.enlight.ru/crypto/articles/vinokurov/gost_i.htm
4. ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ. Симметричные системы и блочные шифры — rain.ifmo.ru/cat/view.php/theory/coding/cryptography-2005/block
5. Журнал Byte. № 8 (60), август 2003. Современные алгоритмы шифрования — www.bytemag.ru/articles/detail.php?ID=6645, Сергей Панасенко
6. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. — М.: Горячая линия — Телеком, 2002. — 175 с. — (Специальность. Для высших учебных заведений). — 3000 экз. — ISBN 5-93517-075-2
7. On The Construction of Pseudo-Random Permutation: Luby-Rackoff Revisited
8. A. Menezes, P. van Oorschot, S. Vanstone. §7.6 IDEA // Handbook of Applied Cryptography — www.cacr.math.uwaterloo.ca/hac/about/chap7.pdf. — CRC-Press, 1996. — P. 263. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7
9. U.S. Patent 3,798,359 — patft.uspto.gov/netacgi/nph-Parser?patentnumber=3,798,359  — www.pat2pdf.org/pat2pdf/foo.pl?number=3,798,359 (англ.)
10. U.S. Patent 3,796,830 — patft.uspto.gov/netacgi/nph-Parser?patentnumber=3,796,830  — www.pat2pdf.org/pat2pdf/foo.pl?number=3,796,830 (англ.)
11. Arthur Sorkin. Lucifer, A Cryptographic Algorithm. Cryptologia, Выпуск 8(1), Январь 1984, стр. 22—41, с дополнением в выпуске 8(3), стр. 260—261