KeeLoq и дежавю

Автор: Киви Берд
Опубликовано в журнале "Компьютерра" №32 от 05 сентября 2007 года

В последнюю декаду августа калифорнийский городок Санта-Барбара по традиции принимал в стенах своего университета элиту мировой криптографической науки, съехавшуюся на ежегодную, 27-ю по счету конференцию Crypto 2007. Средства массовой информации, включая и компьютерные издания, обычно освещают этот форум скупо, в отличие, скажем, от куда более пестрой, многолюдной и похожей на богатое шоу RSA Conference или колоритных хакерских съездов Black Hat/DefCon в Лас-Вегасе. Равнодушие журналистов к конференциям Crypto, в общем-то, объяснимо, ведь туда съезжаются все больше математики, никаких демонстраций для их работ в программе мероприятия обычно не предусмотрено, а доклады редко тянут на сенсацию. Но даже если сенсации и случаются - как на сей раз, - то пресса все равно об этом пишет редко. Кроме разве что "Компьютерры".

Революционная это работа или нет, каждый читатель (и особенно автомобилист) пусть решает сам, но группа криптографов из Бельгии и Израиля сделала на Crypto 2007 доклад о серьезной слабости, обнаруженной в противоугонных и охранных электронных системах на основе технологии KeeLoq с динамически изменяющимся кодом (hopping code). Как свидетельствуют специалисты, подавляющее большинство систем радиосигнализации и дистанционного открывания/закрывания дверей работают на микросхемах Microchip Technology, реализующих алгоритм KeeLoq. Это касается как самых известных автономных охранных систем от "Пантеры" и "Аллигатора" до "Клиффорда", так и сигнализаций, встраиваемых при сборке в автомобили Chrysler, Daewoo, Fiat, General Motors, Honda, Jaguar, Toyota, Volvo, Volkswagen и др. Проведенный же бельгийско-израильской командой криптоанализ системы KeeLoq показал, что при сравнительно скромных затратах времени и вычислительных ресурсов (два дня работы компьютеров общей ценой около 10 тысяч евро) злоумышленники могут вскрыть сначала секретный ключ какой-либо конкретной машины, а на его основе - но теперь уже за доли секунды - цифровой ключ любого другого автомобиля этой же компании.

Сам по себе блочный шифр KeeLoq вовсе не плох и мог бы обеспечивать уровень защиты, "примерно эквивалентный алгоритму DES". Задаваемая криптосхемой длина секретного ключа в 64 бита делает нереалистичной атаку лобовым вскрытием, то есть перебором всех возможных ключевых комбинаций. Что же касается более быстрых криптоаналитических техник взлома, то они к KeeLoq долгое время не применялись, поскольку владелец криптосхемы никогда открыто ее не публиковал. Алгоритм и технологию генерации динамического кода разработал южноафриканский криптограф Виллем Смит (Willem Smit) в 1980-е годы, а в середине 1990-х их купила фирма Microchip за десять с лишним миллионов долларов. Кем и когда была допущена утечка криптосхемы в Интернет, вряд ли узнаешь (в Википедии, например, информация появилась в 2006-м), но точно известно, что произошло это через один из российских хакерских сайтов. Судя по материалам этого сайта, наши умельцы легко преодолевали защиту KeeLoq еще в 2000 году, причем не взламывая криптографию, а лишь подавляя радиосеанс связи законного владельца с машиной и одновременно записывая генеририруемые устройством комбинации доступа. Хотя при динамической генерации кода комбинация каждый раз вырабатывается новая, в схеме есть техническая слабость, позволяющая жуликам обманывать автоматику, прибегая к трюку с глушением. Но с научно-криптографической точки зрения такое жульничество не представляет интереса.

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

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

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