Неразличимость шифротекста (Uyjg[lncnbkvm, onsjkmytvmg)

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

Криптосистема считается безопасной с точки зрения неразличимости^[1], если ни один злоумышленник, получив шифротекст, случайно выбранный из двухэлементного пространства сообщений, определённого противником, не может идентифицировать соответствующий этому шифротексту открытый текст с вероятностью значительно лучше, чем при случайном угадывании (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^[2] определяется следующей игрой между злоумышленником и испытателем. Для систем, основанных на вычислительной безопасности, злоумышленник моделируется вероятностной полиномиальной машиной Тьюринга, что означает, что он должен завершить игру и выдать догадку за полиномиальное число временных шагов. В этом определении E(PK, M) представляет шифротекст сообщения M , полученный с использованием ключа PK:

Испытатель генерирует пару ключей PK, SK на основе некоторого параметра безопасности k (например, размер ключа в битах) и публикует PK злоумышленнику. Испытатель сохраняет SK.
Злоумышленник может выполнить полиномиально ограниченное число шифрований или других операций.
В конце концов, злоумышленник представляет два отдельных открытых текста $\scriptstyle M_{0},M_{1}$ испытателю.
Испытатель выбирает бит b $\scriptstyle \in$ {0, 1} случайным образом и посылает испытываемый шифротекст C = E(PK, $\scriptstyle M_{b}$ ) обратно злоумышленнику.
Злоумышленник может выполнять любое количество дополнительных вычислений или шифрований. Наконец, он выводит просто значение b.

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

Несмотря на то, что злоумышленник знает $\scriptstyle M_{0}$ , $\scriptstyle M_{1}$ и PK, вероятностный характер E означает, что шифротекст $\scriptstyle M_{b}$ будет лишь одним из многих допустимых шифротекстов, а, следовательно шифрование $\scriptstyle M_{0}$ , $\scriptstyle M_{1}$ и сравнение полученных шифротекстов с шифротекстом испытателя на даёт злоумышленнику какого-либо существенного преимущества.

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

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

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

Испытатель генерирует пару ключей PK, SK на основе некоторого параметра безопасности k (например, размер ключа в битах) и публикует PK злоумышленнику. Испытатель сохраняет SK.
Злоумышленник может выполнять любое количество шифрований, вызовов дешифрования с оракулом на основе произвольных шифротекстов или других операций.
В конце концов, злоумышленник представляет два отдельных открытых текста $\scriptstyle M_{0},\,M_{1}$ испытателю.
Испытатель выбирает бит b $\scriptstyle \in$ {0, 1} случайным образом и посылает испытываемый шифротекст C = E(PK, $\scriptstyle M_{b}$ ) обратно злоумышленнику.
Злоумышленник может выполнять любое количество дополнительных вычислений или шифрований.
1. В определении IND-CCA1, злоумышленник не может выполнять дальнейшие расшифрования с оракулом.
2. В определении IND-CCA2, злоумышленник может выполнять дальнейшие вызовы оракула, но не может использовать для этого шифротекст C.
Наконец, злоумышленник выдает предположение о значении b.

Криптосистема надёжна в смысле IND-CCA1 или IND-CCA2, если никакой противник не имеет существенного преимущества в данной игре.

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

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

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

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

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

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

Если алгоритм шифрования E может быть сконструирован таким образом, что злоумышленник (как правило, определяется как наблюдатель в течение полиномиального времени), знающий открытый текст сообщения m, не в состоянии различать E(m) и свеже-сгенерированную случайную битовую строку той же длины, что и E(m), то из этого следует, что при E(m1) такой же длины, как E(m2), эти два шифротекста будут неотличимы друг от друга для злоумышленника, даже если он знает открытый текст m1 и m2 (IND-CPA).^[8]

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

Эквиваленты и их смысл

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

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

Примечания

↑ ¹ ² ³ ⁴ ⁵ Krohn, Maxwell. On the Definitions of Cryptographic Security: Chosen-Ciphertext Attack Revisited (англ.). — 1999. Архивировано 23 декабря 2018 года.
↑ Katz, Jonathan; Lindell, Yehuda. Introduction to Modern Cryptography: Principles and Protocols (англ.). — Chapman and Hall/CRC, 2007. Архивировано 8 марта 2017 года.
↑ Chakraborty, Debrup; Rodríguez-Henríquez., Francisco. Cryptographic Engineering (неопр.) / Çetin Kaya Koç. — 2008. — С. 340. — ISBN 9780387718170.
↑ iang. Indistinguishable from random (неопр.) (20 мая 2006). Дата обращения: 6 августа 2014. Архивировано 15 августа 2014 года.
↑ Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja Elligator: Elliptic-curve points indistinguishable from uniform random strings (неопр.) (28 августа 2013). Дата обращения: 23 января 2015. Архивировано 5 ноября 2014 года.
↑ Möller, Bodo. A Public-Key Encryption Scheme with Pseudo-random Ciphertexts // Computer Security – ESORICS 2004 (неопр.). — 2004. — Т. 3193. — С. 335—351. — (Lecture Notes in Computer Science). — ISBN 978-3-540-22987-2. — doi:10.1007/978-3-540-30108-0_21.
↑ Moore, Cristopher; Mertens, Stephan. The Nature of Computation (неопр.). — 2011. — ISBN 9780191620805.
↑ Reingold, Omar Pseudo-Random Synthesizers, Functions and Permutations (неопр.) 4 (ноябрь 1998). Дата обращения: 7 августа 2014. Архивировано 19 февраля 2014 года.
↑ Rogaway, Phillip Nonce-Based Symmetric Encryption (неопр.) 5–6 (1 февраля 2004). Дата обращения: 7 августа 2014. Архивировано 10 мая 2013 года.
↑ Silvio Micali, Shafi Goldwasser Probabilistic encryption (неопр.) (1984).

Литература

Katz, Jonathan; Lindell, Yehuda. Introduction to Modern Cryptography: Principles and Protocols (англ.). — Chapman & Hall / CRC Press, 2007. — ISBN 978-1584885511.

[CCA2-1] ¹ ² ³ ⁴ ⁵ Krohn, Maxwell. On the Definitions of Cryptographic Security: Chosen-Ciphertext Attack Revisited (англ.). — 1999. Архивировано 23 декабря 2018 года.

[2] Katz, Jonathan; Lindell, Yehuda. Introduction to Modern Cryptography: Principles and Protocols (англ.). — Chapman and Hall/CRC, 2007. Архивировано 8 марта 2017 года.

[3] Chakraborty, Debrup; Rodríguez-Henríquez., Francisco. Cryptographic Engineering (неопр.) / Çetin Kaya Koç. — 2008. — С. 340. — ISBN 9780387718170.

[4] iang. Indistinguishable from random (неопр.) (20 мая 2006). Дата обращения: 6 августа 2014. Архивировано 15 августа 2014 года.

[5] Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja Elligator: Elliptic-curve points indistinguishable from uniform random strings (неопр.) (28 августа 2013). Дата обращения: 23 января 2015. Архивировано 5 ноября 2014 года.

[6] Möller, Bodo. A Public-Key Encryption Scheme with Pseudo-random Ciphertexts // Computer Security – ESORICS 2004 (неопр.). — 2004. — Т. 3193. — С. 335—351. — (Lecture Notes in Computer Science). — ISBN 978-3-540-22987-2. — doi:10.1007/978-3-540-30108-0_21.

[7] Moore, Cristopher; Mertens, Stephan. The Nature of Computation (неопр.). — 2011. — ISBN 9780191620805.

[8] Reingold, Omar Pseudo-Random Synthesizers, Functions and Permutations (неопр.) 4 (ноябрь 1998). Дата обращения: 7 августа 2014. Архивировано 19 февраля 2014 года.

[9] Rogaway, Phillip Nonce-Based Symmetric Encryption (неопр.) 5–6 (1 февраля 2004). Дата обращения: 7 августа 2014. Архивировано 10 мая 2013 года.

[10] Silvio Micali, Shafi Goldwasser Probabilistic encryption (неопр.) (1984).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]