Interested Article - Noekeon

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

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

Длина ключа в NOEKEON равна 128 битам. В каждом раунде NOEKEON использует последовательность преобразований, обратных самим себе, которые с легкостью могут быть реализованы в аппаратном или программном обеспечении, причем даже в таком, где существует возможность атаки по сторонним каналам . Шифр является компактным в реализации на различных языках программирования , быстро работает на различных аппаратных средствах и является очень эффективным в широком диапазоне платформ . Однако, NOEKEON не отвечал требованиям , что показал криптоанализ, проведенный Ларсом Кнудсеном и в апреле 2001. Кнудсен и показали, что на данный шифр возможна атака на основе связанных ключей , из-за чего шифр не прошел отбор в проекте 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 и применении раундовых констант.

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

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

Первое слово входных данных складывается с помощью операции 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

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