Тема 4.1.3. Криптоанализ, криптографические примитивы, криптографические протоколы, управление ключами.

Что такое криптографический примитив?

Самый нижний уровень криптосистемы. Это самый маленький "кирпичик" или деталь из которых она может быть составлена. Иногда используют название "атомарный примитив (atomic primitive)". Источником примитивов являются труднорешаемые математические проблемы (например проблема дискретного логарифма может служить основой однонаправленной функции) и специально созданные конструкции (блочные шифры, хэш-функции).

Иногда при конструировании примитивов второго рода, термин "примитив" используется к их составным частям — например S-блокам блочного шифра AES, хотя правильнее говорить об "элементах внутренней структуры примитива".

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

Что такое режим использования криптопримитива?

Сам по себе криптопримитив может быть несовершенен и/или недостаточен. Асимметричный алгоритм RSA требует дополнения определённым способом по размеру блока, блочные шифры требуют использования определённого режима шифрования. Режим использования — это промежуточный уровень детализации между самим криптопримитивом и протоколом.

Что такое криптографический протокол?

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

Что такое криптографический стандарт?

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

Что такое информационно-теоретическая, безусловная и абсолютная модели безопасности?

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

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

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

Что такое стандартная модель безопасности?

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

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

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

Что представляет собой модель случайного оракула?

Случайный оракул — это абстрактная функция, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе на выходе случайный оракул (RO — Random Oracle)выдаёт строку истинно случайных чисел фиксированной длины и записывает "запрос/ответ" в память. При последующих запросах RO проверяет: если такой запрос уже был, то выдаётся предыдущий ответ. Если не было, то производится новый цикл: генерация истинно случайной строки, её вывод, запись в память запроса и ответа. Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при количестве запросов, стремящимся к очень большим величинам (что требуется для моделирования криптопротоколов), его память и быстродействие также должны стремиться к бесконечности.

На основе модели RO построены хэш-функции. Они пытаются воплотить идею RO в реальном мире на основе псевдослучайных функций, отображающие строки длиной от одного байта до примерно 2256 бит в короткие хэш-значения с фиксированной длиной, обычно до 29(512-бит). Существуют экспериментальные модели хэшей и с выходом длиной, задаваемой также до произвольно больших значений.

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

С другой стороны, протокол, построенный с учётом модели случайного оракула (ROM — Random Oracle Model), будет обладать свойствами неразличимости от идеальной модели. Доказательство стойкости в ROM даёт уверенность в том, что протокол собран из исходных частей правильно при условии, что сами исходные части идеальны. Такое доказательство является разновидностью статистической проверки, в виде расширенного формального языка, адаптированного к анализу криптографических протоколов.

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

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

Что такое модель идеального шифра?

Идеальный блочный шифр в такой модели (Ideal Cipher Model — ICM) рассматривается следующим образом. Пусть размер блока шифра — b, размер ключа — k.
Тогда каждый ключ задаёт таблицу псевдослучайной перестановки (Pseudo Random Permutation — PRP) всех возможных вариантов открытого текста во все возможные варианты шифртекста (размер каждого "варианта" равен размеру блока, т.е. b). Число строк в такой таблице будет 2b.

При смене ключа (даже если между ключами есть явные зависимости) должна получаться другая PRP-таблица, не имеющая никакой связи с предыдущей, как если бы её заполнили с помощью генератора истинно случайных чисел. Число таких таблиц — 2k.

Очевидно, что такая модель используется впервую очередь для проектирования блочных шифров. При этом к такому шифру предъявляются самые высокие критерии безопасности по нахождению различителя от идеальной модели. Шифр должен быть не только устойчив к атакам с известными, подобранными, адаптивно-подобранными открытыми и шифртекстаим, но и к более экзотическим атакам: любые действия с шифром должны требовать не меньше ресурсов, чем простой перебор в отношении к идеальной модели — например такие "атаки" — найти ключ, который из данного открытого текста даёт заданный шифртекст, использовать вход открытого текста и ключ в качестве функции сжатия для хэш-функций (при такой атаке противнику известны и ключ, и открытый текст, и шифртекст, и полное внутреннее состояние шифра на каждом раунде) и др.

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

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

Что такое доказуемая безопасность (стойкость)?

Форма доказательства, показывающая, что в рамках модели, рассматривающей широкий спектр атак, противнику придётся проделать для взлома протокола такую же работу, как и для решения сложной математической проблемы (стандартная модель) или для нахождения различителя между протоколом и идеальной моделью (Random Oracle Model, Ideal Cipher Model).

Если принципы доказуемой безопасности подвергаются критике, можно ли доверять результатам работ на её основе?

Этот вопрос является причиной споров по поводу самих основ современной криптографии. Более подробное освещение данной темы дано в статьях "О непростых взаимоотношениях между математикой и криптографией" и "Полемика по поводу понятий криптографической безопасности".

Кроме Коблица и Менезиса, дополнительную критику современной криптографии показывает Николя Куртуа в своей работе "Новые границы в симметричном криптоанализе". Его аргументы состоят в частности в том, что успешное противостояние криптопримитива nизвестным атакам не исключает возможности появления новой атаки под номером n+1, против которой он будет нестоек. И точно оценить вероятность появления такой атаки невозможно. Такое возникает, потому что сведение всех атак к некоторой общей проблеме всегда неполно. Проблема неполноты — естественное ограничение методологии доказуемой безопасности.

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

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