Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




27.01.2021


27.01.2021


27.01.2021


27.01.2021


27.01.2021





Яндекс.Метрика





New Data Seal

24.02.2021

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

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

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

  • Ключ представляет собой отображение: k : { 0 , 1 } 8 → { 0 , 1 } 8 , {displaystyle k:{0,1}^{8} ightarrow {0,1}^{8},} то есть размерность пространства таких ключей ( 2 8 ) 2 8 = 2 2048 , {displaystyle (2^{8})^{2^{8}}=2^{2048},} что более чем достаточно для предотвращения перебора ключей.
  • Система использует 2 заранее известных (не динамичных) S-блока: S 0 , S 1 , { 0 , 1 } 4 → { 0 , 1 } 4 , {displaystyle S_{0},S_{1},{0,1}^{4} ightarrow {0,1}^{4},} ключевое расписание состоит из одного ключа k . {displaystyle k.} Блок открытого текста делится на 2 подблока m i {displaystyle m_{i}} размером 64 бита каждый. Для того, чтобы посчитать f k ( m i ) : {displaystyle f_{k}(m_{i}):}
  • m i {displaystyle m_{i}} разбивается на восемь 8-битных частей. За m i ∗ {displaystyle m_{i}^{*}} обозначим байт, образованный первым битом каждого байта в m i {displaystyle m_{i}}
  • каждая часть m i {displaystyle m_{i}} разбивается на два 4-битных ниббла
  • к левому нибблу применяется S 0 , {displaystyle S_{0},} к правому — S 1 {displaystyle S_{1}}
  • в случае, если j {displaystyle j} -ый бит k ( m i ∗ ) {displaystyle k(m_{i}^{*})} равен 1, поменяются местами нибблы j {displaystyle j} -ой части после S 0 S 1 {displaystyle S_{0}S_{1}} преобразования
  • к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.

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

Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за T k {displaystyle T_{k}} преобразование, соответствующее одному раунду NDS, то есть T k ( m i − 1 , m i ) = ( m i , m i − 1 ⊕ f k ( m i ) ) . {displaystyle T_{k}(m_{i-1},m_{i})=(m_{i},m_{i-1}oplus f_{k}(m_{i})).} Далее, F = T 16 {displaystyle F=T^{16}} будет обозначать все 16 раундов. Заметим, что F {displaystyle F} и T {displaystyle T} коммутируют: F T ( m ) = T 16 T ( m ) = T T 16 ( m ) = T F ( m ) . {displaystyle FT(m)=T^{16}T(m)=TT^{16}(m)=TF(m).} В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа k ( q ) , q ∈ { 0 , 1 } 8 . {displaystyle k(q),;qin {0,1}^{8}.} Тогда если мы будем знать k ( q ) {displaystyle k(q)} для каждого возможного q , {displaystyle q,} ключ будет считаться взломанным.

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

  • Подобрать сообщение m = ( m 0 , m 1 ) , {displaystyle m=(m_{0},m_{1}),} так, чтобы m 1 ∗ = q . {displaystyle m_{1}^{*}=q.}
  • Взломщик получает зашифрованное сообщение ( m 16 , m 17 ) = F ( m ) , {displaystyle (m_{16},m_{17})=F(m),} соответствующее открытому тексту m . {displaystyle m.}
  • Пусть k ~ {displaystyle { ilde {k}}} — один из возможных 8-битных ключей (всего 2 8 {displaystyle 2^{8}} комбинаций). И пусть T ~ = T k ~ ( m ) {displaystyle { ilde {T}}=T_{ ilde {k}}(m)} есть результат после работы от 1 раунда с ключом k ~ {displaystyle { ilde {k}}} .
  • Если k ~ = k ( q ) , {displaystyle { ilde {k}}=k(q),} то T ~ = T ( m ) {displaystyle { ilde {T}}=T(m)} и F ( T ~ ) = F T ( m ) = T F ( m ) = T ( m 16 , m 17 ) = ( m 17 , ? ) . {displaystyle F({ ilde {T}})=FT(m)=TF(m)=T(m_{16},m_{17})=(m_{17},?).} Следовательно левая половина F ( T ~ ) {displaystyle F({ ilde {T}})} согласована с правой половиной F ( m ) = ( m 16 , m 17 ) . {displaystyle F(m)=(m_{16},m_{17}).}
  • Взломщик получает зашифрованное сообщение F ( T ~ ) , {displaystyle F({ ilde {T}}),} соответствующее заранее выбранному тексту T ~ . {displaystyle { ilde {T}}.} Если правая половина F ( m ) {displaystyle F(m)} соответствует левой половине F ( T ~ ) , {displaystyle F({ ilde {T}}),} то можно считать k ~ {displaystyle { ilde {k}}} допустимым значением для k ( q ) . {displaystyle k(q).} В худшем случае нужно будет перебрать 2 8 = 256 {displaystyle 2^{8}=256} комбинаций k ~ {displaystyle { ilde {k}}} для нахождения нужного значения.
  • Повторяем процедуру для каждого q ∈ { 0 , 1 } 8 , {displaystyle qin {0,1}^{8},} получая значение ключа k {displaystyle k} с помощью 2 8 ( 2 8 + 1 ) = 65792 {displaystyle 2^{8}(2^{8}+1)=65792} заранее выбранных открытых текстов.
  • Атаки на шифр

    В 1977 Эдна Гроссман и Брайант Такермен впервые продемонстрировали атаку на NDS с помощью сдвиговой атаки. Этот метод использует не более 4096 подобранных открытых текстов. В их лучшем испытании они смогли восстановить ключ только с 556 подобранными открытыми текстами.