Введение
Свойство некоторых криптосистем
Неразличимость шифротекста — это свойство многих схем шифрования. Интуитивно, если криптосистема обладает свойством неразличимости, то противник не сможет отличить пары шифротекстов, зашифрованных разными сообщениями. Свойство неразличимости при атаке с выбранным открытым текстом считается базовым требованием для большинства криптосистем с открытым ключом, безопасность которых может быть доказана, хотя некоторые схемы также обеспечивают неразличимость при атаке с выбранным шифротекстом и адаптивной атаке с выбранным шифротекстом. Неразличимость при атаке с выбранным открытым текстом эквивалентна свойству семантической безопасности, и многие криптографические доказательства используют эти определения как взаимозаменяемые. Криптосистема считается безопасной с точки зрения неразличимости, если ни один противник, получив шифротекст сообщения, случайно выбранного из двухэлементного пространства сообщений, заданного противником, не сможет определить, какое сообщение было зашифровано, с вероятностью, значительно превышающей вероятность случайного угадывания (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. Противник может выполнить полиномиально ограниченное количество шифрований или других операций. В конечном итоге, противник предоставляет вызывающему лицу два различных выбранных открытых текста. Вызывающее лицо выбирает бит b из {0, 1} равномерно случайным образом и отправляет противнику шифротекст вызова C = E(PK, ). Противник может выполнить любое количество дополнительных вычислений или шифрований. Наконец, противник выдает предположение о значении b. Криптосистема является неразличимой при атаке с выбранным открытым текстом, если каждый вероятностный полиномиальный противник имеет лишь пренебрежимо малое "преимущество" перед случайным угадыванием. Противник считается обладающим пренебрежимо малым "преимуществом", если он выигрывает вышеуказанную игру с вероятностью , где – пренебрежимая функция параметра безопасности k, то есть для каждой (ненулевой) полиномиальной функции существует такая, что для всех .
Несмотря на то, что противник знает и PK, вероятностная природа E означает, что шифрование будет лишь одним из множества допустимых шифротекстов, и, следовательно, шифрование и сравнение полученных шифротекстов с шифротекстом вызова не дает противнику никакого существенного преимущества. Хотя вышеуказанное определение специфично для криптосистемы с асимметричным ключом, его можно адаптировать к симметричному случаю, заменив функцию шифрования с открытым ключом на оракул шифрования, который сохраняет секретный ключ шифрования и шифрует произвольные открытые тексты по запросу противника.
The challenger generates a key pair PK, SK based on some security parameter k (e. g., a key size in bits), and publishes PK to the adversary. The challenger retains SK. The adversary may perform a polynomially bounded number of encryptions or other operations. Eventually, the adversary submits two distinct chosen plaintexts to the challenger. The challenger selects a bit b {0, 1} uniformly at random, and sends the challenge ciphertext C = E(PK, ) back to the adversary. The adversary is free to perform any number of additional computations or encryptions. Finally, the adversary outputs a guess for the value of b. A cryptosystem is indistinguishable under chosen plaintext attack if every probabilistic polynomial time adversary has only a negligible "advantage" over random guessing. An adversary is said to have a negligible "advantage" if it wins the above game with probability , where is a negligible function in the security parameter k, that is for every (nonzero) polynomial function there exists such that for all
Although the adversary knows , and PK, the probabilistic nature of E means that the encryption of will be only one of many valid ciphertexts, and therefore encrypting , and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non negligible advantage to the adversary. While the above definition is specific to an asymmetric key cryptosystem, it can be adapted to the symmetric case by replacing the public key encryption function with an encryption oracle, which retains the secret encryption key and encrypts arbitrary plaintexts at the adversary's request.
Симметричная игра IND-CPA, формализованная
Противоборственный процесс выполнения выбранного атаки открытым текстом обычно описывается в форме криптографической игры. Для проверки на симметричную устойчивость к IND CPA определяется описанная выше игра. Пусть – функция генерации ключа, – функция шифрования, и – функция дешифрования. Пусть – симметричная схема шифрования. Игра определяется следующим образом:
Столько раз, сколько пожелает, противник выбирает два сообщения открытого текста по своему усмотрению и предоставляет их оракулу LR, который возвращает шифротекст, зашифровавший одно из сообщений. Преимущество противника определяется его вероятностью угадать значение *b*, значения, выбранного случайным образом в начале игры, которое определяет, какое сообщение зашифровано в оракуле LR. Следовательно, его преимущество определяется как:
Если противник не может определить, существует ли сообщение вообще, это дает автору сообщения правдоподобное отрицание. Некоторые разработчики зашифрованных каналов связи предпочитают делать содержимое каждой зашифрованной датаграммы неотличимым от случайных данных, чтобы затруднить анализ трафика. Некоторые разработчики систем хранения зашифрованных данных предпочитают делать данные неотличимыми от случайных данных, чтобы облегчить сокрытие данных. Например, некоторые виды шифрования диска, такие как TrueCrypt, пытаются скрыть данные в невинных случайных данных, оставшихся после определенных видов удаления данных. В качестве другого примера, некоторые виды стеганографии пытаются скрыть данные, приводя их в соответствие со статистическими характеристиками невинного "случайного" шума изображения на цифровых фотографиях. Для поддержки таких систем шифрования с возможностью отрицания, некоторые криптографические алгоритмы специально разработаны для того, чтобы сделать шифротекстовые сообщения неотличимыми от случайных битовых строк. Большинству приложений не требуется, чтобы алгоритм шифрования создавал зашифрованные сообщения, неотличимые от случайных битов. Однако некоторые авторы считают такие алгоритмы шифрования концептуально более простыми и удобными в работе, а также более универсальными на практике, и большинство алгоритмов шифрования IND CPA, по-видимому, фактически создают зашифрованные сообщения, неотличимые от случайных битов.
Эквивалентность и последствия
Неразличимость является важным свойством для обеспечения конфиденциальности зашифрованных сообщений. Однако в некоторых случаях было обнаружено, что свойство неразличимости влечет за собой другие, на первый взгляд, не связанные свойства безопасности. Иногда эти взаимосвязи действуют в обоих направлениях, делая два определения эквивалентными; например, известно, что свойство неразличимости при адаптивной атаке на основе выбранного шифротекста (IND CCA2) эквивалентно свойству невосприимчивости к изменениям при том же сценарии атаки (NM CCA2). Эта эквивалентность не является очевидной, поскольку невосприимчивость к изменениям относится к целостности сообщения, а не к конфиденциальности. В других случаях было продемонстрировано, что неразличимость можно комбинировать с определенными другими определениями, чтобы получить еще более полезные определения, и наоборот. Следующий список суммирует некоторые известные взаимосвязи, хотя он далеко не исчерпывающий. Обозначение означает, что свойство А подразумевает свойство В. означает, что свойства А и В эквивалентны. означает, что свойство А не обязательно подразумевает свойство В.
IND CPA – семантическая безопасность в модели CPA. NM CPA (невосприимчивость к изменениям при атаке на основе выбранного открытого текста) IND CPA. NM CPA (невосприимчивость к изменениям при атаке на основе выбранного открытого текста) IND CCA2. NM CCA2 (невосприимчивость к изменениям при адаптивной атаке на основе выбранного шифротекста) IND CCA2.