Noekeon
NOEKEON | |
---|---|
![]() | |
Создатель | Йоан Даймен Michaël Peeters Gilles Van Assche Винсент Рэймен |
Опубликован | 2000 г. |
Размер ключа | 128 бит |
Размер блока | 128 бит |
Число раундов | 16 |
NOEKEON — семейство из двух блочных шифров, разработанных Йоаном Дайменом, Michaël Peeters, Gilles Van Assche и Винсентом Рэйменом и представленных в исследовательском проекте NESSIE[1]. Два шифра представляют собой NOEKEON в прямом режиме (direct mode) и в косвенном режиме (indirect mode). Отличаются режимы только процедурой расширения ключа.
Общие сведения
Длина ключа в NOEKEON равна 128 битам. В каждом раунде NOEKEON использует последовательность преобразований, обратных самим себе, которые с легкостью могут быть реализованы в аппаратном или программном обеспечении, причем даже в таком, где существует возможность атаки по сторонним каналам. Шифр является компактным в реализации на различных языках программирования, быстро работает на различных аппаратных средствах и является очень эффективным в широком диапазоне платформ[2]. Однако, NOEKEON не отвечал требованиям Wide Trail Design Strategy, что показал криптоанализ, проведенный Ларсом Кнудсеном и Håvard Raddum в апреле 2001. Кнудсен и Raddum показали, что на данный шифр возможна атака на основе связанных ключей[3], из-за чего шифр не прошел отбор в проекте NESSIE.
Описание алгоритма
Шифр
Алгоритм NOEKEON[4] выполняет 16 раундов преобразований с последующим применением функции Theta
. Блок входных данных State
представляет собой четыре 32-битных слов от a[0]
до a[3]
.
Алгоритм NOEKEON в обозначениях C style pseudocode.
Noekeon(WorkingKey,State) { For( i=0 ; i<Nr ; i++) Round(WorkingKey,State,Roundct[i],0); State[0] ^= Roundct[Nr]; Theta(WorkingKey,State); }
Инверсия шифра выглядит следующим образом:
InverseNoekeon(WorkingKey,State) { Theta(NullVector,WorkingKey); For( i=Nr ; i>0 ; i--) Round(WorkingKey,State,0,Roundct[i]); Theta(WorkingKey,State); State[0] ^= Roundct[0]; }
Число раундов Nr
равно 16. Единственная разница между NOEKEON и его инверсией заключается в вычислении WorkingKey
для инверсии NOEKEON и применении раундовых констант.
Раунд преобразования
Каждый раунд алгоритма выполняет следующие действия:
- Первое слово входных данных складывается с помощью операции XOR с раундовой константой RC[r], где r — номер текущего раунда.
- Над входными словами производится линейное преобразование Theta с участием рабочего ключа WorkingKey.
- Первое слово снова складывается с помощью операции XOR с RC[r].
Описание раундов алгоритма на псевдокоде:
Round(Key,State,Constant1,Constant2) { State[0] ^= Constant1; Theta(Key,State); State[0] ^= Constant2; Pi1(State); Gamma(State); Pi2(State); }
Все функции работают с состоянием State
, на который предоставляется указатель. Всегда одна из входных констант задана, как 0. Если раундовое преобразование применяется в прямом шифре, то Constant2
устанавливается в 0, если же раундовое преобразование используется для обратного шифра, то Constant1 = 0
.
Gamma
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gamma_function_-_NOEKEON.jpg/350px-Gamma_function_-_NOEKEON.jpg)
Gamma является инволютивным нелинейным отображением, по сути являющимся простой табличной заменой. Gamma
производит независимые операции над 32 подблоками бит, называемыми ящиками. Эти ящики состоят из 4 битов, стоящих на одной и той же позиции в каждом из четырёх 32-битовых слов , то есть ящик с номером i формируется из значениями i-х битов каждого из 32-битных слов:
Пусть далее является i-м битом 32-битного слова , то есть является n-м битом ящика . Тогда Gamma действует на ящики из State
следующим образом:
- .
Описание алгоритма Gamma на псевдокоде:
Gamma(a){ a[1] ^= ~a[3]&~a[2]; a[0] ^= a[2]& a[1]; tmp = a[3]; a[3] = a[0]; a[0] = tmp; a[2] ^= a[0]^a[1]^a[3]; a[1] ^= ~a[3]&~a[2]; a[0] ^= a[2]& a[1]; }
Gamma
может быть определена в качестве альтернативы S-блока, применяемого к каждому из ящиков в State
, при этом значения каждого ящика в Gamma
изменяются следующим образом:
Входное значение | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
Выходное значение | 7 | A | 2 | C | 4 | 8 | F | 0 | 5 | 9 | 1 | E | 3 | D | B | 6 |
Theta
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Theta_function_-_NOEKEON.jpg/350px-Theta_function_-_NOEKEON.jpg)
Theta
является линейным отображением, которое применяется к состоянию State
с рабочим ключом k
. State
является массивом из восьми 16-битных колонок. Каждая колонка состоит из четырех наборов по 4 бит, стоящих в словах на позициях, равных по модулю 8. Например, колонка 5 состоит из битов 5, 13, 21 и 29 слова , битов 5, 13, 21 и 29 слова , битов 5, 13, 21 и 29 слова и битов 5, 13, 21 и 29 слова . Theta
выполняет следующую последовательность действий:
Критерии, используемые при разработке преобразования Theta:
- Возможность использовать как в прямом, так и в обратном режиме NOEKEON.
- Относительно небольшое число выполняемых операций.
- Достаточная диффузия данных
- Симметричность.
- Простота описания.
Функция Theta
на псевдокоде:
Theta(k,a){ temp = a[0]^a[2]; temp ^= temp>>>8 ^ temp<<<8; a[1] ^= temp; a[3] ^= temp; a[0] ^= k[0]; a[1] ^= k[1]; a[2] ^= k[2]; a[3] ^= k[3]; temp = a[1]^a[3]; temp ^= temp>>>8 ^ temp<<<8; a[0] ^= temp; a[2] ^= temp; }
Инверсию Theta
можно получить, используя алгебраические свойства линейных отображений и тот факт, что первый о последний компоненты Theta
коммутируют:
Theta(k’,a);
Новый рабочий ключ k' получается путём применения Theta
к начальному ключу k
с нулевым рабочим ключом:
Theta(NullVector,k);
Это значит, что инверсия Theta
равна самой Theta
, только с другим значением рабочего ключа, который можно получить применением Theta
к начальному рабочему ключу.
Операции сдвига
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Shift_operation_-_NOEKEON.jpg/180px-Shift_operation_-_NOEKEON.jpg)
Операции сдвига Pi1
и Pi2
выполняют циклические сдвиги в трех из четырех слов с различными значениями смещения. Значения смещения отобраны в соответствии с следующими критериями:
- Операция Pi2 должна быть обратной к операции Pi1, чтобы иметь возможность использовать одинаковые раундовые преобразования как в прямом, так и в обратном шифрах.
- Все четыре смещения слов в этих операциях должны отличатся по модулю 8.
- Смещение нулевого слова a[0] должно равняться нулю.
- Массив смещений выбирается из множества массивов, оптимизирующих диффузию в течение одного цикла, при этом выбирается первый из всех получившихся массивов в лексикографическом порядке.
Мерой диффузии является количество ящиков на выходе линейной части алгоритма, изменяющихся под воздействием изменения одного из ящиков на входе. Линейная часть алгоритма представляет собой последовательность функций Pi1
, Theta
, Pi2
. Другими словами, мера диффузии — это количество ненулевых ящиков на выходе при условии, что только один ящик на входе был ненулевым. Благодаря симметрии в этих трех функциях, число ненулевых ящиков на выходе не зависит от положения ненулевого ящика на входе. Число ненулевых ящиков на выходе для массива смещений [0,1,5,2]
равно 23, что является наилучшим результатом, удовлетворяющим критериям выбора смещений. Те же утверждения справедливы и для обратных операций.
Операции сдвига на псевдокоде:
Pi1(a){ a[1] <<<= 1; a[2] <<<= 5; a[3] <<<= 2; } Pi2(a){ a[1] >>>= 1; a[2] >>>= 5; a[3] >>>= 2; }
Расширение ключа
В косвенном режиме (indirect mode) рабочий ключ WorkingKey
получается из секретного ключа CipherKey
путём использования NOEKEON
с нулевым WorkingKey
:
WorkingKey = CipherKey; Noekeon(NullVector,WorkingKey);
В прямом режиме (direct mode) рабочий ключ совпадает с секретным, то есть расширение ключа отсутствует:
WorkingKey = CipherKey;
В обоих случаях рабочий ключ не изменяется между раундами.
Раундовые константы
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/Round_constants_-_NOEKEON.jpg/180px-Round_constants_-_NOEKEON.jpg)
Раундовые константы накладываются в каждом раунде алгоритма на значение слова с помощью операции сложения по модулю 2 и используются в шифре для устранения некоторых свойств симметрии:
- Раундовое преобразование выполняется над различными ящиками данных одинаковою.
- Раундовые преобразования одинаковы для всех раундов шифра.
Стоит отметить, что только лишь последний байт раундовых констант является ненулевым, то есть в каждом раунде алгоритма с помощью раундовых констант изменяется только четвертый байт слова . Кроме того, значения констант от RC[1]
до RC[Nr]
в этом байте могут быть вычислены рекурсивным методом. Исходя из этого, раундовые константы можно записать на псевдокоде следующим образом:
Roundct[i] = (‘00’,‘00’,‘00’,RC[i]); RC[0] = 0x80; if (RC[i]&0x80 != 0) RC[i+1] = RC[i]<<1 ^ 0x1B else RC[i+1] = RC[i]<<1;
Такое вычисление соответствует регистру сдвига с линейной обратной связью. Если нужно, то константы могут быть вычислены и в обратном порядке:
if (RC[i]&0x01 != 0) RC[i-1] = RC[i]>>1 ^ 0x8D else RC[i-1] = RC[i]>>1;
Раундовые константы вычисляются таким же образом, как и в алгоритме Rijndael, исключением является заданное значение RC[0]
.
Криптоанализ алгоритма
На рассмотрение в рамках конкурса NESSIE были приняты оба режима алгоритма Noekeon[5]. Оба режима оказались подвержены атаке на основе связанных ключей, которую предложили криптологи Ларс Кнудсен и Håvard Raddum в своей работе[3]. Кроме того, ими же было доказано, что критерии создания таблиц замен в операции Gamma не способствуют высокой криптостойкости алгоритма: при генерации таблицы замен результирующий алгоритм с вероятностью примерно 86 % окажется подвержен линейному и/или дифференциальному криптоанализу. Также было показано, что с большой вероятностью возможно найти связанные ключи. Этих причин оказалось достаточно для невыхода алгоритма Noekeon во второй раунд конкурса.
Примечания
- ↑ Алгоритмы шифрования — участники конкурса NESSIE (неопр.). Дата обращения: 24 ноября 2014. Архивировано 4 марта 2016 года.
- ↑ The NOEKEON Page (неопр.). Дата обращения: 18 ноября 2014. Архивировано 1 марта 2015 года.
- ↑ 1 2 [[Кнудсен, Ларс|Ларс Кнудсен]] и [[Håvard Raddum]] On NOEKEON (неопр.). Дата обращения: 18 ноября 2014. Архивировано 3 марта 2016 года.
- ↑ [[Даймен, Йоан|Йоан Даймен]], [[ Michaël Peeters]], [[Gilles Van Assche]] и [[Рэймен, Винсент|Винсент Рэймен]] Nessie Proposal: NOEKEON (неопр.). Дата обращения: 28 декабря 2014. Архивировано 5 марта 2015 года.
- ↑ [[Håvard Raddum]] The Statistical Evaluation of the NESSIE Submission (неопр.). Дата обращения: 24 ноября 2014. Архивировано 19 января 2022 года.