New Data Seal (New Data Seal)

Перейти к навигации Перейти к поиску
New Data Seal (NDS)
Создатель [IBM]
Создан 1975 год
Размер ключа 2048 бит
Размер блока 128 бит
Число раундов 16
Тип сеть Фейстеля

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

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

[править | править код]

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

  • Ключ представляет собой отображение: то есть размерность пространства таких ключей что более чем достаточно для предотвращения перебора ключей.
  • Система использует 2 заранее известных (не динамичных) S-блока: ключевое расписание состоит из одного ключа Блок открытого текста делится на 2 подблока размером 64 бита каждый. Для того, чтобы посчитать
    1. разбивается на восемь 8-битных частей. За обозначим байт, образованный первым битом каждого байта в
    2. каждая часть разбивается на два 4-битных ниббла
    3. к левому нибблу применяется к правому —
    4. в случае, если -ый бит равен 1, поменяются местами нибблы -ой части после преобразования
    5. к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.

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

[править | править код]

Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за преобразование, соответствующее одному раунду NDS, то есть Далее, будет обозначать все 16 раундов. Заметим, что и коммутируют: В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа Тогда если мы будем знать для каждого возможного ключ будет считаться взломанным.

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

  1. Подобрать сообщение так, чтобы
  2. Взломщик получает зашифрованное сообщение соответствующее открытому тексту
  3. Пусть — один из возможных 8-битных ключей (всего комбинаций). И пусть есть результат после работы от 1 раунда с ключом .
  4. Если то и Следовательно левая половина согласована с правой половиной
  5. Взломщик получает зашифрованное сообщение соответствующее заранее выбранному тексту Если правая половина соответствует левой половине то можно считать допустимым значением для В худшем случае нужно будет перебрать комбинаций для нахождения нужного значения.
  6. Повторяем процедуру для каждого получая значение ключа с помощью заранее выбранных открытых текстов.

Атаки на шифр

[править | править код]

В 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.