Автосигнализации Top Guard, GSM приставка к домофону, GPS мониторинг и охрана транспорта

Звоните сейчас: (067)  401 84 24
                       (044) 209 69 46
г. Киев, П-КТ. ОСВОБОДИТЕЛЕЙ, 1

KeeLoq описание

Краткое описание технологии кодирования KeeLoq

KeeLoq является блочным кодом с 64-разрядным ключом и размером блока 32 бита.

kelodescr pic1

Как видно из рис. 1, блок-схема кодирования состоит из регистра сдвига данных, формирователя нелинейной функции NLF, аргументами которой являются 5 бит регистра данных, логического элемента XOR (исключающее ИЛИ) и регистра сдвига ключа кодирования. Нелинейная обратная связь для регистра данных формируется из бита выхода NLF, двух бит данных и бита ключа кодирования.

Перед началом кодирования исходные данные (исходный текст) и ключ помещаются в соответствующие им регистры. В каждом цикле кодирования содержимое регистра ключа и содержимое регистра данных сдвигаются каждый в своем регистре на один бит вправо так, что новое значение функции XOR попадает на вход регистра данных. После выполнения 528-ти таких циклов кодирования, в регистре данных получается нужный код (шифрованный текст).

Процесс декодирования полностью аналогичен кодированию, за исключением направления сдвига и отводов регистра данных для функций NLF и XOR.

Нелинейная функция введена в алгоритм для устранения линейной связи между исходными и шифрованными текстами. В противном случае этот алгоритм кодирования действительно был бы совсем прост для "взлома". Как известно из школьной алгебры, функции второго (квадратный многочлен) и третьего порядка имеют в общем случае соответственно два и три корня (решения). Здесь используется NLF 32-го порядка и для каждой комбинации 5-ти аргументов эта функция имеет 32 корня.

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

Стандартный формат KeeLoq кода имеет следующий вид (ри.2).

kelodescr pic2

Открыто передаются:

  •  28 бит Серийного Номера передатчика, который должен быть уникальным для каждого выпускаемого производителем передатчика. Этот номер является первичной информацией для распознавания передатчика в приемнике устройства дистанционного управления. Как правило, этот номер используется при формировании ключа кодирования для данного передатчика. Кроме того, в более секретных устройствах управления этот номер может передаваться в закодированном виде (Envelope Code) для исключения возможности применения различных код-грабберов.
  •  4 бита кода команды.
  •  2 бита состояния источника питания передатчика и признака повтора посылки.

kelodescr pic3

Собственно алгоритм KeeLoq используется для кодирования следующих 32 бит данных:

  •  16 бит счетчика синхронизации передаваемых посылок, обеспечивающих правильную работу декодера на приемной стороне.
  •  4 бита команды.
  •  12 бит значения дискриминанта – секретного слова, которое может задаваться для каждой группы устройств, выпускаемых производителем.

Исходные значения всех этих бит помещаются в регистр данных кодера в начале процесса кодирования и через 528 циклов в этом регистре получается набор бит шифра, передаваемго в изменяемой части стандартной посылки. Свойства алгоритма KeeLoq обеспечивают изменение как минимум половины бит этого набора при изменении только одного любого бита исходного набора. Это и обеспечивает неповторимость этой части посылки, препятствующей простому копированию кода из эфира для дальнейшего несанкционированного доступа к охраняемому объекту.

Использование KeeLoq в системах идентификации Свой-Чужой

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

В автомобилях Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, VW, Jaguar в качестве такого алгоритма используется KeeLoq. При этом иммобилайзер формирует 32-разрядные запросы случайным (квазислучайным) образом и оба устройства – иммобилайзер и транспондер используют одинаковые ключи кодирования.

Использование KeeLoq в дистанционном управлении

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

Передатчик передает сформированные кодером посылки, изображенные на рис. 2. Приемник принимает такую посылку и сравнивает полученный Серийный Номер с зарегистрированными в его "памяти" Номерами передатчиков (практически не ограниченное количество). Если сигнал поступает от "своего" передатчика, декодер, используя соответствующий этому номеру Индивидуальный Ключ, декодирует зашифрованные 32 бита посылки и проверяет совпадение Счетчика Синхронизации и Дискриминанта. Если все совпадает, - выполнят принятую команду.

Сравнение Счетчика Синхронизации происходит по правилу, исключающему выполнение переданных раннее команд. При этом, если принятое значение Счетчика больше имеющегося в приемнике на 16 (в "рабочем окне"), то команда выполняется сразу. Если принятое значение счетчика лежит в диапазоне 16< Сч < 215 (в "окне ресинхронизации"), приемник запомнит это значение и выполнит команду, если она будет сразу повторена со значением Счетчика не превышающем запомненную величину на 16. Все команды с полученным значением Счетчика более 215 и менее хранящегося в приемнике игнорируются. Значение Счетчика Синхронизации выполненной команды запоминается, как текущее.

Схемы формирования и использования Ключей

В KeeLoq технологии используется два типа ключей:

  • Ключ Производителя (Мастер Код) – 64-разрядное слово, уникальное для каждого производителя и используемое для формирования Индивидуальных Ключей для каждого устройства этого производителя.
  • Индивидуальный Ключ устройства – 64-разрядное слово уникальное для каждого устройства кодирования, формируемое по определенному алгоритму с использованием Ключа Производителя. Этот ключ одинаков для кодирования и декодирования информации.

Ключ Производителя представляет главный секрет системы кодирования и является основной целью любой атаки или "взлома" KeeLoq вопреки расхожим домыслам о "взломе" кода KeeLoq, алгоритмы которого, а так же тексты их программной реализации широко известны. В явном виде этот ключ используется в технологическом оборудовании, на котором выполняется программирование стандартных микросхем кодеров, и в микропроцессорах конкретных устройств, выполняющих программную генерацию Индивидуальных Ключей для декодирования сообщений от конкретных кодеров.

Индивидуальный Ключ стандартных микросхем кодеров формируется в технологических программаторах во время производства конкретных устройств и хранится в EEPROM кодера. Ключ Производителя в памяти кодеров не хранится. В декодере Индивидуальные Ключи каждого передатчика формируются при его регистрации с использованием его же индивидуальных данных, например, Серийного Номера, и хранятся эти ключи в EEPROM декодера. Так как в формировании Индивидуальных Ключей устройств должен использоваться Ключ Производителя, то он всегда хранится в ROM памяти декодера.

Процедуры формирования Индивидуальных Ключей кодирования составляют главный секрет технологии KeeLoq. Некоторые процедуры защищены даже патентами и не могут быть использованы бесплатно другими производителями. Стандартные процедуры описаны в руководствах по применению микросхем компании Мicrochip, что послужило успешному "взлому" ключей некоторых производителей, использующих самые простые из них.

В общем, описание стандартных процедур формирования Индивидуальных Ключей выглядит следующим образом.

kelodescr pic4

На рис. 4 представлены две декларируемые в официальных документах Микрочип и в статьях по их "взлому" схемы формирования Индивидуальных Ключей кодирования. На самом деле две представленные схемы демонстрируют 4 процедуры формирования Ключа.

Первая разновидность процедуры называется "Обычной" (Normal). Её смысл заключается в использовании 28-разрядного Серийного Номера конкретного устройства в качестве исходного текста для получения уникального для этого устройства Индивидуального Ключа. При этом функции F1 и F2 тем или иным способом преобразуют Серийный Номер в 32-разрядное исходное слово, а в качестве кодирующих алгоритмов могут использоваться либо сложный нелинейный алгоритм декодирования KeeLoq, либо простая логическая функция исключающего ИЛИ (XOR).

Вторая разновидность процедуры называется "Защищенной" (Secure). Её смысл заключается в использовании для формирования Индивидуального Ключа не открыто передаваемого Серийного Номера, а индивидуального для каждого кодера, так называемого "Зерна". Зерно может иметь длину (в зависимости от модели стандартной микросхемы HCS-кодера) 32, 48 или 60 бит и генерируется как случайное число при технологическом программировании микросхемы. Это Зерно хранится в EEPROM кодера. На рис. 5, 6, 7 представлены различные варианты формирования Индивидуального Ключа с использованием Зерна.

kelodescr pic5

kelodescr pic7

Эта процедура обеспечивает достаточно мощную защиту от различных атак на KeeLoq, однако она практически н еиспользуется в коммерческих устройствах, т.к. требует достаточно много программных ресурсов. Наиболее часто используется следующая процедура.

Третья разновидность процедуры называется "Простой" (Simple). Эта процедура редко упоминается в официальной документации Микрочип и в работах по "взлому" Ключей. Однако эта процедура имеется в технологических программаторах стандартных микросхем KeeLoq кодеров и Мicrochip предлагает пример исходного текста программной реализации соответствующего декодера. Смысл этой процедуры заключается в самой дешевой реализации программного декодера, код которого занимает всего 250 байт в программой памяти процессора, предоставляя большую часть этой памяти для реализации потребительских функций, например, в сигнализации. Достигается это тем, что во всех изделиях производителя просто используются одинаковые Индивидуальные Ключи и, как правило, им является Ключ Производителя. С коммерческой точки зрения это очень выгодно – по всем внешним признакам KeeLoq, а на самом деле "кукла".

Непосредственно в соответствие используемым процедурами формирования Индивидуальных Ключей применяются и процедуры регистрации передатчиков дистанционного управления (кодеров) в приемных устройствах (декодерах). В оригинальной литературе Мicrochip этот процесс называется "обучение" приемников передатчикам.

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

При использовании Защищенной процедуры, приемное устройство переводится в режим регистрации передатчиков, а регистрируемый передатчик переводится в режим генерации его уникального Зерна, например, нажатием одновременно 4-х кнопок передачи команд. Зерно передается вместо изменяемой части посылки, а приемник принимает его вместе с Серийным Номером, формирует по заданному алгоритму Индивидуальный Ключ данного передатчика и записывает его в соответствующий данному передатчику фрагмент памяти. Вслед за передачей Зерна на передатчике нажимается кнопка передачи любой команды и приемник записывает в тот же фрагмент памяти значения Счетчика Синхронизации и Дискриминанта для дальнейшего декодирования сообщений данного передатчика.

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

В приведенном описании преднамеренно акцентируется внимание на широком применении стандартных микросхем кодеров серии HCS и широко известных примеров программного обеспечения для реализации декодеров на микропроцессорах фирмы Мicrochip. Применение этих стандартных и широко известных средств вызвало штормовую волну разнообразных и небезуспешных атак на применяемую практически во всем мире в промышленных масштабах технологию кодирования KeeLoq. Однако, даже из этого краткого описания очевидно, что в этой технологии возможно применение множества средств, обеспечивающих надежную защиту от любых атак.

Home Статьи KeeLoq описание

 Украина, г. Киев,

        пр-кт. Освободителей, 1

  (067) 401 84 24

  (044) 209 69 46

  (067) 566 34 33

  Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

  www.dedal.com.ua