10.08 // Swap or Not: простейшие блочные шифры претендуют на стойкость

Несмотря на множество предложенных блочных шифров, в их основе лежат только два варианта конструкций: нечто, что по существу выглядит как некоторая разновидность сети Файстеля (напр. DES, FEAL, MARS, RC6) или SP-сеть (Rijndael, Safer, Serpent, Square). Соответствено, в литературе имеется описание того, как можно сконструировать псевдослучайные перестановки (Pseudo Random Permutations — PRP) из псевдослучайных функций (Pseudo Random Functions — PRF) для доказуемо-безопасных сетей Файстеля, так же как и для режимов операций, из которых могут быть созданы SP-сети (сети замены-перестановки на обратимых операциях). Возможно, что никаких других фундаментально отличающихся путей создания блочных шифров просто не существует. Но может быть просто никто не замечал других возможностей.

Исследователи Ви Тан Хо, Филип Рогуэй (Кафедра компьютерных наук Университета Калифорнии, Дэвис, США) и Бен Моррис (Кафедра математики Университета Калифорнии, Дэвис, США) предложили принципиально новую конструкцию создания блочных шифров. Консультантами в работе служили Михир Беллэйр и Терент Спайс. Следует отметить, что Рогуэй и Беллейр — одни из ведущих специалистов в области доказуемой безопасности, поэтому их разработки привлекают заслуженное внимание.

Самым удивительным свойством новых шифров является минималистичная простота. Если не рассматривать реализации ключевого расписания (авторы их не представили, но их создание может быть делом будущего), то весь шифр может уместиться в короткий однострочник, понятный практически любому программисту-любителю. Другим удивительным свойством является использование одной единственной линейной операции – XOR, которая задаёт перестановки, что приводит к созданию нелинейности. Наконец, шифр, основанный на таком прототипе, возможно будет реализован с ничтожными затратами памяти на исполнение.

Для создания новых шифров исследователи предложили конструкцию swap-or-not-сетей. Сложно перевести это столь же коротким термином, как вариант это может быть "перестановка-обмен с исключениями". В основе идеи лежат хорошо известные алгоритмы математики и комбинаторики первой половины XX века, связанные с генерацией перестановок, аналогичных перетасовке карточной колоды. Исследователям удалось привести первичные доказательства, что такие алгоритмы превосходят по соотношению затрат к стойкости обычные алгоритмы конвертирования PRF → PRP, используемые для создания блочных шифров. Помимо этого, такие алгоритмы претендуют на наилучшее решение проблемы шифрования с сохранением длины и формата сообщения (Format-Preserving Encryption — FPE), когда необходимо шифровать данные, имеющие размер меньше блока традиционного шифра, но при этом именно в блочном режиме, а не наложением гаммы. Такая задача может возникнуть при шифровании номеров PIN, социального страхования, записей в базах данных, использовании недвоичных систем счисления, с возможностью как компромисса в сторону пониженной стойкости, так и с сохранением стойкости на обычном уровне.

Несмотря на то, что алгоритм удивительно простой, следует по порядку рассмотреть несколько вариантов — от простого к сложному, хотя каждый из них сам по себе может стать прототипом каких-либо полезных реализаций.

Пусть первое значение X — это n-битовый исходный текст из множества χ = {0,1}ⁿ. Пусть на каждом раунде значение X подвергается операции XOR с n-битовым раундовым подключом K_i, результат записывается как X'. Затем следует сравнить, какое значение получилось больше: X или X' и записать большее значение в X^ˆ. Затем нужно применить n-битовую функцию раунда F_i(X^ˆ), которая является уникальной для каждого раунда и выдаёт псевдослучайную свёртку в виде однобитового значения F_i: {0,1}ⁿ → {0,1}. Если выход этой функции равен единице, то X заменяется на X' — на свою парную точку, в противном случае на этом раунде не происходит никаких изменений.

Поскольку операция X → K_i ⊕ X — это инволюция (самообратимое преобразование), то расшифровка происходит простым прохождением раундов в обратном порядке.

К вопросу о конкретной реализации функции F_i мы вернёмся в конце работы, а сейчас рассмотрим более подробно, почему авторы предложили рассматривать блочный шифр, как перетасовку колоды карт.

Если существует некоторый метод по перетасовке колоды N карт, то он определяет соответствующий метод шифрования N точек: достаточно поместить карту на каждую позицию X ∈ [N], где [N] = {0, 1, …, N-1}; перетасовать карты; затем посмотреть на какой позиции оказалась карта, которая изначально была на позиции X. Такую позицию можно назвать шифртекстом Y для X. Случайность, используемая для шифрования, определяется ключом.

Первое, что нужно, чтобы использовать перетасовку карт в качестве вычислительно приемлемого шифра — это требование вычислений с забыванием или рассеянных вычислений, идея которых была высказана Мони Наором. В забывчивой перетасовке можно следить за траекторией одной карты, не обращая внимания на другие карты в колоде. Большинство известных алгоритмов перетасовок таковыми не являются. Наиболее известный алгоритм рассеянной перетасовки — алгоритм Торпа, поэтому он подходит под метод swap-or-not. Вот как он выглядит в качестве перестановки.

Для колоды из N = 2ⁿ карт, каждая из которых размещена на позиции X ∈ [N] случайным образом выбирается n-битовый ключ K. Для каждой пары размещений {X, K ⊕ X} подбрасывается монета b для получения одного бита энтропии. Если выпадает "орёл" или бит "1", то X и K ⊕ X меняются местами. Если "0", то ничего не происходит. Используя независимые честные монеты процесс может быть повторён r раундов для достижения требуемого качества перемешивания ("стойкости").

Если алгоритм swap-or-not-перетасовки со второй иллюстрации перевести обратно на язык криптографии, то мы получим первый алгоритм, swap-or-not-шифр. Это лишь разные взгляды на один и тот же процесс. Случайный выбор парных карт, определяемый ключом K в i-той перетасовке, определяется раундовым подключом K_i в шифровании. Случайный бит b, выкидываемый на каждом раунде в перетасовке пары {X, K ⊕ X}, в случае шифрования соответствует F_i(X^ˆ).

Теперь рассмотрим этот алгоритм шифрования с обобщённой областью определения:

Вместо того, чтобы использовать операцию XOR, или иначе говоря, группу G = ({0, 1}ⁿ, ⊕), алгоритм может быть исполнен на любой конечной абелевой группе G = ([N], +]). Для определённости, пусть элементы этой группы нумеруются с нуля: [N] = {0, …, N – 1}. Если с операцией XOR шифр мог иметь размер блока, равный любой величине степени двойки, то в случае с произвольной группой в этом нет необходимости. Размер блока шифра может быть любым конечным числом, для этого оператор группы можно задать, к примеру, как сложение по модулю N. Нужно лишь выбирать равномерно и случайно значение K из области N, которое также не является степенью двойки, т.е. не относится к {0,1}ⁿ. Вместо парных обменов {X, K ⊕ X} будут использоваться обмены {X, K – X}, а для замены выбором будет X' ← k_i – X вместо X' ← K_i ⊕ X. Вот и все отличия от первого алгоритма.

Авторы анализируют стойкость своей swap-or-not-конструкции на основании основополагающей работы Любы-Ракоффа, в которой подразумевается, что соответствующие части преобразования выбираются равномерно и однородно. Тогда алгоритм на третьей иллюстрации можно описать как преобразование SN [r, N, +]: k x [N] → [N], в виде блочного шифра E с количеством раундов r, областью определения сообщений [N], указанным оператором группы "+" и где область определения значений ключей включает все возможные подключи K₁, …, K_r ∈ [N] и всех возможных раундовых функций F₁, …, F_r: [N → {0, 1}]. Таким образом ключ KF для данного шифра состоит из равномерно выбранных раундовых подключей K_i и F_i.

Для оценки стойкости блочного шифра его сравнивают со стойкой псевдослучайной перестановкой ("strong-PRP"). Сложность нахождения различителя между такой перестановкой и блочным шифром определяет уровень защиты от атак с подобранным шифртекстом, которые включают в себя и атаки с известным и подобранным открытым текстом. Для описания такой модели атакующего A, пытающегося взломать блочный шифр E, помещают в один из двух миров. В первом мире атакующий имеет доступ к оракулу E_KF(∙) для случайных KF, а также доступ к его обратному (расшифровывающему) оракулу E^-1_KF(∙). В другом мире атакующий имеет дело с равномерной случайной перестановкой π: [N] → [N], также как и с обратной перестановкой, π^-1(∙). Цель атакующего — определить в каком из миров он находится: в мире управляемом сконструированным шифром или в мире, управляемом случайным оракулом, задающим наборы фиксированных случайных перестановок. В общем виде его успех в этом деле описывается вероятностной зависимостью от числа запросов q к определяемому оракулу:

Исследователям удалось вывести конкретное значение, которое равно:

Грубо говоря, достаточно минимум r = 6 lg N раундов swap-or-not для начала хорошего приближения к CCA-стойкости. После этого преимущество противника падает обратно-экспоненциально в зависимости от r. Это превосходит стойкость сетей Файстеля и перестановок Торпа.

На графике показаны результаты приближения CCA-преимущества для q запросов при N = 2⁶⁴. По оси x значения пронормированы в виде log₂(q). Два правых графика показывают результаты шифра swap-or-not с восьмью проходами (512 раундами) (SN-8) и с 10 (SN-10) (один проход определяется как верхнее округление lg N раундов). Для сравнения: два левых графика — это сбалансированная сеть Файстеля по классическим результатам Любы-Ракоффа для четырёх раундов (LR-4) и шестираундовому результату Патарина (LR-6). Посредине показаны перестановки Торпа (TH-8, TH-20).

В качестве простого числового примера, можно показать, что swap-or-not шифрование 64-битных строк за 1200 раундов с использованием случайных раундовых функций позволяет достичь максимального CCA-преимущества менее, чем 10^-10, даже если противник может сделать q = 2⁶³ запросов. Несмотря на большое число раундов, никакая другая конструкция не обеспечивает безопасность при q близком к N. Кроме того, можно предположить, что раунды swap-or-not будут исполняться эффективнее традиционных сетей Файстеля.

Авторы также приводят вывод информационно-теоретической и комплексно-теоретической оценки стойкости алгоритма.

Однако, можно заметить, что наличие нереализованной идеальной функции F в каждом раунде делает алгоритм слишком теоретическим. Можно ли использовать какую-либо реальную функцию для получения однобитовой свёртки? На этот вопрос авторы отвечают утвердительно.

В качестве такой функции возможно использование двоичного скалярного произведения — цепочки XOR-операций между битами текущего состояния раунда и некоего раундового подключа L_i, дающей на выходе один бит:

Используя два раундовых подключа K_i и L_i возможно представить полноценный алгоритм:

Здесь отмечается, что использование наибольшего значения max для выбора {X, X'} является обязательным требованием, в противном случае, при использовании минимума, X = 0ⁿ всегда будет шифроваться как 0ⁿ.

Итак, авторы представили простейший полноценный, обоснованно-стойкий алгоритм блочного шифрования, обладающий свойствами замены и перемешивания (лавинным эффектом), работающий только на операции XOR.

Читатель, знакомый с основами доказуемой безопасности, может почуять подвох в этом месте, о котором говорят сами авторы. При замене идеальной случайной функции F на сконструированную, доказательства стойкости теряют свою строгость и простейшее приближение r = 6n (например 6 ∙ 128 = 768 раундов) не может быть применено.

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

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

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

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

Работа исследователей была проведена на гранты Национального Научного Фонда США по программе финансирования математических наук. По их утверждению, открытие нового метода создания шифров явилось случайным побочным результатом исследований в области создания алгоритмов блочного шифрования с сохранением формата сообщений (FPE). Пока ключевого расписания к данным алгоритмам не создано, в работе предлагается использовать swap-or-not-сети для FPE-шифрования совместно с шифром AES.

P.S.
Работа авторов заслужила честь открыть конференцию CRYPTO-2012.
А на Rump-сессии в ходе закрытия конференции Серж Водене попытался сделать "закрытие" этого "открытия". В докладе "Конец шифрования на перетасовке карт?" он указал на уязвимость в практической реализации алгоритма, в том виде как он был предложен авторами. Он отметил, что выбор максимального значения не может быть использован для замены значений, т.к. это в некоторых случаях приводит к утечке информации об определённых битах ключа и превращению алгоритма в линейную функцию. Для спасения алгоритма он предложил реализовать идею Генри Гильберта в использовании функции выбора X^ˆ ← (X + X') mod 2^l.

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

Источник: Cryptography and Security Archive, Advances in Cryptology — CRYPTO 2012, Crypto 2012 rump session.