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\to <!--\; \to \; -->\{0,1{\}}^8,$$k:\{0,1\}^{8}\rightarrow \{0,1\}^{8},$  то есть размерность пространства таких ключей $(2^8{)}^{2^8}=2^{2048},$$(2^{8})^{2^{8}}=2^{2048},$  что более чем достаточно для предотвращения перебора ключей.
• Система использует 2 заранее известных (не динамичных) S-блока: $S_0,S_1,\{0,1{\}}^4\to <!--\; \to \; -->\{0,1{\}}^4,$$S_{0},S_{1},\{0,1\}^{4}\rightarrow \{0,1\}^{4},$  ключевое расписание состоит из одного ключа $k.$$k.$  Блок открытого текста делится на 2 подблока $m_i$$m_i$ размером 64 бита каждый. Для того, чтобы посчитать $f_k(m_i):$$f_{k}(m_{i}):$ 
  1. $m_i$$m_i$ разбивается на восемь 8-битных частей. За $m_i^{\ast <!--\; \ast \; -->}$$m_{i}^{*}$ обозначим байт, образованный первым битом каждого байта в $m_i$$m_i$ 
  2. каждая часть $m_i$$m_i$ разбивается на два 4-битных ниббла
  3. к левому нибблу применяется $S_0,$$S_{0},$  к правому — $S_1$$S_{1}$ 
  4. в случае, если $j$$j$ -ый бит $k(m_i^{\ast <!--\; \ast \; -->})$$k(m_{i}^{*})$  равен 1, поменяются местами нибблы $j$$j$ -ой части после $S_0{S}_1$$S_{0}S_{1}$ преобразования
  5. к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.

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

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

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

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

Атаки на шифр Править

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