22238

Атака на DES уменьшенный до восьми циклов

Лекция

Информатика, кибернетика и программирование

Введение в дифференциальный криптанализ 1 Атака на DES уменьшенный до восьми циклов Чтобы найти другие биты Эли Бихам и Ади Шамир фильтруют все пары и оставляют только те которые имеют ожидаемое значение используя при этом известные значения h и значения ключевых битов K8 входящих в S6 S7 и S8. Ожидаемое число остающихся пар есть 53. Они применяют аналогичный метод счета используя увеличенное отношение S N созданное большой концентрацией правильных пар и затем снова фильтруют пары. Неправильная пара не отвергается этим или...

Русский

2013-08-04

414 KB

2 чел.

ЛЕКЦИЯ 5

Тема 1. Введение в дифференциальный криптанализ

1 Атака на DES уменьшенный до восьми циклов

Чтобы найти другие биты, Эли Бихам и Ади Шамир фильтруют все пары и оставляют только те, которые имеют ожидаемое значение , используя при этом известные значения h и значения ключевых битов K8, входящих в S6, S7 и S8. Ожидаемое число остающихся пар есть 53.

Следующие биты, которые они ищут, это двенадцать битов K8, которые соответствуют S2 и S5. Они применяют аналогичный метод счета (используя увеличенное отношение S/N, созданное большой концентрацией правильных пар) и затем снова фильтруют пары. Неправильная пара не отвергается этим или предшествующим фильтром с вероятностью 2-20 и, таким образом, почти все оставшиеся пары являются правильными.

Используя известные подключевые биты K8, можно вычислить значения 20-ти битов каждого из H и H* для каждой пары и таким образом вычислить 20 битов каждого из g и g* (g = l  H, l разность левых полублоков шифртекстов). Таблица 1 показывает зависимость битов g и битов подключа K7 в седьмом цикле для известных и неизвестных битов подключа K8 в восьмом цикле. Цифры 1, 3 и 4 означают, что они зависят от величины неизвестных ключевых битов, входящих в соответствующий S блок на восьмом цикле. ‘+’ означает, что они зависят только от известных битов K8. Восемь ключевых битов не использованы совсем в K8 и отмечены ..

В S блок

g биты

Ключевые би

#

ты KSg

S1

+4++++

3+..4+

S2

++3++1

134333

S3

+14+++

+1+41+

S4

++++31

11..1+

S5

31++4+

+++.++

S6

4++13+

+.+.++

S7

3+4+++

+++.++

S8

++31+4

++++++

Таблица 1. Известные биты в седьмом цикле.

Ожидаемое значение G известно из формулы G = f  h. Мы можем теперь найти 18 отсутствующих битов K8 полным перебором 218 возможностей для каждой пары. Таким образом мы, знаем H, H* и g, g* и 40 битов K7. Для каждой пары мы проверяем, что ожидаемое значение G поддерживается. Для правильного значения тех 18 ключевых битов ожидаемое G поддерживается почти для всех отфильтрованных пар. Все другие возможные значения удовлетворяют ожидаемому значению G только для нескольких пар (обычно 2-3 пары, в то время как правильное значение поддерживается для 15 пар). Для сохранения компьютерного времени мы ищем первоначально для 12 ключевых битов, входящих в S1 и S4 в восьмом цикле. Их достаточно для вычисления  как показано в таблице 9. Аналогичными методами мы находим эти 12 битов и затем находим другие восемь битов. Это завершает вычисление 48 битов K8. Только восемь ключевых битов все еще неизвестны и они могут быть найдены полным перебором 256 случаев, используя одну пару шифротекстов, и проверяя, какой XOR открытого текста равен ожидаемому.

Чтобы сохранить дисковое пространство мы можем фильтровать пары сразу, как только они создаются и отвергать все определенные неправильные пары (оставляя 0.851/3 из всех пар). Следовательно, в случае счета 24 битов, 25000 пар сводятся к около 7500 парам. Для случая счета 18 битов Эли Бихам и Ади Шамир разработали другой критерий, который отвергает большинство неправильных пар, оставляя почти все правильные пары. Этот критерий базируется на тщательно выбранной весовой функции, отвергающий любую пару, чей вес ниже, чем конкретный порог. Этот критерий является расширением фильтрации при идентификации неправильных пар (где порог является фактически нулем) и базируется на идее, что правильная пара как правило предлагает более вероятные ключевые значения, чем неправильная пара. Весовая функция является произведением числа возможных ключей для каждого из пяти участвующих в вычислениях S блоков (т.е., числа соответствующих выходов таблиц распределения побитовых разностей). Порог выбирается так, чтобы максимизировать объем отброшенных пар, оставляя как можно больше правильных пар. Наилучшее пороговое значение, какое было найдено экспериментально это 8192, которое отвергает около 97% неправильных пар и оставляет почти все правильные пары. Это действительно уменьшает  число анализируемых пар. Фактически из 150000 для анализа остается около 7500 пар, что приводит к соответствующему уменьшению времени выполнения атаки.

S2x

S2x*

S2y

S2y*

123456

123456

1234

1234

000010

001010

0001

1011

000110

001110

1110

0100

010001

011001

1100

0110

010101

011101

0001

1011

100000

101000

0000

1010

100010

101010

1110

0100

100100

101100

0111

1101

100110

101110

1011

0001

Таблица 2. Возможные примеры 08x  Ax с помощью S2 (в двоичном представлении).

Атакующая программа находит ключ меньше, чем за две минуты на COMPAQ персональном компьютере с 95% коэффициентом успеха (используя 150000 пар). Используя 250000 пар коэффициент успеха увеличивается почти до 100%. Программа использует 460K памяти, большая часть которой идет для счетного массива (одного байта достаточно для каждого счетчика, т.к. максимальный счет около 53, и, таким образом, общий размер массива равен 218 байт), и предварительно подготовленные для ускорения счета таблицы. Программа, содержащая 224 ячеек памяти, находит ключ, используя только 25000 пар.

2. Атака на DES с произвольным количеством циклов

На этой лекции мы рассмотрим атаку на полный 16-ти цикловый DES. Эта атака, как и предыдущая, находит некоторые биты подключа последнего цикла. Другие биты подключа последнего цикла могут быть вычислены используя эти известные биты и уменьшением криптосистемы до меньшего количества циклов. Только восемь битов не появляются в подключе последнего цикла и они могут найдены перебором оставшихся 256 возможных ключей.

Приведенная на Рис. 1 итеративная характеристика может использо-ваться, для того, чтобы выполнить криптоанализ (по крайней мере в принципе) вариантов DES с произвольным количеством циклов. Именно на основе этой итеративной характеристики Эли Бихаму и Ади Шамиру удалось обосновать атаку на полный 16-цикловый DES со сложностью меньшей, чем прямой перебор ключей.

Значение 19 60 00 00x обозначено . Итеративная характеристика имеет вид:

Рис. 1. Итеративная характеристика обнуляющего типа.

Мы ее будем называть итеративной характеристикой обнуляющего типа, так как в ней используется переход . Она имеет вероятность

.

Действительно,  только для трех S блоков: S1, S2 и S3, для которых:

 с вероятностью 14/64;

 с вероятностью 8/64;

 с вероятностью 10/64,

а для других S блоков (S4, . . . , S8),    всегда.

Таким образом, B = 0 с вероятностью .

Легко убедиться, что конкатенацией приведенной выше итеративной характеристики с собой и с одноцикловой характеристикой с вероятностью 1 (тождественного типа) мы получаем характеристики с вероятностями, представленными в таблице 1. Кроме того, плайнтекстовые и шифртекстовые XOR-ы этих характеристик равны:  и для последующих циклов (например, для пятицикловой характеристики  пятый из этих циклов также удовлетворяет условию ).

Действительно, непосредственные построения приводят к очевидному результату:

всегда;

с вероятностью близкой к 1/234;

всегда;

с вероятностью близкой к 1/234;

всегда,

и так можно продолжать для любого числа циклов.

Число циклов

Вероятность

3

1/234

5

1/55000

7

2-24

9

2-32

11

2-40

13

2-48

15

256

Таблица 1. Вероятности итеративной характеристики в зависимости от числа циклов.

Примечание Есть другое значение, для которого лемма 2 и теорема 2 выполняются с теми же вероятностями. Эта значение = 1B 60 00 00x. Есть также несколько дополнительных значений, для которых вероятности характеристик меньше. Наилучшее из них   = 00 19 60 00x, для которого вероятность равна точно 1/256. Расширение этой итеративной характеристики на 15 циклов, имеет вероятность 256.

Существует несколько возможных типов атаки, в зависимости от количества дополнительных циклов в криптосистеме, которые не покрываются самой характеристикой. Рассмотренная выше атака на DES, сведенный к восьми циклов, использовала пяти цикловую характеристику и три дополнительных цикла Этот тип атаки Эли Биханом и Ади Шамиром был назван 3R-атакой. Другими типами атак являются 2R-атака с двумя дополнительными циклами и 1R-атака с одним дополнительным циклом (где характерным оказывается (является) фиксированное r’). 0R-атака также возможна, но она может быть сведена к 1R-атаке с лучшей статистикой и тем же S/N. 0R-атака имеет преимущество в том, что правильные пары могут быть распознаны почти без ошибок (вероятность неправильной пары, чтобы выжить, есть 2-64), и, таким образом, требуемая память может стать неприемлемой при клик методе. Для фиксированной криптосистемы желательно использовать самую короткую возможную характеристику из-за своей лучшей статистики. Таким образом, 3R-атака более желательна чем 2R-атака и обе более желательны чем 1R-атака. Остановимся на сущности этих атак более подробно.

3.1. 3R-атаки

В 3R-атаках вычисления могут быть сделаны на всех битах подключа последнего цикла, входящих в S блоки, которые имеют нулевые входные XOR-ы в цикле, следующим за последним.

В DES уменьшенном до восьми циклов сначала могут быть обнаружены 30 битов подключа, используя итеративную характеристику с пятью циклами (чья вероятность около 1/55000) атакой, которая является подобной одной из рассмотренных в предыдущей лекции.

Используя массив размером 224, мы имеем S/N = 224/44 0,8 55000 = 1,5. Нам нужно около 220 пар. Используя массив размером 230, мы имеем S/N = 230/45 55000 19. Около 67% (10,85) пар могут быть идентифицированы выдвижением как правильные пары.

3.2 2R-атаки

В 2R-атаках, подсчет может быть сделан для всех битов подключа последнего цикла. Возможные проверки, могут быть сделаны для всех предшествующих цикловых S блоков. S блок, чей входной XOR является нулем, должен также иметь выходной XOR нулем, т.е. шанс успеха этого выбора равен 1/16. Для других S блоков шанс успеха около 0.8.

В DES сведенному к девяти циклам 48 битов K9 могут обнаруживаться используя 226 пар используя семи цикловую характеристику. Мы знаем, что:

P = (;0)

a = 0  A = 0  всегда

b =   B= 0  с вероятностью около 1/234

c = 0  C = 0  всегда

g = 0  G = 0  всегда

h =   H = i  g = r

i = r  I = h  l = l  

T= (l; r).

Мы можем проверить, что h H и i I и считать возможные случаи ключевых битов. Переходы h  H пять S блоков удовлетворяют
S’Eh = S’Ih = 0 и таким образом S’Oh должно быть нулем (который случается для неправильных пар с вероятностью 1/16), пока другие три S блока удовлетворяют условию S’Ih  S’Oh (которое случается для неправильных пар с вероятностью 0.8). Следовательно, для вычисления всех 48 битов K9 имеем  и при вычислении 18 битов имеем . Даже раздельный счет шести ключевых битов, вводящих каждый S блок возможен с . Идентификация неправильных пар оставляет только 0.83*(1/16)5*0.88+2-24 неправильных пар и таким образом только около одной неправильной пары остаутся на каждую правильную пару. Вероятность характеристики есть 2-24 и таким образом нам нужно около 226 пар для криптоанализа. Этой атаке нужно больше данных чем предшествующей 3R-атаке на DES, сведенный к девяти циклам, но нужна значительно меньшая память. Из-за очень хорошей идентификации неправильных пар (только около восьми пар не отвергаются, четыре правильных пары и четыре неправильных пары) возможно использовать метод клики на всех 48 битах.

Одиннадцать циклов могут быть взломаны использованием девяти цикловой характеристики с массивом размера 218 и  при использовании 235 пар. Метод клики может все еще использоваться на 48 битах подключа с с идентификацией, которая содержит список из 2322-24 = 28 неправильных пар на каждую правильную пару.

13 циклов могут быть взломаны используя одиннадцати цикловую характеристику с массивом размера 230 и  используя 243 пар. Kлик метод невозможен, поскольку 2432-24 = 219 пар не отвергается. Счетные схемы на 18 и 24 битов не рекомендуются из-за низкого уровня S/N

15 циклов могут быть взломаны используя 13-цикловую характеристику с массивом размера 212 и  используя 251 пары. Это все еще быстрее чем полный перебор, но требуются нереальные объемы пространства и зашифрованных текстов.

3.3. 1R-атаки 

Вычисления в 1R-атаках могут быть сделаны на всех битах подключа последнего цикла, входящего в S блоки с ненулевыми входными XOR-ами. Сама проверка значений r и вероятных чеков во всех других S блоках в последнем цикле могут быть сделаны. Для S блоков с нулевыми входными XOR выходные XOR должны быть нулем тоже, то есть, контрольная ставка успеха 1/16. С Так как входной XOR является константой, то мы ее не можем различить между различными значениями подключа. Тем не менее, количество таких значений небольшое (восемь во всех 1R-атаках описанных здесь) и каждая может быть проверена позже в параллель следующей частью алгоритма (или через полный поиск или дифференциальной криптоаналитической атакой).

Десятицикловая характеристика может быть взломана, используя девяти цикловую характеристику, где

h =   H = 0 с вероятностью 1/234

i = 0  I = 0 всегда

j =  = r  J = l  i = l.

Мы можем легко идентифицировать правильные пары. Эти пары удовлетворяют условию r = и 20 битов на выходе l из S4, . . . , S8 - нули. Это также воздерживается (выдерживается) для 2-52 неправильных пар. Для других трех S блоков мы считаем возможные значения их 18 ключевых битов с . Таким образом нам нужно 234 пар.

Двенадцать циклов могут быть взломаны используя одиннадцати цикловую характеристику с  и 242 пары.

Четырнадцатицикловая характеристика может быть взломана используя 13-цикловую характеристику с  и 250 пар.

Для шестнадцатицикловой характеристики мы получаем отношение сигнал-шум  используя 15-цикловую характеристику. Она может быть взломана используя 257 пар. Заметим, что критерий 257 пар является более времяемким, чем прямой перебор для 256 возможных ключей.


 

А также другие работы, которые могут Вас заинтересовать

44596. Сетевые архитектуры ArcNet и ArcNet Plus 48 KB
  Физическая топология звезда шина звезда – шина; логическая топология упорядоченное кольцо; широкополосная передача данных 25 Мбит с и 20 Мбит с для rcNet Plus; метод доступа маркерный; средой передачи может быть: коаксиальный кабель длиной 600 м при звезде и 300 м при шине; витая пара максимальная длина 244 м – при звезде и шине; Компьютеры могут быть коаксиальным кабелем связаны в шину или в иных случаях подключены к концентраторам которые могут быть: пассивными; активными; интеллектуальными....
44597. Token Ring (Маркерное кольцо) 61.5 KB
  Физическая топология звезда; логическая топология кольцо; узкополосный тип передачи; скорость передачи 4 и 16 Мбит с; соединение неэкранированной и экранированной витой пары; метод доступа – маркерное кольцо. Формат кадра используемый в сетях Token Ring Аппаратные компоненты Логическое кольцо в этой сетевой архитектуре организуется концентратором который называется модулем множественного доступа MSU – MultySttion ccess Unit или интеллектуальным модулем множественного доступа SMU – Smrt Multysttion ccess Unit....
44598. FDDI - распределенный волоконно-оптический интерфейс передачи данных 42 KB
  В сети FDDI компьютер: захватывает маркер на определенный интервал времени; за этот интервал передает столько кадров сколько успеет; завершает передачу либо по окончании выделенного интервала времени либо из-за отсутствия передаваемых кадров. Этим объясняется более высокая производительность FDDI чем Token Ring которая позволяет циркулировать в кольце только одному кадру. FDDI основана на технологии совместного использования сети.
44599. СЕТЕВЫЕ АРХИТЕКТУРЫ 34.5 KB
  В соответствии со стандартными протоколами физического уровня выделяют три основные сетевые архитектуры Данные Циклический избыточный код для проверки ошибок Приемника источника Формат кадра в Ethernet Поле Тип протокола используется для идентификации протокола сетевого уровня IPX и IP маршрутизируемый или нет....
44600. Причины расширения ЛВС и используемые для этого устройства 28.5 KB
  С ростом компаний растут и ЛВС. Однако существуют устройства которые могут: сегментировать ЛВС так что каждый сегмент станет самостоятельной ЛВС; объединять две ЛВС в одну; подключать ЛВС к другим сетям для объединения их в интернет.
44601. Мост как устройство комплексирования ЛВС 190 KB
  Эти устройства как и репитеры могут увеличивать размер сети и количество РС в ней; соединять разнородные сетевые кабели. на более высоком чем репитеры и учитывают больше особенностей передаваемых данных позволяя: восстанавливать форму сигналов но делая это на уровне пакетов; соединять разнородные сегменты сети например Ethernet и Token Ring и переносить между ними пакеты; повысить производительность эффективность безопасность и надежность сетей что будет рассмотрено ниже. Принципы работы мостов Работа моста основана на...
44602. Маршрутизаторы 41 KB
  Маршрутизатор в отличие от моста имеет свой адрес и используется как промежуточный пункт назначения. Однако эта таблица существенно отличается от таблиц мостов тем что она содержит не адреса узлов а адреса сетей Для каждого протокола используемого в сети строится своя таблица которая включает: все известные адреса сетей; способы связи с другими сетями; возможные пути маршрутизации; стоимости передачи данных по этим путям. Маршрутизаторы принимая пакеты не проверяют адрес узла назначения а выделяют только адрес сети. Они...
44603. Подключение репитера в ЛВС 168.5 KB
  Подключение репитера в ЛВС Репитеры передают весь трафик в обоих направлениях и работают на физическом уровне модели OSI. Однако репитеры позволяют соединять два сегмента которые используют различные физические среды передачи сигналов кабель – оптика кабель – пара и т. Некоторые многопортовые репитеры работают как многопортовые концентраторы соединяющие разные типы кабелей.