Линейный криптоанализ

Криптоанализ со связанными ключами

В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?

Криптоанализ со связанными ключами похож на дифференциальный криптоанализ, но он изучает разл и-чие между ключами. Вскрытие отличается от любого из ранее рассмотренных: криптоаналитик выбирает связь между парой ключей, но сами ключи остаются ему неизвестны. Данные шифруются обоими ключами. В вар и-анте с известным открытым текстом криптоаналитику известны открытый текст и шифротекст данных, шифр о-ванных двумя ключами. В варианте с выбранным открытым текстом криптоаналитик пытается выбрать откр ы-тый текст, зашифрованный двумя ключами.

Модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа, менее безопасен. Криптоанализ со связанными ключами может взломать такой вариант алгоритма, использовав только 2 ¹⁷ вы­бранных открытых текстов для выбранных ключей или 2³³ известных открытых текстов для выбранных ключей [158, 163].

Такое вскрытие также не реализуемо на практике, но оно интересно по трем причинам. Во первых, это пе р-вая попытка криптоаналитического вскрытия алгоритма генерации подключей в DES. Во вторых, это вскрытие не зависит от количества этапов криптографического алгоритма, он одинаково эффективен против DES с 16, 32 или 1000 этапами. И в третьих, DES невосприимчив к такому вскрытию. Изменение количества битов циклич е-ского сдвига мешает криптоанализу со связанными ключами.

Линейный криптоанализ представляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsura Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные приближения для оп и-сания работы блочного шифра (в данном случае DES.)

Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, вы получите бит, который представляет собой XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с некот о-рой вероятностьюp. Еслиp Ф 1/2, то это смещение можно использовать. Используйте собранные открытые те к-сты и связанные шифротексты для предположения о значениях битов ключа. Чем больше у вас данных, тем вернее предположение. Чем больше смещение, тем б ыстрее вскрытие увенчается успехом.

Как определить хорошее линейное приближение для DES? Найдите хорошие одноэтапные линейные пр и-ближения и объедините их. (Начальная и заключительная перестановки снова игнорируются, так как они не влияют на вскрытие.) Взгляните на S-блоки. У них 6 входных битов и 4 выходных. Входные биты можно объ е-динить с помощью операции XOR 63 способами (2⁶ - 1), а выходные биты - 15 способами. Теперь для каждого S-блока можно оценить вероятность того, что для случайно выбранного входа входная комбинация XOR равна некоторой выходной комбинации XOR. Если существует комбинация с достаточно большим смещением, то л и-нейный криптоанализ может сработать.

Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я и з-

бавлю вас от длительного изучения таблиц, наиболее смещенным S-блоком является пятый S-блок. Действ и-тельно, для 12 входов второй входной бит равен XOR всех четырех выходных битов. Это соответствует вероя т-ности 3/16 или смещению 5/16, что является самым большим смещением для всех S-блоков. (Шамир писал об этом в [1423], но не смог найти способа использовать.)

На 4-й показано, как воспользоваться этим для вскрытия функции этапа DES. Ь26 - это входной бит S-блока 5. (Я нумерую биты слева направо от 1 до 64. Мацуи игнорирует это принятое для DES соглашение и нумерует свои биты справа налево и от 0 до 63. Этого хватит, чтобы свести вас с ума.) с₁₇, с₁₈, с₁₉, с₂₀ - это 4 выходных бита S-блока 5. Мы можем проследить Ь₂₆ в обратном направлении от входа в S-блок. Для получения Ь₂₆ бит объединяется с помощью XOR с битом подключа K_h26. А бит Х_г1 проходит через подстановку с расширением, чтобы превратиться в а₂₆. После S-блока 4 выходных бита проходят через Р-блок, превращаясь в четыре выхо д-ных бита функции этапа: Y₃, Y_H, Y_u и Y₂₅. Это означает, что с вероятностью 1/2 - 5/6:

Х17 © Г3 © Г8 © У14 © Y25 = K_h26

X

Хм

Е

Е(Х)

К,

Э26

-$

К/,26

ь26

S-блок

Ci7,Cig,Ci9, C20

У

Уз, Ye, Y_u, Y₂₅

Рис. 12-8. 1-этапное линейное приближение для DES.

Способ, которым можно объединить линейные приближения для различных этапов, похож на тот, который обсуждался для дифференциального криптоанализа. На 3-й показано 3-этапное линейное приближение с веро­ятностью 1/2+0.0061. Качество отдельных приближений различно: последнее очень хорошо, первое достаточно хорошо, а среднее - плохо. Но вместе эти три 1-этапных приближения дают очень хорошее трехэтапное пр и-ближение.

A

Км,26

к,+1,26

К/,26

A

Л=[3, 8, 14, 25] В=[8, 14, 25]

С вероятностью 1/2+6.1*10^-3

Рис. 12-9. 3-этапное линейное приближение DES.

Базовое вскрытие должно использовать наилучшее линейное приближение для 16-этапного DES. Для него требуется 2⁴⁷ известных открытых блоков, а результатом вскрытия является 1 бит ключа. Это не очень полезно. Если вы поменяете местами открытый текст и шифротекст и используете дешифрирование вместе с шифров а-нием, вы сможете получить 2 бита. Это все еще не очень полезно.

Существует ряд тонкостей. Используйте 14-этапное линейное приближение для этапов с 2 по 15. Попробуем угадать 6 битов подключа для S-блока 5 первого и последнего этапов (всего, таким образом, 12 битов ключа). Для эффективности выполняем линейный криптоанализ параллельно 2 ^п раз и выбираем правильный вариант, основываясь на вероятностях. Это раскрывает 12 битов и Ь₂₆, а поменяв местами открытый текст и шифротекст мы получим еще 13 битов. Для получения оставшихся 30 битов используйте исчерпывающий поиск. Существ у-ют и друге приемы, но описанный является основным.

При вскрытии таким образом полного 16 этапного DES ключ будет раскрыт в среднем с помощью 2 ⁴³ из­вестных открытых текстов. Программная реализации этого вскрытия, работая на 12 рабочих станциях НР9735, раскрыла ключ DES за 50 дней [1019]. В момент написания этой книги это наиболее эффективный способ вскрытия DES.

Линейный криптоанализ сильно зависит от структуры S-блоков, оказалось, что S-блоки DES не оптимизир о-ваны против такого способа вскрытия. Действительно, смещение в S-блоках, выбранных для DES, находится между 9 и 16 процентами, что не обеспечивает надежной защиты против линейного криптоанализа [1018]. С о-гласно Дону Копперсмиту [373, 374] устойчивость к линейному криптоанализу "не входило в число критериев проектирования DES". Либо разработчикам не было известно о линейном криптоанализе, либо при проектир о-вании они отдали преимущество устойчивости против известного им еще более мощного средства вскрытия.

Линейный криптоанализ новее, чем дифференциальный, и в ближайшее время возможно дальнейшее пр о-движение в этом направлении. Некоторые идеи выдвинуты в [1270, 811], но не ясно, можно ли их эффективно применить против полного DES. Однако они очень хорошо работают против вариантов с уменьшенным числом этапов.

Дата добавления: 2014-11-29