Дифференциальный криптоанализ высшего порядка

В криптографии блочных дифференциальный криптоанализ высшего порядка является обобщением дифференциального криптоанализа , атаки, используемой против шифров . В то время как в стандартном дифференциальном криптоанализе используется разница только между двумя текстами, дифференциальный криптоанализ более высокого порядка изучает распространение набора различий между большим набором текстов. Сюэцзя Лай в 1994 году заложил основу, показав, что дифференциалы являются частным случаем более общего случая производных более высокого порядка. Ларс Кнудсен в том же году смог показать, как концепцию производных более высокого порядка можно использовать для проведения атак на блочные шифры. Эти атаки могут превосходить стандартный дифференциальный криптоанализ. Дифференциальный криптоанализ высшего порядка, в частности, использовался для взлома KN-Cipher , шифра, который, как ранее было доказано, невосприимчив к стандартному дифференциальному криптоанализу.

Производные высшего порядка

Блочный шифр, который отображает $n$-битовые строки для $n$-битовые строки для фиксированного ключа можно рассматривать как функцию $f:\mathbb {F} _{2}^{n}\to \mathbb {F} _{2}^{n}$. В стандартном дифференциальном криптоанализе нужно найти пару входных разностей. $\alpha$ и разница выходов $\beta$ такие, что два входных текста с разницей $\alpha$ скорее всего, приведут к выходным текстам с разницей $\beta$ то есть, что $f(m\oplus \alpha )\oplus f(m)=\beta$ верно для многих $m\in \mathbb {F} _{2}^{n}$. Обратите внимание, что используемая здесь разница представляет собой XOR , что является обычным случаем, хотя возможны и другие определения разницы.

Это мотивирует определение производной функции $f:\mathbb {F} _{2}^{n}\to \mathbb {F} _{2}^{n}$ в какой-то момент $\alpha$ как

$\Delta _{\alpha }f(x):=f(x\oplus \alpha )\oplus f(x)$.

Используя это определение, $i$-я производная при $(\alpha _{1},\alpha _{2},\dots ,\alpha _{i})$ можно рекурсивно определить как

$\Delta _{\alpha _{1},\alpha _{2},\dots ,\alpha _{i}}^{(i)}f(x):=\Delta _{\alpha _{i}}\left(\Delta _{\alpha _{1},\alpha _{2},\dots ,\alpha _{i-1}}^{i-1}f(x)\right)$.

Так например $\Delta _{\alpha _{1},\alpha _{2}}^{(2)}f(x)=f(x)\oplus f(x\oplus \alpha _{1})\oplus f(x\oplus \alpha _{2})\oplus f(x\oplus \alpha _{1}\oplus \alpha _{2})$.

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

Дифференциальные атаки высшего порядка

Для реализации атаки с использованием производных более высокого порядка необходимы знания о распределении вероятностей производной шифра. Вычисление или оценка этого распределения, как правило, является сложной задачей, но если известно, что рассматриваемый шифр имеет низкую алгебраическую степень , можно использовать тот факт, что производные уменьшают эту степень. Например, если известно, что шифр (или анализируемая S-блок-функция) имеет только алгебраическую степень 8, любая производная 9-го порядка должна быть равна 0.

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

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

Ограничения дифференциальных

Работает для малых или малых S-блоков или малых S-блоков. В дополнение к операциям AND и XOR.

См. также

• Дифференциальный криптоанализ
• KN-шифр
• Кубическая атака