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

===={{a name="1404"}}""14.04 // Алгебраический криптоанализ против проездных карточек""====

Исследователи Nicolas T. Courtois, Karsten Nohl и Sean O'Neil опубликовали анонс работы ((http://eprint.iacr.org/2008/166 "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), то развитие алгебраического криптоанализа может серьёзно пересмотреть существующие методы дизайна шифров.

Ранее алгебраический криптоанализ был использован для взлома шифра охранных сигнализаций ((http://eprint.iacr.org/2007/062 KeeLoq)), хотя более практичными оказались методы на основе анализа побочных каналов.

++Источник: ((http://eprint.iacr.org/2008/166 Cryptology ePrint Archive))++

Ваше имя:
	Запомнить псевдоним (сохранить в cookie)
	OpenPGP-подписанный текст в кодировке Помощь
	Сохранить параметры OpenPGP в cookie

Для корректной работы разрешите в своем браузере показ изображений.

Пожалуйста, напишите, кого/что вы видите
на изображенной слева картинке. Если
там несколько персонажей/предметов,
перечислите их в именительном падеже
через пробел (одинаковых приводите во
множественном числе).

(осталось попыток на решение теста: 3)

Поддержка BBCode включена