id: Гость   вход   регистрация
текущее время 12:22 29/03/2024
Владелец: unknown (создано 14/04/2008 15:39), редакция от 24/04/2008 20:23 (автор: volandlm) Печать
Категории: криптография, криптоанализ, симметричное шифрование, атаки
http://www.pgpru.com/Новости/2008/АлгебраическийКриптоанализПротивПроездныхКарточек
создать
просмотр
редакции
ссылки

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


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


Источник: Cryptology ePrint Archive


 
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3