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

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

Криптосистема считается безопасной с точки зрения неотличимости , если ни один злоумышленник при условии шифрования сообщения, случайно выбранного из двухэлементного пространства сообщений, определенного противником, не может идентифицировать выбор сообщения с вероятностью, значительно лучшей, чем вероятность случайного угадывания ( 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 :

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

Криптосистема неотличима при атаке с использованием выбранного открытого текста, если каждый вероятностный противник с полиномиальным временем имеет лишь незначительное « преимущество » перед случайным угадыванием. Говорят, что противник имеет незначительное «преимущество», если он выиграет указанную выше игру с вероятностью. $\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-CPA, формализованная

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

Противник столько раз, сколько пожелает, выбирает два открытых текстовых сообщения по своему выбору и передает их оракулу LR , который возвращает зашифрованный текст, шифрующий одно из сообщений. Преимущество противника определяется вероятностью угадать значение b, значение, выбранное случайным образом в начале игры, которое определяет сообщение, зашифрованное в оракуле LR . Таким образом, его преимущество определяется как: ^{[ 1 ]} $\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. Однако в дополнение к открытому ключу (или оракулу шифрования в симметричном случае) злоумышленнику предоставляется доступ к оракулу дешифрования , который расшифровывает произвольные зашифрованные тексты по запросу противника, возвращая открытый текст. В неадаптивном определении злоумышленнику разрешено запрашивать этого оракула только до тех пор, пока он не получит зашифрованный текст вызова. В адаптивном определении злоумышленник может продолжать запрашивать оракул дешифрования даже после того, как он получил зашифрованный текст запроса, с оговоркой, что он не может передать зашифрованный текст запроса для расшифровки (в противном случае определение было бы тривиальным).

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

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

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

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

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

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

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

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

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

Эквиваленты и последствия

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

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Белларе, Михир; Рогауэй, Филипп (11 мая 2005 г.). «Введение в современную криптографию, глава 5: симметричное шифрование» (PDF) . п. 93 . Проверено 6 апреля 2020 г.
^ Чакраборти, Дебруп; Родригес-Энрикес, Франциско (2008). Четин Кая Коч (ред.). Криптографическая инженерия . п. 340. ИСБН 9780387718170 .
^ Ян (20 мая 2006 г.). «Неотличимо от случайного» . Проверено 6 августа 2014 г.
^ Бернштейн, Дэниел Дж.; Гамбург, Майк; Краснова, Анна; Ланге, Таня (28 августа 2013 г.). «Эллигатор: точки эллиптической кривой, неотличимые от однородных случайных строк» (PDF) . Проверено 23 января 2015 г.
^ Мёллер, Бодо (2004). «Схема шифрования с открытым ключом и псевдослучайными зашифрованными текстами». Компьютерная безопасность – ESORICS 2004 . Конспекты лекций по информатике. Том. 3193. стр. 335–351. дои : 10.1007/978-3-540-30108-0_21 . ISBN 978-3-540-22987-2 .
^ Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений . ISBN 9780191620805 .
^ Рогауэй, Филипп (01 февраля 2004 г.). «Симметричное шифрование на основе Nonce» (PDF) . стр. 5–6 . Проверено 7 августа 2014 г.

Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл / CRC Press . ISBN 978-1584885511 .

[:0-1] Перейти обратно: ^а ^б Белларе, Михир; Рогауэй, Филипп (11 мая 2005 г.). «Введение в современную криптографию, глава 5: симметричное шифрование» (PDF) . п. 93 . Проверено 6 апреля 2020 г.

[2] Чакраборти, Дебруп; Родригес-Энрикес, Франциско (2008). Четин Кая Коч (ред.). Криптографическая инженерия . п. 340. ИСБН 9780387718170 .

[3] Ян (20 мая 2006 г.). «Неотличимо от случайного» . Проверено 6 августа 2014 г.

[4] Бернштейн, Дэниел Дж.; Гамбург, Майк; Краснова, Анна; Ланге, Таня (28 августа 2013 г.). «Эллигатор: точки эллиптической кривой, неотличимые от однородных случайных строк» (PDF) . Проверено 23 января 2015 г.

[5] Мёллер, Бодо (2004). «Схема шифрования с открытым ключом и псевдослучайными зашифрованными текстами». Компьютерная безопасность – ESORICS 2004 . Конспекты лекций по информатике. Том. 3193. стр. 335–351. дои : 10.1007/978-3-540-30108-0_21 . ISBN 978-3-540-22987-2 .

[6] Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений . ISBN 9780191620805 .

[7] Рогауэй, Филипп (01 февраля 2004 г.). «Симметричное шифрование на основе Nonce» (PDF) . стр. 5–6 . Проверено 7 августа 2014 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]