openPGP в России

14.04 // Алгебраический криптоанализ против проездных карточек

Исследователи Nicolas T. Courtois, Karsten Nohl и Sean O'Neil опубликовали анонс работы "Algebraic Attacks on the Crypto-1 Stream Cipher in MiFare Classic and Oyster Cards"^[link1], в которой рассматривается применение алгебраического криптоанализа против потокового шифра Crypto-1.

Этот потоковый шифр не отличается криптостойкостью, он рассчитан на использование в чипах дешёвых проездных карт (London's Oyster Card, Netherlands OV chipcard, US Bostons Charlie card), хотя также эти чипы применяются и в системах правительственной безопасности. Размер ключа шифра всего 48 бит. Однако взлом отдельной карты грубой силой пока ещё можно считать не практичным.

Первоначально этот закрытый коммерческий алгоритм был восстановлен путём реверс-инжиниринга. Затем удалось осуществить практический взлом карты в течении нескольких минут, используя уязвимости протокола и недостаточно качественный генератор случайных чисел в считывателях карт.

Новый этап взлома: полностью пассивный перехват и алгебраический криптоанализ. Сеанс связи с картой может быть перехвачен пассивным сканером на расстоянии, и из единственного сеанса извлекается ключ карты с помощью алгебраического криптоанализа. Для этого достаточно всего несколько минут работы персонального компьютера и около 50 битов шифртекста.

Интерес к алгебраическому криптоанализу возник из-за попытки разработать методику взлома шифра AES/Rijndael, который основан на алгебраических операциях. Однако при решении этой задачи авторы столкнулись с серьёзными трудностями и пока успешно опробуют свой метод на простых шифрах, в том числе изначально и не имеющими чисто алгебраической структуры.

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

Сложный процесс шифрования разбивается на множество элементарных шагов в виде примитивных функций, которые можно описать алгебраически уравнениями невысокого порядка над полем GF(2). Для решения систем таких уравнений используется математический аппарат на основе базисов Грёбнера и алгоритмов решения SAT-задач.

Именно создание оптимизированных алгоритмов, требующих меньших объёмов памяти, позволило добиться успехов в алгебраическом криптоанализе. И если взлом шифра проездных карточек не так важен (потенциально, более дорогие версии этих чипов могут поддерживать и DES, и AES), то развитие алгебраического криптоанализа может серьёзно пересмотреть существующие методы дизайна шифров.

Ранее алгебраический криптоанализ был использован для взлома шифра охранных сигнализаций KeeLoq^[link2], хотя более практичными оказались методы на основе анализа побочных каналов.

Источник: Cryptology ePrint Archive^[link1]