Введение
Входные данные криптографической примитивной
In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between (potentially similar) segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation. Some cryptographic primitives require the IV only to be non repeating, and the required randomness is derived internally. In this case, the IV is commonly called a nonce (a number used only once), and the primitives (e. g. CBC) are considered stateful rather than randomized. This is because an IV need not be explicitly forwarded to a recipient but may be derived from a common state updated at both sender and receiver side. (In practice, a short nonce is still transmitted along with the message to consider message loss.) An example of stateful encryption schemes is the counter mode of operation, which has a sequence number for a nonce. The IV size depends on the cryptographic primitive used; for block ciphers it is generally the cipher's block size. In encryption schemes, the unpredictable part of the IV has at best the same size as the key to compensate for time/memory/data tradeoff attacks. When the IV is chosen at random, the probability of collisions due to the birthday problem must be taken into account. Traditional stream ciphers such as RC4 do not support an explicit IV as input, and a custom solution for incorporating an IV into the cipher's key or internal state is needed. Some designs realized in practice are known to be insecure; the WEP protocol is a notable example, and is prone to related IV attacks.
В криптографии вектор инициализации (IV) или начальная переменная является входными данными для криптографической примитивной, используемой для задания начального состояния. Обычно IV должен быть случайным или псевдослучайным, но иногда достаточно, чтобы он был непредсказуемым или уникальным. Случайность критически важна для некоторых схем шифрования для достижения семантической безопасности – свойства, при котором повторное использование схемы с одним и тем же ключом не позволяет злоумышленнику установить связь между (потенциально похожими) сегментами зашифрованного сообщения. Для блочных шифров использование IV описывается режимами работы. Некоторые криптографические примитивы требуют, чтобы IV был только уникальным, а необходимая случайность генерируется внутри. В этом случае IV обычно называют одноразовым числом (nonce), а примитивы (например, CBC) считаются сохраняющими состояние, а не рандомизированными. Это связано с тем, что IV не обязательно нужно явно передавать получателю, его можно вывести из общего состояния, обновляемого как отправителем, так и получателем. (На практике короткий nonce все же передается вместе с сообщением, чтобы учесть возможность потери сообщения.) Режим работы счетчика является примером схемы шифрования, сохраняющей состояние, и использует порядковый номер в качестве nonce. Размер IV зависит от используемой криптографической примитивной; для блочных шифров он обычно равен размеру блока шифра. В схемах шифрования непредсказуемая часть IV в лучшем случае имеет размер, равный размеру ключа, чтобы противостоять атакам, основанным на компромиссе между временем, памятью и данными. При случайном выборе IV необходимо учитывать вероятность коллизий из-за парадокса дней рождения. Традиционные потоковые шифры, такие как RC4, не поддерживают явный IV в качестве входных данных, и требуется специальное решение для включения IV в ключ шифра или его внутреннее состояние. Некоторые реализованные на практике конструкции оказались небезопасными; протокол WEP является ярким примером и подвержен атакам, связанным с IV.
In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between (potentially similar) segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation. Some cryptographic primitives require the IV only to be non repeating, and the required randomness is derived internally. In this case, the IV is commonly called a nonce (a number used only once), and the primitives (e. g. CBC) are considered stateful rather than randomized. This is because an IV need not be explicitly forwarded to a recipient but may be derived from a common state updated at both sender and receiver side. (In practice, a short nonce is still transmitted along with the message to consider message loss.) An example of stateful encryption schemes is the counter mode of operation, which has a sequence number for a nonce. The IV size depends on the cryptographic primitive used; for block ciphers it is generally the cipher's block size. In encryption schemes, the unpredictable part of the IV has at best the same size as the key to compensate for time/memory/data tradeoff attacks. When the IV is chosen at random, the probability of collisions due to the birthday problem must be taken into account. Traditional stream ciphers such as RC4 do not support an explicit IV as input, and a custom solution for incorporating an IV into the cipher's key or internal state is needed. Some designs realized in practice are known to be insecure; the WEP protocol is a notable example, and is prone to related IV attacks.
Мотивация
Блок-шифр – один из самых основных примитивов в криптографии и часто используется для шифрования данных. Однако сам по себе он может быть использован только для кодирования блока данных предопределенного размера, называемого размером блока. Например, однократный вызов алгоритма AES преобразует 128-битный блок открытого текста в блок шифротекста размером 128 бит. Ключ, который подается на вход шифру, определяет соответствие между открытым текстом и шифротекстом. Если необходимо зашифровать данные произвольной длины, простая стратегия заключается в разделении данных на блоки, каждый из которых соответствует размеру блока шифра, и шифровании каждого блока отдельно с использованием одного и того же ключа. Этот метод небезопасен, поскольку одинаковые блоки открытого текста преобразуются в одинаковые блоки шифротекста, и злоумышленник, наблюдающий за зашифрованными данными, может легко определить их содержимое, даже не зная ключ шифрования. Чтобы скрыть закономерности в зашифрованных данных, избегая необходимости выпуска нового ключа после каждого использования блок-шифра, необходим метод рандомизации входных данных. В 1980 году NIST опубликовал национальный стандарт под названием Federal Information Processing Standard (FIPS) PUB 81, в котором определены четыре так называемых режима работы блок-шифра, каждый из которых описывает различное решение для шифрования набора входных блоков. Первый режим реализует простую стратегию, описанную выше, и был определен как режим электронной кодовой книги (ECB). В отличие от него, каждый из других режимов описывает процесс, в котором шифротекст из одного этапа шифрования блоков смешивается с данными из следующего этапа шифрования. Для запуска этого процесса требуется смешать дополнительное входное значение с первым блоком, которое называется вектором инициализации. Например, режим цепочки шифрования блоков (CBC) требует непредсказуемого значения, размер которого равен размеру блока шифра, в качестве дополнительного ввода. Это непредсказуемое значение добавляется к первому блоку открытого текста перед последующим шифрованием. В свою очередь, шифротекст, полученный на первом этапе шифрования, добавляется ко второму блоку открытого текста и так далее. Конечная цель схем шифрования – обеспечить семантическую безопасность: благодаря этому свойству злоумышленнику практически невозможно получить какую-либо информацию из наблюдаемого шифротекста. Можно показать, что каждый из трех дополнительных режимов, определенных NIST, является семантически безопасным при так называемых атаках с выбранным открытым текстом.
Свойства
Свойства IV зависят от используемой криптографической схемы. Основным требованием является уникальность, то есть ни один IV не должен повторно использоваться с одним и тем же ключом. Для блочных шифров повторное использование значений IV приводит к тому, что схема шифрования вырождается в режим электронной кодовой книги: одинаковые IV и одинаковый открытый текст приводят к одинаковому шифротексту. В потоковых шифрах уникальность критически важна, поскольку в противном случае открытый текст может быть тривиально восстановлен. Пример: потоковые шифры шифруют открытый текст P в шифротекст C, генерируя ключевой поток K из заданного ключа и IV и вычисляя C как C = P xor K. Предположим, что злоумышленник перехватил два сообщения C1 и C2, зашифрованных одним и тем же ключом и IV. Тогда знание P1 или P2 раскрывает другой открытый текст, поскольку C1 xor C2 = (P1 xor K) xor (P2 xor K) = P1 xor P2. Многие схемы требуют, чтобы IV был непредсказуем для противника. Это достигается путем выбора IV случайным или псевдослучайным образом. В таких схемах вероятность дублирования IV пренебрежимо мала, но необходимо учитывать эффект парадокса дней рождения. Что касается требования уникальности, то предсказуемый IV может позволить восстановить (частичный) открытый текст. Пример: рассмотрим сценарий, в котором легитимный участник по имени Алиса шифрует сообщения, используя режим шифрования блочной цепочки. Предположим также, что существует противник по имени Ева, который может наблюдать эти шифрования и способен отправлять Алисе сообщения в открытом тексте для шифрования (то есть Ева способна осуществить атаку с выбранным открытым текстом). Теперь предположим, что Алиса отправила сообщение, состоящее из вектора инициализации IV1 и начинающееся с блока шифротекста CAlice. Пусть PAlice обозначает первый блок открытого текста сообщения Алисы, E – шифрование, а PEve – предположение Евы для первого блока открытого текста. Теперь, если Ева сможет определить вектор инициализации IV2 следующего сообщения, она сможет проверить свое предположение, отправив Алисе сообщение в открытом тексте, начинающееся с (IV2 xor IV1 xor PEve); если ее предположение верно, этот блок открытого текста будет зашифрован Алисой в CAlice. Это связано со следующим простым наблюдением: CAlice = E(IV1 xor PAlice) = E(IV2 xor (IV2 xor IV1 xor PAlice)). В зависимости от того, должен ли IV для криптографической схемы быть случайным или только уникальным, схема называется рандомизированной или с состоянием. В то время как рандомизированные схемы всегда требуют, чтобы отправитель передавал выбранный им IV получателям, схемы с состоянием позволяют отправителю и получателю совместно использовать общее состояние IV, которое обновляется предопределенным образом с обеих сторон.
C1 xor C2 = (P1 xor K) xor (P2 xor K) = P1 xor P2. Many schemes require the IV to be unpredictable by an adversary. This is effected by selecting the IV at random or pseudo randomly. In such schemes, the chance of a duplicate IV is negligible, but the effect of the birthday problem must be considered. As for the uniqueness requirement, a predictable IV may allow recovery of (partial) plaintext. Example: Consider a scenario where a legitimate party called Alice encrypts messages using the cipher block chaining mode. Consider further that there is an adversary called Eve that can observe these encryptions and is able to forward plaintext messages to Alice for encryption (in other words, Eve is capable of a chosen plaintext attack). Now assume that Alice has sent a message consisting of an initialization vector IV1 and starting with a ciphertext block CAlice. Let further PAlice denote the first plaintext block of Alice's message, let E denote encryption, and let PEve be Eve's guess for the first plaintext block. Now, if Eve can determine the initialization vector IV2 of the next message she will be able to test her guess by forwarding a plaintext message to Alice starting with (IV2 xor IV1 xor PEve); if her guess was correct this plaintext block will get encrypted to CAlice by Alice. This is because of the following simple observation:
CAlice = E(IV1 xor PAlice) = E(IV2 xor (IV2 xor IV1 xor PAlice)). Depending on whether the IV for a cryptographic scheme must be random or only unique the scheme is either called randomized or stateful. While randomized schemes always require the IV chosen by a sender to be forwarded to receivers, stateful schemes allow sender and receiver to share a common IV state, which is updated in a predefined way at both sides.
Блоковые шифры
Блочное шифрование данных обычно описывается как режим работы. Режимы работы в основном определены для шифрования и аутентификации, хотя существуют и более новые разработки, объединяющие оба решения в так называемых режимах аутентифицированного шифрования. В то время как режимы шифрования и аутентифицированного шифрования обычно используют вектор инициализации (IV), соответствующий размеру блока шифра, режимы аутентификации часто реализуются как детерминированные алгоритмы, при этом IV устанавливается в ноль или другое фиксированное значение.
Шифры потоков
В потоковых шифрах векторы инициализации (IV) загружаются в ключевое внутреннее секретное состояние шифра, после чего выполняется несколько раундов шифрования перед выдачей первого бита выходных данных. В целях повышения производительности разработчики потоковых шифров стремятся минимизировать количество этих раундов, однако определение минимально необходимого количества раундов для обеспечения безопасности потоковых шифров – непростая задача. Учитывая также такие факторы, как потеря энтропии, свойственная каждой конкретной конструкции шифра, связанные IV и другие атаки, использующие IV, представляют собой известную угрозу безопасности для потоковых шифров, что делает загрузку IV в потоковых шифрах серьезной проблемой и предметом продолжающихся исследований.
ВЭП IV
Алгоритм шифрования 802.11 под названием WEP (сокращение от Wired Equivalent Privacy) использовал короткий 24-битный IV, что приводило к повторному использованию IV с одним и тем же ключом, из-за чего его было легко взломать. Атака с помощью внедрения пакетов позволяла взламывать WEP за считанные секунды. В конечном итоге это привело к отказу от использования WEP.
SSL 2.0 IV
В режиме шифрования блоками с цепочкой (режим CBC) IV не обязательно должен быть секретным, но должен быть непредсказуемым (в частности, для любого заданного открытого текста не должно быть возможности предсказать IV, который будет ассоциирован с этим открытым текстом до генерации IV) в момент шифрования. Кроме того, для режима обратной связи по выходу (режим OFB) IV должен быть уникальным. В частности, (ранее) распространенная практика повторного использования последнего блока шифротекста сообщения в качестве IV для следующего сообщения является небезопасной (например, этот метод использовался в SSL 2.0). Если злоумышленник знает IV (или предыдущий блок шифротекста) до указания следующего открытого текста, он может проверить свои предположения об открытом тексте какого-либо блока, который был зашифрован тем же ключом ранее. Это известно как атака TLS CBC IV, также называемая атакой BEAST.