New Data Seal (NDS) — блочный шифр, основанный на алгоритме Люцифера, который позже стал стандартом DES. Шифр был разработан в компании IBM в 1975 году. Для шифрования NDS использует делит входные (незашифрованные) данные на блоки по 128 бит и использует очень длинный ключ размером 2048 бит. Структура шифра точно такая же, как и у DES: cеть Фейстеля с 16 раундами.
Принцип работы
Шифр NDS является достаточно простым в частности из-за того, что в каждом раунде сети Фейстеля в его основе используется один и тот же ключ.
- Ключ представляет собой отображение:
то есть размерность пространства таких ключей
что более чем достаточно для предотвращения перебора ключей.
- Система использует 2 заранее известных (не динамичных) S-блока:
ключевое расписание состоит из одного ключа
Блок открытого текста делится на 2 подблока
размером 64 бита каждый. Для того, чтобы посчитать
разбивается на восемь 8-битных частей. За
обозначим байт, образованный первым битом каждого байта в ![{\displaystyle m_{i))](https://wikimedia.org/api/rest_v1/media/math/render/svg/95ec8e804f69706d3f5ad235f4f983220c8df7c2)
- каждая часть
разбивается на два 4-битных ниббла
- к левому нибблу применяется
к правому — ![{\displaystyle S_{1))](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9)
- в случае, если
-ый бит
равен 1, поменяются местами нибблы
-ой части после
преобразования
- к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.
Алгоритм взлома
Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за
преобразование, соответствующее одному раунду NDS, то есть
Далее,
будет обозначать все 16 раундов. Заметим, что
и
коммутируют:
В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа
Тогда если мы будем знать
для каждого возможного
ключ будет считаться взломанным.
Процедура атаки следующая:
- Подобрать сообщение
так, чтобы ![{\displaystyle m_{1}^{*}=q.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c12b59cb3cff0e6e436dcd52c04787c3da7679da)
- Взломщик получает зашифрованное сообщение
соответствующее открытому тексту ![{\displaystyle m.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bd92c867d56467c0f878ef318eefcd701b8ec1a)
- Пусть
— один из возможных 8-битных ключей (всего
комбинаций). И пусть
есть результат после работы от 1 раунда с ключом
.
- Если
то
и
Следовательно левая половина
согласована с правой половиной ![{\displaystyle F(m)=(m_{16},m_{17}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed990999c7847f726f965245bd8831306a8b68fc)
- Взломщик получает зашифрованное сообщение
соответствующее заранее выбранному тексту
Если правая половина
соответствует левой половине
то можно считать
допустимым значением для
В худшем случае нужно будет перебрать
комбинаций
для нахождения нужного значения.
- Повторяем процедуру для каждого
получая значение ключа
с помощью
заранее выбранных открытых текстов.
Атаки на шифр
В 1977 Эдна Гроссман и Брайант Такермен впервые продемонстрировали атаку на NDS с помощью сдвиговой атаки[1][2]. Этот метод использует не более 4096 подобранных открытых текстов. В их лучшем испытании они смогли восстановить ключ только с 556 подобранными открытыми текстами.