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

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

KeeLoq взлом

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

Статьи о тестовых атаках на код KeeLoq:

  1. "Attacks on the KeeLoq Block Cipher and Authentication Systems". Andrey Bogdanov. June, 2007. File: keeloq_rfidsec2007.
  2. "A Practical Attack on KeeLoq". Sebastian Indesteege, Nathan Keller, Orr Dunkelman, Eli Biham, Bart Preneel. February 2008. File: article-1045.
  3. "On the Power of Power Analysis in the Real World: A Complete Break of the KeeLoq Code Hopping Scheme". Thomas Eisenbarth, Timo Kasper, Amir Moradi, Christof Paar, Mahmoud Salmasizadeh, and Mohammad T. Manzuri Shalmani. June, 2008. File: crypto2008_keeloq.
  4. "Breaking KeeLoq in a Flash". Markus Kasper, Timo Kasper, Amir Moradi, and Christof Paar. March 2009. File: africacrypt2009_keeloq.

Анализ материалов опубликованных статей

Причиной, побудившей меня провести довольно тщательный анализ указанных материалов, стала впервые попавшаяся в Интернете ссылка на фундаментально аргументированные результаты реальных теоретических и практических исследований свойств технологии кодирования, давно известной и широко применяемой в мире в промышленных масштабах под брендом KeeLoq. Хотя первые практические атаки (достаточно успешные) на сигнализации с этим кодом стали известны еще в 2002 году. Эти атаки не имели ничего общего со взломом кода, а точнее ключей кодирования, и по нынешней терминологии то было применение код-грабберов с кодозамещающей технологией, построенной чисто на саботаже работы канала управления сигнализации, заставляющей владельца рефлекторно нажимать все кнопки пульта управления. Защититься от таких грабберов удалось довольно просто путем небольших "косметических" изменений алгоритмов дистанционного управления (по крайней мере, в наших системах Top Guard).

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

Было бы неплохо, если бы читатель сразу отбросил в сторону скептицизм по поводу авторитета довольно большой группы молодых исследователей из Бельгии, Израиля, Ирана и Германии под руководством профессора и доктора г-на Кристофа Паара с одной стороны и руководителя небольшой компании Дедал Электроник с другой. Лучше давайте вместе объективно рассмотрим полученные замечательные с научной точки зрения результаты довольно талантливых исследователей, применивших много оригинальных методов и неожиданных подходов к решению поставленной задачи.

С научной точки зрения это действительно блестящие результаты и я получил огромное удовольствие от многих оригинальных решений, использованных в проведенных исследованиях. Однако, последовавшее за столь смелыми и результативными научными исследованиями, такое же смелое заявление в СМИ о полном "взломе" (breaking) KeeLoq было, наверное, все же довольно неуместным и преждевременным.

Перед тем, как перейти к краткому обзору указанных материалов хочу ответить на естественный вопрос читателей: "А зачем им были нужны эти исследования?" По традиции международной ассоциации криптографии такие тестовые исследования на устойчивость к потенциальному влому проводятся для всех систем специального и массового применения. С другой стороны, молодым ученым (аспирантам) необходимы практические исследования, на которых они могут продемонстрировать свое умение постановки и научного решения конкретной проблемы. Так, что для аспирантов это была замечательная и результативная работа, "народно-хозяйственное" значение которой заключалось в доказательстве ограниченной (не абсолютной) криптостойкости блочных сверточных кодов с длиной ключа 64 бита и "вредности" массового использования в системах безопасности стандартных микросхем с широко известными криптологическими алгоритмами функционирования. Официальная мотивация этих исследований заключалась в беспокойстве о всемирных масштабах применения изделий и технологий компании Microchip, криптостойкость которых ранее не проходила профессиональной проверки и не имеет никаких официальных сертификатов. Конечно, намерения благие, понятные и важные, тем более, что в результате были показаны действительно слабые места широко используемой в мире технологии, но не более. Другое дело кто этими результатами воспользовался и в каких целях, но об этом позже, а теперь, набравшись терпения и, самое главное, - спокойствия, давайте перейдем к рассмотрению по сути результатов опубликованных атак на KeeLoq.

1. "Aтаки на блочный шифр KeeLoq и системы идентификации"

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

kelata pic1

Основного успеха прямой аналитической атаки удалось добиться применением кусочно-линейной аппроксимации важнейшей защитной функции алгоритма шифрования KeeLoq – нелинейной функции обратной связи (NLF) с 5-ю переменными. При этом для синтеза ключа шифрования устройства (не производителя!) необходимо 232 пар исходной и закодированной этим ключом информации (в терминологии криптографии – пар текстов). С теоретической точки зрения все отлично: взяли стандартный алгоритм шифрования и сгенерировали полный комплект (232 штук) исходных (подлежащих шифрованию) 32-разрядных блоков (текстов) и все соответствующие им зашифрованные блоки (тексты) переменной части кода KeeLoq и запомнили полученную таблицу (232 Х 4Byte = 16 GB) для дальнейшей обработки; применили довольно сложные алгоритмы синтеза (восстановления) ключей и обрадовали народ известием, что с помощью компьютеров уже полностью "сломали" KeeLoq. Ну да, а что разве сами разработчики кода не давали оценку сложности его взлома? Да, при прямом переборе всех вариантов полного формата кода KeeLoq нужно перебрать 264 вариантов. Исследователям удалось подобрать оригинальный метод вычисления ключа кодирования устройства – это отдельная довольно важная заслуга, позволяющая сократить число переборов до 232 вариантов.

Отлично, поспешим воспользоваться замечательным результатом для "компьютерного взлома" KeeLoq. Берем предназначенный для "взлома" брелок и начинаем "генерить" необходимый массив данных (реально даже это не совсем просто) и тут выясняется, что физическая длительность каждой реализации кода (текста) составляет 100 миллисекунд. Вот досада! У нас готова вся теория, написано необходимое программное обеспечение и "разогреты" компьютеры, да вот оказывается, что нужные 16 GB исходных данных будут готовы только через 13 лет, ну в крайнем случае, если у кого-то длительность посылки 50 мсек., - через 6,5 лет. Вот это прокол! К тому же это все для "взлома" ключа только одного брелока, а ведь у других брелоков могут быть другие ключи и тогда снова долгая процедура "сбора исходных данных".

В самом общем случае, для полного "взлома" не кода KeeLoq (как Вы теперь сами понимаете), а линейки изделий конкретного производителя, нужно получить именно Ключ Производителя, который он использует для генерации Индивидуальных Ключей своей продукции. Вот тогда, с большими допущениями, можно говорить о каких-то возможностях преодоления систем контроля доступа, использующих KeeLoq-подобные системы кодирования. Вот что по поводу вычисления кода производителя говорит автор статьи [1]: "Алгоритмы и схемы получения ключей, описанные выше, позволяют добыть некоторую(!) информацию о Ключе Производителя из уже имеющегося Индивидуального Ключа кодирования устройства". Это откровенное признание исследователя говорит о том, что не так все просто с вычислением Ключа Производителя, хотя теперь, практически всю работу можно выполнить путем "чистых" вычислений на компьютере. В зависимости от используемого производителем способа генерации ключей шифрования устройств, код производителя может быть вычислен полностью или частично: "Остальные работы по проведению атаки, как описано выше, дают возможность снизить безопасность (т.е. "укоротить" код производителя) до 32, 48, 60, или 0 бит в зависимости от метода генерации ключей и допущений модели безопасности". Таким образом, показано, что "чисто" компьютерный "взлом" ключа производителя не такая уж простая задача и может быть решена в лучшем случае только на 50%!

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

2. "Практическая атака на KeeLoq"

В статье сообщается, что поставлен новый рекорд в добыче Индивидуального Ключа кодирования KeeLoq за счет разработки нового алгоритма синтеза ключа над полем в 216 пар исходных и закодированных текстов и объединения в единый кластер 50-ти двухядерных компъютеров. При затратах всего в 10,000 Евро удалось сгенерировать исходный набор данных всего за 65 минут и вычислить Индивидуальный Код устройства за 3,4 дня. Ура, мы лучше всех и заявляем со всей ответственностью: "Мы расследовали использование KeeLoq на практике и заключили, что наша атака может быть использована для взлома средств безопасности реальных систем". Какой ужас, не правда ли? Если посмотреть, какими формулами, терминами и выкладками наполнен оригинальный текст статьи, то не появится и тени сомнения в авторитетности авторов. Физически 216 образцов пар текстов действительно можно получить примерно за час. Это полный нок-аут для KeeLoq! Перечитываем статью еще раз. Да все правильно, за счет определенных оригинальных допущений и увеличения сложности и продолжительности вычислительных операций действительно достаточно 216 образцов пар текстов. Ну что ж, начинаем с новыми силами и вдохновением "ломать" KeeLoq. Берем реальный брелок с Microchip HCS кодером, прилаживаем внешний генератор имитации нажатия кнопок с периодом 200 мсек., подключаем интерфейс записи шифрованных посылок в компьютер и начинаем процесс формирования массива данных. Внутренний счетчик HCS-микросхемы успешно раз за разом инкрементируется, данные шифруются и пишутся. Стоп! Да ведь это только шифрованные тексты, обозначаемые в описанных алгоритмах, как Сi, а где же взять соответствующие им исходные тексты Pi? Ведь если во всех алгоритмах четко указано, что должны использоваться пары Ci,Pi, то какой ключ мы вычислим?

"Ерунда, - говорят авторы, - в KeeLoq-кодерах нельзя сделать предустановку счетчика посылок, но ведь он все время повторяется". Логично, но вероятность вычисления индивидуального ключа устройства по этому супер алгоритму составляет всего 1,5Х10-5. Я Вам скажу, что это очень мало, но для уверенного 100% вычисления того же ключа на указанных 50-ти компьютерах понадобится 610 лет (216 Х 3,4 дня для перебора всех пар текстов), а это уже очень много!

В чем ошибка столь почтенных экспертов? Смотрим текст статьи и оказывается, этот супер алгоритм отлично работает только с микросхемой транспондера HCS-410 в которой действительно можно собрать весь необходимый массив пар текстов примерно за час работы, но и здесь, думаю не так все просто. Зачем же вводить в заблуждение мировую общественность? Вы создали оригинальный математический аппарат для вычисления Индивидуальных Ключей KeeLoq по широко известнгому алгоритму с использованием всего 216 пар текстов, но вот эффективность его практического применения давайте не будем так широко афишировать, ведь не зря другие эксперты разработали другие оригинальные подходы к возможному "взлому" ключей KeeLoq.

И так, смотрим, что же еще появилось по нашим данным против KeeLoq в 2008 году.

3. "Мощные средства анализа тока потребления в реальном мире. Полный взлом алгоритма Hopping-кода KeeLoq"

Авторы этой статьи признаются, что их внимание к очень широко используемой технологии KeeLoq было привлечено "волной" проводящихся исследований с целью выявления возможных "недостатков практических реализаций KeeLoq-технологий" и получения на этой основе возможности доступа к ключам кодирования-декодирования. "В результате мы представили три очень практичные атаки для взлома ключей, что позволит отказаться от услуг тех атак на KeeLoq, которые существуют сейчас в данной области". И все-таки не такой уж он слабый этот "крепкий орешек", если прямыми методами вскрыть его не удается. "Поскольку результаты предыдущих исследований оказались применимыми только для транспондеров HCS410 и нереализуемыми для Hopping-кодов", исследователи решили пойти уже путем косвенного анализа физических процессов, происходящих в микросхемах, выполняющих шифрование (в передатчиках) и дешифрования (в приемниках). Нужно отметить, что в мире давно известны методы "съема" информации с использованием сетей электропитания. Еще в 60-х годах ХХ века во время проведения конфиденциальных совещаний в помещениях отключались от розеток все потребители потому, что уже тогда в качестве микрофона можно было использовать, например, обычный вентилятор, а вот в 1999 году был открыт так называемый метод "Дифференциального анализа энергии" (differential power analysis (DPA)), позволяющий извлекать криптографические ключи из секретных устройств, используя для этого образы (осциллограммы) изменения тока потребления. Суть DPA-метода заключается в зависимости тока потребления исследуемого цифрового устройства, состоящего из множества триггеров и логических элементов, от логических состояний всех этих триггеров и элементов. В силу технологических особенностей изготовления современных микросхем (CMOS-технология), еще более информативными являются импульсы, возникающие при изменении логических состояний цифровых элементов внутри микросхемы. Вот так выглядит, например, осциллограмма потребляемого тока микропроцессором 8051 в момент выполнения фрагмента программы дешифрования кода RSA с использованием закрытого ключа.

kelata pic2

Конечно, картинка красивая, но после 8051 появились более совершенные процессоры с RISC-архитектурой (к ним относятся и PIC-процессоры), в которых "распараллелены" процессы обработки информации и получить такую четкую картинку уже не возможно. Следующая картинка иллюстрирует характер тока потребления тока одного из стандартных "аппаратных" кодеров серии HCS фирмы Microchip.

kelata pic3

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

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

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

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

  •  Далее исследователи предлагают алгоритм, с помощью которого за приемлемое для практики время, с использованием созданных моделей и корреляционного анализа можно подобрать значение искомого ключа шифрования. В точности математической базы построения этих алгоритмов сомневаться не приходится. Для получения ключа шифрования из аппаратно реализованных стандартных HCS-микросхем требуется буквально десяток секунд, а вот с программной реализацией декодера не все так просто из-за отсутствия информации о точном моменте начала процесса декодирования или генерации индивидуального ключа в процессе регистрации брелока (обучения). Ведь для корреляционного сравнения процессов необходимо их точное совмещение, а если ход выполнения программы в исследуемом процессоре все время меняется в зависимости от значений обрабатываемых данных, например в операторах условного перехода, или в случае использования специальных программных уловок для защиты от таких методов атаки, то эффективность этого метода снижается вплоть до нуля.
  •  На точность исследований сильно влияют помехи от других внутренних устройств таких например, как тактовый генератор. Даже разное конструктивное и технологическое исполнение микросхем (DIP и SOIC) приводящее к снижению потребляемого тока (SOIC), влияет на точность исследований. Эта проблема решается путем дальнейшей фильтрации и сглаживания.

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

4. "Молниеносный взлом KeeLoq"

Вполне логичным стало появление этой работы (2009 г.), посвященной совершенствованию "взлома" программной реализации декодера, позволяющей непосредственно получить ключ производителя, используемый в регистрации новых передатчиков. Здесь так же используется анализ тока потребления и предлагается использовать вместо дифференциального DPA-метода более простой SPA-метод (Simple Power Analysis), а ключевой идеей стал более "тонкий" анализ приведенного на рис.4 алгоритма кодирования, и широко известного текста программы декодирования, рекомендованного Microchip для применения в PIC-процессорах с предположением, что он используется во всех декодерах и на разных моделях PIC-процессоров.

kelata pic4

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

kelata pic5

Так как фрагменты (f) и (i) не имеют никакого отношения к значениям интересующих бит, их не стоит принимать во внимание, а среди остальных, только фрагмент (b) имеет длительность исполнения программы, зависящую от значения анализируемого бита. Длительность исполнения одного цикла шифрования решили считать в циклах микропроцессора, для устранения влияния на результат вклада фрагментов (f) и (i) решили считать длительность по модулю 2. Таким образом, можно в каждом цикле получать значение 9-го бита регистра данных, ну а дальше вычислять значения бит используемого ключа шифрования. Вот на этой очень слабой «зацепке» длительностью всего в один цикл PIC-микропроцессора и построен весь дальнейший очень громоздкий и весьма неустойчивый в практической реализации аппарат «вскрытия» ключа.

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

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

kelata pic6

На фрагменте а) рис.6 приведена осциллограмма тока потребления PIC-процессора во время выполнения процедуры шифрования. Известно, что практически каждый цикл программной инструкции выполняется за 4 "машинных" такта микропроцессора. Исследователи собрали осциллограммы каждого такта в отдельности (фрагменты d), c), d), e) и проанализировали их. Лучшими автокорреляционными свойствами обладают образы первых и четвертых тактов, поэтому исследователи использовали только их для построения «опорной» функции полного цикла шифрования, используемой для вычисления коэффициента взаимной корреляции с процессом потребления тока на протяжении всего процесса шифрования. Как видно из следующего рис.7, в результате получается довольно четкий результат, позволяющий с достаточной точностью (при соответствующем оборудовании и ряде других существенных допущений) определить продолжительность выполнения циклов шифрования (1 и 0 это значения 9-го бита регистра данных) и, как следствие, вычислить в последствии значения бит ключа шифрования.

kelata pic7

Действительно, исследователи получили превосходный с научной точки зрения результат, позволяющий только за одно короткое измерение получить 64 бита Ключа Производителя коммерческого продукта без необходимости предварительного сбора и обработки ни исходных текстов, ни зашифрованных текстов. Вот только напрасно они поспешили делать триумфальное заявление о полном и молниеносном разгроме KeeLoq. Могу честно признаться, что после первого беглого прочтения статьи мне стало немного досадно от краха былой уверенности в надежности этой замечательной технологии. Пришлось, как видите, разобраться более внимательно и оказалось, что слабость совсем не в KeeLoq, а в единственной «зацепке» длиной всего в один цикл микропроцессора. Представляете, эта «зацепка» устраняется из программы шифрования тоже буквально за несколько секунд! Спасибо исследователям, теперь нашим кодерам и декодерам нестрашны такие атаки. Кроме того, исследователи применяли этот метод на процессорах PIC16C56 и PIC16F84A (97-й год прошлого века!), имеющих довольно большой ток потребления по сравнению с современными процессорами, изготавливаемыми по нано-технологиям и имеющими значительно меньший ток потребления, что значительно осложняет эффективность анализа процессов по потребляемому току.
Заявление о применении атаки к достаточно большому набору промышленных устройств говорит только о том, что во всех этих устройствах использована широко известная стандартная программа декодирования и PIC-микропроцессоры, её реализующие. Программа легко корректируется для исправления указанной «зацепки» и KeeLoq становится опять «непробиваемым» по отношению к этому виду атаки. Ну а если в устройствах используется совершенно другой микропроцессор с другой системой команд и неизвестным текстом программы декодирования, то ни о каком успехе такой атаки вообще нечего и говорить! Более того, в статье исследователи сами говорят о высокой чувствительности их метода даже к экземплярам тестируемых устройств и что для каждого экземпляра нужно подбирать реализации «опорных» функций, участвующих корреляционном способе вычисления длительности циклов шифрования.
Таким образом, нужно очень осторожно относиться к громким заявлениям о молниеносных победах даже, казалось бы, авторитетных специалистов.

ЗАКЛЮЧЕНИЕ

  •  

    Ломают не код KeeLoq, а его ключи

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

  •  

    Крах KeeLoq никто не доказал

    Следует весьма осторожно относиться к заявлениям рекламного характера, таким, например, как во всех приведенных статьях о "полном крахе" KeeLoq, а тем более еще и в одно мгновение. Так, например, в статье [1] утверждается, что успех достигнут в результате обработки 232 пар исходных и шифрованных текстов, а оказалось, что для этого нужно, как минимум 3 года, да и для KeeLoq систем дистанционного управления невозможно получить исходные тексты вообще. С вычислением Ключа Производителя в этой статье тоже не очень все ясно. Сделать это можно только в том случае, если производитель системы в целях снижения себестоимости продукции использовал действительно «дефектные» схемы формирования Индивидуальных Ключей устройства или вовсе использовал Простой KeeLoq, где в качестве Индивидуального Ключа вообще используется непосредственно Ключ Производителя. Вероятно, в этой связи авторы и говорили о том, что "работы по проведению атаки дают возможность снизить безопасность (т.е. "укоротить" код производителя) до 32, 48, 60, или 0 бит в зависимости от метода генерации ключей и допущений модели безопасности".

    Теперь читателю будет понятно, что плох не сам KeeLoq, а плохи методы его использования различными производителями.

    В статье [2] авторы так же поспешили заявить о своем триумфе над KeeLoq, хотя в действительности успех был достигнут только для одного из приложений, а именно в системах идентификации типа Свой-Чужой на стандартных микросхемах HCS-410 фирмы Microchip, где запрос передается в незакодированном виде. Вот и хорошо, что нашли действительно слабое место. Теперь этот сигнал запроса нужно закрыть с помощью несложного кодирования и этот недостаток будет устранен без всякого "краха" KeeLoq.

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

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

    Обратите пожалуйста внимание на тот факт, что ни одна из опубликованных атак не показала принципиального недостатка самого алгоритма, позволяющего получить Ключ Производителя за приемлемое время. Исследователи даже сравнивали KeeLoq с шифром AES, указывая на то, что он гораздо лучше потому, что у него длина ключа 128 бит. Это верно, но и минимальная длина блока данных AES 128 бит и вообще придназначен он для дистанционного управления, а для шифрования документов. Разработчики KeeLoq указывали именно на то, что этот алгоритм является оптимальным с точки зрения его применения для дистанционного управления (скорость выполнения команды) и времени "взлома" ключа, целесообразного для автомобиля. Зачем нужен ключ кодирования устройства через 6 лет? Как же, скажет внимательный читатель, а вот в статье [4] говорят, что за несколько секунд "ключик в кармане"! Но ведь для этого использовались недостатки конкретной программной реализации алгоритма в конкретном типе микропроцессоров. А что будет, если использованную в [4] "зацепочку" выровнять, т.е. устранить разницу выполнения выбранных ветвей программы или реализовать алгоритм на другом процессоре, с другим набором инструкций и другим механизмом их выполнения? Очевидно, что тогда keeLoq вновь окажется пригодным для решения отведенных ему задач!

  •  

    Проведение тестовых атак полезно

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

    Все указанные недостатки реализаций могут быть легко устранены. Даже кодирование Серийного Номера кодера для передачи через эфир предусмотрено в KeeLoq. Нужно только правильно использовать все возможности этой технологии для создания надежных систем безопасности.

    Очевидно, что успех многих атак на KeeLoq обусловлен не столько недостатками этой технологии, сколько выбором очень простых в реализации (дешевых) её разновидностей. Поскольку реальные атаки на автомобильные охранные системы и KeeLoq начались в 2002 году, нашей компанией, например, еще тогда были приняты меры для защиты от разного рода грабберов и, читая указанные статьи, я лишний раз убедился в том, что применение стандартных средств в системах безопасности не может обеспечить должной надежности. Поэтому в передатчиках наших систем повышенной надежности, реализующих не совсем стандартные алгоритмы, мы применяем микропроцессоры, а не стандартные HCS кодеры. Так что неиспользованные резервы KeeLoq, а тем более нестандартная их реализация будут и в дальнейшем обеспечивать надежную безопасность автомобилей.

  •  

    Как на самом деле открывают автомобили?

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

    Что должна делать программа этого код-граббера? По команде "оператора" принять из эфира сигнал установленного для KeeLoq формата и выделить из него Серийный Номер передатчика и код команды. В стандартном сигнале они открыты. Далее, для каждого предварительно "добытого" Ключа Производителя нужно декодировать переменную часть сигнала и запомнить полученные в результате декодирования Дискриминант, Счетчик Синхронизации и код команды. Сравнить декодированные коды команды с командой принятой в открытом блоке. Для совпавших кодов команды нужно взять соответствующий Ключ Производителя, Дискриминант, Счетчик Синхронизации +1, код команды и по известному алгоритму кодирования сформировать и передать новую посылку. Если все совпало, - сигнализация повторит сигналы включения охраны. Теперь в нужный момент нужно включить в граббере режим подбора кода выключения охраны и запомнить его для данного Ключа. На эту процедуру понадобится максимум 4 секунды. Теперь мы можем открывать и закрывать данный автомобиль, пока его владелец не поменяет сигнализацию или откажется от её услуг вообще, что одинаково опасно как, как мало какие механические замки могут устоять против твердосплавных варварских отмычек.

    Что мы в данном случае взломали? Код KeeLoq или Ключ Производителя? Наверное, все согласятся с тем, что ни то и ни другое, а скорее всего сигнализацию, производители которой, используя "коммерческую" версию KeeLoq дискредитировали не только свою торговую марку, но и торговую марку KeeLoq. А ведь первоначально Microchip выдавал разрешение на использование технологии и торговой марки KeeLoq по лицензионному соглашению…

  •  

    Откуда в код-граберах Ключи Производителя?

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

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

    Вторая версия – так же достаточно правдоподобна. Вполне возможно использование метода [2] для получения Индивидуального Ключа кодирования запасных брелоков известных двусторонних (наиболее покупаемых в СНГ) сигнализаций, в которых используются стандартные кодеры HCS. Но ведь этот метод позволяет получить только Индивидуальный Ключ, а не Ключ Производителя, - скажет осведомленный читатель. А кто Вам сказал, что в этих сигнализациях используется Обычный (Nomal), а тем более Защищенный (Sequre) KeeLoq? Скорее всего, судя по отведенным для реализации всяких сервисных функций программным ресурсам процессора сигнализаций, там Простой (Simple) KeeLoq, а значит и защита Ключа Производителя НУЛЕВАЯ. Все было бы понятно, но ключи появились все же в 2007 году, а этот метод в 2008-м.

    Третья версия - использование опубликованного в 2009 году в [4] единственно имеющего практическую реализацию для получения Ключа Производителя метода, мало вероятна по той же причине, что сами ключи проявились на 2 года раньше, да и для реализации этого метода, скорее всего, нужны те специалисты, которые его разработали, но торговать ключами они не станут по морально-этическим соображениям.

    Кому выгодна борьба с KeeLoq, ведь при правильном его применении он таки обеспечивает заданные его предназначением параметры безопасности? На этот вопрос достаточно легко ответить, если провести анализ интенсивности "нападок" на автосигнализации с этим кодом. Обратите внимание, что обычно после критики KeeLoq следует реклама новых средств. Конечно, новое это хорошо, но следуя истинным путем, нельзя использовать неэтичные методы.

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

Комментарии по данной теме самих исследователей криптосистем

Вопрос: Занятие исследованием слабых мест систем безопасности, - это безответственно, не как ли?

Ответ: Вовсе нет! Попытки анализа систем безопасности и публикация результатов является центральным правилом научного сообщества в области криптографии вот уже более 30-ти лет. Это повседневная работа тысяч ученых во всем мире, - большая часть которых занимается этим в университетах, но немало и в промышленности, - направленная на выявление слабых мест систем безопасности и публикации полученных результатов. Почему они занимаются этим? Время снова и снова показывает, что лучшим путем к построению истинных систем безопасности является проведение их анализа незаинтересованными специалистами. «Анализировать» - значит пытаться взломать их. Иначе потребители и компании, использующие системы безопасности, никогда не узнают надежные они или нет. По сути, если каждая в отдельности система, чья безопасность основывается на секрете (т.е. на подробностях, где содержаться секреты), была однажды взломана, детальные подробности этой системы, например, алгоритм шифрования, становятся широко известными. Чрезвычайно поучительно, что NSA (Национальное Агентство Безопасности США, являющееся крупнейшей организацией по созданию и взлому кодов в мире) рекомендует общеизвестный шифр AES (Прогрессивный Стандарт Кодирования) для кодирования информации правительства США, вплоть до совершенно секретных данных. Удивительно: Если даже NSA полагается на широко известный алгоритм, то почему люди должны пользоваться непроверенными алгоритмами в коммерческой продукции?

Вопрос: Почему раннее опубликованные атаки не могут применяться к Hopping коду KeeLoq?

Ответ: Раннее опубликованные атаки очень выразительны с математической и криптографической точек зрения. Наиболее удачная из известных атак требует 65536 (215) пар исходных и шифрованных текстов для вычисления Индивидуального Ключа устройства. Более того, имеются два недостатка практического применения.

Во-первых, такая атака применима только в том случае, если KeeLoq используется в системах контроля доступа типа Свой-Чужой. Однако, в большинстве приложений KeeLoq используется в алгоритме Hopping кода.

Во-вторых, даже если KeeLoq используется в системах контроля доступа типа Свой-Чужой, Код Производителя может быть вычислен из Индивидуального Кода устройства, только в том случае, если алгоритм формирования ключа построен на более слабой функции XOR (исключающее ИЛИ). Многие реальные системы используют более сильные схемы формирования ключей, основанные на полном алгоритме KeeLoq.

Вопрос: Насколько трудоемко проведение атак?

Ответ: Атака состоит из двух фаз.

В первой фазе, по нашей оценке инженеру без предварительных знаний в области DPA (дифференциальный анализ тока потребления) и криптографии, для проведения экспертизы понадобится 4-6 месяцев.

Во второй фазе, в течение которой собственно выполняется атака на исследуемое устройство, вполне достаточно умеренных знаний и оборудования.

Вопрос: Нужен ли физический доступ к моему пульту дистанционного управления, для его клонирования?

Ответ: Нет, достаточно перехватить из эфира две посылки сигнала пульта дистанционного управления, но только в том случае, если известен Ключ Производителя.

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

Home Статьи KeeLoq взлом

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

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

  (067) 401 84 24

  (044) 209 69 46

  (067) 566 34 33

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

  www.dedal.com.ua