Стойкость криптосхем после компрометации ключей

From CryptoWiki
Revision as of 23:47, 23 May 2018 by 18-BogatyrevDV (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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

Contents

Используемые обозначения

𝑣 ← 𝑥 — значение 𝑥 присваивается переменной 𝑣.

𝑥 ←$ 𝑋 — переменной 𝑥 присваивается случайное число из распределения 𝑋; если 𝑋 — конечное множество, то 𝑥 присваивается значение, равновероятно выбранное из 𝑋.

𝜋 — используемый протокол аутентифицированного обмена ключами.

KGen — алгоритм генерации ключа.

Ψ — алгоритм протокола аутентифицированного обмена ключами.

𝑠𝑡𝑠 — сессионные данные.

𝑠𝑡 — долговременные данные пользователя .

pk — открытый ключ пользователя .

sk — секретный ключ пользователя .

𝑠actor — идентификатор пользователя, выполняющего сессию 𝑠, где 𝑠actor ∈ ℘, ℘ — множество всех идентификаторов.

𝑠role — роль (инициатор ℑ или отвечающий ℜ), исполняемая пользователем в сессии 𝑠.

𝑠peer — предполагаемый партнер по общению 𝑠actor, где где 𝑠peer ∈ ℘.

𝑠key — сессионный ключ, полученный в ходе сессии.

𝑠rand — источник случайности, используемый в сессии.

𝑠step — следующий шаг протокола.

𝑠status — статус сессии, где 𝑠status ∈ {активна, принята, отклонена}.

𝑠.𝑚𝑖 — 𝑖-е отправленное сообщение.

𝑠sent — все сообщения, отправленные sactor в течение сессии.

𝑠recv — все сообщения, принятые 𝑠actor в течение сессии.

Перечень запросов, возможно доступных злоумышленнику 𝒜:

  • create(, 𝑟, ) — создание нового оракула сессии с в роли 𝑟 и партнером ; 𝑠rand генерирует случайное значение и Ψ выполняется, обновляя состояние и возвращая сообщение
  • send(, 𝑟, ) — выполняет Ψ на 𝑖-м оракуле сессии , обновляя состояние, и возвращает результат
  • corrupt() — раскрывает долговременный ключ
  • randomness(, 𝑖) — раскрывает 𝑠rand, где 𝑠 = (, 𝑖)
  • session-key(, 𝑖) — раскрывает 𝑠key, где 𝑠 = (, 𝑖)
  • cr-create(, 𝑟, , 𝑟𝑛𝑑) — создает сессию аналогично create, но устанавливает 𝑠rand = 𝑟𝑛𝑑
  • test-session(𝑠) — подбрасывает монетку 𝑏 ←$ {0, 1} и возвращает 𝑘𝑏, где 𝑘1 = * 𝑠key, а 𝑘0$ KGen
  • guess(𝑏′) — конец игры

В рамках модели [1] действующие лица рассматриваются как оракулы, а злоумышленник — как вероятностная машина Тьюринга с полиномиальным временем.

Определения

Различают 2 вида компрометации.

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

Полная компрометация — факт доступа злоумышленника к долговременному ключу.

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

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

Определение 1. Пусть 𝜋 — протокол из ℎ ≥ 2 сообщений, где если ℎ — чётное, то количество сообщений, отправленных обоими сторонами равно, а если ℎ — нечётное, то инициатор отправляет одно дополнительное сообщение. Пусть 𝑠 обозначает сессию протокола 𝜋 со статусом 𝑠status = принята. Тогда сессия 𝑠 частично совпадает с сессией 𝑠′ со статусом 𝑠′status ≠ ⊥ при выполнении следующих условий, где 𝑠send[1..𝑙] описывает конкатенацию первых 𝑙 сообщений, отправленных в сессии 𝑠 и 𝑠recv[1..𝑙] описывает конкатенацию первых 𝑙 сообщений, полученных в сессии 𝑠:

  • 𝑠role ≠ 𝑠′role ∧ 𝑠actor = 𝑠′peer ∧ 𝑠peer ∧ 𝑠′actor, а также либо
  • 𝑠role = ℑ ∧ 𝑠send[1..𝑚] = 𝑠′recv[1..𝑚] ∧ 𝑠recv[1..𝑚] = 𝑠′send[1..𝑚] при 𝑚 = ℎ/2, если ℎ чётное и 𝑚 = (ℎ-1)/2, если ℎ нечётное, или
  • 𝑠role = ℜ ∧ 𝑠send[1..(𝑚-1)] = 𝑠′recv[1..(𝑚-1)] ∧ 𝑠recv[1..𝑚] = 𝑠′send[1..𝑚] при 𝑚 = ℎ/2, если ℎ чётное и 𝑚 = (ℎ-1)/2, если ℎ нечётное.

Если в дополнение к этому (𝑠status, 𝑠sent, 𝑠recv) = (𝑠′status, 𝑠′recv, 𝑠′sent), тогда 𝑠 совпадает с 𝑠′.

Если же 𝑠′status ≠ ⊥ и 𝑠′sent = 𝑠recv, то 𝑠′ — оригинальная сессия 𝑠.

Определение 2. Предикат свежести — булев предикат, который принимает сессию некоторого протокола 𝜋 и последовательность запросов (включая аргументы и результаты).

Определение 3. Пусть 𝜋 — протокол из ℎ ≥ 2 сообщений, пусть 𝑄 описывает множество запросов 𝒜, а 𝐹 — предикат свежести. Тогда (𝑄,𝐹) — модель безопасности протокола аутентифицированного обмена ключами.

Определение 4. Пусть 𝜋 — протокол из ℎ ≥ 2 сообщений, а 𝑋 = (𝑄,𝐹) — модель безопасности протокола аутентифицированного обмена ключами. Тогда опишем игру, проверяющую безопасность, как эксперимент 𝑊(𝑋):

  1. Алгоритм установки выполнен
  2. Злоумышленник собирает всю общедоступную информацию (включая идентификаторы пользователей и их открытые ключи), а затем вычисляет произвольно, выполняя последовательность запросов из множества 𝑄 \ {test-session, guess}.
  3. Злоумышленник может продолжить выпускать запросы из 𝑄 при условии, что 𝑠 продолжает удовлетворять 𝐹.
  4. 𝒜 выпускает бит 𝑏′ при помощи запроса guess(𝑏′), как свое предположение для бита 𝑏, выбранного в ходе запроса test-session. Игра заканчивается, и 𝒜 выигрывает, если 𝑏=𝑏′.

Определение 5. Протокол 𝜋 называется корректным в модели безопасности (𝑄,𝐹) если для любого злоумышленника 𝒜, рассматриваемого как вероятностная машина Тьюринга с полиномиальным временем, 𝑊(𝑋)-преимущество

OPCS 1.PNG

злоумышленника 𝒜 пренебрежимо для параметра безопасности, где функция 𝑓(𝑘) пренебрежима, когда для любого 𝑐 > 0 существует такое 𝑘0, что для любого 𝑘 > 𝑘0 |𝑓(𝑘)| < 𝑘-𝑐.

Определение 6. Базовая модель безопасности — модель 𝑋𝑏𝑎𝑠𝑖𝑐 определена 𝑄 = {create, send, corrupt, randomness, session-key, test-session, guess} и OPCS 2.PNG, где

  • (𝐹1) Ни один session-key(𝑠)-запрос не был отправлен
  • (𝐹2) Для любых сессий 𝑠*, таких, что 𝑠* совпадает с 𝑠 ни один session-key(𝑠*)-запрос не был отправлен
  • (𝐹3) Ни один randomness(𝑠)-запрос не был отправлен
  • (𝐹4) Для любых сессий 𝑠*, таких, что 𝑠* совпадает с 𝑠 ни один randomness(𝑠*)-запрос не был отправлен
  • (𝐹5) Если для сессии 𝑠 не существует оригинальной, тогда ни один corrupt(𝑠peer)-запрос не был отправлен до создания сессии 𝑠, или до тех пор, пока 𝑠status = активна, и 𝑠recv пуст.

Определение 7. В работе [2] предложено называть EUF-CMA схемой цифровой подписи такую схему, в которой вероятность злоумышленника создать пару сообщение-подпись, отличную от известных пренебрежимо мала при любых известных парах сообщение-подпись.

Там же предложено называть DDH-предположением предположение, что (𝑔𝑥, 𝑔𝑦, 𝑔𝑥𝑦) тяжело отличить от (𝑔𝑥, 𝑔𝑦, 𝑔𝑧), то есть вероятность определить это пренебрежима.

Определение 8. Пусть pcs-hsm описывает предикат трассировки, который

  • для всех запросов hsm(𝑥,...), 𝑥 = 𝑠peer; и
  • все запросы hsm(𝑥,...) были отправлены до того, как сессия 𝑠 была создана,

где запрос hsm(A;...) дописывает к кортежу своих аргументов секретный ключ skA.

Определение 9. Сессия 𝑠 называется обновленной, если существует "промежуточная" сессия 𝑠′ с совпадающей сессией 𝑠′′ такой, что

  • 𝑠actor = 𝑠′actor и 𝑠peer = 𝑠′peer
  • 𝑠′ и 𝑠′′ принято до создания 𝑠
  • не более одного запроса corrupt(𝑠′actor) и (randomness(𝑠′) или cr-create(𝑠′) создания сессии 𝑠′) было отправлено
  • не более одного запроса corrupt(𝑠′peer) и (randomness(𝑠′′) или cr-create(𝑠′′) создания сессии 𝑠′′) было отправлено.

Определение 10. Модель KE-PCS определяется (𝑄,𝐹), где 𝑄 = {create,send, corrupt} и 𝐹 = 𝑃1 ∧ 𝑃2, где

  • запрос corrupt возникает, если вообще возникает, по отношению к 𝑠peer и до создания 𝑠 (𝑃1)
  • если для 𝑠 не существует оригинальной сессии, а запрос corrupt был отправлен, то 𝑠 считается обновленной (𝑃2)

Определение 11. Пусть 𝒞(Â, B̂) — действующий в соответствии с протоколом злоумышленник, который создаёт сессию с Â как инициатором, передает первоначальное сообщение B̂, возвращает его ответ Â, и так далее, пока Â не закончит сессию. Сетевым злоумышленником называется любой злоумышленник, который выполняет только запросы create и send. Протокол 𝜋 считается стойким, если для любых Â и B̂, 𝒞 вызывает пару совпадающих сессий с одинаковым ключом у Â с B̂ и наоборот. Протокол стойкий к сетевым атакам, если 𝒞(Â, B̂) по-прежнему может вызывать пары совпадающих сессий с одинаковыми ключами, выполняясь последовательно даже после любого сетевого злоумышленника.

Условия стойкости криптосхем после компрометации ключей

Рисунок 1. Протокол Диффи-Хеллмана, использующий цифровую подпись

Утверждение 1. Стойкость криптосхем после компрометации ключей не достижима после неограниченной компрометации предполагаемого партнера.

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

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

Теорема 1. Для EUF-CMA схемы цифровой подписи протокол Диффи — Хеллмана, использующий такую подпись соответствует базовой модели безопасности, при предположении DDH.

Пример такого протокола представлен на рисунке 1, где 𝑛A, 𝑛B, 𝑥, 𝑦 — случайные числа, Sigsk {M} — цифровая подпись сообщения M на ключе sk, Â и B̂ — идентификаторы пользователей, а ℎ - сессионный ключ.

Теорема 2. Пусть ℑ(A, skA, 𝑚) — алгоритм электронной подписи EUF-CMA схемы электронной подписи, а 𝜋 — протокол, приведенный на рисунке 1, безопасный в базовой модели 𝑋𝑏𝑎𝑠𝑖𝑐 = (𝑄,𝐹). Тогда 𝜋 безопасен в модели (𝑄 ∪ {hsm}, 𝐹 ∩ pcs-hsm) при предположении DDH.

Теорема 3. Никакой протокол, не содержащий состояний, не безопасен в соответствии с KE-PCS.

Теорема 4. Никакой корректный однораундовый протокол, который безопасен в соответствии с KE-PCS, не может быть стойким к сетевым атакам.

Протокол обмена ключами, обеспечивающий стойкость после компрометации ключей

Рисунок 2. Выполнение протокола 𝜋.

В работе [2] было предложено улучшение общей схемы обмена ключами для обеспечения стойкости после компрометации ключа:

Пусть 𝜋 — протокол обмена ключами, состоящий из трех сообщений. Предположим, что открытые ключи Диффи — Хеллмана распределены для всех участников, и 𝜋 вычисляет основной ключ, из которого получаются сессионные ключи. В работе определяется 𝜋, как модификация 𝜋 следующим образом:
  • Для каждого пользователя B̂ определяется новые глобальные переменные состояния 𝐼𝑆B̂, Â и OPCS 4.PNG. Первая переменная хранит одно значение, а вторая список (возможно, пустой) значений. В начале 𝐼𝑆B̂, Â установлено в 𝑔𝑎𝑏 для всех Â, B̂.
  • В сессии 𝑠 между участниками Â и B̂ каждое сообщение 𝑚𝑗 от Â к B̂ заменяется на <𝑚𝑗, 𝜇𝑗>, где 𝜇𝑗 — код аутентификации сообщения: MAC(𝑚𝑗; 𝐼𝑆Â, B̂, а каждое сообщение 𝑚𝑗 от B̂ к Â заменяется на <𝑚𝑗; 𝜇𝑗>, где 𝜇𝑗 = MAC(𝑚𝑗; 𝐼𝑆B̂, Â).
  • После получения <𝑚1; 𝜇1> B̂ действует следующим образом:
    • Если 𝜇1 = MAC(𝑚1, 𝐼𝑆B̂, Â, B̂ переходит к следующему шагу.
    • Иначе B̂ проверяет каждое значение 𝑖𝑠 ∈OPCS 4.PNG, выполняется ли равенство 𝜇1 = MAC(𝑚1; 𝑖𝑠). При выполнении равенства B̂ заменяет 𝐼𝑆B̂, Â ← 𝑖𝑠 и очищает OPCS 4.PNG ← ∅, а затем переходит к следующему шагу.
    • Иначе B̂ отклоняет сессию.
  • Выполняется функция формирования ключа (KDF): 𝐼𝑆B̂, Ânew ← KDF(σ, 𝐼𝑆B̂, Â, 1) и присоединяется к OPCS 4.PNG, где σ — счетчик.
  • основной ключ 𝑝𝑚𝑠 ← KDF(σ) заменяется 𝑝𝑚𝑠′ ← KDF(σ, 𝐼𝑆B̂, Â, 0).
  • B̂ вычисляет 𝜇2 и отправляет <𝑚2; 𝜇2>.
  • Â проверяет 𝜇2, используя свой промежуточный секрет и отклоняет, если проверка оказывается проваленной. Иначе Â обновляет 𝐼𝑆Â, B̂new ← 𝐼𝑆Â, B̂new = KDF(σ, 𝐼𝑆Â, B̂, 1) и <𝑚3; 𝜇3>.
  • B̂ проверяет 𝜇2, подтверждая потенциальное значение из текущей сессии, и если проверка оказывается успешной, то ключ принимается, а переменные устанавливаются в следующие значения: 𝐼𝑆B̂, Ânew ← 𝐼𝑆B̂, Ânew и OPCS 4.PNG ← ∅.

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

DECIM

В работе [3] был представлен протокол DECIM (Detecting Endpoint Compromise In Messaging), обеспечивающий стойкость после компрометации ключей. Он был также использован в одноименном мессенджере.

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

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

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

Глоссарий

Управление ключами симметричных криптосистем

Схемы цифровой подписи

Открытое распределение ключей

Базовые конструкции протоколов распределения ключей

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

Библиографический указатель

Перейти к списку литературы

Вернуться к оглавлению

Богатырёв Д.В., 2018