. Минимализм в криптографии, или схема Even–Mansour
Минимализм в криптографии, или схема Even–Mansour

Минимализм в криптографии, или схема Even–Mansour

Израильские ученые Шимон Ивэн (Shimon Even) и Ишай Мансур (Yishay Mansour) еще в 1997 году задались вопросом: насколько минимальной конструкцией может обладать стойкий блочный шифр? Под минимальностью они подразумевали число конструктивных элементов в схеме шифра, а под стойкостью — любую (формально верную) оценку снизу сложностей атак на этот шифр. Как говорится, под катом — описание минимального (и по сей день) блочного шифра с доказуемой стойкостью.

Лирическое отступление

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

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

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

Израильские ученые Шиман Ивэн (Shimon Even) и Ишэй Мансур (Yishay Mansour) в [EM97] предложили способ построить блочный шифр, обладающий доказуемой стойкостью, на основе единственной случайно выбранной подстановки из .

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

Множества, наборы
  • — неупорядоченное множество элементов
  • — упорядоченное множество элементов
Начертания
  • — пространства, используемые криптосистемами
  • — алгоритмы, модели вычислений
  • — оракулы
  • — множества, выработанные алгоритмами
  • — подстановки
  • — задачи
Обозначения
  • — множество открытых текстов (сообщений)
  • — открытые тексты
  • — множество шифртекстов (криптограмм)
  • — шифртексты
  • — множество ключей
  • — ключи
  • — истинный ключ
  • — функция шифрования
  • — функция расшифрования
  • — оракулы, реализующие подстановки
  • — оракулы, реализующие функции на ключе
  • — вероятность успеха алгоритма
  • — время выполнения алгоритма
Определения
  • — множество открытых текстов (plaintexts),
  • — множество шифртекстов (ciphertexts),
  • — множество ключей (keys),
  • — (инъективная) функция шифрования (encipher):
  • — функция расшифрования (decipher):

Классическая схема Even–Mansour

Израильские ученые Шимон Ивэн (Shimon Even) и Ишай Мансур (Yishay Mansour) в своей работе предложили блочный шифр c доказуемой криптостойкостью, для которого требуется всего одна подстановка , которая случайным (или псевдослучайным) образом выбирается из множества всех перестановок над открытыми текстами.

При этом предполагается, что выбранная подстановка не является частью ключа, и доступна любому атакающему в виде некоторого «черного ящика».

Утверждается, что, с точки зрения атакующего, предложенный шифр практически неотличим от идеального случайного шифра, и вероятность успешного вскрытия системы (восстановления секретного ключа ) полиномиально мала (основной результат — Теорема 2, Следствие 2.1 из нее, и Теорема 3).

Утверждается также, что использование псевдослучайной подстановки вместо истинно случайной подстановки не изменяет показанной стойкости шифра.

Описание

Пусть , и — подстановка, выбранная из множества всех подстановок над множеством открытых текстов, а — обратная к ней.

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

Пространства открытых и шифртекстов являются пространствами двоичных –мерных векторов: , а пространство ключей системы является пространством двоичных векторов размерности : .

Секретный ключ является упорядоченной парой двух –мерных подключей (половин) и ; каждый подключ выбирается случайно из пространства –мерных двоичных векторов с равной вероятностью .

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

Шифрование открытого текста с помощью секретного ключа и выбранной подстановки производится следующим образом:

а расшифрование шифртекста с помощью ключа и выбранной подстановки — следующим:

Действительно, просто? Взяли сообщение, поксорили с первой половиной ключа, по открытой и доступной всем табличке заменили, поксорили со второй половиной ключа, и получилась криптограмма. Здорово, правда? Почему же никто не использует эту схему на практике? Ведь она намного проще AES, да и DES. Самый простой блочный шифр. Где здесь подвох?

О минимальности схемы

    Отсутствует сложение с первым подключом.

Функция шифрования имеет вид:

Злоумышленник может легко вычислить секретный ключ , зная подстановку :

Функция шифрования имеет вид:

Злоумышленник может легко вычислить секретный ключ , зная подстановку :

Функция шифрования имеет вид:

Злоумышленник может легко вычислить секретный ключ :

О стойкости схемы

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

Далее, если подстановка, значение которой вычисляет оракул ( ), выбрана, а шифрование и расшифрование осуществляется на фиксированном ключе , то индекс у обозначений оракулов мы будем опускать: .

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

Назовем такие пары –парами, а набор всех –пар, выработанных некоторым алгоритмом в результате его выполнения, обозначим через , или просто .

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

Назовем такие пары –парами, а набор всех –пар, выработанных некоторым алгоритмом в результате его выполнения, обозначим через , или просто .

Определение –пары и называются пересекающимися, если , либо .

Аналогичное определение можно сформулировать и для –пар.

Определение –пары и называются пересекающимися, если , либо .

  • пересекающиеся –пары совпадают;
  • пересекающиеся –пары совпадают.

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

Под временем выполнения алгоритма будем понимать число запросов, выполненных этим алгоритмом к оракулам .

Определение Функция называется полиномиально мaлой (polynomially negligable), если для любого полинома найдется , такое, что для всех выполняется :

Определение Задачу назовем трудной, если вероятность успеха любого решающего ее алгоритма, полиномиально ограниченного по времени, полиномиально мала.

Описание формальной модели

В предложенной в [EM97] модели злоумышленник в полном объеме обладает знаниями об устройстве шифра и выбранной подстановке . Для вскрытия системы злоумышленник использует некоторый алгоритм , который может решать одну из двух задач: задачу дешифрования , или задачу построения новой пары открытый текст / шифртекст .

Задача дешифрования ( )
  • (ограниченный по ) оракул расшифровывает всякий –мерный двоичный набор (шифртекст) , кроме , на ключе :

Алгоритм успешно вскрывает систему, если .

Задача построения новой пары открытый текст / шифртекст ( )

Под задачей построения новой пары текстов ( , existential forgery problem) понимается проблема построения такой пары , которая бы удовлетворяла соотношению , и при этом не состояла из запроса и ответа к одному из оракулов . При этом всякий алгоритм , используемый злоумышленником для решения задачи, может обращаться ко всем четырем оракулам .

Успехом алгоритма считается получение новой корректной пары открытого текста и шифртекста .

Сведение задачи построения пары текст / шифртекст к задаче вскрытия ( )

Теорема 1 (EFP to CP reduction) Пусть , и существует алгоритм , решающий задачу вскрытия за время с вероятностью успеха , тогда существует алгоритм , строящий пару текстов за то же самое время с вероятностью успеха :

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

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

  1. Зафиксируем шифртекст ;
  2. Начнем выполнение алгоритма ;
  3. Выберем случайное , распределенное равномерно на отрезке ;
  4. Остановим выполнение алгоритма после запросов к оракулам;
  5. Если в запросе алгоритм запрашивает шифрование , то выполнение алгоритма прекращается, и исходная пара — .

Следствие 1.1 Пусть задача трудна (для любого полиномиального решающего алгоритма его вероятность успеха полиномиально мала), тогда задача тоже трудна (для любого полиномиального решающего алгоритма его вероятность успеха полиномиально мала).

Следует заметить, что обратное утверждение (сводимость ) не верно в общем случае: в некоторых классах криптосистем существуют открытые тексты, такие, что соответствующие им шифртексты заранее известны и не зависят от ключа (например, в схеме RSA).

Стойкость системы при использовании случайной подстановки
  • показать, что на любом этапе полиномиально ограниченной атаки, множество «хороших» ключей (ключей, истинность которых злоумышленник ни подтвердить, ни опровергнуть на основе имеющихся у него данных) экспоненциально велико (Лемма 1);
  • показать, что злоумышленник может «угадать» истинный ключ только с полиномиально малой вероятностью (Теорема 2);
  • показать, что злоумышленник собрать достаточно данных для выявления истинного ключа за полиномиальное число запросов к оракулам (Теорема 2).

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

Очевидно, такой ключ удовлетворяет этой –паре, ведь

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

Аналогичное определение можно сформулировать и для вторых подключей .

Определение Второй подключ ключа называется плохим относительно алгоритма и выработанных им множеств и , если существуют –пара и –пара , такие, что ; и хорошим в другом случае:

Определение Ключ называется хорошим, если оба подключа и являются хорошими, и плохим в другом случае.

Утверждение 2 (True subkeys share goodness) При секретном ключе и перестановке подключи и либо оба являются хорошими, либо плохими:

Лемма 1 (The fraction of bad keys) Пусть алгоритм выработал множества и непересекащихся –пар и –пар соответственно, тогда доля плохих ключей в ключевом пространстве не превышает .

Согласно определению плохого подключа, некоторый подключ является плохим, если найдется –пара и –пара , такие, что

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

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

Оба подключа выбираются из , что позволяет получить верхние оценки для числа плохих ключей:

и доли плохих ключей в ключевом пространстве :

  • подстановка неотличима от истинной подстановки на полученных множестве –пар:
  • подстановка неотличима от истинной подстановки на полученных множестве –пар:

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

Лемма 2 (Distribution of true key candidates) Пусть и — множества –пар и –пар соответственно, а — истинный ключ, тогда вероятность того, что некоторый ключ является секретным ключом , одинакова для всех :

При условии, что ключи распределены равномерно:

и подстановка выбрана случайно:

получаем, что искомая вероятность является условной вероятностью

Воспользуемся формулой Байеса:

Легко видеть, что доказательство леммы сводится к доказательству утверждения .

Покажем, что для любого ключа множество –пар можно преобразовать в эквивалентное множество –пар , ограничивающих подстановку , по следующему правилу:

Очевидно, что, при фиксированной подстановке , если ключ удовлетворяет –паре , то он удовлетворяет и –паре . Заметим также, что , потому что указанное отображение задает биекцию .

Так, выражение для вероятности принимает следующий вид:

Если при этом ключ является хорошим, то множества –пар и не пересекаются по определению хорошего ключа:

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

Теорема 2 (Boundary for success probability of any solving ) Пусть подстановка выбрана случайно из и ключ выбран случайно из , тогда для вероятности успеха алгоритма , решающего задачу , справедлива следующая верхняя оценка:

где — число запросов к оракулам и , а — число запросов к оракулам и .

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

Обозначим через и множества –пар и –пар, порожденные алгоритмом при первых запросах:

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

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

  • запрос к оракулу :
    • пара , в таком случае выработанные алгоритмом множества не изменятся, и ключ останется хорошим;
    • пара , в таком случае имеют место следующие равенства:

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

    Число плохих подключей (на шаге ) по определению плохого подключа равно числу различных сумм , где индекс пробегает по всем –парам множества , а индекс — по всем –парам множества :

    Учитывая полученные выше равенства для и , получаем:

    По аналогичным соображениям, число плохих подключей тоже не больше :

    Тогда число плохих ключей на шаге оценивается следующим образом:

    и искомая разность равна:

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

    • запрос к оракулу
    • запрос к оракулу
      • пара , в таком случае выработанные алгоритмом множества не изменятся, и ключ останется хорошим;
      • пара , в таком случае имеют место следующие равенства:

      Подсчитаем число ключей , которые стали плохими в результате формирования такой пары .

      Число плохих подключей (на шаге ) по определению плохого подключа равно числу различных сумм , где индекс пробегает по всем –парам множества , а индекс — по всем –парам множества :

      Учитывая равенства для и , получаем:

      По аналогичным соображениям, число плохих подключей тоже не больше :

      Тогда число плохих ключей на шаге оценивается следующим образом:

      и искомая разность:

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

      • запрос к оракулу .

      Делаем выводы: –пара , выработанная на шаге , приведет к тому, что ключ окажется плохим, с вероятностью, не большей , тогда ключ станет плохим в результате хотя бы одного из таких запросов ( ), не больше .

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

      В другом случае алгоритм «угадывает» корректную –пару :

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

      Заметим, что значение подстановки в точке не ограничено ни одной –парой множества в силу того, что ключ хороший и ни одной –парой в силу того, что «угаданная» пара — новая. Так, может принимать любое из «значений», и искомая вероятность

      Тогда вероятность успеха алгоритма :

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

      Стойкость системы при использовании псевдослучайной подстановки

      Предложенный в [EM97] шифр сохраняет показанное свойство криптостойкости и в том случае, если подстановка выбрана псевдослучайно.

      Для доказательства этого утверждения достаточно пояснить понятие псевдослучайной подстановки.

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

      Другими словами, в представленной модели вычисления с оракулами, псевдослучайная подстановка неотличима от случайной. Поэтому имеет место следующая теорема.

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

      В продолжение

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