New Data Seal

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

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

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

• Ключ представляет собой отображение: $k:\{0,1{\}}^8\to \{0,1{\}}^8,$ то есть размерность пространства таких ключей $(2^8{)}^{2^8}=2^{2048},$ что более чем достаточно для предотвращения перебора ключей.
• Система использует 2 заранее известных (не динамичных) S-блока: $S_0,S_1,\{0,1{\}}^4\to \{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)=T{T}^{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 подобранными открытыми текстами.