Неразличимость шифротекста

Свойство некоторых криптосистем

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

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

Формальные определения

Безопасность с точки зрения неразличимости имеет много определений, в зависимости от предположений о возможностях злоумышленника. Обычно она представляется как игра , в которой криптосистема считается безопасной , если ни один противник не может выиграть игру со значительно большей вероятностью, чем противник, который должен угадывать случайным образом. Наиболее распространенные определения, используемые в криптографии, — это неразличимость при атаке с выбранным открытым текстом (сокращенно IND-CPA), неразличимость при (неадаптивной) атаке с выбранным шифротекстом (IND-CCA1) и неразличимость при адаптивной атаке с выбранным шифротекстом (IND-CCA2). Безопасность по любому из последних определений подразумевает безопасность по предыдущим: схема, которая является безопасной по IND-CCA1, также является безопасной по IND-CPA, а схема, которая является безопасной по IND-CCA2, является безопасной как по IND-CCA1, так и по IND-CPA. Таким образом, IND-CCA2 является самым сильным из трех определений безопасности.

Неразличимость при атаке с выбранным открытым текстом (IND-CPA)

Для вероятностного алгоритма асимметричного шифрования ключа неразличимость при атаке с выбранным открытым текстом (IND-CPA) определяется следующей игрой между противником и претендентом. Для схем, основанных на вычислительной безопасности , противник моделируется вероятностной полиномиальной машиной Тьюринга , что означает, что он должен завершить игру и вывести предположение в течение полиномиального числа временных шагов. В этом определении E ( PK , M ) представляет шифрование сообщения M под ключом PK :

1. Вызывающий генерирует пару ключей PK , SK на основе некоторого параметра безопасности k (например, размера ключа в битах) и публикует PK противнику. Вызывающий сохраняет SK .
2. Злоумышленник может выполнить полиномиально ограниченное число шифрований или других операций.
3. В конце концов, противник предоставляет претенденту два выбранных им различных открытых текста M ₀ и M _{1 .}
4. Вызывающая сторона выбирает бит b ∈ {0, 1} равномерно и случайным образом и отправляет зашифрованный текст вызова C = E ( PK , M _b ) обратно противнику.
5. Злоумышленник может выполнить любое количество дополнительных вычислений или шифрований.
6. Наконец, злоумышленник выдает предположение о значении b .

Криптосистема неразличима при атаке с использованием выбранного открытого текста, если каждый вероятностный полиномиальный противник имеет лишь незначительное « преимущество » перед случайным угадыванием. Говорят, что противник имеет незначительное «преимущество», если он выигрывает в указанной выше игре с вероятностью , где — незначительная функция в параметре безопасности , то есть для каждой (ненулевой) полиномиальной функции poly() существует такое, что для всех . ${\displaystyle \left({\tfrac {1}{2}}\right)\,+\,\epsilon (k)}$ ${\displaystyle \epsilon (k)}$ ${\displaystyle k}$ ${\displaystyle k_{0}}$ ${\displaystyle |\epsilon (k)|\;<\;\left|{\tfrac {1}{\mathrm {poly(k)} }}\right|}$ ${\displaystyle k\;>\;k_{0}}$

Хотя противник знает M ₀ , M ₁ и PK , вероятностная природа E означает, что шифрование M _b будет лишь одним из многих допустимых шифртекстов, и поэтому шифрование M ₀ , M ₁ и сравнение полученных шифртекстов с шифртекстом вызова не дает противнику существенного преимущества.

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

Симметричная игра IND-CPA, формализованная

Сопернический процесс выполнения атаки с выбранным открытым текстом обычно описывается в форме криптографической игры. Для проверки симметричного IND-CPA определяется описанная выше игра. ^[1] Пусть будет функцией генерации ключа, будет функцией шифрования и будет функцией дешифрования. Пусть будет симметричной схемой шифрования. Игра Guess определяется как: ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}$

Столько раз, сколько он захочет, противник выбирает два открытых текстовых сообщения по своему выбору и предоставляет их LR -оракулу, который возвращает шифртекст, шифрующий одно из сообщений. Преимущество противника определяется его вероятностью угадать значение b, значение, выбранное случайным образом в начале игры, которое определяет сообщение, зашифрованное в LR- оракуле. Таким образом, его преимущество определяется как: ^[1] $${\displaystyle \operatorname {Adv} _{\mathcal {SE}}^{\mathrm {ind-cpa} }(A)=2\cdot \Pr \left[\mathrm {Guess} _{\mathcal {SE}}^{A}\Rightarrow \mathrm {true} \right]-1}$$

Неразличимость при атаке с выбранным шифротекстом/адаптивной атаке с выбранным шифротекстом (IND-CCA1, IND-CCA2)

Неразличимость при неадаптивной и адаптивной атаке выбранного шифртекста (IND-CCA1, IND-CCA2) использует определение, похожее на определение IND-CPA. Однако в дополнение к открытому ключу (или оракулу шифрования в симметричном случае) злоумышленнику предоставляется доступ к оракулу расшифровки , который расшифровывает произвольные шифртексты по запросу злоумышленника, возвращая открытый текст. В неадаптивном определении злоумышленнику разрешено запрашивать этот оракул только до тех пор, пока он не получит шифртекст вызова. В адаптивном определении злоумышленник может продолжать запрашивать оракул расшифровки даже после того, как он получил шифртекст вызова, с оговоркой, что он не может передать шифртекст вызова для расшифровки (в противном случае определение было бы тривиальным).

1. Вызывающий генерирует пару ключей PK , SK на основе некоторого параметра безопасности k (например, размера ключа в битах) и публикует PK противнику. Вызывающий сохраняет SK .
2. Злоумышленник может выполнить любое количество вызовов оракула шифрования и дешифрования на основе произвольных шифртекстов или других операций.
3. В конце концов, противник предоставляет претенденту два выбранных им различных открытых текста M ₀ и M _{1 .}
4. Вызывающая сторона выбирает бит b ∈ {0, 1} равномерно и случайным образом и отправляет зашифрованный текст «вызова» C = E ( PK , M _b ) обратно противнику.
5. Злоумышленник может выполнить любое количество дополнительных вычислений или шифрований.
   1. В неадаптивном случае (IND-CCA1) злоумышленник не может совершать дальнейшие вызовы оракула дешифрования.
   2. В адаптивном случае (IND-CCA2) злоумышленник может совершать дальнейшие вызовы оракулу дешифрования, но не может отправлять зашифрованный текст вызова C.
6. Наконец, злоумышленник выдает предположение о значении b .

Схема является безопасной по уровню IND-CCA1/IND-CCA2, если ни один из противников не имеет существенного преимущества для победы в вышеуказанной игре.

Неотличимо от случайного шума

Иногда нам нужны схемы шифрования, в которых строка зашифрованного текста неотличима для злоумышленника от случайной строки. ^[2]

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

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

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

Для поддержки таких отрицаемых систем шифрования специально разработано несколько криптографических алгоритмов, которые делают сообщения с зашифрованным текстом неотличимыми от случайных строк битов. ^{[4] [5] [6]}

Большинству приложений не требуется алгоритм шифрования для создания зашифрованных сообщений, которые неотличимы от случайных битов. Однако некоторые авторы считают, что такие алгоритмы шифрования концептуально проще и легче в работе, а также более универсальны на практике — и большинство алгоритмов шифрования IND-CPA, по-видимому, действительно создают зашифрованные сообщения, которые неотличимы от случайных битов. ^[7]

Эквивалентности и импликации

Неразличимость является важным свойством для сохранения конфиденциальности зашифрованных сообщений. Однако свойство неразличимости в некоторых случаях, как было обнаружено, подразумевает другие, по-видимому, не связанные свойства безопасности. Иногда эти следствия идут в обоих направлениях, делая два определения эквивалентными; например, известно, что свойство неразличимости при адаптивной атаке с выбранным шифротекстом (IND-CCA2) эквивалентно свойству непластичности при том же сценарии атаки (NM-CCA2). Эта эквивалентность не сразу очевидна, поскольку непластичность является свойством, имеющим дело с целостностью сообщения, а не с конфиденциальностью. В других случаях было продемонстрировано, что неразличимость можно объединить с некоторыми другими определениями, чтобы подразумевать еще другие полезные определения, и наоборот. Следующий список суммирует несколько известных следствий, хотя он ни в коем случае не является полным.

Обозначение означает, что свойство A подразумевает свойство B. означает, что свойства A и B эквивалентны . означает, что свойство A не обязательно подразумевает свойство B. ${\displaystyle A\Rightarrow B}$ ${\displaystyle A\Leftrightarrow B}$ ${\displaystyle A\not \Rightarrow B}$

• Семантическая безопасность IND-CPA в рамках CPA. ${\displaystyle \Leftrightarrow }$
• NM-CPA ( неподатливость к атаке с выбранным открытым текстом) IND-CPA. ^[8] ${\displaystyle \Rightarrow }$
• NM-CPA ( неподатливость к атаке с использованием выбранного открытого текста) IND-CCA2. ^[8] ${\displaystyle \not \Rightarrow }$
• NM-CCA2 ( неподатливость к атакам с адаптивным выбранным шифртекстом) IND-CCA2. ^[8] ${\displaystyle \Leftrightarrow }$

Смотрите также

• Отличительная атака
• Вычислительная неразличимость
• Атака с использованием выбранного шифротекста
• Атака с использованием адаптивного выбранного шифртекста

Ссылки

1. Bellare, Mihir; Rogaway, Phillip (11 мая 2005 г.). «Введение в современную криптографию, Глава 5: Симметричное шифрование» (PDF) . стр. 93 . Получено 6 апреля 2020 г. .
2. Чакраборти, Дебруп; Родригес-Энрикес, Франциско (2008). Четин Кая Коч (ред.). Криптографическая инженерия. п. 340. ИСБН 9780387718170.
3. iang (2006-05-20). "Неотличимо от случайного" . Получено 2014-08-06 .
4. Бернстайн, Дэниел Дж.; Гамбург, Майк; Краснова, Анна; Ланге, Таня (28.08.2013). "Эллигатор: точки эллиптической кривой, неотличимые от однородных случайных строк" (PDF) . Получено 23.01.2015 .
5. Мёллер, Бодо (2004). "Схема шифрования с открытым ключом и псевдослучайными шифртекстами". Computer Security – ESORICS 2004. Lecture Notes in Computer Science. Vol. 3193. pp. 335–351. doi :10.1007/978-3-540-30108-0_21. ISBN 978-3-540-22987-2.
6. Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений. ISBN 9780191620805.
7. Рогауэй, Филлип (2004-02-01). "Nonce-Based Symmetric Encryption" (PDF) . стр. 5–6 . Получено 2014-08-07 .
8. Bellare, M., Desai, A., Pointcheval, D., & Rogaway, P. (1998). Отношения между понятиями безопасности для схем шифрования с открытым ключом. В Advances in Cryptology—CRYPTO'98: 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings 18 (стр. 26–45). Springer Berlin Heidelberg.

• Katz, Jonathan; Lindell, Yehuda (2007). Введение в современную криптографию: принципы и протоколы. Chapman & Hall / CRC Press . ISBN 978-1584885511.