Потоковый шифр - Stream cipher

Работа ключевой поток генератор в A5 / 1, поточный шифр на основе LFSR, используемый для шифрования разговоров по мобильному телефону.

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

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

Свободное вдохновение из одноразового блокнота

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

Потоковый шифр использует гораздо меньший и более удобный ключ, например 128 бит. На основе этого ключа он генерирует псевдослучайный поток ключей, который может быть объединен с цифрами открытого текста аналогично одноразовому блокноту. Однако за это приходится платить. Ключевой поток теперь псевдослучайный, а значит, не совсем случайный. Доказательство безопасности, связанное с одноразовым блокнотом, больше не действует. Потоковый шифр вполне может оказаться полностью небезопасным.

Типы

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

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

Шифр Лоренца SZ машина, использовавшаяся немецкими военными во время Второй мировой войны

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

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

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

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

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

Примером самосинхронизирующегося потокового шифра является блочный шифр в зашифрованная обратная связь (CFB) Режим.

На основе регистров сдвига с линейной обратной связью

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

Нелинейные комбинирующие функции

Один из подходов - использовать п LFSR параллельно, их выходы объединены с помощью п-ввод двоичной логической функции (F).

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

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

Обычно LFSR меняются регулярно. Один из подходов к введению нелинейности состоит в том, чтобы LFSR синхронизировался нерегулярно, управляемый выходом второго LFSR. К таким генераторам относятся импульсный генератор, то генератор переменного шага и усадочный генератор.

An генератор переменного шага состоит из трех LFSR, которые для удобства назовем LFSR0, LFSR1 и LFSR2. Выход одного из регистров решает, какой из двух других должен использоваться; например, если LFSR2 выдает 0, LFSR0 синхронизируется, а если он выдает 1, вместо этого синхронизируется LFSR1. Выход - это исключающее ИЛИ последнего бита, созданного LFSR0 и LFSR1. Начальное состояние трех LFSR является ключевым.

Импульсный генератор (Бет и Пайпер, 1984) состоит из двух LFSR. Один LFSR синхронизируется, если вывод секунды равен 1, в противном случае он повторяет свой предыдущий вывод. Затем этот выходной сигнал (в некоторых версиях) объединяется с выходом третьего LFSR, синхронизируемого с регулярной частотой.

В усадочный генератор использует другой подход. Используются два LFSR, оба регулярно синхронизируются. Если выход первого LFSR равен 1, выход второго LFSR становится выходом генератора. Однако, если первый LFSR выводит 0, вывод второго отбрасывается, и генератор не выводит никаких битов. Этот механизм страдает от временных атак на второй генератор, поскольку скорость на выходе может изменяться в зависимости от состояния второго генератора. Этого можно избежать путем буферизации вывода.

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

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

Другой дизайн

RC4 является одним из наиболее широко используемых конструкций потокового шифра.

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

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

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

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

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

Короткие периоды для потоковых шифров были практической проблемой. Например, 64-битные блочные шифры типа DES может использоваться для генерации ключевого потока в обратная связь по выходу (OFB) режим. Однако, если не использовать полную обратную связь, результирующий поток будет иметь период около 2³² блоки в среднем; для многих приложений период слишком мал. Например, если шифрование выполняется со скоростью 8 мегабайты в секунду, поток периода 2³² блоки будут повторяться примерно через полчаса.^{[сомнительный – обсудить]}

Некоторые приложения, использующие потоковый шифр RC4 уязвимы из-за слабых мест в программе настройки ключей RC4; новые приложения должны либо избегать RC4, либо убедиться, что все ключи уникальны и в идеале не связанный (например, генерируется хорошо посеянным CSPRNG или криптографическая хеш-функция ) и что первые байты ключевого потока отбрасываются.

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

Применение

Потоковые шифры часто используются из-за их скорости и простоты реализации на оборудовании, а также в приложениях, где открытый текст имеет неизвестную длину, например, безопасный беспроводной подключение. Если блочный шифр (не работающий в режиме потокового шифрования), которые должны были использоваться в этом типе приложений, разработчик должен был бы выбрать либо эффективность передачи, либо сложность реализации, поскольку блочные шифры не могут напрямую работать с блоками короче их размера блока. Например, если 128-битный блочный шифр получил отдельные 32-битные пакеты открытого текста, три четверти переданных данных будут набивка. Блочные шифры должны использоваться в кража зашифрованного текста или остаточное завершение блока режим, чтобы избежать заполнения, в то время как потоковые шифры устраняют эту проблему, естественно работая с наименьшим блоком, который может быть передан (обычно байтами).

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

ЧаЧа становится наиболее широко используемым потоковым шифром в программном обеспечении^[1]; другие включают: RC4,A5 / 1,A5 / 2,Хамелеон, РЫБЫ, Спираль,ИСААК, MUGI,Панама,Феликс, Щука,Сальса20,ПЕЧАТЬ, SOBER,СОБЕР-128,иПроснуться.

Сравнение

Ручей шифр	Творчество Дата	Скорость (циклов на байт )	(биты)			Атака
Ручей шифр	Творчество Дата	Скорость (циклов на байт )	Эффективный ключ-длина	Вектор инициализации	Внутренний штат	Самый известный	Вычислительная сложность
A5 / 1	1989	?	54 или 64 (дюйм 2G )	22 (в 2G)	64	Активный КПА ИЛИ КПА компромисс между временем и памятью	~ 2 секунды ИЛИ 2^39.91
A5 / 2	1989	?	54	114	64?	Активный	4.6 миллисекунды
Ахтербан-128/80	2006	1 (аппаратный)	80/128	80/128	297/351	Грубая сила для длины кадра L ≤ 2⁴⁴. Корреляционная атака для L ≥ 2⁴⁸.	2⁸⁰ соотв. 2¹²⁸ для L ≤ 2⁴⁴.
CryptMT	2005	?	Переменная	до 19968	19968	Не указано (2008)	Не указано (2008)
РЫБЫ	1993	?	Переменная	?	?	Атака с использованием известного открытого текста	2¹¹
Зерно	До 2004 г.	?	80	64	160	Ключевые выводы	2⁴³
HC-256	До 2004 г.	4 (Вт_P4)	256	256	65536	?	?
ИСААК	1996	2.375 (Вт_{64-битный}) – 4.6875 (Вт_{32-битный})	8–8288 (обычно 40–256)	Нет данных	8288	(2006) Первый раунд деривация слабого внутреннего состояния	4.67×10¹²⁴⁰ (2001)
MUGI	1998–2002	?	128	128	1216	Не указано (2002)	~ 2⁸²
ПАНАМА	1998	2	256	128?	1216?	Коллизии хэшей (2001)	2⁸²
Феликс	До 2004 г.	до 8 (Вт_x86)	256 + 128 бит nonce	128?	?	Дифференциальный (2006)	2³⁷
Щука	1994	?	Переменная	?	?	Не указано (2004)	Не указано (2004)
Py	До 2004 г.	2.6	8–2048? (обычно 40–256?)	64	8320	Криптоаналитический теория (2006)	2⁷⁵
Кролик	2003-февраль	3.7(Вт_P3) – 9.7(Вт_ARM7)	128	64	512	Не указано (2006)	Не указано (2006)
RC4	1987	7 W_P5^[2]	8–2048 (обычно 40–256)	RC4 не принимает IV. Если кто-то хочет IV, его нужно как-то смешать с ключом.	2064	Шамир начальные байты ключ-вывод ИЛИ КПА	2¹³ ИЛИ 2³³
Сальса20	До 2004 г.	4.24 (Вт_G4) – 11.84 (Вт_P4)	256	64-битный одноразовый номер + позиция 64-битного потока	512	Вероятностный метод нейтральных долот	2²⁵¹ на 8 туров (2007)
Кричать	2002	4–5 (Вт_мягкий)	128 + 128-битный одноразовый номер	32?	64-битная функция раунда	?	?
ПЕЧАТЬ	1997	?	?	32?	?	?	?
СНЕГ	До 2003 г.	?	128 или 256	32	?	?	?
СОБЕР-128	2003	?	до 128	?	?	Кузница сообщений	2⁻⁶
СОСЕМАНУК	До 2004 г.	?	128	128	?	?	?
Тривиум	До 2004 г.	4 (Вт_x86) – 8 (Вт_LG)	80	80	288	Атака грубой силы (2006)	2¹³⁵
Тьюринг	2000–2003	5.5 (Вт_x86)	?	160	?	?	?
ЖИЛЕТ	2005	42 (Вт_ASIC) – 64 (Вт_FPGA)	Переменная (обычно 80–256)	Переменная (обычно 80–256)	256–800	Не указано (2006)	Не указано (2006)
Проснуться	1993	?	?	?	8192	CPA & CCA	Уязвимый
Ручей шифр	Творчество Дата	Скорость (циклов на байт )	(биты)			Атака
Ручей шифр	Творчество Дата	Скорость (циклов на байт )	Эффективный ключ-длина	Вектор инициализации	Внутренний штат	Самый известный	Вычислительная сложность

Мелочи

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

Смотрите также

Заметки

^ https://blog.cloudflare.com/do-the-chacha-better-mobile-performance-with-cryptography/
^ П. Праситсангари и П. Кришнамурти (2003). «Анализ энергопотребления алгоритмов RC4 и AES в беспроводных локальных сетях» (PDF). Архивировано из оригинал (PDF) на 2013-12-03. Цитировать журнал требует | журнал = (Помогите)

использованная литература

Мэтт Дж. Б. Робшоу, Технический отчет Stream Ciphers TR-701, версия 2.0, RSA Laboratories, 1995 (PDF).
Бет, Томас; Пайпер, Фред (1985). Генератор остановки и движения (PDF). ЕВРОКРИПТ '84. С. 88–92. Дои:10.1007/3-540-39757-4_9.
Кристоф Паар, Ян Пельцль, «Потоковые шифры», Глава 2 «Понимание криптографии, Учебник для студентов и практиков». (сопутствующий веб-сайт содержит онлайн-курс криптографии, охватывающий поточные шифры и LFSR), Springer, 2009.

внешние ссылки

[1] ttps://blog.cloudflare.com/do-the-chacha-better-mobile-performance-with-cryptography/

[2] П. Праситсангари и П. Кришнамурти (2003). «Анализ энергопотребления алгоритмов RC4 и AES в беспроводных локальных сетях» (PDF). Архивировано из оригинал (PDF) на 2013-12-03. Цитировать журнал требует | журнал = (Помогите)

[1]

[2]