КиЛок

KeeLoq — это запатентованный аппаратный блочный шифр , использующий сдвиговый регистр с нелинейной обратной связью (NLFSR). Протокол однонаправленной передачи команд был разработан Фредериком Брюэром из Nanoteq (Pty) Ltd., криптографический алгоритм был создан Гидеоном Куном из Университета Претории , а кремниевая реализация была разработана Виллемом Смитом из Nanoteq (Pty) Ltd ( Юг) . Африка ) в середине 1980-х годов. KeeLoq был продан Microchip Technology Inc в 1995 году за 10 миллионов долларов. Он используется в кодировщиках и декодерах со скачкообразным кодом , таких как NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX и MCS31X2. KeeLoq использовался во многих системах удаленного доступа без ключа такими компаниями, как Chrysler , Дэу , Фиат , Форд , ГМ , Хонда , Мерседес-Бенц , Toyota , Volvo , Volkswagen Group , Clifford, Shurlok и Jaguar .

Описание

Шифрование KeeLoq

Кодеры KeeLoq с «переходным кодом» шифруют заполненный 0 32-битный блок с помощью шифра KeeLoq для создания 32-битного « прыжкового кода ». 32-битный вектор инициализации линейно добавляется ( XOR ) к 32 младшим битам до ключа шифрования и после дешифрования .

Шифр KeeLoq принимает 64-битные ключи и шифрует 32-битные блоки, выполняя однобитовый NLFSR в течение 528 раундов. Функция обратной связи NLFSR 0x3A5C742E или

$F(a,b,c,d,e)=d\oplus e\oplus ac\oplus ae\oplus bc\oplus be\oplus cd\oplus de\oplus ade\oplus ace\oplus abd\oplus abc$

KeeLoq использует биты 1, 9, 20, 26 и 31 состояния NLFSR в качестве входных данных во время шифрования и биты 0, 8, 19, 25 и 30 во время дешифрования. Его выходные данные линейно комбинируются (XOR) с двумя битами состояния NLFSR (биты 0 и 16 при шифровании и биты 31 и 15 при дешифровании) и с ключевым битом (бит 0 состояния ключа при шифровании и бит 15 состояние ключа при расшифровке) и возвращается в состояние NLFSR в каждом раунде.

Версии

В этой статье описан протокол Classic KeeLoq, но разработаны и более новые версии. Совершенная система KeeLoq — это алгоритм на основе таймера, улучшающий классическую систему KeeLoq. Цель этой новой версии — содержать более надежный стандартный шифр AES-128 , который заменяет алгоритм шифрования KeeLoq, и иметь счетчик, управляемый таймером, который постоянно увеличивается, что является противоположностью классическому KeeLoq, где счетчик увеличивается в зависимости от кнопки. нажимать. Это обеспечивает защиту от атак методом перебора , а также атак захвата и воспроизведения , известных как RollJam в честь работы Сами Камкара .

Атаки

Повтор атаки

Для простоты отдельные реализации «прыжкового кода» обычно не используют криптографические одноразовые номера или временные метки . Это делает протокол по своей сути уязвимым для атак с повторным воспроизведением : например, заглушив канал во время перехвата кода, вор может получить код, который можно будет использовать на более позднем этапе. Что-то вроде «кодграббера». хотя теоретически он интересен, он, похоже, не широко используется угонщиками автомобилей.

Подробное описание недорогого прототипа устройства, разработанного и изготовленного Сами Камкаром для использования этой техники, появилось в 2015 году. Устройство размером с кошелек можно было спрятать на запертом автомобиле или рядом с ним, чтобы получить единый код доступа без ключа, который можно было использовать в позднее время, чтобы разблокировать автомобиль. Устройство передает сигнал глушения, чтобы заблокировать прием автомобилем сигналов подвижного кода с брелока владельца, одновременно записывая эти сигналы от обеих его двух попыток, необходимых для разблокировки автомобиля. Записанный первый код передается транспортному средству только тогда, когда владелец предпринимает вторую попытку, а записанный второй код сохраняется для использования в будущем. Была объявлена ​​демонстрация DEF CON 23.

Криптоанализ

Расшифровка KeeLoq

KeeLoq был впервые криптоанализирован Андреем Богдановым с использованием скользящих методов и эффективных линейных аппроксимаций . Николя Куртуа атаковал KeeLoq, используя скользящие и алгебраические методы. Атаки Богданова и Куртуа не представляют никакой угрозы для реальных реализаций, которые кажутся гораздо более уязвимыми для простого перебора ключевого пространства , которое сокращается во всех известных на сегодняшний день реализациях шифра с прыгающим кодом . Некоторые «кодограбберы» KeeLoq используют устройства на базе FPGA для взлома ключей KeeLoq методом грубой силы в течение примерно двух недель из-за уменьшенной длины ключа в реальных реализациях.

В 2007 году исследователи группы COSIC в университете Левена , Бельгия , (KULeuven) в сотрудничестве с коллегами из Израиля обнаружили новую атаку на систему. Используя детали алгоритма, которые стали известны в 2006 году, исследователи начали анализировать слабые места. После определения части ключа, общей для автомобилей конкретной модели, уникальные части ключа могут быть взломаны с помощью только прослушивания связи между ключом и автомобилем.

Микрочип представлен в 1996 году. версия микросхем KeeLoq, использующая 60-битное начальное число. Если используется 60-битное начальное число, злоумышленнику потребуется примерно 1011 дней обработки на выделенной параллельной машине для перебора, прежде чем система будет взломана.

Атаки по побочным каналам

В марте 2008 года исследователи с кафедры встроенной безопасности Рурского университета в Бохуме , Германия, представили полный прорыв в системах удаленного доступа без ключа, основанных на технологии KeeLoq RFID. Их атака работает на всех известных системах контроля доступа в автомобилях и зданиях, использующих шифр KeeLoq.

Атака команды Bochum позволяет восстановить секретные криптографические ключи, встроенные как в приемник, так и в пульт дистанционного управления. Он основан на измерении потребления электроэнергии устройством во время шифрования. Применяя так называемые методы анализа побочных каналов к следам мощности, исследователи могут извлечь из приемников ключ производителя, который можно рассматривать как главный ключ для генерации действительных ключей для пультов дистанционного управления одного конкретного производителя. В отличие от описанной выше криптоаналитической атаки, которая требует около 65536 выбранных пар открытого текста-шифротекста и дней вычислений на ПК для восстановления ключа, атака по побочному каналу также может быть применена к так называемому режиму работы KeeLoq Code Hopping (также известному как переключение кода). код ), который широко используется для систем бесключевого доступа (автомобили, гаражи, здания и т. д.).

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

Внешние ссылки

• Сайт микрочипа KeeLoq
• Введение в совершенную технологию KeeLoq
• Семейство кодировщиков HCSXXX – Информация о продукте
• Ultimate KeeLoq Technology, новое поколение безопасности — с двойным кодировщиком KeeLoq MCS3142
• «Спецификация алгоритма дешифрования KeeLoq» (PDF) . Архивировано (PDF) из оригинала 23 апреля 2007 г.
• Реализация C KeeLoq на GitHub
• Исходный код C от Ruptor
• Богданов, Андрей (31 августа – 5 сентября 2007 г.). Криптоанализ блочного шифра KeeLoq . Информационная безопасность и криптология: Третья конференция SKLOIS, Inscrypt 2007, переработанные избранные статьи. Синин, Китай. [1] .
• Н.Т. Куртуа и Г.В. Бард, «Алгебраические и скользящие атаки на KeeLoq»
• «Пресс-релиз Университета Бохума / HGI о полном отказе от систем входа на базе KeeLoq» (PDF) .
• Физический криптоанализ приложений KeeLoq с прыгающим кодом