Ключи, замки, отмычки

(Впервые опубликовано – ноябрь 2007)

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

Но сколь бы разнообразными ни казались марки автомобилей и защищающих их электронных систем безопасности, в основе своей практически все схемы защиты сводятся к двум базовым технологиям ― KeeLoq фирмы Microchip и DST от Texas Instruments.

Поэтому анализ стойкости лишь двух этих систем дает вполне объективное представление о реальной надежности нынешних противоугонных средств на основе микрокомпьютера и беспроводной связи.

carkeys

КлючеЗамок: теория

Технология KeeLoq (близкий по смыслу перевод этой лингвоконструкции использован в подзаголовке) на сегодняшний день представляет собой наиболее распространенное в индустрии решение для бытовых систем охраны, связанных с дистанционным открыванием / закрыванием дверей (в гаражах, к примеру), с радиосигнализацией и ― самое главное ― с противоугонными средствами защиты в автомобилях.

В своем материальном виде KeeLoq выглядит как набор недорогих микросхем, выпускаемых американской компанией Microchip Technology и реализующих очень популярную на сегодня технологию динамически изменяющегося кода доступа (rolling code или, эквивалентно, hopping code).

По свидетельству специалистов, именно эти микросхемы встраиваются ныне в охранную электронику автомобилей на конвейерах известнейших автопредприятий вроде Chrysler, Daewoo, Fiat, General Motors, Honda, Jaguar, Toyota, Volkswagen, Volvo и так далее. Кроме того, имеются свидетельства, что эти же микросхемы используют в своих противоугонных системах Clifford, Shurlok и прочие компании, специализирующиеся на технологиях безопасности.

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

Кодер выполнен в виде пульта-брелка дистанционного управления и при каждом сеансе связи (установка/снятие машины с охраны нажатием кнопки) передает идентификационный номер (ID#) динамически меняющегося кода и зашифрованное значение внутреннего счетчика. Декодер находится в автомобиле и расшифровывает сообщение, отправленное по радиоканалу пультом-кодером.

В памяти декодера всегда находятся те же самые ID-номера и значения счетчика, что и в кодере, поскольку в самом начале эксплуатации два устройства были спарены специальной процедурой синхронизации, именуемой «обучением». Благодаря этой процедуре декодер всякой конкретной машины ставит / снимает систему в режим охраны только по сигналу того пульта-кодера, с которым он был спарен.

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

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

Фирменный документ Microchip с грифом «конфиденциально» и описанием устройства декодера был выложен на одном из российских хакерских сайтов. Там его нашел молодой и даровитый криптограф Андрей Богданов, в 2001-2005 гг. обучавшийся на факультете защиты информации Российского гуманитарного университета, а ныне являющийся сотрудником Рурского университета Бохума, Германия.

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

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

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

Эту работу проделала довольно большая объединенная команда исследователей из университетов г. Лувена (Бельгия) и Technion (Израиль). Среди участников, в частности, можно назвать таких ученых как бельгиец Барт Пренэль, возглавляющий COSIC (лабораторию компьютерной безопасности Лувенского университета, где учились и работали создатели AES, нынешнего мирового криптостандарта), и израильтянин Эли Бихам (соавтор метода дифференциального криптоанализа, являющегося важнейшим методом вскрытия блочных шифров).

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

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

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

У разных компаний длина постоянного участка может отличаться. Но в целом, по сути дела, криптографами был найден способ для отыскания и накопления постоянных мастер-ключей, подходящих ко всем автомобилям и сигнализациям известных марок. Имея комплект таких ключей, подобрать комбинацию доступа к конкретному автомобилю ― дело нескольких секунд…

После оглашения этих результатов на конференции, компания Microchip Technology какое-то время отмалчивалась (хотя исследователи известили ее о своих успехах вскрытия заблаговременно), но затем все же выпустила по данному поводу пресс-релиз. Текст его очень лаконичен и выглядит так:

«После тщательного изучения заявлений, сделанных криптографами, компания пришла к выводу, что система KeeLoq, в ее рекомендованных для реального мира реализациях, является безопасной. Microchip признает успех высоко талантливых исследователей в их теоретической атаке на блочный шифр. Однако реальная система KeeLoq включает в себя намного больше, чем просто криптографический алгоритм. Заявления исследователей, будто машину можно угнать на основе сделанных ими открытий, являются ошибочными вследствие нескольких неверных допущений».

В чем суть «неверных допущений», компания разъяснять не пожелала, поскольку «не считает, что публичные дебаты о том, как воровать автомобили, идут на пользу потребителям».

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

Транспондер Цифровой Подписи

Два года тому назад другая ― американская ― группа криптографов из университета Джонса-Хопкинса и центра RSA Labs опубликовала заметную работу об успешном взломе еще одной базовой технологии для электронной защиты автомобилей под названием DST или Digital Signature Transponder.

Чипы радиочастотной идентификации DST, изготовляемые компанией Texas Instruments, в виде электронных ключей Vehicle Immobilizer (и их предшественников попроще) входят в комплект порядка 200 миллионов автомобилей, проданных за последние годы на мировом рынке такими фирмами как Ford, Nissan, Toyota и другие.

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

Физически DST обычно представляет собой микрочип и катушку антенны, запаянные в маленькую капсулу из пластика или стекла. Внутри чипа DST хранится секретный криптографический ключ длиной 40 бит (в компьютерном мире такая длина ключа, напомним, считалась безнадежно слабой еще в начале 1990-х годов). При взаимодействии с ридером машины DST сначала излучает зашитый в него при изготовлении 24-битный идентификатор, а затем подтверждает себя в процессе протокола аутентификации, построенного по принципу «оклик-отзыв» (challenge-response).

Суть его вкратце такова. Считыватель инициирует протокол, посылая случайную последовательность-«оклик» размером 40 бит. DST шифрует своим ключом эту последовательность, сокращает длину полученного результата и выдает в эфир ответ длиной 24 бита. Таким образом, вся стойкость данного устройства к попыткам взлома, клонирования или аппаратно-программных симуляций сводится к секретному ключу и тайне применяемого алгоритма шифрования.

Такие подробности, впрочем, стали известны лишь после того, как молодые ученые-криптографы (аспиранты университета и их консультанты из RSA Labs) решили испытать реальную прочность защиты, обеспечиваемой секретным и предположительно стойким к взлому чипом DST. Хотя исследователи не обладали особыми навыками хакеров-взломщиков, имевшихся у них знаний криптографии и компьютерной техники, в сочетании с тремя месяцами напряженной работы, оказалось вполне достаточно, чтобы полностью вскрыть неизвестную схему и продемонстрировать на практике технику для ее обхода.

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

Примененный в исследовании арсенал действительно впечатляет: конструирование радиочастотного приемопередатчика для опросов чипа и математический криптоанализ для вскрытия схемы «черного ящика» по входу-выходу; поиск дополнительной информации в Сети и изготовление специализированного программно-аппаратного комплекса для перебора ключей; теоретические расчеты для отыскания оптимального соотношения «время перебора / объем памяти вычислителя» и сугубо практические испытания устройства-«отмычки» ― при запуске нового «Форда» электронным симулятором ключа.

Короче говоря, группа аспирантов сумела более чем убедительно продемонстрировать реальную серьезность угрозы и явно недостаточную защиту DST. Фирма Texas Instruments, правда, прореагировала на взлом очень спокойно, назвав атаку «чересчур мудреной» и куда менее реалистичной, чем хорошо известные кражи машин с помощью их погрузки на платформу тягача.

Никаких известий об усилении криптографии в системах DST пресса с тех пор не публиковала.

КлючеЗамок: практика

Возвращаясь к системе KeeLoq, можно отметить, что вскрывшие ее криптографы не пошли по стопам своих американских коллег, и не стали, похоже, доводить дело до «полевых испытаний» на реальных машинах. Разумно решив, что с неадекватным уровнем защиты здесь, в общем-то, все и так уже ясно.

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

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

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

Разумеется, эта слабость давно и хорошо известна изготовителю. Но предполагается неизвестной для массовых пользователей и рядовых злоумышленников. Почему, вероятно, и не исправляется. Как не усиливается и очевидно слабая криптография в KeeLoq и DST, по уровню своей стойкости соответствующая бытовым компьютерным программам примерно 1980-х годов.

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

The End

[ВРЕЗКИ]

* * *

Краткая история в фактах: 1980-е

Согласно неофициальной истории автомобильных противоугонных средств, первую электронную систему такого рода ― под названием Pass Key I ― в промышленных масштабах начала устанавливать компания General Motors в своих машинах Corvette 1986 года выпуска. Устройство системы было довольно примитивным ― в основание ключа зажигания встраивался небольшой шарик, и когда такой ключ вставлялся в замок зажигания, бортовая электроника машины определяла электрическое сопротивление шарика и его соответствие ожидаемому значению.

Для ключей имелось всего 15 разных, заранее заданных значений сопротивления, но и в таком виде система Pass Key произвела революцию в сфере автомобильной безопасности. Ибо впервые стало так, что принципиально важный элемент электронной противоугонной системы стал находиться вне автомобиля. Эйфория, правда, длилась совсем недолго.

Поскольку люди имеют тенденцию терять ключи, потоком пошли жалобы на слишком большие сложности с получением новых ключей взамен утерянных. В General Motors пришлось частично раскрыть секрет устройства, позволив дилерам и авторизованным слесарям держать болванки ключей с Pass Key. Уже в начале 1990-х полиция арестовала первого угонщика, у которого была изъята связка ключей, где имелись все 15 разных вариантов электронного ключа GM.

* * *

Краткая история в фактах: 1990-е

К середине 1990-х стремительный рост черного рынка в Восточной Европе привел к гигантскому росту автоугонов в Европе Западной. Германские страховые компании сильно надавили на автопроизводителей по поводу заводского усиления защиты машин, и в 1995 году корпорация BMW начала первой применять существенно более сложную противоугонную систему на основе RFID, чипов радиочастотной идентификации.

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

Когда ключ вставлялся в замок зажигания, передатчик в рулевой колонке опрашивал микрочип в пластмассовой ручке ключа. Радиочип отвечал особой комбинацией заданной длины. Если бортовой компьютер машины получал правильный код доступа, он включал систему зажигания и всю остальную электронику.

Лишь наиболее дорогие машины вроде престижных моделей Mercedes и Lexus использовали существенно более сложный динамический код доступа, вновь генерируемый при каждом очередном запросе-ответе охранной системы.

Как и Pass Key в предыдущем десятилетии, новая технология с RFID была чрезвычайно эффективна в защите от угонов ― на протяжении первых нескольких лет. Например, угоны машин Ford Mustang, одной из первых в США моделей, массово оборудованных транспондерами в 1997 году, упали более чем на 70% по сравнению с 1995 годом (оставшуюся долю отнесли к украденным ключам).

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

* * *

Краткая история в фактах: 2000-е

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

Американский журналист Брэд Стоун, когда у него в 2005 году угнали от дома собственную новую машину Honda Civic, оборудованную заводской противоугонной электроникой, поначалу был уверен в какой-то изощренной хайтек-краже. Но через несколько дней брошенную машину нашли на одном из городских пляжей, всю прокуренную и набитую окурками, но в остальном нетронутую. Иначе говоря, Хонду явно угоняла какая-то шпана просто покататься.

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

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

Для эксперимента Стоун обернул алюминиевой фольгой ручку ключа с RFID-чипом, чтобы заблокировать работу транспондера. Ключ по-прежнему входил в замок зажигания, естественно, но запустить мотор уже не мог. Тогда Стоун, руководствуясь инструкцией из секретной базы, стал выполнять нетривиальную последовательность сдвигов ручки тормоза, перемежающихся поворотами ключа зажигания между положениями «On» и «Start».

Со второй попытки машина действительно завелась ― что и требовалось доказать.

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

* * *

 [КОНЕЦ ВРЕЗОК]