Доказательная криптография

[fat_crocodile]

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

K -- множество ключей
M -- множество сообщений, считаем их всех одной длинны
C -- множество зашифрованных сообщений (шифротекстов).

E: K * M --> C -- шифрующая функция, c = E(k, m), k -- ключ, m -- сообщение, c -- зашифрованное
D: K * C --> M -- дешифрующая функция, m = D(k, c)
D(k, E(k, m)) = m -- основное требование

Абсолютная криптографическая стойкость (perfect secrecy)
Термин, предложенный Шенноном в работе Communication Theory of Secrecy Systems. Мысль следующая: противник получает зашифрованное сообщение, но, как бы умён он ни был, не получает никакой дополнительной информации об исходном сообщении (напоминаю: все одной длинны, т.е. длину он уже как бы знает).

То есть, для любых m0, m1 из M и любого c из C, вероятность того, что это c получено из m0 равна вероятности того, что c получено из m1.

Логично? Логично. А теперь фокус. Вот небольшое сообщение m, размером 1Мб. Вот прекрасный современный шифр AES с ключом 128 бит. Вот зашифрованное сообщение c, перехваченное противником.

Рассуждение на пальцах: очевидно, что получив 128-битный ключ, противник полностью восстановит сообщение m, то есть для счастья ему не хватает 128 бит. А изначально ему не хватало 8 * 1024 * 1024 = 8 388 608 бит. А значит в результате перехвата он узнал больше чем 99.99% информации (ничего себе утечка!), но при этом всё ещё ничего не понял. Вот это дурак! В этом месте стоит удивиться, что криптография вообще возможна, на мой взгляд это довольно нетривиально.

Менее на пальцах: перебрав всё множество K можно вычислить все D(k, c) для конкретного c, это будут все возможные сообщения. Если мощность множества K меньше чем мощность множества M, в результате противник сузит круг возможных сообщений, то есть получит дополнительную информацию. И стойкость не будет абсолютной.

Отсюда вывод: для достижения абсолютной стойкости размер ключа должен быть не меньше, чем размер сообщения.

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

Одноразовый блокнот (one-time pad, OTP)
Устроен очень просто. Исходное сообщение это строка бит (0 и 1), ключ это случайна строка бит той же длины. Шифрование заключается в выполнении побитового xor-а, дешифрование аналогично.

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

Очень полезное свойство, только вот несколько непрактичные ключи. Для записи ключа собственно и нужен блокнот.

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

Псевдо-случайные генераторы (pseudo random generators, PRG)
В чём основная фишка OTP? В длинной случайной строке бит. Допустим! Что есть такая прекрасная функция PRG: K --> {0, 1}n, генерирующая из относительно короткого ключа строку бит длиной n, причём такую, что ни один "эффективный противник" "не сможет отличить её" от действительно случайной.

Тогда можно использовать эту функцию для генерации ключей для OTP, и ни один эффективный противник не сможет его "взломать".

Тут много непонятных слов, которые надо определять через другие слова, которые тоже надо определять. Для начала разберёмся с определениям PRG:

• Что значит "эффективный противник": давайте считать, что работающий полиномиальное время от log(|K|). Конечно, очевидно, что при фиксированном размере K можно подобрать такую степень полинома, что он будет перекрывать экспоненту, а значит с теоретической точки зрения все такие шифры бессмысленны. Но мы не будем обращать на это внимания :) На практике берётся какое-то "достаточно много на данный момент".
• Что значит "не может отличить от действительно случайной": мы скармливаем противнику в произвольном порядке строчки, сгенерированные PRG и случайные (миллион китайцев бросают монетку, записывают результат), а тот пытается угадать. И если есть хоть какая-то заметная разница между его ответами на PRG-строчки и случайные строчки, то считаем, что он сломал этот PRG (так как его можно использовать как индикатор).
• Что значит "есть хоть какая-то заметная разница" (все помнят, что такое условная вероятность? вспоминайте):
  
  | P(противник сказал, что строка случайная | строка случайная) - P(противник сказал, что строка случайная | строка сгенерирована) | = ε
  и ε достаточно велика. Если же ε пренебрежимо мала, то заметной разницы нет.
• Что значит "пренебрежимо мала": давайте считать, что если падает по экспоненте от log(|K|). Для фиксированных K та же история что и с эффективностью.

Тут тоже можно удивиться. PRG отображает относительно небольшое множество K в огромное по сравнению с ним множество {0, 1}n. Противник, не ограниченный требованием эффективности может просто перебрать все возможные ключи из K и посчитать все возможные строки на выходе PRG, их будет намного-намного меньше чем 0.001% от всего множества {0, 1}n, фактически они попадают в исчезающе малое подмножество. Но при этом более простого способа их идентифицировать не существует. Чудеса! Даже хочется вспомнить что-нибудь топологическое типа всюду плотного множества, но тут всё конечное и дискретное, не понятно, как одно к другому разумно приделать...

Наконец, что значит "взломать":

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

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

| P(противник сказал, что первое | шифровалось первое) - P(противник сказал, что первое | шифровалось второе) |
не пренебрежимо мало.

При этом эффективный противник ограничен в количестве запросов и в количестве вычислений. Кажется, по-русски это называется "вычислительной криптостойкостью" (semantic security по-английски).

Определение понятны. Теперь, почему при наличии такой PRG её выход можно использовать как ключ к OTP:

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

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

Здорово! Но, существуют ли такие волшебные функции? Если бы это было известно, отсюда сразу же следовало бы что P!=NP, а этого пока никто не доказал. Так что мы не знаем, хотя и очень верим.

Поточные шифры
На этой идее основаны поточные шифры.

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

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

Блочные шифры
Кратко ту же историю для блочных шифров.

• вводим случайные перестановки и/или случайные функции
• доказываем, что бороться с ними бесполезно, ни один противник ничего хорошего сделать не сможет
• но, блин, их много. Например, перестановок на 128-битных блоках 2128! (факториал), а функций так и вообще.
• вводим псевдо-случайные перестановки (pseudo random permutation, PRP) и/или функции (PRF), такие что ни один эффективный противник не может отличить их от настоящих.
• доказываем, что тогда и с шифром из них эффективный противник ничего сделать не сможет
• существуют ли такие PRP? Мы не знаем
• зато, кстати, если они есть, то из них можно изготовить хороший PRG, это доказывается
• но предлагаем конкретную функцию в качестве кандидата
• получаем блочный шифр, шифрующий один блок

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

Контроль целостности
Ещё одна история. Тут вдруг мы обнаруживаем, что до сих пор рассматривали только один тип атак, но могут же быть и другие. А что если противник будет вмешиваться в канал передачи сообщений и портить их? Надо как-то уметь это определять. Или, что если он может послать нам какой-нибудь текст на расшифровку и получить результат?

• И вот мы придумываем случайное отображение MAC: K * M --> S, которое по по ключу и сообщению выдаёт случайный относительно короткий код...
• Доказываем, что подделать его не получится...
• Потом говорим "а давайте псевдо-случайное", такое, что эффективный противник не сможет отличить..
• Доказываем, что тогда он не сможет его и подделать
• К нашей чести -- конструируем такой MAC из PRP. То есть их существование всё ещё не доказано, но по крайней мере сведено к старой задаче.

Тут тоже есть интересные части, но сейчас не о них.

Я думаю, вы уловили паттерн.

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


• Доказываем, что при определённых ограничениях нас вполне устроит второе.


• Доказываем надёжность с огромным запасом "на всякий случай".


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

Пользу от этого занятия я вижу в следующем:

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

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