Построение модели противника в криптографии на примере 5G-AKA

Исследователь лаборатории криптографии компании «Криптонит» Кирилл Царегородцев (@kirtsar) сравнил разные подходы к оценке безопасности криптографических протоколов. В качестве примера он использовал протокол 5G-AKA, применяемый для аутентификации в современных сетях мобильной связи.

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

Сразу же можно задать вопрос: а что значит «безопасный»? Чего мы хотим добиться? Какие у нас есть для этого изначальные возможности и ресурсы, которыми мы располагаем? От кого именно мы защищаемся – от любопытного соседа, который просто пассивно прослушивает радиоэфир, или от некоторой могущественной спецслужбы, в распоряжении которой могут быть огромные вычислительные мощности и специализированное оборудование? Все эти вопросы не так просты, как может показаться на первый взгляд, и под ними прячется огромное количество подводных камней, на которые легко налететь, если предварительно не ответить (или хотя бы попытаться ответить) на каждый из таких вопросов.

В нашем выступлении на конференции «РусКрипто’2022» мы коснулись лишь одной части этой сложной задачи по обеспечению безопасной связи, а именно, алгоритма 5G-AKA.

Его двумя основными задачами являются выработка сеансового общего секретного ключа между пользователем и домашней сетью (т.н. Authenticated Key Exchange или AKE‑протокол [1]) и явная аутентификация сторон взаимодействия.

Исходными здесь являются следующие положения:

1.      Между телефоном и домашней сетью уже распределен некоторый общий секретный ключ (например, он «зашит» в SIM-карту на этапе её производства, либо получен в результате работы алгоритмов, заложенных в технологии eSIM).

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

3.      Нам противодействует могущественный активный противник, который контролирует все сообщения в сети и может по своему усмотрению прерывать доставку сообщений, как-либо их видоизменять, присылать сообщения в неправильном порядке и т.д. (т.н. модель угрозы Долева — Яо [2]).

Самым сложным представляется вопрос о том, что же именно считать «безопасным» протоколом выработки сеансового ключа (или, следуя Канту: «На что я могу надеяться, если делаю то, что мне надлежит делать?»). Традиционным является экспертный подход, в ходе которого протокол изучается профессиональным сообществом на наличие конкретных «типичных» атак. При этом к протоколу выдвигается ряд некоторых полуформальных требований, описывающих, от чего именно мы пытаемся защититься. При обнаружении атаки, которая в каком‑либо смысле нарушает одно из требований, протокол модифицируется таким образом, чтобы противостоять подобной атаке в дальнейшем. Протокол признается безопасным, если на протяжении некоторого (относительно продолжительного) промежутка времени не было найдено новых атак.

Именно этому пути следует организация 3GPP, занимающаяся разработкой и стандартизацией протоколов, связанных с технологией 5G. Экспертами 3GPP в рамках различных сопроводительных документов выдвигаются различные полуформализованные требования к протоколу 5G‑AKA, составленные на основе предыдущих «типичных атак» на протокол и исходя из того, что именно эксперты считают угрозой для абонентов. Особенностью подобных требований является то, что они сформулированы на «простом» языке, который допускает множество интерпретаций. Как пример, можно привести фразу, которой описывается свойство user untraceability (неотслеживаемость пользователя) из документа TS133.102: “an intruder cannot deduce whether different services are delivered to the same user by eavesdropping”.

Уже в такой постановке задачи можно выделить некоторые потенциальные проблемы. Во-первых, по каким причинам рассматривается только пассивный противник (eavesdropping)? Во-вторых, более серьезное возражение: как именно дать какие-либо количественные (а не качественные) оценки (вероятности) выполнения или невыполнения свойства?

Проблема формализации

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

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

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

2.  Zero knowledge: все сообщения в протоколе можно промоделировать, не зная долговременных секретов. В таком случае транскрипция протокола не дает никакой информации противнику, поскольку он сам в состоянии сгенерировать подобное распределение двоичных сообщений без необходимости взаимодействовать с реальными участниками.

3.  Left-or-Right: противник не может определить, с каким из двух им выбранных участников он общается в данный момент времени. В таком случае противник не может понять, кому какая транскрипция протокола соответствует, а также являются ли две транскрипции записью протокола с одним и тем же участником или с различными.

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

Плюсы и минусы подхода «доказуемой стойкости»

Сведение задачи к конкретным математическим моделям с дальнейшей оценкой вероятностей в явном виде (т.н. подход «доказуемой стойкости») имеет несколько плюсов по сравнению с предыдущим вышеозначенным экспертным подходом.

Так, экспертному подходу присущи следующие недостатки:

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

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

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

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

2.  Возможно отклонение и в другую сторону. Так, ограничения в используемой «технике» и сложности доказательства могут давать избыточно пессимистичные результаты. Как пример тут может рассматриваться прием, используемый при доказательствах неподделываемости некоторых типов цифровых подписей, известный в фольклоре как «forking lemma» [6]. Он дает завышенную оценку вероятности успеха противника в силу невозможности доказать результат иным (не косвенным) методом на данном этапе развития науки.

3.  Модели для свойств безопасности очень чувствительны к изначальным предположениям, вплоть до «незначительных» изменений: так, иногда возвращение кодов ошибок или замер времени выполнения операции дает противнику возможность полностью скомпрометировать протокол (см. «атаки по побочным каналам», а также [4] для примера подобных атак).

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