Потоковые шифры: принципы и особенности

Введение

Тип симметричного шифра

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

Вдохновение от одноразового подкладки

Шифры потока можно рассматривать как приближение к принципу работы теоретически невзламываемого шифра – одноразового шифра (OTP). Одноразовый шифр использует ключевой поток, состоящий из полностью случайных чисел. Этот ключевой поток поочередно комбинируется с цифрами открытого текста для формирования шифротекста. Безопасность этой системы была доказана Клодом Э. Шенноном в 1949 году. Однако ключевой поток должен генерироваться абсолютно случайным образом, иметь длину не меньше длины открытого текста и не использоваться повторно. Это делает систему сложной в реализации для многих практических задач, и в результате одноразовый шифр не получил широкого распространения, за исключением наиболее критически важных приложений. Генерация, распространение и управление ключами имеют решающее значение для таких приложений. Шифр потока использует гораздо меньший и более удобный ключ, например, 128 бит. На основе этого ключа он генерирует псевдослучайный ключевой поток, который комбинируется с цифрами открытого текста аналогичным образом, как и в одноразовом шифре. Однако это достигается ценой потери безопасности. Ключевой поток теперь является псевдослучайным и, следовательно, не является истинно случайным. Доказательство безопасности, применимое к одноразовому шифру, больше недействительно. Вполне возможно, что шифр потока окажется полностью небезопасным.

Типы

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

Шифры синхронного потока

В синхронном потоковом шифре поток псевдослучайных цифр генерируется независимо от открытого и зашифрованного сообщений, а затем комбинируется с открытым текстом (для шифрования) или зашифрованным текстом (для расшифровки). В наиболее распространенной форме используются двоичные цифры (биты), а ключевой поток комбинируется с открытым текстом с использованием операции исключающего ИЛИ (XOR). Это называется двоичным аддитивным потоковым шифром. В синхронном потоковом шифре отправитель и получатель должны быть строго синхронизированы для успешной расшифровки. Если при передаче сообщения добавляются или удаляются цифры, синхронизация теряется. Для восстановления синхронизации можно систематически перебирать различные сдвиги, чтобы получить правильную расшифровку. Другой подход заключается в добавлении меток к зашифрованному тексту в регулярных точках выходного потока. Однако, если цифра повреждена при передаче, а не добавлена или потеряна, то будет затронут только один бит открытого текста, и ошибка не распространится на другие части сообщения. Это свойство полезно при высокой вероятности ошибок передачи, но затрудняет обнаружение ошибки без дополнительных механизмов. Более того, из-за этого свойства синхронные потоковые шифры очень уязвимы к активным атакам: если злоумышленник может изменить цифру в зашифрованном тексте, он может внести предсказуемые изменения в соответствующий бит открытого текста; например, инвертирование бита в зашифрованном тексте приведет к инвертированию того же бита в открытом тексте.

Самосинхронизирующие потоковые шифры

Другой подход использует несколько предыдущих N цифр шифротекста для вычисления ключевого потока. Такие схемы известны как самосинхронизирующиеся потоковые шифры, асинхронные потоковые шифры или шифротекстовый автоключ (CTAK). Идея самосинхронизации была запатентована в 1946 году и имеет то преимущество, что приемник автоматически синхронизируется с генератором ключевого потока после получения N цифр шифротекста, что упрощает восстановление в случае потери или добавления цифр в поток сообщений. Одиночные ошибки ограничены в своем воздействии, влияя только на максимум N цифр открытого текста. Примером самосинхронизирующегося потокового шифра является блочный шифр в режиме обратной связи по шифру (CFB).

Основанные на линейных регрессорах смены

Потоковые шифры часто строятся с использованием линейных регистров сдвига с обратной связью (LFSR), поскольку их можно легко реализовать в аппаратном обеспечении и удобно анализировать математически. Однако использование LFSR само по себе недостаточно для обеспечения надёжной безопасности. Были предложены различные схемы для повышения безопасности LFSR.

Нелинейные функции комбинирования

Поскольку LFSR по своей сути линейны, одним из способов устранения этой линейности является подача выходов нескольких параллельных LFSR на нелинейную булеву функцию для создания комбинированного генератора. Различные свойства такой комбинирующей функции критически важны для обеспечения безопасности результирующей схемы, например, для предотвращения корреляционных атак.

генераторы с тактовым управлением

Обычно LFSR продвигаются по шагам регулярно. Один из способов внести нелинейность – использовать нерегулярную синхронизацию LFSR, управляемую выходом второго LFSR. К таким генераторам относятся генератор "стоп-и-гоу", генератор с чередующимся шагом и генератор сжатия. Генератор с чередующимся шагом состоит из трех LFSR, которые для удобства мы будем называть LFSR0, LFSR1 и LFSR2. Выход одного из регистров определяет, какой из двух других использовать; например, если LFSR2 выдает 0, то выполняется синхронизация LFSR0, а если 1 – то LFSR1. Выход формируется как исключающее ИЛИ последнего бита, сгенерированного LFSR0 и LFSR1. Начальное состояние трех LFSR является ключом. Генератор "стоп-и-гоу" (Beth и Piper, 1984) состоит из двух LFSR. Один LFSR синхронизируется, если выход второго равен 1, в противном случае он повторяет свой предыдущий выход. Затем этот выход (в некоторых вариантах) комбинируется с выходом третьего LFSR, синхронизируемого с регулярной частотой. Генератор сжатия использует иной подход. Используются два LFSR, оба синхронизируемые регулярно. Если выход первого LFSR равен 1, выход второго LFSR становится выходом генератора. Однако, если первый LFSR выдает 0, выход второго отбрасывается, и генератор не выдает бит. Этот механизм уязвим к временным атакам на второй генератор, поскольку скорость выдачи выходных данных изменяется в зависимости от состояния второго генератора. Это можно смягчить, используя буферизацию выходных данных.

Генератор фильтров

Другой подход к повышению безопасности LFSR — передача всего состояния одного LFSR в нелинейную фильтрующую функцию.

Другие конструкции

Вместо линейного привода можно использовать нелинейную функцию обновления. Например, Климов и Шамир предложили треугольные функции (Т-функции) с одним циклом на n-битных словах.

Безопасность

Для того чтобы потоковый шифр был безопасным, его ключевой поток должен иметь большой период, и должно быть невозможно восстановить ключ шифра или его внутреннее состояние по ключевому потоку. Криптографы также требуют, чтобы ключевой поток не содержал даже незначительных смещений, позволяющих злоумышленникам отличить его от случайного шума, и не имел обнаруживаемых взаимосвязей между ключевыми потоками, соответствующими связанным ключам или связанным криптографическим нонсам. Это должно быть справедливо для всех ключей (не должно быть слабых ключей), даже если злоумышленник может знать или выбирать часть открытого или зашифрованного текста. Как и другие криптографические атаки, атаки на потоковые шифры могут быть теоретическими, то есть не обязательно представлять собой практические способы взлома шифра, но указывать на потенциальные уязвимости. Безопасное использование надёжного синхронного потокового шифра требует, чтобы один и тот же ключевой поток никогда не использовался повторно. Обычно это означает, что для каждого обращения к шифру должен предоставляться новый нонс или ключ. Разработчики приложений также должны учитывать, что большинство потоковых шифров обеспечивают конфиденциальность, а не аутентичность: зашифрованные сообщения могут быть изменены в процессе передачи. Короткие периоды для потоковых шифров представляют практическую проблему. Например, 64-битные блочные шифры, такие как DES, могут использоваться для генерации ключевого потока в режиме обратной связи по выходу (OFB). Однако, при отсутствии полной обратной связи, полученный поток имеет период в среднем около 2<sup>32</sup> блоков; для многих приложений этот период слишком мал. Например, при скорости шифрования 8 мегабайт в секунду поток с периодом 2<sup>32</sup> блоков повторится примерно через полчаса. Некоторые приложения, использующие потоковый шифр RC4, уязвимы из-за недостатков в процедуре инициализации ключа RC4; новые приложения должны либо избегать использования RC4, либо обеспечивать уникальность всех ключей и, в идеале, их независимость (например, генерируя их с помощью хорошо инициализированного CSPRNG или криптографической хеш-функции), а также отбрасывать первые байты ключевого потока. Компоненты потоковых шифров часто проще для понимания, чем компоненты блочных шифров, и поэтому с меньшей вероятностью скрывают случайные или преднамеренные уязвимости.

For a stream cipher to be secure, its keystream must have a large period, and it must be impossible to recover the cipher's key or internal state from the keystream. Cryptographers also demand that the keystream be free of even subtle biases that would let attackers distinguish a stream from random noise, and free of detectable relationships between keystreams that correspond to related keys or related cryptographic nonces. That should be true for all keys (there should be no weak keys), even if the attacker can know or choose some plaintext or ciphertext. As with other attacks in cryptography, stream cipher attacks can be certificational so they are not necessarily practical ways to break the cipher but indicate that the cipher might have other weaknesses. Securely using a secure synchronous stream cipher requires that one never reuse the same keystream twice. That generally means a different nonce or key must be supplied to each invocation of the cipher. Application designers must also recognize that most stream ciphers provide not authenticity but privacy: encrypted messages may still have been modified in transit. Short periods for stream ciphers have been a practical concern. For example, 64 bit block ciphers like DES can be used to generate a keystream in output feedback (OFB) mode. However, when not using full feedback, the resulting stream has a period of around 232 blocks on average; for many applications, the period is far too low. For example, if encryption is being performed at a rate of 8 megabytes per second, a stream of period 232 blocks will repeat after about a half an hour. Some applications using the stream cipher RC4 are attackable because of weaknesses in RC4's key setup routine; new applications should either avoid RC4 or make sure all keys are unique and ideally unrelated (such as generated by a well seeded CSPRNG or a cryptographic hash function) and that the first bytes of the keystream are discarded. The elements of stream ciphers are often much simpler to understand than block ciphers and are thus less likely to hide any accidental or malicious weaknesses.

Сравнение

Streamcipher Дата создания Скорость (циклов на байт) (бит) Атака Эффективность длина ключа Вектор инициализации Внутреннее состояние Наиболее известная вычислительная сложность A5/11989 54 или 64 (в 2G) 22 (в 2G) 64 Активный KPA или KPA компромисс времени и памяти ~ 2 секунды или 239.91 A5/21989 54 114 64? Активный 4.6 миллисекунды Achterbahn 128/80 2006 1 (аппаратное обеспечение) 80/128 80/128 297/351 Брутфорс для длин кадров L ≤ 244. Корреляционная атака для L ≥ 248, 280 или 2128 для L ≤ 244. CryptMT2005 Переменная до 19968 19968 (2008) (2008) Crypto 1 До 1994 48 16 48 Активный KPA (2008) 40 мс или 248 (2008) E0 (шифр) До 1999 Переменная (обычно 128) 4 132 KPA (2005) 238 (2005) FISH1993 Переменная Атака на основе известного открытого текста 211 Grain До 2004 80 64 160 Вывод ключа 243 HC 256 До 2004 4 (WP4) 256 256 65536 ISAAC1996 2.375 (W64 бит) – 4.6875 (W32 бит) 8–8 288 (обычно 40–256) 8288 (2006) Первый раунд, слабое выведение внутреннего состояния 4.67×10^12 40 (2001) MICKEY До 2004 80 Переменная (0 до 80) 200 Дифференциальная атака (2013) 232.5 MUGI 1998–2002 128 128 1216 ~ 282 PANAMA 1998 22 56 128? 1216? Коллизии хеш-функций (2001) 282 Phelix До 2004 до 8 (Wx86) 256 + 128-битный одноразовый номер 128? Дифференциальная (2006) 237 Pike 1994 Переменная (2004) (2004) Py До 2004 2.68–2048? (обычно 40–256?) 64 8320 Криптоаналитическая теория (2006) 275 Rabbit 2003 Фев 3.7 (WP3) – 9.7 (WARM7) 128 64 512 (2006) (2006) RC4 1987 7 WP5 8–2048 (обычно 40–256) RC4 не использует IV. Если требуется IV, его необходимо смешать с ключом. 2064 Shamir начальные байты вывод ключа или KPA 213 или 233 Salsa20 До 2004 4.24 (WG4) – 11.84 (WP4) 256 64-битный одноразовый номер + 64-битная позиция потока 512 Вероятностный метод нейтральных битов 2251 для 8 раундов (2007) Scream 2002 4–5 (Wsoft) 128 + 128-битный одноразовый номер 32? 64-битная раундовая функция SEAL 1997 32? SNOW До 2003 128 или 256 32 SOBER 128 2003 до 128 Подделка сообщения 2^-6 SOSEMANUK До 2004 128 128 Trivium До 2004 4 (Wx86) – 8 (WLG) 80 80 288 Брутфорс (2006) 2135 Turing 2000–2003 5.5 (Wx86) 160 VEST 2005 42 (WASIC) – 64 (WFPGA) Переменная (обычно 80–256) Переменная (обычно 80–256) 256–800 (2006) (2006) WAKE 1993 8 192 CPA и CCA Уязвим

StreamcipherCreationdate Speed(cycles per byte)(bits)AttackEffectivekey length Initialization vector InternalstateBest known ComputationalcomplexityA5/1198954 or 64 (in 2G)22 (in 2G)64Active KPA ORKPA time–memory tradeoff~ 2 seconds OR239.91A5/219895411464?Active4.6 milliseconds Achterbahn 128/8020061 (hardware)80/12880/128297/351Brute force for frame lengths L ≤ 244. Correlation attack for L ≥ 248.280 resp. 2128 for L ≤ 244. CryptMT2005 Variable up to 19968 19968 (2008) (2008)Crypto 1 Pre 1994 48 16 48 Active KPA (2008) 40 ms OR248 (2008)E0 (cipher) Pre 1999 Variable(usually 128) 4 132 KPA (2005) 238 (2005)FISH1993VariableKnown plaintext attack211Grain Pre 20048064160Key derivation243HC 256 Pre 20044 (WP4)25625665536ISAAC19962.375 (W64 bit) –4.6875 (W32 bit)8–8288(usually 40–256)8288(2006) First roundweak internal state derivation4.67×101240 (2001)MICKEY Pre 2004 80 Variable (0 to 80) 200 Differential Fault Attack (2013) 232.5 (2013)MUGI1998–20021281281216 (2002)~ 282PANAMA19982256128?1216?Hash collisions (2001)282Phelix Pre 2004 up to 8 (Wx86)256 + a 128 bit nonce128?Differential (2006)237Pike1994Variable (2004) (2004)Py Pre 20042.68–2048? (usually 40–256? )648320Cryptanalytic theory (2006)275Rabbit2003 Feb3.7(WP3) – 9.7(WARM7)12864512 (2006) (2006)RC419877 WP58–2048(usually 40–256)RC4 does not take an IV. If one desires an IV, it must be mixed into the key somehow.2064Shamir initial bytes key derivation OR KPA213 OR 233Salsa20 Pre 20044.24 (WG4) –11.84 (WP4)256 a 64 bit nonce + a 64 bit stream position512Probabilistic neutral bits method2251 for 8 rounds (2007)Scream20024–5 (Wsoft)128 + a 128 bit nonce32?64 bit round functionSEAL199732?SNOW Pre 2003128 or 25632SOBER 1282003up to 128Message forge2−6SOSEMANUK Pre 2004128128Trivium Pre 20044 (Wx86) –8 (WLG)8080288Brute force attack (2006)2135Turing2000–20035.5 (Wx86)160VEST200542 (WASIC) –64 (WFPGA)Variable(usually 80–256)Variable(usually 80–256)256–800 (2006) (2006)WAKE19938192CPA & CCAVulnerableStreamcipherCreationdateSpeed(cycles per byte)(bits)AttackEffectivekey lengthInitialization vectorInternalstateBest knownComputationalcomplexity

Интересные факты

В документах Агентства национальной безопасности США иногда используется термин "алгоритмы комбинирования", обозначающий алгоритмы, использующие некоторую функцию для объединения генератора псевдослучайных чисел (PRNG) с потоком открытого текста.