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

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

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

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

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

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

Атаки на шифр

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

Примечания

1. E. K. Grossman, Thomas J. Watson IBM Research Center Research Division, B. Tuckerman. Analysis of a Feistel-like Cipher Weakened by Having No Rotating Key. — IBM Thomas J. Watson Research Division, 1977. — 33 с.
2. Henry Beker, Fred Piper. Cipher Systems: The Protection of Communications. — John Wiley & Sons, 1982. — С. 263–267. — ISBN 0-471-89192-4.