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


 

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

6806. Ограничения целостности в SQL Oracle 188.5 KB
  Ограничения целостности в SQL Oracle Цели лабораторной работы Изучить возможности SQL Oracle по описанию и поддержанию ограничений целостности. Приобрести практический опыт по описанию ограничений целостности. Теоретические о...
6807. Измерение сопротивления прямым и косвенным методами 68 KB
  Измерение сопротивления прямым и косвенным методами. Подготовка приборов к измерению сопротивления В7-26 Переключатель рода работ перевести в положение r и проверить нулевое положение указателя при замкнутых накоротко гнездах...
6808. Одержання тонкоплівкових структур термічним випаровуванням у вакуумі 66.5 KB
  Одержання тонкоплівкових структур термічним випаровуванням у вакуумі Ціль роботи: ознайомлення з методом осадження тонкоплівкових покриттів з пари речовини, що випаровується у вакуумі. Робота містить у собі одержання металевих плівок методом термічн...
6809. Базова VLAN Конфігурація 572 KB
  Базова VLAN Конфігурація Діаграма топології Таблиця адрес Пристрій (Ім'я хоста) Інтерфейс IP адрес Маска підмережі Шлюз по замовчуванню S1 VLAN 99 172.17.99.11 255.255.255.0 N/A S2 VLAN....
6810. Параметрична ідентифікація параметрів з використанням функцій чутливості 116.93 KB
  Параметрична ідентифікація параметрів з використанням функцій чутливості. Для математичної моделі коливання трьох мас, які поєднані між собою пружинами з відповідними жорсткостями, і відомої функції спостереження координат моделі потрі...
6811. Data manipulation in SQL Oracle 110 KB
  Data manipulation in SQL Oracle Purpose of the lab To study SQL Oracle possibilities in inserting, updating and deleting rows in a tables. To acquire practical skills in inserting, updating and deleting rows in a tables by using SQ...
6812. Манипулирование данными в SQL Oracle 121 KB
  Манипулирование данными в SQLOracle Цели лабораторной работы Изучить возможности SQL Oracle по вставке, обновлению и удалению строк в таблице. Приобрести практический опыт по вставке, обновлению и удалению строк в таблице с и...
6813. Опрацювання текстової інформації в MS-Word. Форматування та друк тексту 421 KB
  Опрацювання текстової інформації в MS-Word. Форматування та друк тексту Мета: удосконалити навички щодо створення та збереження документів та їх копій у текстовому редакторі Word, навички щодо редагування і форматування тестів. Теоретичні відомості ...
6814. Обработка результатов многократных равноточных наблюдений при прямых измерениях 318.5 KB
  Обработка результатов многократных равноточных наблюдений при прямых измерениях. Цель работы: изучить порядок обработки результатов многократных наблюдений при прямых измерениях приобрести навыки стандартной обработки результатов наблюдений, оценки...