Halka — блочный шифр с размером блока 64 бита, длиной ключа 80 бит и количеством раундов 24. В данном шифре используются в качестве нелинейных элементов 8-битные S-блоки. Главной особенностью является вычисление на основе LFSR, требующего 138 логических элементов, что делает данный шифр применимым в облегчённой криптографии, несмотря на использование 8-битного S-блока. Развёртывание ключа осуществляется по схеме, аналогичной той, что используется для блочного шифра PRESENT. Данный шифр был представлен в 2014 году.
История Несмотря на существование широко используемых блочных шифров, таких как AES, который был создан еще в 1998 году, область разработки новых блочных шифров является активной и в настоящее время. В 2014 году был разработан шифр Halka. По заявлению автора, шифр стал уникальным во многих отношениях: это первое использование 8-битного S-блока в облегчённой криптографии; традиционно LFSR был использован только в потоковых шифрах, в то время как Halka — блочный; Halka сочетает в себе сильные стороны как AES, так и PRESENT.
Возможное применение Применение шифра возможно в повсеместных вычислениях, включающих RFID, сенсорных сетях и устройствах, для которых достаточно 80-битного размера ключа.
Алгоритм Halka состоит из 24 раундов. Ниже приведён алгоритм шифра.
Обозначим в -м раунде состояние 64-битного блока как и раундовый ключ, т.е. ключ, используемый в одном раунде и получаемый из первоначального ключа, как .
На вход принимаются значение ключа и незашифрованный текст . Значение блока в первом раунде равняется . Генерируются раундовые ключи на основе ключа . Далее циклически для 24 раундов выполняются: Трансформация при шифровании, при которой к состоянию применяется XOR с раундовым ключом , AES-подобное нелинейное преобразование (S-блок), построение которого состоит из взятия мультипликативной инверсии с использованием LFSR в поле Галуа , причем предварительно разделяется на восемь равных 8-битных частей, над которыми и производятся данные операции, после чего результаты конкатенируются. Перестановка битов в блоке случайным образом, однако с условием, что все биты одной 8-битной части текущего блока переходят в биты различных 8-битных частей блока следующего уровня. Цикл завершается. Выполняется последняя операция XOR для и .
Мультипликативная инверсия с использованием LFSR Главной особенностью Halka является реализация мультипликативного инвертирования для нелинейного преобразования (S-блок) с использованием LFSR, использующего в качестве функции обратной связи примитивный многочлен и требующего на 8-битный S-блок всего 138 логических элементов. В то время как для ранее известных реализаций требуется не менее 253. Реализация шифра Halka малоресурсна, но несмотря на это, она удобна в использовании по отношению к программному обеспечению.
В данном разделе описывается вычисление мультипликативной инверсии при помощи регистра сдвига с обратной связью (LFSR).
Математическое описание Преобразование LFSR для циклов может быть записано как: {| | ,
где — матрица преобразования LFSR, — состояние LFSR в -й отсчёт времени или начальное состояние, а — состояние LFSR в -й отсчёт времени, то есть после запуска тактовых циклов.
Так как в качестве функции обратной связи используется примитивный многочлен, LFSR будет генерировать последовательность с максимальным периодом. Поэтому если — длина LFSR, то выполнение циклов возвращает начальное состояние, при этом все промежуточные значения будут различными: {| |.
Для вычисления мультипликативной инверсии заданного входного вектора необходимо определить новое состояние LFSR такое, что : {| | , что равносильно . |} Для 8-битного LFSR это означает следующее:
Последнее равенство используется в реализации алгоритма мультипликативной инверсии с использованием LFSR. Произвольный выбор начального состояния позволяет не выделять аффинное преобразование после взятия мультипликативной инверсии в отдельный шаг, как это сделано в AES, так как уже является результатом применения к мультипликативной инверсии некоторого преобразования, однозначно определяемого по . Такой подход позволяет избежать трудоёмких операций вроде матричного умножения. При этом выбор конкретного начального значения не оказывает существенного влияния на криптографические свойства шифра.
Реализуемый алгоритм Следующий алгоритм выполняется в аппаратной реализации мультипликативной инверсии:
Имеются: 8-битный LFSR, начальное состояние initial_seed = и первоначальный S-box_input = . Преобразование LFSR инициализируется как lfsr_state = S-box_input = . Преобразование LFSR запускается до тех пор, пока не будет выполнено равенство: lfsr_state = initial_seed = . Затем запускается обратное преобразование LFSR до тех пор, пока не будет совершенно в сумме 255 преобразований (то есть если прямое преобразование было выполнено раз, то обратное раз). На выходе принимается lfsr_state = .
Данный алгоритм даёт на выходе мультипликативную инверсию входного 8-битного блока S-box_input .
Аппаратная реализация Аппаратная реализация осуществляется следующим образом: Конструируется LFSR из восьми триггеров с двумя входами (например, D-триггеры). Конструируются необходимые логические элементы, обеспечивающие на входе LFSR функцию обратной связи. Конструируется логическая схема, подключающаяся ко входам триггеров, обеспечивающая обратное преобразование LFSR для того же примитивного многочлена. Выход LFSR подключается к 8-входному вентилю NAND (через несколько вентилей NOT), выход которого подключён ко входам триггеров так, чтобы организовать логику управления LFSR в обратном направлении. Используется 8-битный счётчик LFSR. Выходной сигнал счётчика подключается к 8-входному вентилю NAND (через несколько вентилей NOT), чтобы сигнализировать о завершении 255 циклов. Конечное состояние LFSR содержит мультипликативную инверсию поданного начального значения.
Криптоанализ Дифференциальный и линейный криптоанализ Для 8-битных S-блоков, используемых в Halka, вероятность дифференциальной характеристики составляет . За раунд дифференциальная вероятность равняется . После 24 раундов общая вероятность любой дифференциальной характеристики составит . Также существуют исследования, которые доказывают, что шифр Halka не так устойчив к дифференциальному анализу, как утверждает автор шифра.
Линейное смещение мультипликативной инверсии равно . Тогда полное линейное смещение Halka составит после 24 раундов .
Алгебраическая атака Для Halka не требуется анализ против алгебраических атак, потому что AES-подобное нелинейное преобразование(S-блок) не может быть описано квадратными уравнениями.
Анализ на связанных ключах и сдвиговая атака Нет никаких доказательств того, что алгоритм планирования ключей PRESENT, используемый в Halka, может быть подвержен атаке на связанных ключах и сдвиговой атаке. Кроме того, 8-битный S-блок, используемый в Halka, усиливает данный алгоритм развёртывания ключей.
Кубическая атака Так как AES невосприимчив к , то и Halka устойчив к подобным атакам.
Структурные атаки В силу побитовой перестановки Halka получение словоподобных структур, используемых в интегральных и коллизионных атаках, невозможно, что делает его невосприимчивым к подобным атакам.
Примечания
Литература
Книги
Статьи
Ссылки Облегчённая криптография
Категория:Блочные шифры