aprlv Aug 28 2015 at 11:20

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

15 min

17K

Information Security*Cryptography*Mathematics*

From sandbox

+26

Comments 22

hellman Aug 28 2015 at 13:45

К недостаткам логично отнести то что ключ 2n бит даёт стойкость всего n бит. За 2^n ломается очевидным mitm'ом. Соответственно, логично либо использовать один и тот же ключ два раза, либо использовать KDF (чтобы получить из одного ключа два). Есть ли у этих способов слабости, или, наоборот, доказательства стойкости?

aprlv Aug 28 2015 at 15:18

Мог бы раскрыть интригу в следующей публикации, но поскольку желающих нет, а вопрос есть, отвечу: да, действительно, стойкость в n бит. И да, есть модификация этой схемы, в которой подключи совпадают: $\underline{K}_1 = \underline{K}_2$ . Показано, что криптографическая стойкость схемы при этом существенно не меняется.

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

hellman Aug 28 2015 at 13:58

А где-нибудь 1-раундовый Even-Mansour все-таки используется? Я слышал только про Chaskey MAC.

aprlv Aug 28 2015 at 15:24

Честно отвечу, что классическая конструкция Even–Mansour (единственная итерация, и в качестве операции смешивания используется $\oplus$ ), — чисто теоретический результат.

Эта конструкция часто используется в качестве одного из раундов большого количества более сложных шифров, в том числе в LED и AES (Rijndael).

MichaelBorisov Aug 29 2015 at 12:05

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

Если иметь стойкую функцию подстановки (не хуже, чем случайную подстановку) — то думаю, вполне достаточно и одного раунда.

soniq Aug 28 2015 at 22:51

Остался вопрос, какая подстановка хорошая, а какая не очень

soniq Aug 28 2015 at 22:53

Я так понял, доказательство стойкости шифра свели к доказательству «хорошести» подстановки, про которую ничего не известно.

aprlv Aug 29 2015 at 00:01

soniq, невнимательно читали) Стойкость шифра доказана для тех случаев, в которых

подстановка $\pi$ выбрана случайно из $S_{2^n}$ (читайте, является истинно случайной биекцией множества в себя), либо
подстановка $\pi$ является псевдослучайной (например, представлена некоторой легко вычислимой биекцией, как в AES), но при этом полиномиально неотличима от случайной = (нет такого алгоритма, который за полиномиальное время мог бы определить, является ли данная подстановка псевдослучайной, или нет).

Шифр считаем стойким, если вероятность осуществить успешную атаку за полиномиальное время полиномиально мала (извините за каламбур):
$p = \mathcal{O}\!\left( \operatorname{poly}{(n)} \cdot 2^{-n}\right).$

soniq Aug 29 2015 at 08:47

Ах, security by obscurity, оракула же украдут за О(1).

aprlv Aug 29 2015 at 09:57

Не очень понимаю, что имеете в виду под кражей оракула)

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

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

MichaelBorisov Aug 29 2015 at 12:09

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

А почему, собственно, мы имеем только оракула? Я считаю, что злоумышленнику доступен не только оракул для функции подстановки, но и полное математическое описание этой функции, т.е. таблица либо формула.

Ведь для применяемых на практике шифров (AES и т.д.) функция подстановки (со всеми ее потрохами) является публичной, секретен только ключ.

aprlv Aug 29 2015 at 13:17

А почему, собственно, мы имеем только оракула?

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

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

Если подстановка случайная, то никакого математического (алгоритмического) описания у нее нет, а что касается таблицы замены — таблица вычислительно эквивалентна оракулу относительно временной сложности атаки, только занимает в памяти $n2^n$ бит, что совершенно неудобно.

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

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

MichaelBorisov Aug 29 2015 at 12:04

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

Для случайных подстановок длиной 32 бита уже можно реализовать шифрование на современной элементной базе. Интересно, не дает ли малая длина блока в 32 бит каких-то специфических слабостей шифра сама по себе?

Большое спасибо за статью, жду продолжения, тема очень интересна!

icoz Aug 29 2015 at 12:46

Либо я что-то недопонял, либо на текст длиной n символов нужен будет ключ длиной 2n символов. Это прорыв от одноразового блокнота! Здесь нужно в два раза больше ключей.

aprlv Aug 29 2015 at 13:28

icoz, это блочный шифр. Вам достаточно $2n$ бит секретного ключа, чтобы шифровать сколь угодно большое число блоков открытого текста (каждый блок имеет размер $n$ бит).

aprlv Aug 29 2015 at 13:26

MichaelBorisov Я бы не стал сравнивать криптостойкость одноразового блокнота со стойкостью предложенной схемы, а дело вот в чем:

Одноразовый блокнот является абсолютно криптостойким (по Шеннону), это означает, что, даже имея неограниченные ресурсы (память, и время), Вам не удасться дешифровать шифртекст. Такая криптостойкость безотносительна, она не зависит ни от ресурсов злоумышленника, ни от величины параметра $n$ .
Схема Even–Mansour гарантирует лишь стойкость от любых полиномиальных атак. При отсутствии ограничений по времени выполнения атаки, либо по памяти, доступной атакующему, шифр легко ломается. Конкретнее об этом расскажу тогда в следующей публикации.

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

MichaelBorisov Aug 29 2015 at 14:03

Поскольку схема Even-Mansour (поправьте меня, если ошибаюсь) является наиболее общим выражением концепции «блочный шифр» — то получается, что нельзя в принципе создать невзламываемых (эквивалентно концепции «одноразового блокнота») блочных шифров?

А что если применить не конкретно схему Even-Mansour, а более общую схему — ключезависимую подстановку на блоке? Например, чтобы подстановка была истинно случайной и сама являлась ключом? Сводится ли такая схема к Even-Mansour? Если нет — то ломается ли она теми же методами, что Even-Mansour?

aprlv Aug 29 2015 at 13:42

32 бита — это просто смешно, а не криптостойкость (с, А. Е. Жуков). Любой сможет взломать такой шифр на домашнем компьютере. Приемлимой длиной ключа сейчас считается 128 бит (поправьте меня, если ошибаюсь). Проблема практического применения этой схемы в том и заключается, что подстановки на таких больших множествах ~~хрен задашь~~ занимают много места в памяти.

MichaelBorisov Aug 29 2015 at 14:08

Длина блока и длина ключа — это разные вещи. Например, AES имеет длину блока 128 бит, а длина ключа может составлять 128, 192 или 256 бит. То же касается шифра ГОСТ: блок длиной 64 бит, ключ — 256 бит. Я спрашивал о том, дает ли малая длина блока (в частности, 32 бит) преимущества взломщику? Ключ при этом может иметь длину вплоть до 32*2^32 бит (если это будет истинно случайная таблица подстановки).

aprlv Aug 29 2015 at 20:19

Нет, про 32 бита — это я в ответ на Ваш пост писал:

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

Для случайных подстановок длиной 32 бита уже можно реализовать шифрование на современной элементной базе. Интересно, не дает ли малая длина блока в 32 бит каких-то специфических слабостей шифра сама по себе?

А в схеме Even-Mansour длина блока совпадает с фактической длиной ключа.

А что если применить не конкретно схему Even-Mansour, а более общую схему — ключезависимую подстановку на блоке? Например, чтобы подстановка была истинно случайной и сама являлась ключом? Сводится ли такая схема к Even-Mansour? Если нет — то ломается ли она теми же методами, что Even-Mansour?

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

MichaelBorisov Aug 30 2015 at 11:34

Ясно, спасибо. Действительно, похоже, Even-Mansour к «идеальному блочному шифру» скорее всего не сводится. Но зато он значительно проще и имеет доказанную криптостойкость. Жду продолжения ваших статей о шифрах!

aprlv Oct 7 2015 at 23:38

Да, кстати, насчет малой длины блока. Ну конечно, длина блока — критически важный параметр для криптосистемы. Поскольку любой блочный шифр может быть рассмотрен как некоторая подстановка на очень большом множестве (алфавите блоков), то любой шифр может быть взломан с использованием полной кодовой книги (при фиксированном ключе). Так, чем меньше выбранная длина блока, тем меньше памяти требуется злоумышленнику для размещения кодовой книги. Так, при длине блока в 32 бита, кодовая книга занимает, как вы правильно заметили, всего 32 * (2^32) бит, что примерно равно 18 ГБ, и, на мой взгляд, вполне осуществимо.

Show the best of all time