Что вам стоит знать про Crypto-1

Что вам стоит знать про Crypto-1

Серафим Перекалин

Что такое Crypto-1?

Crypto-1 - это проприетарный потоковый шифр, разработанный компанией Philips Semiconductors (впоследствии NXP Semiconductors) специально для бесконтактных смарт-карт семейства MIFARE Classic. Долгое время его схема держалась в секрете, однако в 2007-2008 годах группы исследователей (Карстен Нол, Шон Девлин, Генрик Плёц и другие) провели успешный реверс-инжиниринг и опубликовали полное описание алгоритма.

Области применения

Карты MIFARE Classic с Crypto-1 использовались в самых разных сферах по всему миру:

  • Транспортные системы - лондонская Oyster, нидерландская OV‑Chipkaart, бостонская CharlieCard и многие другие.
  • Системы контроля доступа - в университетах (особенно в Нидерландах), на военных объектах (там же), в аэропортах (Схипхол).
  • Коммерческие системы - например, европейские кофейные автоматы Nespresso Pro использовали MIFARE Classic для оплаты.

Масштаб внедрения был огромным - по данным NXP, продано более 200 миллионов таких карт (и это только официальная статистика).

Чем интересен этот алгоритм?

Crypto-1 стала примером того, как опора на подход «security through obscurity» и проприетарность не являются гарантом безопасности и высокой криптостойкости.

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

Внутреннее устройство Crypto-1

В общем и целом, алгоритм представляет собой потоковый шифр с 48-битным секретным ключом.

Основным элементом является 48-битный регистр сдвига с линейной обратной связью (LFSR), в котором хранится внутреннее состояние. Для генерации ключевого потока используется нелинейная фильтрующая функция (20 входов, 1 выход), которая преобразует состояние LFSR в псевдослучайную битовую последовательность. Этим потоком затем шифруются данные, передаваемые между картой и считывателем.

Дополнительно, во время аутентификации задействуется 16-битный LFSR, выступающий в роли генератора псевдослучайных чисел (PRNG) для формирования nonce (случайного числа) считывателя.


Работа Crypto-1 проходит в двух режимах:

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

Ключевые уязвимости

Проблем у Crypto-1 достаточно:

  1. Предсказуемый PRNG - 16-битный LFSR инициализируется детерминированно (часто от времени), что позволяет атакующему вычислить будущие nonce и использовать это в атаках.
  2. Уязвимый протокол аутентификации - для восстановления внутреннего состояния LFSR достаточно перехватить несколько известных битов открытого текста (например, заголовки кадров стандарта ISO 14443).
  3. Недостаточная стойкость LFSR - хотя 48-битный ключ сам по себе не поддаётся прямому перебору, из-за линейной структуры и малой нелинейности фильтра ключ может быть восстановлен методами алгебраического криптоанализа крайне быстро.

Известные практические атаки

По результатам исследований были выведены следующие эффективные атаки на Crypto-1:

  • Nested attack - если известен хотя бы один ключ доступа к любому сектору карты, можно восстановить все остальные ключи, используя предсказуемость PRNG считывателя.
  • DarkSide attack - позволяет восстановить ключ даже без начального известного ключа, используя только несколько сеансов аутентификации и манипулируя запросами.
  • Reused Keys Nested attack - вариант nested, когда один и тот же ключ используется в нескольких секторах, что ускоряет взлом.
  • Algebraic attack - перехватывается около 50 бит ключевого потока; выходные биты выражаются в виде уравнений в алгебраической нормальной форме, затем система преобразуется в конъюнктивную нормальную форму и решается с помощью SAT-решателя. Этот метод часто комбинируют с другими для ускорения.
  • Аппаратный бэкдор - в 2024 году было доказано, что в картах FM11RF08S и многих других (включая старые оригинальные чипы NXP и Infineon) присутствует отдельный аппаратный бэкдор - недокументированные команды аутентификации с универсальными ключами, которые позволяют полностью обойти все защитные механизмы, включая статический зашифрованный nonce.

Что было сделано для защиты?

Вместо модификации самого алгоритма Crypto-1 (что невозможно без смены чипа) компания NXP выпустила обновлённые версии карт - MIFARE Classic EV1 и EV2, в которых были добавлены:

  • неперезаписываемый уникальный идентификатор (UID);
  • улучшенный (но всё ещё не криптостойкий) PRNG;
  • счётчики и проверки временных меток для усложнения replay-атак;
  • возможность блокировки записи в защищённые секторы после персонализации.

Однако сам алгоритм Crypto-1 остался неизменным - 48-битный LFSR и его структура не были переработаны. Поэтому все перечисленные атаки по-прежнему применимы (хотя некоторые требуют больше времени или специфических условий).

Где почитать подробнее


Report content on this page

Report Page

Please submit your DMCA takedown request to dmca@telegram.org