Потоковый шифр

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

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

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

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

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

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

Типы [ править ]

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

Шифры синхронного потока [ править ]

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

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

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

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

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

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

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

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

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

Функции нелинейного комбинирования [ править ]

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

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

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июнь 2008 г. )

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

Обычно LFSR меняются регулярно. Один из подходов к введению нелинейности состоит в том, чтобы LFSR синхронизировался нерегулярно, управляемый выходом второго 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 в функцию нелинейной фильтрации .

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июнь 2008 г. )

Другой дизайн [ править ]

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

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

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июнь 2008 г. )

Безопасность [ править ]

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

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

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

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

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

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

Использование [ править ]

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

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

ChaCha становится наиболее широко используемым потоковым шифром в программном обеспечении; ^[1] другие включают: RC4 , A5 / 1 , A5 / 2 , Chameleon , FISH , Helix , ISAAC , MUGI , Panama , Phelix , Pike , Salsa20 , SEAL , SOBER , SOBER-128 и WAKE .

Сравнение [ править ]

Этот раздел требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. ( Июль 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Потоковый шифр	Дата создания	Скорость ( циклов на байт )	(биты)			Атака
Потоковый шифр	Дата создания	Скорость ( циклов на байт )	Эффективная длина ключа	Вектор инициализации	Внутреннее состояние	Самый известный	Вычислительная сложность
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 48 .	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-битный одноразовый номер	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 Вт P5 ^[2]	8–2048 (обычно 40–256)	RC4 не принимает IV. Если кто-то хочет IV, его нужно как-то смешать с ключом.	2064	Получение ключа начальных байтов Шамира ИЛИ KPA	2 ¹³ ИЛИ 2 ³³
Сальса20	До 2004 г.	4,24 (Вт G4 ) - 11,84 (Вт P4 )	256	64-битный одноразовый номер + позиция 64-битного потока	512	Вероятностный метод нейтральных долот	2 ²⁵¹ 8 раундов (2007)
Крик	2002 г.	4–5 ( мягкий W )	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 (W ASIC ) - 64 (W FPGA )	Переменная (обычно 80–256)	Переменная (обычно 80–256)	256–800	Не указано (2006)	Не указано (2006)
БУДИТЬ	1993 г.	?	?	?	8192	CPA и CCA	Уязвимый
Потоковый шифр	Дата создания	Скорость ( циклов на байт )	(биты)			Атака
Потоковый шифр	Дата создания	Скорость ( циклов на байт )	Эффективная длина ключа	Вектор инициализации	Внутреннее состояние	Самый известный	Вычислительная сложность

Интересные факты [ править ]

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

См. Также [ править ]

eSTREAM
Регистр сдвига с линейной обратной связью (LFSR)
Регистр сдвига с нелинейной обратной связью (NLFSR)

Примечания [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

Технический отчет RSA о работе потокового шифра.
Криптоанализ и разработка потоковых шифров (диссертация Хунцзюня Ву).
Анализ облегченных потоковых шифров (диссертация С. Фишера).

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

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