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 возможных ключей.


 

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

12059. Валютная система и валютная политика России 245 KB
  ВВЕДЕНИЕ Валютная система – это совокупность двух понятий – валютного механизма и валютных отношений. Под валютным механизмом понимаются правовые нормы и институты представляющие их на национальном и международном уровнях. Валютные отношения – это повседневные свя
12060. Разработка экономического обоснования целесообразности открытия автосервиса ООО «Нижегородец» 396.5 KB
  Реферат Выпускная квалификационная работа бакалавра 51 с. 2 разд. 6 рис. 11 табл. 14 источников. БИЗНЕСПЛАН АВТОСЕРСВИС НИЖЕГОРОДЕЦ ВЫСОКИЙ УРОВЕНЬ СПРОСА АВТОМОЙКА ШИНОМОНТАЖ ИНСТРУМЕНТЫ Объектом работы является деятельность ООО Нижегородец. Целью выпускн...
12061. ДЕЙСТВУЮЩАЯ ПРАКТИКА ОРГАНИЗАЦИИ УЧЕТА ЗАРАБОТНОЙ ПЛАТЫ 978.5 KB
  СОДЕРЖАНИЕ ВВЕДЕНИЕ ГЛАВА 1. МЕТОДИЧЕСКИЕ ОСНОВЫ ОРГАНИЗАЦИИ УЧЕТА ОПЛАТЫ ТРУДА 1.1. Сущность понятие оплаты труда и ее формы 1.2. Исследование нормативной базы по оплате труда 1.3. Особенности деятельности предприятия и его учетная политика . ГЛАВА 2. ДЕЙСТВУЮ...
12062. Проблеми та перспективи розвитку валютних операцій в АКБ «Фінанси та кредит» та у банках України 411 KB
  Вступ Актуальність обраної теми полягає в тому що валютні операції банків займають важливе місце серед статей прибутку сучасного банку але питання здійснення зазначених операцій є досить складним і потребує детального вивчення. Сьогодні банк може запропонувати кл
12063. ШЛЯХИ ПІДВИЩЕННЯ ПРИБУТКОВОСТІ КОМЕРЦІЙНИХ БАНКІВ 325 KB
  ВСТУП Банківська система є важливою складовою економічної системи держави. Забезпечення стабільного прозорого функціонування банківських установ є однією з умов забезпечення конкурентоспроможності української економіки. У вітчизняній еконо
12064. НАПРАВЛЕНИЯ СОВЕРШЕНСТВОВАНИЯ ДЕЯТЕЛЬНОСТИ ОАО «СБЕРЕГАТЕЛЬНОГО БАНКА» НА ВАЛЮТНОМ РЫНКЕ 450 KB
  Сделки покупки-продажи иностранной валюты Наличные сделки покупки-продажи today omorrow spot Срочные сделки покупки-продажи forward futures option swap Сделки с разрывами даты валютирования Чистая балансовая позиция Открытая валютна...
12065. ОБЩАЯ ХАРАКТЕРИСТИКА ДЕЯТЕЛЬНОСТИ ЛЕНИНСКОГО ОТДЕЛЕНИЯ № 4158 АК СБ РФ 127.5 KB
  Введение Расчетнокассовый центр одно из центральных звеньев банковской системы. Развитие их деятельности – необходимое условие реального создания банковского механизма. Процесс экономических преобразований начался с реформирования банковс...
12066. Основные направления совершенствования денежно-кредитной политики в Российской Федерации 173 KB
  Введение Денежнокредитная политика – одно из четырех направлений единой финансовой политики государства обеспечивающих устойчивость экономики и достижение экономического роста. Именно она контролирует инфляцию и рост денежной массы. Наличие в Российской Федерац
12067. Совершенствование системы финансового анализа банковской деятельности 1.49 MB
  Введение Актуальность темы. Банки – неотъемлемая составляющая современного денежного хозяйства их деятельность тесно связана с потребностями производства. Банки создают основу рыночного механизма с помощью которого функционирует экономика