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 является достаточно простым в частности из-за того, что в каждом раунде сети Фейстеля в его основе используется один и тот же ключ.
- Ключ представляет собой отображение: то есть размерность пространства таких ключей что более чем достаточно для предотвращения перебора ключей.
- Система использует 2 заранее известных (не динамичных) S-блока: ключевое расписание состоит из одного ключа Блок открытого текста делится на 2 подблока размером 64 бита каждый. Для того, чтобы посчитать
- разбивается на восемь 8-битных частей. За обозначим байт, образованный первым битом каждого байта в
- каждая часть разбивается на два 4-битных ниббла
- к левому нибблу применяется к правому —
- в случае, если -ый бит равен 1, поменяются местами нибблы -ой части после преобразования
- к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.
Алгоритм взлома
Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за преобразование, соответствующее одному раунду NDS, то есть Далее, будет обозначать все 16 раундов. Заметим, что и коммутируют: В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа Тогда если мы будем знать для каждого возможного ключ будет считаться взломанным.
Процедура атаки следующая:
- Подобрать сообщение так, чтобы
- Взломщик получает зашифрованное сообщение соответствующее открытому тексту
- Пусть — один из возможных 8-битных ключей (всего комбинаций). И пусть есть результат после работы от 1 раунда с ключом .
- Если то и Следовательно левая половина согласована с правой половиной
- Взломщик получает зашифрованное сообщение соответствующее заранее выбранному тексту Если правая половина соответствует левой половине то можно считать допустимым значением для В худшем случае нужно будет перебрать комбинаций для нахождения нужного значения.
- Повторяем процедуру для каждого получая значение ключа с помощью заранее выбранных открытых текстов.
Атаки на шифр
В 1977 Эдна Гроссман и Брайант Такермен впервые продемонстрировали атаку на NDS с помощью сдвиговой атаки.[1][2] Этот метод использует не более 4096 подобранных открытых текстов. В их лучшем испытании они смогли восстановить ключ только с 556 подобранными открытыми текстами.
Примечания
- 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 с.
- Henry Beker, Fred Piper. Cipher Systems: The Protection of Communications. — John Wiley & Sons, 1982. — С. 263–267. — ISBN 0-471-89192-4.