Noekeon (Noekeon)

NOEKEON
Создатель	Йоан Даймен Michaël Peeters Gilles Van Assche Винсент Рэймен
Опубликован	2000 г.
Размер ключа	128 бит
Размер блока	128 бит
Число раундов	16

NOEKEON — семейство из двух блочных шифров, разработанных Йоаном Дайменом,  Michaël Peeters, Gilles Van Assche и Винсентом Рэйменом и представленных в исследовательском проекте NESSIE. Два шифра представляют собой NOEKEON в прямом режиме (direct mode) и в косвенном режиме (indirect mode). Отличаются режимы только процедурой расширения ключа.

Общие сведения

Длина ключа в NOEKEON равна 128 битам. В каждом раунде NOEKEON использует последовательность преобразований, обратных самим себе, которые с легкостью могут быть реализованы в аппаратном или программном обеспечении, причем даже в таком, где существует возможность атаки по сторонним каналам. Шифр является компактным в реализации на различных языках программирования, быстро работает на различных аппаратных средствах и является очень эффективным в широком диапазоне платформ. Однако, NOEKEON не отвечал требованиям Wide Trail Design Strategy, что показал криптоанализ, проведенный Ларсом Кнудсеном и Håvard Raddum в апреле 2001. Кнудсен и Raddum показали, что на данный шифр возможна атака на основе связанных ключей, из-за чего шифр не прошел отбор в проекте NESSIE.

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

Шифр

Алгоритм NOEKEON выполняет 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 и применении раундовых констант.

Раунд преобразования

Каждый раунд алгоритма выполняет следующие действия:

1. Первое слово входных данных складывается с помощью операции XOR с раундовой константой RC[r], где r — номер текущего раунда.
2. Над входными словами производится линейное преобразование Theta с участием рабочего ключа WorkingKey.
3. Первое слово снова складывается с помощью операции 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

Операция Gamma алгоритма NOEKEON

Gamma является инволютивным нелинейным отображением, по сути являющимся простой табличной заменой. Gamma производит независимые операции над 32 подблоками бит, называемыми ящиками. Эти ящики состоят из 4 битов, стоящих на одной и той же позиции в каждом из четырёх 32-битовых слов $a[n]$, то есть ящик с номером i формируется из значениями i-х битов каждого из 32-битных слов:

$T_{i}=a[3]_{i}*8+a[2]_{i}*4+a[1]_{i}*2+a[0]_{i}$

Пусть далее $a[n]$ является i-м битом 32-битного слова $a[n]$, то есть $a[n]$ является n-м битом ящика $T_{i}$. Тогда Gamma действует на ящики из State следующим образом:

• $a[1]=a[1]\oplus ({\overline {a[3]}}\land {\overline {a[2]}});$
• $a[0]=a[0]\oplus (a[2]\land a[1]);$
• $tmp=a[3];$
• $a[3]=a[0];$
• $a[0]=tmp;$
• $a[2]=a[2]\oplus (a[0]\oplus a[1]\oplus a[3]);$
• $a[1]=a[1]\oplus ({\overline {a[3]}}\land {\overline {a[2]}});$
• $a[0]=a[0]\oplus (a[2]\land a[1]);$.

Описание алгоритма 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

Операция Theta алгоритма NOEKEON

Theta является линейным отображением, которое применяется к состоянию State с рабочим ключом k. State является массивом из восьми 16-битных колонок. Каждая колонка состоит из четырех наборов по 4 бит, стоящих в словах $a[n]$ на позициях, равных по модулю 8. Например, колонка 5 состоит из битов 5, 13, 21 и 29 слова $a[0]$, битов 5, 13, 21 и 29 слова $a[1]$, битов 5, 13, 21 и 29 слова $a[2]$ и битов 5, 13, 21 и 29 слова $a[3]$. Theta выполняет следующую последовательность действий:

• $t=a[0]\oplus a[2],$
• $t=t\oplus (t\ggg 8)\oplus (t\lll 8),$
• $a[1]=a[1]\oplus t,$
• $a[3]=a[3]\oplus t,$
• $a[0]=a[0]\oplus k[0],$
• $a[1]=a[1]\oplus k[1],$
• $a[2]=a[2]\oplus k[2],$
• $a[3]=a[3]\oplus k[3],$
• $t=a[1]\oplus a[3],$
• $t=t\oplus (t\ggg 8)\oplus (t\lll 8),$
• $a[0]=a[0]\oplus t,$
• $a[2]=a[2]\oplus t.$

Критерии, используемые при разработке преобразования 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 к начальному рабочему ключу.

Операции сдвига

Операция сдвига Pi1

Операции сдвига 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;

В обоих случаях рабочий ключ не изменяется между раундами.

Раундовые константы

Наложение раундовых констант

Раундовые константы накладываются в каждом раунде алгоритма на значение слова $a[0]$ с помощью операции сложения по модулю 2 и используются в шифре для устранения некоторых свойств симметрии:

• Раундовое преобразование выполняется над различными ящиками данных одинаковою.
• Раундовые преобразования одинаковы для всех раундов шифра.

Стоит отметить, что только лишь последний байт раундовых констант является ненулевым, то есть в каждом раунде алгоритма с помощью раундовых констант изменяется только четвертый байт слова $a[0]$. Кроме того, значения констант от 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. Оба режима оказались подвержены атаке на основе связанных ключей, которую предложили криптологи Ларс Кнудсен и Håvard Raddum в своей работе. Кроме того, ими же было доказано, что критерии создания таблиц замен в операции Gamma не способствуют высокой криптостойкости алгоритма: при генерации таблицы замен результирующий алгоритм с вероятностью примерно 86 % окажется подвержен линейному и/или дифференциальному криптоанализу. Также было показано, что с большой вероятностью возможно найти связанные ключи. Этих причин оказалось достаточно для невыхода алгоритма Noekeon во второй раунд конкурса.