New Data Seal

New Data Seal (NDS) — блочный шифр, основанный на алгоритме Люцифера, который позже стал стандартом DES. Шифр был разработан в компании IBM в 1975 году. Для шифрования NDS использует делит входные (незашифрованные) данные на блоки по 128 бит и использует очень длинный ключ размером 2048 бит. Структура шифра точно такая же, как и у DES: cеть Фейстеля с 16 раундами.

New Data Seal (NDS)
Создатель	[IBM]
Создан	1975 год
Размер ключа	2048 бит
Размер блока	128 бит
Число раундов	16
Тип	сеть Фейстеля

Принцип работы

Шифр NDS является достаточно простым в частности из-за того, что в каждом раунде сети Фейстеля в его основе используется один и тот же ключ.

• Ключ представляет собой отображение: $k:\{0,1\}^{8}\rightarrow \{0,1\}^{8},$ то есть размерность пространства таких ключей $(2^{8})^{2^{8}}=2^{2048},$ что более чем достаточно для предотвращения перебора ключей.
• Система использует 2 заранее известных (не динамичных) S-блока: $S_{0},S_{1},\{0,1\}^{4}\rightarrow \{0,1\}^{4},$ ключевое расписание состоит из одного ключа $k.$ Блок открытого текста делится на 2 подблока $m_{i}$размером 64 бита каждый. Для того, чтобы посчитать $f_{k}(m_{i}):$
  1. $m_{i}$разбивается на восемь 8-битных частей. За $m_{i}^{*}$обозначим байт, образованный первым битом каждого байта в $m_{i}$
  2. каждая часть $m_{i}$разбивается на два 4-битных ниббла
  3. к левому нибблу применяется $S_{0},$ к правому — $S_{1}$
  4. в случае, если $j$-ый бит $k(m_{i}^{*})$ равен 1, поменяются местами нибблы $j$-ой части после $S_{0}S_{1}$преобразования
  5. к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.

Алгоритм взлома

Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за $T_{k}$ преобразование, соответствующее одному раунду NDS, то есть $T_{k}(m_{i-1},m_{i})=(m_{i},m_{i-1}\oplus f_{k}(m_{i})).$Далее, $F=T^{16}$ будет обозначать все 16 раундов. Заметим, что $F$ и $T$ коммутируют: $FT(m)=T^{16}T(m)=TT^{16}(m)=TF(m).$В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа $k(q),\;q\in \{0,1\}^{8}.$Тогда если мы будем знать $k(q)$ для каждого возможного $q,$ ключ будет считаться взломанным.

Процедура атаки следующая:

1. Подобрать сообщение $m=(m_{0},m_{1}),$так, чтобы $m_{1}^{*}=q.$
2. Взломщик получает зашифрованное сообщение $(m_{16},m_{17})=F(m),$ соответствующее открытому тексту $m.$
3. Пусть ${\tilde {k}}$ — один из возможных 8-битных ключей (всего $2^{8}$ комбинаций). И пусть ${\tilde {T}}=T_{\tilde {k}}(m)$ есть результат после работы от 1 раунда с ключом ${\tilde {k}}$.
4. Если ${\tilde {k}}=k(q),$то ${\tilde {T}}=T(m)$и $F({\tilde {T}})=FT(m)=TF(m)=T(m_{16},m_{17})=(m_{17},?).$ Следовательно левая половина $F({\tilde {T}})$ согласована с правой половиной $F(m)=(m_{16},m_{17}).$
5. Взломщик получает зашифрованное сообщение $F({\tilde {T}}),$ соответствующее заранее выбранному тексту ${\tilde {T}}.$ Если правая половина $F(m)$ соответствует левой половине $F({\tilde {T}}),$то можно считать ${\tilde {k}}$ допустимым значением для $k(q).$ В худшем случае нужно будет перебрать $2^{8}=256$комбинаций ${\tilde {k}}$ для нахождения нужного значения.
6. Повторяем процедуру для каждого $q\in \{0,1\}^{8},$ получая значение ключа $k$ с помощью $2^{8}(2^{8}+1)=65792$ заранее выбранных открытых текстов.

Атаки на шифр

В 1977 Эдна Гроссман и Брайант Такермен впервые продемонстрировали атаку на NDS с помощью сдвиговой атаки. Этот метод использует не более 4096 подобранных открытых текстов. В их лучшем испытании они смогли восстановить ключ только с 556 подобранными открытыми текстами.