NUSH | это... Что такое NUSH? (original) (raw)

NUSH
Создатель: Анатолий Лебедев, Алексей Волчков
Создан: 1999 г.
Опубликован: 2000 г.
Размер ключа: 128, 192, 256 бит
Размер блока: 64, 128, 256 бит
Число раундов: 36, 68, 132

NUSH («Наш») — блочный алгоритм симметричного шифрования, разработанный Анатолием Лебедевым и Алексеем Волчковым для российской компании LAN Crypto.

NUSH имеет несколько различных вариантов, имеющих разный размер блока (64, 128, 256 бит), различное число раундов (в зависимости от размера блока равно 36, 128 или 132 раунда) и использует длину ключа в 128, 192 или 256 бит. Алгоритм не использует S-блоки, а только такие операции, как AND, OR, XOR, сложение по модулю и циклические сдвиги. Перед первым и после последнего раунда проводится «отбеливание» ключа.

Данный алгоритм был выдвинут в проекте NESSIE, но не был выбран, так как было показано, что линейный криптоанализ может быть эффективнее, чем атака перебором.

На основе алгоритма шифрования можно построить и другие алгоритмы. Несколько их них изложены в настоящей статье.

Содержание

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

Шифрование

Введём обозначения. Пусть N=4n — длина шифруемого блока открытого текста P=P_3P_2P_1P_0. KS_i (start key) — выбирается по некоторому расписанию на основе ключа К. Побитово добавляется к исходному тексту: a_0b_0c_0d_0=P_3P_2P_1P_0 \oplus KS_0KS_1KS_2KS_3 После этого происходит r-1 раундов, задаваемых следующими уравнениями, в которых KR_i (Round subKey)- раундовые подключи, # — побитовая конъюнкция или дизъюнкция, выбирается в соответствии с расписанием, C_i, S_i — известные константы, >>>j — циклический сдвиг вправо на j бит:

for i=1…(r-1)

a_i = b_{i-1}

b_i = ((c_i \oplus (KR_{i-1} + C_{i-1})) + b_{i-l})>>>S_{i-1}

c_i = d_{i-1}

d_i = a_{i-1} + ( b_i \# d_{i-l} )

Последняя итерация отличается от основных только отсутствием перестановки после вычисления выражений в правых частях равенств:

a_r = a_{r-l} + (c_r \# d_{r-l} )

b_r = b_{r-1}

c_r=((c_{r-1} \oplus (KR_{r-1} +C_{r-1}))+b_{r-1})>>>S_{r-1}

d_r = d_{r-1}

Выход: зашифрованный блок M_0M_1M_2M_3=a_rb_rc_rd_r \oplus KF_0KF_1KF_2KF_3

Расшифрование

По общей формуле для обращения произведения операторов (AB)^{-1}=B^{-1}A^{-1} строится и процедура расшифрования.

a_rb_rc_rd_r=M_0M_1M_2M_3 \oplus KF_0KF_1KF_2KF_3

Выполняется одна итерация по расшифрованию:

d_{r-1} = d_r

b_{r-1} = b_r

a_{r-1} = a_r - (c_r \# d_{r-1})

c_{r-1} = c_r >>> (n-S_{r-1}) (n=N/4 — длина c_r, можно производить циклический сдвиг влево на S_{r-1})

c_{r-1} = c_{r-1} - KR_{r-1} - b_{r-1}

После этого основной цикл расшифрования, состоящий из итераций, также несущественно отличающихся от предыдущей:

for i=r-1…1

d_{i-1} = c_i

b_{i-1} = a_i

a_{i-1} = d_i - (b_i \# c_{i-1})

c_{i-1} = (b_i >>> (n-S_{i-1}))-KR_{i-1}-a_{i-1}

Комментарии

В некоторых источниках считают, что процедура шифрования состоит из в 4 раза меньшего числа раундов, состоящих из 4 итераций приведённого выше типа (без начального и конечного сложения по модулю 2). Так, сами авторы шифра записывали свой алгоритм следующим образом:

R(a,b,c,d,k,s)=a_1b_1c_1d_1

c_1 = (c + k + b)>>>s

a_1 = a+ c_1 \# d

b_1 = b

d_1 = d

R(a, b, c, d, k_1, s_1)

R(b, c, d, a, k_2, s_2)

R(c, d, a, b, k_3, s_3)

R(d, a, b, c, k_4, s_4)

где k_i=k_i+C_i — к итерационному ключу k_i добавляется соответствующая константа C_i

Алгоритмы аналогичны, поскольку операция «+» определена авторами отдельно от основного описания метода шифрования. Следует отметить, что расписание операций «+» можно изменить, выбирая обратимые бинарные операции над векторами длины n. Нелинейная операция обычного сложения с игнорированием переполнения призвана усложнить линейный криптоанализ. А операция XOR помогают избежать дифференциального криптоанализа. В дальнейшем будет рассматриваться первое описание алгоритма, приведённое в статье китайских математиков, произведших линейный криптоанализ алгоритма.

Выбор операций «+» был произведён по итогам исследований распараллеливания вычислений на процессорах типа Pentium. Выбор изменения порядка регистров a, b, c, d от раунда к раунду ускоряет появление диффузии и конфузии. Базовые операции (XOR, сложение по модулю 2^n, OR, AND) и их порядок ускорили выполнение алгоритма, реализованного на языке С на большинстве платформ, а имплементация алгоритма на ассемблере достаточно короткая.

Простота реализации

Из приведённого описания видно, что для реализации алгоритма необходимо:

При этом отсутствуют таблицы подстановок, присутствующие, например, в ГОСТе, а раунд состоит из 6 операций. То, что сдвиг осуществляется на заранее известную величину, не зависящую ни от открытого текста, ни от ключа, существенно упрощает реализацию алгоритма на микросхемах. Простота алгоритма позволяет легко проверить, что в конкретной имплементации отсутствует так называемый «черный ход».

Параметры

Константы C_i и S_i

Длина N блока составляет 64 бита

Проводится 36 раундов

i C_i i C_i i C_i i C_i
0 ac25 9 6a29 18 96da 27 d25e
1 8a93 10 6d84 19 905f 28 a926
2 243d 11 34bd 20 d631 29 1c7b
3 262e 12 a267 21 aa62 30 5f12
4 f887 13 cc15 22 4d15 31 4ecc
5 c4f2 14 04fe 23 70cb 32 3c86
6 8e36 15 b94a 24 7533 33 28db
7 9fa1 16 df24 25 45fc 34 fc01
8 7dc0 17 40ef 26 5337 35 7cb1
i S_i i S_i i S_i i S_i
0 4 9 2 18 5 27 13
1 7 10 9 19 1 28 12
2 11 11 4 20 2 29 3
3 8 12 13 21 4 30 6
4 7 13 1 22 12 31 11
5 14 14 14 23 3 32 7
6 5 15 6 24 9 33 15
7 4 16 7 25 2 34 4
8 8 17 12 26 11 35 14

Длина блоков 128 бит

При длине блока 128 бит проводится 68 раундов. Поэтому задаются 68 32-битных констант C_i и 68 констант 0<=S_i<=31.

Длина блока 256 бит

При длине блока 256 бит проводится 132 раундов. Поэтому задаются 132 64-битных константы C_i и 132 константы 0<=S_i<=63.

Расписание ключей

Ключ представляется в виде K=K_0K_1... конкатенации N/4-битных слов. KS и KF задаются произвольным образом, а в качестве раундовых ключей по очереди используются все K_i

128-битный ключ

Блок в 64 бита

Ключ К делится на 8 слов KS_0=K_4,\ KF_0= K_3,\ KS_1=K_5,\ KF_1=K_2, KS_2=K_6,\ KF_2=K_1,\ KS_3=K_7,\ KF_3=K_0,\ KR_i=K_{i\ mod\ 8},\ i=0...35

Блоки в 128 бит и 256 бит

Ключ К делится на 4 и 2 слова соответственно, поэтому раундовые ключи повторяются с периодом 4 или 2. В последнем случае среди KS и KF есть одинаковые.

192-битный ключ

В зависимости от длины блока ключ делится на 12, 6, и 3 n-битных частей, что определяет период повторения раундовых ключей.

256-битный ключ

Здесь ключ является объединением 16, 8 или 4 двоичных слов.

Расписание операции

I # i # i # i #
0 AND 16 OR 32 OR 48 AND
1 OR 17 OR 33 OR 49 AND
2 AND 18 AND 34 AND 50 AND
3 OR 19 AND 35 OR 51 AND
4 OR 20 AND 36 OR 52 AND
5 OR 21 AND 37 AND 53 AND
6 OR 22 AND 38 OR 54 OR
7 OR 23 OR 39 AND 55 AND
8 AND 24 AND 40 OR 56 OR
9 OR 25 OR 41 AND 57 OR
10 OR 26 OR 42 AND 58 OR
11 AND 27 OR 43 OR 59 AND
12 OR 28 AND 44 OR 60 AND
13 AND 29 OR 45 AND 61 AND
14 OR 30 AND 46 AND 62 OR
15 OR 31 AND 47 AND 63 OR

Для дальнейших итераций все повторяется: \#_i=\#_{i\ mod\ 64}

Быстродействие

В алгоритме отсутствуют операции с битовою сложностью выше, чем O(k), где k — битовая длина модуля или операндов (например, у произведения по модулю, нахождения обратного (по умножению) элемента или наибольшего общего делителя битовая сложность O(k^2), а у возведения в степень — O(k^3)). Поэтому естественно ожидать высокой скорости работы алгоритма. Авторами приводятся следующие данные:

Размер блока, бит Программа на С Программа на ассемблере
Тактов на блок Тактов на байт Тактов на блок Тактов на байт
64 180 23 130 17
128 340 22 250 16

Безопасность

Главной причиной отсеивания алгоритма NUSH в конкурсе NESSIE стала найденная Ву Венлингом и Фенгом Денго уязвимость алгоритма к линейному криптоанализу.

В своей статье «Линейный криптоанализ блочного шифра NUSH» они используют понятие сложности атаки \delta=(\varepsilon,\ \eta), где \varepsilon характеризует потребности в памяти, а \eta — в объёме вычислений.

Для N=64 и N=128 бит предложено 3 вида атак, а для N=256 — два. Сложности соответствующих атак:

Длина блока, бит Длина ключа, бит \delta
64 128 (2^{58},\ 2^{124}),\ (2^{60},\ 2^{78}),\ (2^{62},\ 2^{55})
192 (2^{58},\ 2^{157}),\ (2^{60},\ 2^{96}),\ (2^{62},\ 2^{58})
256 (2^{58},\ 2^{125}),\ (2^{60},\ 2^{78}),\ (2^{62},\ 2^{53})
128 128 (2^{122},\ 2^{95}),\ (2^{124},\ 2^{57}),\ (2^{126},\ 2^{52})
192 (2^{122},\ 2^{142}),\ (2^{124},\ 2^{75}),\ (2^{126},\ 2^{58})
256 (2^{122},\ 2^{168}),\ (2^{124},\ 2^{81}),\ (2^{126},\ 2^{63})
256 128 (2^{252},\ 2^{122}),\ (2^{254},\ 2^{119})
192 (2^{252},\ 2^{181}),\ (2^{254},\ 2^{177})
256 (2^{252},\ 2^{240}),\ (2^{254},\ 2^{219})

Для некоторых случаев версия с 192-битным ключом существенно надежнее, чем с более длинным ключом. Также можно заметить, что для есть случаи, когда сложности атак шифра с самой маленькой длиной ключа и самой большой практически совпадают. Кроме того, увеличение длины ключа сказывается не так сильно на сложности атаки, как хотелось бы.

Таким образом, существуют атаки на шифр NUSH эффективнее полного перебора. Поэтому есть вероятность улучшения этих атак или достижения вычислительной техниой уровня, достаточного для взлома шифра в разумное время.

Криптоанализ алгоритма

В качестве примера рассмотрим вторую атаку на шифр с длиной блока N=64 бита. Криптоанализ основан на построении зависимостей между битами ключа, исходного и зашифрованного текста, справедливых с вероятностью, отличающейся от 1/2. Эти соотношения строятся на основе уравнения, справедливого с вероятностью 3/4

a_i[0]\oplus b_i[0] \oplus d_i[0]=a_{i-1}[0]\oplus b_{i-1}[0] \oplus d_{i-1}[0] \oplus \theta, \theta = \begin{cases} 1, & \mbox{if } \#=OR\\ 0, & \mbox{if } \#=AND \end{cases}

Это уравнение можно проверить, используя описание алгоритма, и учтя, что для последнего (младшего) разряда операции «+» и \oplus совпадают. Действительно, имеем соотношение d_i[0]=a_{i-1}[0] \oplus b_i[0] \oplus d_{i-1}\oplus \theta \ \Leftrightarrow \ b_i[0] \oplus d_i[0]=a_{i-1}[0] \oplus d_{i-1}\oplus \theta. Добавив к обеим частя равенства соотношение a_i[0]=b_{i-1}[0] получим требуемое.

Далее учитывая конкретные значения S_i можно показать, что a_2[0]\oplus b_2[0] \oplus d_2[0] зависит не от всех бит ключа и открытого текста, а именно:

a_2[0]\oplus b_2[0] \oplus d_2[0]\ =\ f_1(P_0[0-7], P_1[0-11], P_2[0-11], P_3[0], KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_0[0-11], KR_1[0-7])

Рассмотрев 4 первых раунда дешифрования, можно установить, что a_{31}[0]\oplus b_{31}[0] \oplus d_{31}[0]\ =\ f_2(M_0[0-9], M_1[0-11], M_2[0-9, 12], M_3[0,1], KF_0[0,1], KF_1[0-9,12], KF_2[0-11], KF_3[0-9], KR_{32}[0],KR_{33}[0], KR_{34}[0], KR_{35}[0-9]).

Используя Piling-up лемму, a_2[0]\oplus b_2[0] \oplus d_2[0]=a_{31}[0]\oplus b_{31}[0] \oplus d_{31}[0] с вероятностью 0.5+2^{-30}. Получили связь между m_0 битами ключа и открытым и зашифрованным текстами.

Из расписания ключей можно получить, что если длина ключа составляет 128 или 256 бит, то m_0=78, если же ключ состоит из 192 бит, то m_0=96. Из этих данных оцениваем временную сложность атаки, задаваемой следующим алгоритмом:

Сложность по объёму хранимой информации оценивается как 2^{60}. Именно стольким количеством пар открытый-шифрованный текст должен обладать криптоаналитик. При этом тексты отнюдь непроизвольные. Из приведенных соотношений видно, что f_1,\ f_2 зависят не от всех битов входного и выходного блоков. Соответственно, среди выборки блоков открытого и зашифрованных текстов должны быть блоки с отличающимися соответствующими битами. Работа алгоритма с меньшим числом известных текстов возможна, но тогда с меньшей вероятностью найденное «максимальное» число на втором этапе будет действительно соответствовать настоящему ключу в виду непревышения корня из дисперсии числа событий «уравнение выполняется» над мат. ожиданием разницы чисел этого события и ему противоположного (можно рассмотреть схему Бернулли, где вероятность «успеха» равна вероятности выполнения соотношения).

Другие предложенные в той же статье атаки отличаются анализом на последней стадии соотношений для других раундов и самостоятельного интереса не представляют.

Другие алгоритмы на основе NUSH

На основе NUSH можно построить другие алгоритмы. В частности:

Хэш-функция

Перед началом хэширования происходит удлинение текста:

В функции используются следующие переменные:

Начальные значения: T=[C_0...C_{15}], M=[C_{16}...C_{31}], где C_i — константы, которые прибавляются во время шифрования к ключу KR, KS=KF=KR=0

For i = 0 to l-1

{

For j=0 to L/2-1 //L — число раундов для соответствующего вида NUSH

{

C_{2j} = T_{j mod 16}

C_{2*j+1} =M_{j mod16}

}

V = TEXT_i

H = NUSH(V) //Операция шифрования

[H_0...H_3]+=[V_0...V_3]

For j=15 to 4

T_j = T_{j-4}

[T_0...T_3]=[H_0...H_3]

For j=15 to 4

M_j = M_{j-4}

[M_0...M_3]=[V_0...V_3]

}

For i= 0 to 3

{

For j=0 to L/2-1

C_{2*j} = T_{j mod 16}

H = NUSH(M_i)

For j=15 to 4

T_j = T_{j-4}

[T_0...T_3]=[H_0...H_3]

}

Значение хэш-функции длиной t*n (t<16) бит — первые t n-битовых слов регистра T

Код аутентичности сообщения

На основе хэш-функции может быть построена процедура аутентификации сообщения. От предыдущего алгоритма отличается только использованием ненулевого ключа.

Синхронный поточный шифр «NUSH Stream»

Пусть SYNC — известный двоичный вектор длины LENGTH. Есть два варианта этого шифра.

Вариант 1

Пусть N = LENGTH — длина блока, используемого при шифровании алгоритмом NUSH (LENGTH = 64, 128, 256) Пусть GAMMA=[GAMMA_0...GAMMA_{COUNT}] — вектор из COUNT N-битовых слов, который будет складываться с исходным текстом и с шифротекстом для шифрования и расшифрования соответственно.

SYNC = SYNC \oplus NUSH(SYNC)

For i =0 to COUNT −1

{

GAMMA_i= NUSH(SYNC)

SYNC = (SYNC + 65257) mod 2^N

}

Вариант 2

Здесь N=LENGTH / 2, где соответственно LENGTH = 128, 256, 512. Пусть T=[T_0T_1T_2T_3] — вектор длины N, SYNC=[SYNC_0SYNC_1] — вектор длины 2N T — временный регистр длины N=4n, C_{n}, C_{n+1}, C_{n+2},C_{n+3} — соответствующие константы алгоритма NUSH.

Производимые вычисления:

SYNC[0] = SYNC[0] ^ NUSH(SYNC[0])

SYNC[1] = SYNC[1] ^ NUSH(SYNC[1]) T=SYNC[1]

For i =0 to COUNT −1

{

[C_nC_{n+1}C_{n+2}C_{n+3}]=T

GAMMA_i= NUSH(SYNC_0)

SYNC_0 = (SYNC_0 + 65257 ) mod\ 2^N

T = (T + 127) mod 2^N

}

Асимметричное шифрование

Выбор параметров

Вводится специфическая группа G c определенной авторами алгоритма операцией на основе умножения Монтгомери (Montgomery multiplication).

Умножение Монтгомери. Выберем простое число P длиной в n бит, число N\ge n Для двух целых А и В произведением Монтгомери будет число: A \otimes B = \frac{AB+P(ABM\ mod\ 2^N)}{2^N}, где M=-P^{-1}\ mod\ 2^N. Под делением на 2^N подразумевается игнорирование младших N бит числа. Групповая операция: A\diamondsuit B=\begin{cases} A\otimes B & A\otimes B<P\\ A\otimes B-P & else\end{cases}

\otimes вычисляеся при N=n. А и В считаются равными, если отличаются или на Р, или на 0. Получена абелева мультипликативная группа G. Можно построить изоморфизм между G и приведенной системой вычетов по модулю P: \phi: G \ni m \rightarrow m\times 2^N \ mod \ P \in F^*_P

Группа строится с использованием простого числа P такого, что {P-1} \over 2 — тоже простое.

Криптостойкость алгоритма обеспечивается сложностью задачи дискретного логарифмирования. Сложность взлома оценивается как O(e^{\frac{1}{3} \times log P \times log^2 P)}). В этой группе выбирается генератор a. Закрытый ключ: случайное равномерно распределенное на отрезке [0, P-2] целое число x. Открытый ключ: элемент группы G b=a^x.

Шифрование

Выход: c||e

Расшифрование

Электронная цифровая подпись

Данный алгоритм построен на основе описанной ранее хэш-функции. Пусть Q — простое число длиной 2m бит, являющееся делителeм числа P-1. Под операцией A \circ B мы будем понимать уже введеную ранее операцию A\otimes B, где в качестве простого числа используется Q.

Открытый ключ

Закрытый ключ

Любое число x \in [1, Q-1]. В идеале, выбираемое с равномерным распределением.

Подписание

Проверка подписи

Подпись считается верной, если d=Hash_m(Message||\ |g^e \diamondsuit b^d|) Приведу доказательство корректности схемы. Очевидно, что корректность алгоритма равносильна верности равенства c=|g^e \diamondsuit b^d|.

Полученное равенство можно переписать в виде степеней генератора g подгруппы H в следующим образом: |g^{r-x \circ d} \diamondsuit (g^{x \circ 1})^d|=|g^r|. A=|A|\ mod\ P из определения. Откуда g^{r-(x \circ d)+d(x \circ 1)} = g^r\ mod\ P. Операция \circ линейна по второму аргументу с точностью до взятия равенства по модулю Q. В самом деле, A \otimes (b_1+...+b_k)=\frac {A(b_1+...+b_k)+Q((A(b_1+...+b_n)M\ mod\ 2^N)}{2^N}=\frac {Ab_1+Q((Ab_1M\ mod\ 2^N)}{2^N}+...+\frac {Ab_k+Q((Ab_nM\ mod\ 2^N)}{2^N}=A \circ b_1+...+A \circ b_k\ mod\ Q. Следовательно, d(x \circ 1) = x \circ d\ mod\ Q. Откуда и следует доказываемое равенство, поскольку порядок элемента g равен Q.

Схемы аутентификации

Процесс аутентификации похож на схему цифровой подписи. Открытый и закрытый ключи выбираются абсолютно аналогично. Закрытый ключ хранится у того, кто хочет подтвердить свою «подлинность» (пусть это сторона А). В процессе аутентификации можно выделить четыре стадии:

Примечания

Ссылки

Просмотр этого шаблона Симметричные криптосистемы
Поточный шифр A3 • A5 • A8 • Decim • MICKEY • RC4 • Rabbit • SEAL • SOSEMANUK • Trivium • VMPC
Сеть Фейстеля ГОСТ 28147-89 • Blowfish • Camellia • CAST-128 • CAST-256 • CIPHERUNICORN-A • CIPHERUNICORN-E • CLEFIA • Cobra • DFC • DEAL • DES • DESX • EnRUPT • FEAL • FNAm2 • HPC • IDEA • KASUMI • Khufu • LOKI97 • MARS • NewDES • Raiden • RC5 • RC6 • RTEA • SEED • Sinople • TEA • Triple DES • Twofish • XTEA • XXTEA
SP-сеть 3-WAY • ABC • AES (Rijndael) • Akelarre • Anubis • ARIA • BaseKing • BassOmatic • CRYPTON • Diamond2 • Grand Cru • Hierocrypt-L1 • Hierocrypt-3 • KHAZAD • Lucifer • Present • Rainbow • SAFER • Serpent • SHARK • SQUARE • Threefish
Другие FROG • NUSH • REDOC • SHACAL • SC2000