Встраиваемая система безопасности на основе блочного алгоритма

Целью выпускной квалификационной работы является защита блочного алгоритма Keeloq путём изменения характеристик.
Задача заключается в изменении нелинейной функции алгоритма Keeloq, что позволит нам предотвратить взлом кода дистанционно-управляемых устройств алгебраическим и код-грабберами.
...

Введение 3
Глава 1 Описание шифров 6
Глава 2 Описание блочного шифра 9
Глава 3 Описание алгоритма программирования Keeloq 11
Алгоритм KeeLoq 11
Анализ стойкости 14
Микросхема HSC200 20
Глава 4 Описание приборов 24
Глава 5 Кодирование и тестовые измерения 25
Описание кодера и декодера 25
Запрограммированный алгоритм Keeloq и тесты 27
Глава 6 Программное обеспечение по модернизации Keeloq 30
Глава 7 Обход систем безопасности 34
Заключение 37
Список литературы 38
Глоссарий 39
Приложения 41

С ростом спроса на охранные системы автомобилей и упорядочивания частоты радиоканала производители сигнализаций перешли на динамическое кодирование. Данный вариант подразумевает то, что при каждом нажатии на кнопку брелока в эфир посылается уникальный код команды, вероятность повторения которого крайне мала. Теперь записанную в память граббера посылку можно было выкинуть, т.к. блок сигнализации с ней уже отработал и выкинул из списка правильных пакетов. Появился революционный метод кодирования под названием Keeloq. В середине 80-х этот алгоритм шифрования был разработан Джидеоном Куном в Nanoteq Pty Ltd, и продан Microchip Technology Inc в 1995 году. В настоящее время алгоритм Keeloq принят во всем мире и положен в основу тестовых критериев для систем безопасности в Великобритании, адаптир ован рядом европейских производителей и использован в собственных системах, разработанных "Форд" и "Ягуар".
Большинство автомобильных систем безопасности основаны на блочном алгоритме Keeloq. Keeloq используется в большинстве дистанционных систем управления замком, в таких компаниях как Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Jaguar

Технология KeeLoq на сегодняшний день представляет собой наиболее распространенную технологию для бытовых систем охраны, связанных с дистанционным открыванием/закрыванием дверей с беспроводной сигнализацией и с противоугонными средствами защиты в автомобилях.KeeLoq представляет собой набор недорогих микросхем, выпускаемых американской компанией Microchip Technology и реализующих очень популярную на сегодняшний день технологию динамически изменяющегося кода доступа (rolling code или hopping code).Набор микросхем Microchip универсально подходят для различных спаренных устройств в системах защищенного доступа. Но рассматривают её чаще на примере противоугонной системы автомобиля, где пара устройств, состоящая из кодера и декодера.Кодер представляет собой брелок-пульт дистанционного управленияи при каждом сеансе связи передает идентификационный номер динамически меняющегося кода и зашифрованное значение внутреннего счетчика. Декодер, находящийся в автомобиле расшифровывает сообщение, отправленное по радиоканалу пультом-кодером.В памяти декодера всегда находятся те же самые идентификационные номера и значения счетчика, что и в кодере, т.к. в начале эксплуатации два устройства были спарены процедурой синхронизации. Благодаря этой процедуре декодер конкретной машины ставит, либо снимает систему в режим охраны только по сигналу именно того брелока, с которым он был синхронизирован.В 2006 году схема KeeLoq стала общеизвестной информацией, поскольку произошла ее утечка в интернет. Фирменный документ Microchip с грифом «конфиденциально» и описанием устройства декодера был выложен на одном из российских хакерских сайтов. Там его нашел криптограф Андрей Богданов, в 2001-2005 гг. обучавшийся на факультете защиты информации Российского гуманитарного университета, а ныне являющийся сотрудником Рурского университета Бохума, Германия.Одной из специализаций лаборатории компьютерной безопасности, где работает Богданов, является система электронной защиты для автомобильной промышленности, поэтому он взялся за анализ KeeLoq. И довольно быстро нашел общие слабые места алгоритма, а затем, после изучения конкретных протоколов, реализующие KeeLoq в реальных приложениях, и потенциально очень серьезные дыры в стойкости системы.Свои открытия Богданов опубликовал в нескольких статьях, представленных на криптографических конференциях.В основе своей блочный шифр KeeLoq достаточно хорош и реально мог бы обеспечивать вполне приличный уровень защиты. Задаваемая криптосхемой длина секретного ключа в 64 бита делает нереалистичной атаку лобовым вскрытием, т.е. перебором всех возможных ключевых комбинаций.Но суть всякого криптоанализа схемы ― в нахождении способов взлома более быстрого, чем тотальный перебор ключей. И в этом отношении алгоритм KeeLoq оказался чрезвычайно уязвим.На том же российском хакерском сайте, откуда в мир утекла секретная криптосхема KeeLoq, еще с 2000-го года продается некое радиоэлектронное «изделие» по цене продвинутого сотового телефона. Суть работы этого изделия в том, что в радиусе примерно полусотни метров вокруг машины-жертвы оно ставит мощную радиопомеху в довольно широком диапазоне частот, а одновременно тонко настроено на прием той частоты, где передается текущий код доступа с пульта владельца автомобиля.Из-за глушения приемник-декодер охранной системы KeeLoq в машине не ловит слабый сигнал от пульта, но в тот же момент этот сигнал перехватывает «изделие». В итоге же законный владелец не может открыть собственную машину, а в изделие записывается текущий код доступа, позже позволяющий вскрыть машину.Краткая история в фактах: 1980-е. Согласно неофициальной истории автомобильных противоугонных средств, первую электронную систему такого рода ― под названием Pass Key I ― в промышленных масштабах начала устанавливать компания General Motors в своих машинах Corvette 1986 года выпуска. В основание ключа зажигания встраивался небольшой шарик, и когда такой ключ вставлялся в замок зажигания, бортовая электроника машины определяла электрическое сопротивление шарика и его соответствие ожидаемому значению.Для ключей имелось всего 15 разных, заранее заданных значений сопротивления, но и в таком виде система Pass Key произвела революцию в сфере автомобильной безопасности. Учитывая человеческий фактор, возможна потеря ключа. В General Motors пришлось частично раскрыть секрет устройства, что позволило дилерам и авторизованным слесарям держать болванки ключей с Pass Key. В начале 1990-х полиция арестовала первого угонщика, у которого была изъята связка ключей из всех 15 разных вариантов электронного ключа GM.К середине 1990-х рост черного рынка в Восточной Европе привел к гигантскому росту автомобильных угонов в Западной Европе. В 1995 году корпорация BMW начала первой применять более сложную противоугонную систему на основе RFID(Radio Frequency IDentification), чипов радиочастотной идентификации. Американские и японские автоконцерны быстро переняли новую технологию в своих наиболее дорогих моделях. Большинство новых систем на основе транспондеров-иммобилайзеров поначалу использовали фиксированный код доступа, уникальный и постоянный для конкретной машины.Когда ключ вставлялся в замок зажигания, передатчик в рулевой колонке опрашивал микрочип в пластмассовой ручке ключа. Радиочип отвечал особой комбинацией заданной длины. Если бортовой компьютер машины получал правильный код доступа, он включал систему зажигания и остальную электронику.Лишь наиболее дорогие машины вроде престижных моделей Mercedes и Lexus использовали существенно более сложный динамический код доступа, вновь генерируемый при каждом очередном запросе-ответе охранной системы.Как и Pass Key в предыдущем десятилетии, новая технология с RFID была эффективна на протяжении первых нескольких лет. Страховые компании абсолютно уверовали в ее абсолютную стойкость. Когда угонщики освоили принцип работы транспондеров-иммобилайзеров процент краж снова вырос. Страховщики несколько лет отказывались верить в слабости технологии, ссылаясь на нечестности самих автовладельцев.Для многих марок автомобилей, оборудованных противоугонной системой с RFID-иммобилайзером, существуют пути обхода. В 2005 году у журналиста Брэда Стоуна угнали новую машину Honda Civic, оборудованную заводской противоугонной электроникой, но через несколько дней брошенную машину нашли нетронутой. Стоун вскоре установил, что обход системы безопасности конкретно для Хонды ― это серия манипуляций с ключом и рычагом стояночного тормоза. Оказалось, что каждая машина имеет уникальный код для обхода защиты, который связан с VIN, идентификационным номером транспортного средства. В базе данных автокорпорации по VIN можно получить необходимую последовательность манипуляций с рычагом тормоза.Знающие автомеханики, имеют механический мастер-ключ, подходящий для разных замков зажигания, и владеют описанной технологией обхода электроники, что необходимо им для профессиональной деятельности. К сожалению, этими же навыками могут владеть и угонщики.[7]Микросхема HSC200Для необходимого нам исследования мы используем брелок, в основе которого лежит микросхема HCS200(Рис.6).Рис.6 Микросхема HCS200Приведём пример кодера KeeLoq с "прыгающим" кодом HCS200Секретность:•Программируемый 28-битных серийный номер•Программируемый 64-битный код ключа•Каждая передача имеет уникальный код•32-битный "прыгающий" код•28-битный серийный номер, 4-бита функций•Длина передаваемых данных 66 бит•Защита чтения кода ключаОсновные характеристики:•Напряжение питания от 3,5В до 13,0В•3 входа кнопок, 7 функций•Автоматическое завершение передачи слова•Передача приемнику сигнала о низком напряжении питания•Энергонезависимая синхронизация данных•Простой интерфейс программирования•Интегрированное EEPROM•Интегрированный тактовый генератор•Подтягивающие резисторы на входах кнопок•Минимальное количество внешних компонентовРис.7 Схема создание и хранение ключей кодирования в процессе производства микросхемыВсе системы дистанционного доступа, требующие синхронизации кодов приемника (кодера) и передатчика (декодера), имеют одно узкое место - часто возможна активация передатчика вне радиуса действия приемника. В этом случае синхронизация нарушается, так как все последующие принятые коды будут отличаться от ожидаемых декодером и устройство не сработает. Большинство подобных систем потребует специальной процедуры синхронизации, часто неудобной для пользователя. [9]Рис.8 Окно синхронизации в микросхеме HCS200У Keeloq эта проблема решена процесс восстановления синхронизации автоматический и незаметен для пользователя. Достигнуто это двумя мерами: Во-первых, декодер реагирует не только на первый ожидаемый код, но и на некоторое количество последующих кодов. Таким образом, если передатчик 14 раз сработал вне зоны действия приемника, то на 15 раз, оказавшись уже в зоне приема, он вызовет правильное срабатывание устройства. Действующие коды называются "окном валидности". При ширине окна 15 кодов и общем количестве возможных комбинаций более 4,5 миллиарда риск случайного несанкционированного доступа возрастает очень незначительно. Ширина "окна валидности" – величина, программируемая пользователем и выбираемая оптимальной для конкретного канала связи и требований к безопасности.Во-вторых, восстановление синхронизации в большем диапазоне кодов без потери секретности достигнуто следующим образом: декодер сравнивает два последовательных полученных кода, находящихся вне "окна валидности", с ожидаемыми, но в пределах большего окна "окна ресинхронизации", если оба совпадут, устройство сработает. На практике это может выглядеть так: владелец машины с помощью радио-брелока безуспешно пытается снять ее с сигнализации на большом расстоянии или из-за преграды, когда же очередная посылка оказывается принятой декодером, то она не вызывает его срабатывания из-за рассинхронизации. В таком случае уже следующая попытка владельца приводит к успеху, так как два последовательных кода оказались правильными. Восстановление синхронизации Keeloq требует только одной дополнительной попытки.Рис.9 Организация кодовой комбинации в кодере HCS200При каждой инициализации кодера (нажатие на кнопку пульта дистанционного управления) формируется кодовая последовательность, в которую входит 32-битный «прыгающий код» полученный из 64-битного секретного ключа. «Прыгающий код» уникален для каждой новой кодовой последовательности. Счетчик в KeeLoq кодерах использует 66-битный формат передачи данных.32 бита – «прыгающего кода»28 бит – серийный номер4 бита – функциональный код (нажатие кнопок)1 бит – флаг разряда батареи питания 1 бит – флаг повторенияГлава 4 Описание приборовВо время проведения исследований были использованы следующие технические средства: Код-граббер – это специальный электронный прибор, так же именуемый изделием 502 (или изделие 409), который настроен на рабочую частоту передатчика и способен подслушивать кодовую информацию, записывать ее и посылать в эфир. При этом он отключает противоугонную систему. (Приложение 1)Программатор, работающий совместно с программой для записи секретных ключей и других характеристик в брелок. Именно при его помощи нам удалось записать информацию в микросхему кодера, которая составляет фиксированную часть посылки. (Приложение 2)Частотомер для настройки несущей частоты разрешенного для данных устройств диапазона (Приложение 3)Глава 5 Кодирование и тестовые измеренияОписание кодера и декодера Рис.10 Кодер Формирователи «прыгающего» кода KeeLoq предназначены для однонаправленных систем дистанционного управления. В функции кодера входит только формирование кодовой посылки, разработчику системы дистанционного управления необходимо заботиться об организации канала связи. Инициализация кодера, на передачу кода, происходит по нажатию на кнопку пульта дистанционного управления. Для радиомаяка, на основе технологии KeeLoq, инициализация передачи кода может происходить и под воздействием внешнего электромагнитного поля.В технологии KeeLoq используется система реверсивной идентификации по принципу «свой - чужой». На основе серийного номера передатчика и заводского ключа приемника формируется 64-битный секретный ключ, по специальному алгоритму, записываемый в кодер на этапе его программирования. Секретный ключ не может быть считан из кодера, и он никогда не передается по каналу связи.Рис.11 ДекодерДекодеры KeeLoq предназначены для дешифрации команд поступающие от кодера по каналу связи. После проверки принятого в кодовой последовательности серийного номера и «прыгающего кода», декодер на основании функционального кода активизирует выходы, соответствующие входам кнопок в кодере. Выходы будут удерживаться в активном состоянии до тех пор, пока нажата кнопка на кодере. Время удерживания выходов в активном состоянии после последней принятой кодовой последовательности составляет 500 мс.Для исполнения команд декодером, ему необходимо указать 28/32-битный серийный номер и 64-битный секретный ключ кодера. Также одним из условий выполнения команд декодером, является его синхронизация с кодером.Технология KeeLoq позволяет использовать один секретный ключ для нескольких кодеров, работающих с данным декодером. Одноключевая система менее безопасна, но уменьшается сложность программы и объем необходимой памяти. В одноключевой системе поддерживается синхронизация с каждым из кодеров, вне зависимости от частоты использования.В декодерах KeeLoq используется независимая ключевая система. Для каждого из передатчиков хранится свой серийный номер, секретный ключ и текущая синхронизация.[8]Запрограммированный алгоритм Keeloq и тестыДалее была запрограммирован алгоритм Keeloq на языке программирования высокого уровня. Для этого был выбран C++.В этой программе мы просто проверяем работу функций шифрования и дешифрования для алгоритма KeeLoq. Задаём константу NLF – заранее определённый вектор из 32 битов, который будет затем использоваться в процессе шифрования и дешифрования. Мы обозначим вектор NLF в виде 4-байтового беззнакового целого числа KeeLoq_NLF.Далее мы вводим функцию bit(x, n), которая возвращает бит из двоичной записи числа x, расположенный на позиции под номером n. При этом мы будем предполагать, что младший бит стоит на позиции под номером 0. Для простоты мы зададим функцию bit в виде макроса. Вводим функцию g5(x, a, b, c, d, e). Она формирует новое число на основе битов числа x по следующему принципу: биты, стоящие в числе x на позициях под номером a, b, c, d и e, ставятся соответственно на нулевую, первую, вторую, третью и четвёртую позицию. Биты, начиная с шестой позиции, заполняются нулями. Функцию g5 мы тоже зададим в виде макроса.В продолжении программы мы определяем функцию шифрования под названием KeeLoq_Encrypt. У неё два аргумента: 32-битное беззнаковое целое число data, которое мы будем рассматривать в качестве открытого текста, и 64-битное беззнаковое целое число key – ключ. На выходе функция KeeLoq_Encrypt возвращает беззнаковое целое число, представляющее собой шифртекст. Функция KeeLoq_Encrypt реализует алгоритм шифрования KeeLoq, описанный в главе 3. Внутри функции KeeLoq_Encrypt запускается цикл на 528 повторений, на каждой итерации которого происходит перемешивание и гаммирование битов числа x по соответствующему алгоритму. По окончании работы цикла образуется конечный шифртекст.Определяем функцию дешифрования под названием KeeLoq_Decrypt. У неё два аргумента: 32-битное беззнаковое целое число data, которое мы будем рассматривать в качестве шифртекста, и 64-битное беззнаковое целое число key – ключ. На выходе функция KeeLoq_Decrypt возвращает беззнаковое целое число, представляющее собой шифртекст. Функция KeeLoq_Decrypt реализует преобразование, обратное по отношению к шифрованию, и в итоге расшифровывает текст, получая на выходе открытый текст.После вышеперечисленного начинается основная программа. В ней мы выбираем некоторый открытый текст и ключ (в данном случае в качестве открытого текста мы берём число 1283, а в качестве ключа – число 55395739), производим шифрование и дешифрование, распечатываем результаты на консоль и оцениваем их. (Приложение 4)Также проведя серию тестов используя устройство граббер или изделие 409 (Приложение 1), мы получили следующие результаты:46FD04A2 (1)39379369 (2)9F747B6E (3)0681B323 (4)60055FA9 (5)D389F6FF (6)0BA3FD79 (7)CA009EBA (8)CE2E012E (9)BE056E68 (10)28C79E53 (11)C169634A (12)A0D1678A (13)7EB04F1F (14)1A86CE55 (15)0D45B664 (16)Эти самые результаты получены используя мануфактурный код из всех нулей, запрограммированный с помощью программатора PICPROG (Приложение 2). А так как по характеристикам рабочая частота код-граббера составляет 433,92 МГц., то и брелок должен соответствовать, а проверили мы это при помощи частотомера (Приложение 3).Глава 6 Программное обеспечение по модернизации Keeloq Проведя анализ распределения, используя программу на языке программирования C++ для получения таблицы на 65536 посылок с результатами распределения.В ходе анализа мы поставили цель выяснить, каково соотношение нулей и единиц в шифртекстах, которые получаются в результате действия алгоритма KeeLoq на некоторые сообщения открытого текста по определённому ключу. Для исследования мы решили взять 65536 открытых сообщений, которые в двоичной записи соответствуют числам от 0 до 65535, зашифровать каждое из них по отдельности алгоритмом KeeLoq и посчитать количество нулей и единиц в каждом из полученных 65536 шифртекстов. В качестве ключа шифрования мы выбрали 0x1234567890ABCDEF. Для сбора данных и обработки результатов мы написали компьютерную программу на языке C, код которой приведён в приложении 5. Эта программа перебирает целые числа от 0 до 65535 и, интерпретируя каждое из них как открытый текст, шифрует по ключу 0x1234567890ABCDEF. Каждый полученный шифртекст представляется затем в двоичной форме, и в нём считается число нулевых и единичных битов. Открытый текст и соответствующий ему шифртекст, а также количество нулей и единиц в этом шифртексте записываются в текстовый файл. Кроме того, количество нулей и единиц по каждому шифртексту записывается также в ещё один текстовый файл. Этот файл мы затем открыли в программе Microsoft Excel и построили на основе содержащихся в нём данных диаграмму распределения нулей и единиц в рассмотренных шифртекстах. Эта диаграмма изображена на рис. 12.В начале программы мы задаём те же самые функции, макросы и константы для шифрования и дешифрования, что и в описанной ранее программе.В основной части программы мы шифруем 65536 открытых текстов (представляющих собой целые числа от 0 до 65535), каждый полученный шифртекст представляем в двоичной форме и в таком виде записываем его в текстовый файл. Также мы считаем количество нулей и единиц в каждом шифртексте и записываем эти показатели в другой текстовый файл.Начинается программа с того, что мы вводим три массива, в которые будем затем записывать текстовые символы, работая со строками. Затем мы создаём два файла (f и g), привязываем их к конкретным файлам в файловой системе (в нашем случае мы связываем файл f с файлом C:\Plaintext and Ciphertext.txt, а файл g – с файлом C:\Zeroes and Ones.txt) и открываем эти файлы на запись. В файл f мы будем записывать шифртексты, переведённые в двоичную форму, а в файл g – количество нулей и единиц в этих шифртекстах.В первую строчку файла f мы записываем строку из трёх слов ("Plaintext", "Key", "Ciphertext") – это будет своего рода шапка таблицы.Задаём ключ key для шифрования и дешифрования. В нашем случае это 0x1234567890ABCDEF. Далее преобразуем число key в двоичную форму (получая на выходе набор текстовых символов '0' и '1') и записываем результат в строку keyStr.