Википедия

PALS

PALS — потоковый шифр спроектирован как управляемый часами с новым механизмом изменения шагов, основанным на теории систем таким образом, что используемые в нём структуры устойчивы к обычным атакам. В алгоритме PALS используется основной ключ длиной 256 бит и 32-битный ключ сообщения. При разработке PALS основными критериями должны стать устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. В итоге выходной поток ключей практически аналогичен совершенно случайным последовательностям и устойчив к обычным атакам, таким как корреляционные атаки, алгебраическая атака, атака «разделяй и властвуй», атака компромисса времени и памяти и атаки AIDA/ куба[1].

Базовая структура PALS — комбинированный генератор с памятью, управляемый часами[1].

Введение править

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

Криптосистемы потокового шифра — одна из наиболее востребованных систем, имеющая широкое применение в различных областях. Чтобы создать зашифрованный текст в системе потокового шифра псевдослучайный поток ключей объединяется с цифрами открытого текста[1].

Данный шифр предполагает наличие базовых часов, которые имеют согласованный набор основных временных интервалов, которые затем сравниваются с регистром и его выходными данными. Имеется несколько способов установки системы регистров сдвига с линейной обратной связью(РСЛОС) на основе битов. Работа регистра согласована с работой основных часов. Регистр может двигаться медленнее, чем лежащие в основе часы, занимая более одной базовой единицы для сдвига регистров; но можно предположить, что он никогда не будет сдвигаться быстрее, чем часы, так как в противном случае мы можем настроить базовое время тактирования на время шага регистра. Точно также выходной сигнал системы РСЛОС, управляемой часами, может быть согласован с временем часов или может быть замедлен или изменён по времени часов. Если регистр сдвигается с основным временным интервалом, мы ссылаемся на его регулярную блокировку. Случай совпадения выходных данных с основным интервалом времени носит название обычный выходной сигнал[2].

Для построения бесконечной псевдослучайной последовательности с использованием случайной последовательности конечной длины, был предложен новый потоковый шифр PALS, разработанный как комбинированный генератор с управлением по часам с памятью. Начальный вектор из 1600 битов генерируется путём объединения 256-битного главного ключа с ключом сообщения. 32-битный РСЛОС используется для генерации ключа сообщения. Чтобы получить 256-битную последовательность нужно воздействовать функцией scram-5 восемь раз на 32-битный ключ сообщения. Ключ сеанса получается побитовым XOR, получающегося в результате 256-битной последовательности с основным ключом. Период смены ключа — до 4,25 года. На теории систем и полных случайных последовательностях основана генерация ключевого потока в алгоритме PALS[3].

Одним из подходов к проектированию генераторов потока ключей является теория систем. В теории систем особое внимание уделяется на используемые известные атаки. Таким образом, система выполняется так, чтобы она была устойчивой к таким атакам. Криптосистема признается практически безопасной с точки зрения теории систем, если она не может быть взломана какой-либо известной атакой за разумное время[1].

Для передачи данных с высокой скоростью обычно используются алгоритмы потокового шифрования, а алгоритмы, использующие сдвиговые регистры, могут быть использованы в быстрых реализациях. Последовательности с длинными периодами и хорошими статистическими свойствами обеспечиваются РСЛОС максимальной длины. Но они не могут быть использованы напрямую из-за того, что их линейности делает их подверженными атакам с использованием алгебраических методов[4].

Потоковые шифры работают с изменяющимся во времени преобразованием отдельных цифр открытого текста[5].

Потоковые шифры на основе регистров сдвига с линейной обратной связью править

РСЛОС используется для создания псевдослучайной последовательности в потоковом шифре. РСЛОС используется для генерации бесконечного потока битов. Несколько РСЛОС используются для построения потокового шифра в наиболее используемой форме. РСЛОС проявляет линейное свойство. Следовательно, понятие нелинейности было введено для преодоления недостатка линейного свойства путём нерегулярного изменения тактовой частоты РСЛОС[6].

В основном три класса генераторов псевдослучайных чисел используется потоковым шифром на основе РСЛОС, а именно нелинейная комбинация, генераторы с управлением по часам и нелинейный фильтр. Практически все потоковые шифры на основе РСЛОС используют любые из этих нелинейных методов или комбинацию этих методов с некоторыми дополнительными приложениями, такими как добавление счётчика или комбинации различных РСЛОС со сдвиговыми регистрами с нелинейной обратной связью[6].

Для генерации последовательности широко использовались РСЛОС из-за их встроенной рекурсивной структуры, хорошо изученного поведения и более быстрых реализаций в различных приложениях связи, теории кодирования и криптологии. Линейная повторяемость РСЛОС модифицируется нелинейным фильтрованием для достижения более высоких линейных сложностей и хороших статистических свойств в криптографических алгоритмах. Обычно классические схемы включают генераторы фильтров, комбинированные генераторы, генераторы с управляемыми часами и термоусадочные генераторы[7].

Для криптографических приложений РСЛОС в двоичных генераторах ключей обычно объединяются функциями без памяти. Эти структуры уязвимы для атак корреляции «разделяй и властвуй», основанных на поэтапной корреляции между набором последовательностей РСЛОС и последовательностью потока ключей[8].

Разрушение линейности править

Использование нескольких РСЛОС параллельно- один из общих методов разрушения линейности, свойственной РСЛОС. Поток ключей генерируется как нелинейная функция от выходных данных РСЛОС. Такие генераторы потока ключей называются нелинейными комбинированными генераторами, и носят название объединяющая функция. Данная функция должна удовлетворять нескольким критериям, чтобы противостоять определённым конкретным криптографическим атакам[9].

Генератор потока ключей править

Существует простой основной подход к проектированию генератора потока ключей с использованием РСЛОС. Первый этап — выбор одного или несколько РСЛОС, как правило, с различными полиномами обратной связи и различной длины. (Если полиномы обратной связи все примитивные, а длины все взаимно простые, весь генератор имеет максимальную длину). Начальное состояние РСЛОС — ключ. Для получения бита необходимо сдвинуть РСЛОС один раз (часто это носит название синхронизация). Выходной бит является нелинейной функцией некоторых битов РСЛОС. Данная функция носит название функция объединения, а весь генератор называется генератором комбинации. (Если выходной бит является функцией одного РСЛОС, генератор называется генератором фильтров.)[5].

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

Отдельные генераторы имеют РСЛОС с разной частотой. Бывают случаи, когда тактирование одного генератора зависит от мощности другого. Все они являются электронными версиями машинных шифров, используемых до периода Второй мировой войны и носят название генераторы с часовым управлением[4]. Управление тактовыми импульсами может иметь два возможных варианта: прямую связь, когда выход одного РСЛОС контролирует тактирование другого, или обратную связь, где выход одного РСЛОС контролирует своё собственное тактирование. Несмотря на то, что эти генераторы теоретически подвержены встраиванию и вероятностным атакам корреляции, многие имеют защиту[10][11].Ян Касселлс, до этого возглавлявший направление фундаментальной математики в Кембридже и бывший криптоаналитик Блетчли Парк, сказал, что "криптография — это смесь математики и путаницы и без путаницы математика может быть использована против вас ". Имеется в виду, что в потоковых шифрах требуется некая математическая структура, такая как РСЛОС, для обеспечения максимальной длины и других свойств, а затем сложная нелинейная путаница, чтобы предотвратить доступ к регистру[5].

Компоненты РСЛОС регулярно синхронизируются в генераторах нелинейных комбинаций и генераторах нелинейных фильтров. А именно: перемещение данных во всех РСЛОС контролируется одним и тем же тактом. Главная идея генераторов, управляемых синхронизацией — ввести нелинейность в генераторы потока ключей на основе РСЛОС, имея выход одного РСЛОС, управляющий тактированием (то есть пошагово) второго РСЛОС. Так как второй РСЛОС синхронизируется нерегулярно можно ожидать, что атаки, основанные на регулярном движении РСЛОС, могут быть сорваны[9].

Преимущества потоковых шифров править

Потоковый шифр — важная категория симметричных алгоритмов шифрования. Кроме того, синхронные потоковые шифры не подвержены распространению ошибок, из-за того, что каждый бит независимо шифруется / дешифруется от любого другого. В сравнении с блочными шифрами большинство потоковых шифров намного быстрее и имеют большую эффективность программного обеспечения. Благодаря этим функциям потоковые шифры имеют преимущества при выборе протоколов связи, особенно используемых в беспроводной области[12].

РСЛОС эффективны в аппаратном обеспечении и являются основными строительными блоками этого шифра[12].

Описание алгоритма PALS править

Управление ключами править

Основной задачей PALS является построение бесконечной (вычислительной) псевдослучайной последовательности, используя случайную последовательность конечной длины. Длина основного ключа алгоритма шифрования — 256 бит, что намного короче его исходного состояния (1600 бит), для получения начального вектора этот ключ должен быть расширен соответствующим способом. Для каждого нового сообщения необходимо использовать свой собственный ключ, но изменить основной ключ для каждого сообщения практически невозможно. Исходя из этого, необходимо разработать алгоритм генерации ключа, который генерирует начальный вектор путём объединения основного ключа системы и ключа, называемого ключом сообщения[1].

Для шифрования каждого нового сообщения используется один и тот же ключ[1].

Для этого генерируется сеансовый ключ с ключом сообщения и основным ключом длиной 256 бит. Далее сеансовый ключ расширяется до 1600 бит (начальный вектор). Блок-схема генерации начального вектора показана на рис. 1[1].

 
Рис.1.Блок-схема генерации начального вектора

Генератор ключей сообщений править

Генерация ключа сообщения должна производиться так, чтобы он не повторялся в течение периода смены основного ключа. Работая 24 часа в сутки и используя 32-битный ключ сообщения каждую секунду, через 4,25 года генерируется и используется полный период ключа сообщения, и он снова возвращается в исходное состояние[1].

Период смены ключа — до 4,25 года[3]. Основной ключ должен измениться намного быстрее, чем этот период в криптосистемах[1].

Расчёты показывают, что если основные ключи изменяются с интервалами в четыре года, то не будет проблемы создания повторяющихся сеансовых ключей. РСЛОС длиной 32 бита используется для генерации ключа сообщения, функция обратной связи которого является следующим примитивным полиномом:[1]

C(x)=x32+x29+x24+x23+x21+x19+x17+x16+x14+x13+x11+x9+x6+x3+1

Генератор ключей сеанса править

Для генерации ключа сеанса функция скремблирования должна быть спроектирована так, чтобы воздействовать на все биты ключа сообщения на главном ключе. При фиксированном главном ключе изменение битов ключа каждого сообщения должно изменять каждый из битов основного ключа со средней вероятностью 50 % (эффект лавины). Данная функция скремблирования создаётся сетью замещения-перестановки (SPN). Для обеспечения этого 32-битный ключ сообщения вводится в блок перестановок (P-Box) и получается новая 32-битная последовательность. Результирующие 32 бита делятся на 8 четырёхбитных фрагментов, и каждый фрагмент входит в блок замены (S-box4 × 4). Выходы S-блоков объединяются соответственно и создают 32-битную последовательность. Для достижения хорошей диффузии по всем выходным битам путём изменения входных данных, эту операцию необходимо повторить не меньше, чем 5 раз. На рис. 2 показана данная итерационная функция, которая носит название Scram-5[1].

 
Рис.2.Функция скремблирования(Scram-5)

Чтобы получить 256-битную последовательность нужно воздействовать функцией scram-5 восемь раз на 32-битный ключ сообщения. Ключ сеанса получается побитовым XOR, получающегося в результате 256-битной последовательности с основным ключом(рис.3)[3].

 
Рис.3.Генератор ключей сеанса с использованием Scram-5

Начальный векторный генератор править

Длина используемых в генераторе потока ключей РСЛОС составляет 1600 бит. Требуется 1600-битная последовательность для их начального состояния. Используется РСЛОС из 256 битов, примитивный многочлен степени 256 и четыре S-блока для генерации начального вектора(см. рис 4)[1].

 
Рис.4.Начальный векторный генератор

Начальное состояние этого РСЛОС — 256-битный сеансовый ключ, генерирующий восемь битов в любое время. Четыре 8 × 8-битных S-блока встроены в функцию обратной связи РСЛОС, и один из них выбран и используется для соответствующей диффузии ввода-вывода[1].

Для выбора одного из S-блоков используется содержимое ступеней 128 и 129 (последовательность 00 выберет первый S-блок, 01 второй S-блок, 10 третий S-блок и 11 четвёртый S-блок). Диффузия достигается с доверительной вероятностью 95 % после генерации 320 бит (40 тактов). В связи с этим необходимо отбросить первые 320-бит, а следующие 1600-бит используются в качестве начального состояния генератора потока ключей[1].

Инициализация генератора потока ключей править

Для инициализации восьми РСЛОС,которые используются в генераторе потока ключей PALS, первые 165 битов сеансового ключа делятся на 163 трёхбитных набора следующим образом:

{1,2,3}, {2,3,4}, {3,4,5}, …, {163,164,165}. Каждый набор представляет собой десятичное число от 0 до 7 и указывает один из 8 РСЛОС. Например, если первый набор равен 5, то первый бит начального вектора должен быть помещён в первую ступень шестого РСЛОС. Точно также 163 бита исходного вектора заменяются в восьми РСЛОС. Затем оставшиеся 1437 бит начального вектора заменяются на пустых этапах РСЛОС соответственно. Данная схема используется только для первого ключа сообщения в начале связи. Если ключ сообщения должен отправляться повторно при отправке сообщения, для синхронизации между получателем и передатчиком, для ключей следующего сообщения начальный вектор XOR для содержимого каждого РСЛОС от 1 до 8 соответственно[1].

Возможные применения править

PALS может использоваться во многих приложениях, особенно в финансовой криптографии, благодаря соответствующим функциям безопасности[1].

Достоинства PALS править

Основным преимуществом предлагаемого алгоритма является высокая безопасность[1]. PALS устойчив к различным типам атак[3].

При разработке PALS основными критериями должны стать устойчивость к известным атакам, максимальный период, высокая линейная сложность и хорошие статистические свойства. Поток ключей PALS подобен совершенно случайным последовательностям и устойчив к обычным атакам, таким как алгебраическая атака, атака компромисса времени и памяти, атака «разделяй и властвуй», различающая атака, AIDA / куб атаки и различные типы корреляционных атак[1].

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

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Ashouri, 2019.
  2. ↑ Sultan Al-Hinai, Lynn Batten, Bernard Colbert, Kenneth Wong. Algebraic Attacks on Clock-Controlled Stream Ciphers (англ.) // Information Security and Privacy / Lynn Margaret Batten, Reihaneh Safavi-Naini. — Berlin, Heidelberg: Springer, 2006. — P. 1–16. — ISBN 978-3-540-35459-8. — doi:10.1007/11780656_1. Архивировано 15 июня 2018 года.
  3. ↑ 1 2 3 4 S. Smys, Robert Bestak, Álvaro Rocha. Inventive Computation Technologies. — Springer Nature, 2019-11-02. — 949 с. — ISBN 978-3-030-33846-6.
  4. ↑ 1 2 D. Gollmann, W. G. Chambers. Clock-controlled shift registers: a review (англ.) // IEEE Journal on Selected Areas in Communications. — 2000. — Vol. 7, iss. 4. — P. 525–533. — ISSN 0733-8716.
  5. ↑ 1 2 3 Schneier, Bruce, 1963-. Applied cryptography : protocols, algorithms, and source code in C. — 2nd ed. — New York: Wiley, 1996. — xxiii, 758 pages с. — ISBN 0-471-12845-7, 978-0-471-12845-8, 0-471-11709-9, 978-0-471-11709-4, 978-0-470-22626-1, 0-470-22626-9.
  6. ↑ 1 2 J. K. Mandal, Goutam Saha, Debdatta Kandar, Arnab Kumar Maji. Proceedings of the International Conference on Computing and Communication Systems: I3CS 2016, NEHU, Shillong, India. — Springer, 2018-03-29. — 818 с. — ISBN 978-981-10-6890-4.
  7. ↑ Asad Khan, Amir Khan, Fauzan Mirza. Transform Domain Analysis of Sequences. — 2015-03-03.
  8. ↑ Jovan Dj. Golić. Correlation properties of a general binary combiner with memory (англ.) // Journal of Cryptology. — 1996-03-01. — Vol. 9, iss. 2. — P. 111–126. — ISSN 1432-1378. — doi:10.1007/BF00190805.
  9. ↑ 1 2 Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press. (1997). Дата обращения: 24 января 2020. Архивировано из оригинала 24 июля 2012 года.
  10. ↑ J.D. Golic. Towards Fast Correlation Attacks on Irregularly Clocked Shift Registers (1995). Дата обращения: 24 января 2020. Архивировано 3 марта 2022 года.
  11. ↑ Jovan Dj. Golić, Luke O'Connor. Embedding and probabilistic correlation attacks on clock-controlled shift registers (англ.) // Advances in Cryptology — EUROCRYPT'94 / Alfredo De Santis. — Berlin, Heidelberg: Springer, 1995. — P. 230–243. — ISBN 978-3-540-44717-7. — doi:10.1007/BFb0053439. Архивировано 5 июня 2018 года.
  12. ↑ 1 2 Hadia M. S. El Hennawy, Alaa E. A. Omar, Salah M. A. Kholaif. LEA: Link Encryption Algorithm Proposed Stream Cipher Algorithm (англ.) // Ain Shams Engineering Journal. — 2015-03-01. — Vol. 6, iss. 1. — P. 57–65. — ISSN 2090-4479. — doi:10.1016/j.asej.2014.08.001. Архивировано 30 ноября 2020 года.

Литература править

Источник — https://ru.wikipedia.org/w/index.php?title=PALS&oldid=122339733