Потоковое шифрование

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

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

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

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

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

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

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

Синхронные потоковые шифры [ править ]

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

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

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

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

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

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

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

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

Нелинейные функции объединения [ править ]

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

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

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

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

Другие конструкции [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

ChaCha становится наиболее широко используемым потоковым шифром в программном обеспечении; ^[2] другие включают: RC4 , А5/1 , А5/2 , Хамелеон , РЫБА , Хеликс , ИСААК , МУГИ , Панама , Феликс , Щука , Сальса20 , ТЮЛЕНЬ , ТРЕЗВЫЙ , ТРЕЗВЫЙ-128 ,и БУДИТЬ .

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

Транслировать шифровать	Создание дата	Скорость ( циклов на байт )	(биты)			Атака
Транслировать шифровать	Создание дата	Скорость ( циклов на байт )	Эффективный ключа длина	Вектор инициализации	Внутренний состояние	Самый известный	вычислительный сложность
А5/1	1989	?	54 или 64 (в 2G )	22 (в 2G)	64	Активный КПА ИЛИ KPA Компромисс времени и памяти	~ 2 секунды ИЛИ 2 ^39.91
А5/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 ⁴⁴.
КриптМТ	2005	?	Переменная	до 19968 г.	19968	— (2008)	— (2008)
Крипто-1	До 1994 г.	?	48	16	48	Активная КНА (2008)	40 мс ИЛИ 2 ⁴⁸ (2008) ^[3]
E0 (шифр)	До 1999 г.	?	Переменная (обычно 128)	4	132	КНА (2005)	2 ³⁸ (2005) ^[4]
РЫБА	1993	?	Переменная	?	?	Атака по известному открытому тексту	2 ¹¹
Зерно	До 2004 г.	?	80	64	160	Ключевое происхождение	2 ⁴³
ХК-256	До 2004 г.	4 (В _П4 )	256	256	65536	?	?
ИСААК	1996	2,375 ( _{64-битная версия} ) – 4,6875 ( _{32-разрядная версия} )	8–8288 (обычно 40–256)	—	8288	(2006) Первый тур вывод слабого внутреннего состояния	4.67×10 ¹²⁴⁰ (2001)
МИККИ	До 2004 г.	?	80	Переменная (от 0 до 80)	200	Атака дифференциального отказа (2013)	2 ^32.5 (2013) ^[5]
Я НАДЕЮСЬ	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)
Пи	До 2004 г.	2.6	8–2048? (обычно 40–256?)	64	8320	Криптоаналитическая теория (2006)	2 ⁷⁵
Кролик	2003-февраль	3,7 (W _P3 ) – 9,7 (W _ARM7 )	128	64	512	— (2006)	— (2006)
RC4	1987	7 Вт _P5^[6]	8–2048 (обычно 40–256)	RC4 не принимает капельницу. Если кто-то желает получить IV, его нужно каким-то образом смешать с ключом.	2064	Шамира в начальных байтах Получение ключа ИЛИ KPA	2 ¹³ ИЛИ 2 ³³
Сальса20	До 2004 г.	4,24 (Ш _G4 ) – 11,84 (В _П4 )	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 (Вт _ЛГ )	80	80	288	Атака грубой силы (2006)	2 ¹³⁵
Тьюринг	2000–2003	5,5 (Ш _x86 )	?	160	?	?	?
ЖИЛЕТ	2005	42 ( _ВАСИК ) – 64 (Вт _ПЛИС )	Переменная (обычно 80–256)	Переменная (обычно 80–256)	256–800	— (2006)	— (2006)
БУДИТЬ	1993	?	?	?	8192	цена за конверсию и цена за конверсию	Уязвимый
Транслировать шифровать	Создание дата	Скорость ( циклов на байт )	(биты)			Атака
Транслировать шифровать	Создание дата	Скорость ( циклов на байт )	Эффективный ключа длина	Вектор инициализации	Внутренний состояние	Самый известный	вычислительный сложность

Общая информация [ править ]

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

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

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

^ Дин, Артур; Краус, Аарон (2021). «Глава 3: Домен 3: Архитектура и проектирование безопасности». Официальный (ISC) 2 справочник CISSP CBK (6-е изд.). Хобокен, Нью-Джерси: John Wiley & Sons, Inc., с. 232. ИСБН 978-1-119-78999-4 .
^ «Выполняйте ChaCha: повышение производительности мобильных устройств с помощью криптографии» . 23 февраля 2015 г.
^ Гарсия, Флавио Д.; де Конинг Ганс, Герхард; Мюйрерс, Рубен; ван Россум, Питер; Вердульт, Роэль; Шрёр, Ронни Уичерс; Джейкобс, Барт (4 октября 2008 г.). «Разборка MIFARE Classic» (PDF) . 13-й Европейский симпозиум по исследованиям в области компьютерной безопасности (ESORICS 2008), LNCS, Springer. Архивировано из оригинала (PDF) 23 февраля 2021 года . Проверено 25 июня 2022 г.
^ Лу, Йи; Мейер, Вилли; Водене, Серж (2005). «Атака с условной корреляцией: практическая атака на шифрование Bluetooth». Достижения в криптологии – CRYPTO 2005 (PDF) . Конспекты лекций по информатике. Том. 3621. Санта-Барбара, Калифорния, США. стр. 97–117. CiteSeerX 10.1.1.323.9416 . дои : 10.1007/11535218_7 . ISBN 978-3-540-28114-6 . {{cite book}}: |journal= игнорируется ( помощь ) CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Баник, Субхадип; Майтра, Субхамой; Саркар, Сантану (2013). «Дифференциальная атака на МИККИ 2.0» . Архив электронной печати по криптологии .
^ П. Праситсангари и П. Кришнамурти (2003). «Анализ энергопотребления алгоритмов RC4 и AES в беспроводных локальных сетях» (PDF) . IEEE Глобеком . Архивировано из оригинала (PDF) 3 декабря 2013 г.

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

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

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

[1] Дин, Артур; Краус, Аарон (2021). «Глава 3: Домен 3: Архитектура и проектирование безопасности». Официальный (ISC) 2 справочник CISSP CBK (6-е изд.). Хобокен, Нью-Джерси: John Wiley & Sons, Inc., с. 232. ИСБН 978-1-119-78999-4 .

[2] «Выполняйте ChaCha: повышение производительности мобильных устройств с помощью криптографии» . 23 февраля 2015 г.

[3] Гарсия, Флавио Д.; де Конинг Ганс, Герхард; Мюйрерс, Рубен; ван Россум, Питер; Вердульт, Роэль; Шрёр, Ронни Уичерс; Джейкобс, Барт (4 октября 2008 г.). «Разборка MIFARE Classic» (PDF) . 13-й Европейский симпозиум по исследованиям в области компьютерной безопасности (ESORICS 2008), LNCS, Springer. Архивировано из оригинала (PDF) 23 февраля 2021 года . Проверено 25 июня 2022 г.

[4] Лу, Йи; Мейер, Вилли; Водене, Серж (2005). «Атака с условной корреляцией: практическая атака на шифрование Bluetooth». Достижения в криптологии – CRYPTO 2005 (PDF) . Конспекты лекций по информатике. Том. 3621. Санта-Барбара, Калифорния, США. стр. 97–117. CiteSeerX 10.1.1.323.9416 . дои : 10.1007/11535218_7 . ISBN 978-3-540-28114-6 . {{cite book}}: |journal= игнорируется ( помощь ) CS1 maint: отсутствует местоположение издателя ( ссылка )

[5] Баник, Субхадип; Майтра, Субхамой; Саркар, Сантану (2013). «Дифференциальная атака на МИККИ 2.0» . Архив электронной печати по криптологии .

[6] П. Праситсангари и П. Кришнамурти (2003). «Анализ энергопотребления алгоритмов RC4 и AES в беспроводных локальных сетях» (PDF) . IEEE Глобеком . Архивировано из оригинала (PDF) 3 декабря 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]