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 является достаточно простым в частности из-за того, что в каждом раунде сети Фейстеля в его основе используется один и тот же ключ.
- Ключ представляет собой отображение: [math]\displaystyle{ k : \{0, 1\}^8 \rightarrow \{0, 1\}^8, }[/math] то есть размерность пространства таких ключей [math]\displaystyle{ (2^8)^{2^8} = 2^{2048}, }[/math] что более чем достаточно для предотвращения перебора ключей.
- Система использует 2 заранее известных (не динамичных) S-блока: [math]\displaystyle{ S_0, S_1, \{0,1\}^4 \rightarrow \{0, 1\}^4, }[/math] ключевое расписание состоит из одного ключа [math]\displaystyle{ k. }[/math] Блок открытого текста делится на 2 подблока [math]\displaystyle{ m_i }[/math]размером 64 бита каждый. Для того, чтобы посчитать [math]\displaystyle{ f_k(m_i): }[/math]
- [math]\displaystyle{ m_i }[/math]разбивается на восемь 8-битных частей. За [math]\displaystyle{ m_i^* }[/math]обозначим байт, образованный первым битом каждого байта в [math]\displaystyle{ m_i }[/math]
- каждая часть [math]\displaystyle{ m_i }[/math]разбивается на два 4-битных ниббла
- к левому нибблу применяется [math]\displaystyle{ S_0, }[/math] к правому — [math]\displaystyle{ S_1 }[/math]
- в случае, если [math]\displaystyle{ j }[/math]-ый бит [math]\displaystyle{ k(m_i^*) }[/math] равен 1, поменяются местами нибблы [math]\displaystyle{ j }[/math]-ой части после [math]\displaystyle{ S_0S_1 }[/math]преобразования
- к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.
Алгоритм взлома
Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за [math]\displaystyle{ T_k }[/math] преобразование, соответствующее одному раунду NDS, то есть [math]\displaystyle{ T_k(m_{i-1}, m_i) = (m_i, m_{i-1} \oplus f_k(m_i)). }[/math]Далее, [math]\displaystyle{ F = T^{16} }[/math] будет обозначать все 16 раундов. Заметим, что [math]\displaystyle{ F }[/math] и [math]\displaystyle{ T }[/math] коммутируют: [math]\displaystyle{ FT(m) = T^{16}T(m) = TT^{16}(m) = TF(m). }[/math]В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа [math]\displaystyle{ k(q),\; q \in \{0, 1\}^8. }[/math]Тогда если мы будем знать [math]\displaystyle{ k(q) }[/math] для каждого возможного [math]\displaystyle{ q, }[/math] ключ будет считаться взломанным.
Процедура атаки следующая:
- Подобрать сообщение [math]\displaystyle{ m = (m_0, m_1), }[/math]так, чтобы [math]\displaystyle{ m_1^* = q. }[/math]
- Взломщик получает зашифрованное сообщение [math]\displaystyle{ (m_{16}, m_{17}) = F(m), }[/math] соответствующее открытому тексту [math]\displaystyle{ m. }[/math]
- Пусть [math]\displaystyle{ \tilde{k} }[/math] — один из возможных 8-битных ключей (всего [math]\displaystyle{ 2^8 }[/math] комбинаций). И пусть [math]\displaystyle{ \tilde{T} = T_\tilde{k}(m) }[/math] есть результат после работы от 1 раунда с ключом [math]\displaystyle{ \tilde{k} }[/math].
- Если [math]\displaystyle{ \tilde{k} = k(q), }[/math]то [math]\displaystyle{ \tilde{T} = T(m) }[/math]и [math]\displaystyle{ F(\tilde{T}) = FT(m) = TF(m) = T(m_{16}, m_{17}) = (m_{17}, ?). }[/math] Следовательно левая половина [math]\displaystyle{ F(\tilde{T}) }[/math] согласована с правой половиной [math]\displaystyle{ F(m) = (m_{16}, m_{17}). }[/math]
- Взломщик получает зашифрованное сообщение [math]\displaystyle{ F(\tilde{T}), }[/math] соответствующее заранее выбранному тексту [math]\displaystyle{ \tilde{T}. }[/math] Если правая половина [math]\displaystyle{ F(m) }[/math] соответствует левой половине [math]\displaystyle{ F(\tilde{T}), }[/math]то можно считать [math]\displaystyle{ \tilde{k} }[/math] допустимым значением для [math]\displaystyle{ k(q). }[/math] В худшем случае нужно будет перебрать [math]\displaystyle{ 2^8 = 256 }[/math]комбинаций [math]\displaystyle{ \tilde{k} }[/math] для нахождения нужного значения.
- Повторяем процедуру для каждого [math]\displaystyle{ q \in \{0, 1\}^8, }[/math] получая значение ключа [math]\displaystyle{ k }[/math] с помощью [math]\displaystyle{ 2^8 (2^8 + 1) = 65792 }[/math] заранее выбранных открытых текстов.
Атаки на шифр
В 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.