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 бита каждый. Для того, чтобы посчитать  
    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.