Дифференциальный анализ СПН

Ссылка: Учебник HM Heys

Если мы найдем дифференциальный след, который сохраняется с некоторой значимой вероятностью для n-1 раундов для структуры SPN с n раундами, то мы можем восстановить некоторые биты подключа последнего раунда.

Что происходит, когда мы управляем только дифференциальным следом, который сохраняется с немалой вероятностью только для нескольких раундов R, где R < n-1? Как мы поступим в этом случае, чтобы провести атаку с восстановлением ключа?

Я буду очень признателен за некоторые подсказки, чтобы подумать об этом.

самообучение

Я бы не согласился с ответом @kodlu. В классическом дифференциальном криптоанализе мы платим не за «вероятность» последних раундов, а за перечисление задействованных битов ключа. Другими словами, расшифровка не является статистической.

И это то, что делает использование меньшего $R$ трудно: ключевые догадки. Шифры имеют хорошую диффузию, и с каждым дополнительным раундом для частичного расшифрования в конце число битов ключа, которое необходимо угадать, чтобы проверить разницу вывода (теперь, статистически, на каждое предположение ключа), растет очень быстро.

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

Обратите внимание, что $R$ и количество ключевых битов, которые нужно угадать, находятся в компромиссе: меньше $R$ увеличивает дифференциальную вероятность, но также увеличивает количество угадываемых битов ключа. Обычно выигрыш в дифференциальной вероятности при переходе от $R=n-1$ к $R=n-2$ не уравновешивает увеличение сложности подбора ключа при частичном расшифровывании 2 раундов вместо 1.

Причина $R=n-1$ (или же $R=1,$ применяется к отображению расшифровки) используется следующее. Все индивидуальные дифференциальные аппроксимации, а также дифференциальный след, который выбирается $R$ выход раундов статистический отношения.

Однако теперь можно использовать вывод зашифрованного текста, запускать Sbox в последнем раунде в обратном порядке и условно на каждом предположении для круглых ключей XORed на входы $n^{th}$ круглые Sboxes есть неслучайные и точные предположения для выходов целевых Sbox из раунда $n-1.$ Это означает, что можно провести надежный статистический эксперимент и надежно рассчитать эмпирическую дифференциальную вероятность выбранной разности входных и выходных данных.

На этом этапе, при наличии достаточного количества пар P/C, предположение ключа, дающее наибольшую эмпирическую вероятность, объявляется наиболее вероятным предположением ключа.

Смотрите мой ответ на следующий вопрос для более конкретных деталей.

Учебное пособие по дифференциальному криптоанализу Говарда М. Хейса

Редактировать: Спасибо @fractalice за неаккуратную последнюю часть моего ответа. Действительно, важна вычислительная сложность прохождения ключевых догадок «активных» Sbox в последнем раунде. Таким образом, дифференциальная вероятность $\эпсилон$ принадлежащий $n-1$ дифференциальная характеристика означает, что вам нужно использовать грубо $с/\эпсилон$ пары P/C для того, чтобы эмпирически характеристика была доминирующей, а при наличии $к$ активные Sboxes в последнем раунде вам нужно будет попробовать $2^{4k}$ (поскольку Sbox имеют ширину 4 бита) угадали ключи, пытаясь решить, какие угаданные ключи наиболее вероятны.