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

Каждый установщик рано или поздно сталкивается с необходимостью объяснить «по-простому, на пальцах», как же работает алгоритм Keeloq. Особенно актуально это стало сейчас, при появлении нового устройства интеллектуального взлома автомобильных охран, так называемого «адаптирующегося брелка» (название не самое удачное, вернее, как мы увидим ниже, совсем неудачное). Несмотря на эпиграф, давайте попытаемся осознать, в чем состоит проблема. Для этого придется сделать несколько существенных упрощений.

Система кодирования Keeloq. С нее и начнем. В случае применения в охранной системе «стандартного Keeloq'а», передаваемая в эфир кодовая комбинация (при нажатии на любую кнопку) выглядит следующим образом:

<номер нажатой кнопки><номер брелка><...шифрованная часть...>

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

<<номер нажатой кнопки><дополнительная информация><счетчик нажатия>>

Мы видим, что в структуре Keeloq заранее известно, где что расположено. Кроме того, номер нажатой кнопки передается в эфир дважды: один раз в открытой, другой раз — в шифрованной части. Это обстоятельство нам еще пригодится.
Два слова о счетчике нажатия. Для системы Keeloq нажатие на любую кнопку увеличивает его на единицу. Если он был «x», то следующее нажатие будет пронумеровано как «x+1», затем «x+2» и т.д.
Получая команду из эфира, главный модуль сигнализации проверяет номер брелка. Если номер не совпадает с заранее записанным в память модуля, дальнейшая обработка сигнала прекращается. Если совпадает, производится попытка дешифровки. В этом случае дополнительная информация позволяет проверить, что нажат именно брелок хозяина, а не какой-то другой со случайно совпавшим номером.
Наконец, производится проверка счетчика нажатия. Если счетчик больше, чем зафиксировано в памяти системы, команда считается правильной и выполняется (в соответствии с номером нажатой кнопки). Если меньше или не изменился — возможно, что воспроизводится ранее записанная простейшим граббером команда. Такая команда отвергается.
Основной секрет состоит в том, как же зашифрована «шифрованная часть». Сразу скажем, что это — весьма сложная функция «F», включающая в себя собственно счетчик нажатия «x», номер брелка «C», номер кнопки «B» и основной секрет (пароль) производителя «A» (в случае применения стандартного Keeloq’а). Но что нам эти сложности? Давайте считать, что эта функция очень простая, например — обычный квадратный трехчлен! Итак:

F=Ax2+Bx+C

Сразу становится понятно, как производится дешифровка в главном модуле. Узнав из эфира номер брелка «С», номер кнопки «B» и заранее зная Пароль «А» легко вычислить счетчик «x». Давайте не обращать внимания, что ответов получилось два — мы всегда можем считать верным тот, который больше. Естественно, не зная Пароля «А», мы не сможем вычислить «x».

Этап первый: вычисление пароля. Если посмотреть на нашу функцию чуть внимательнее, то данный алгоритм легко поддается дешифровке. Достаточно лишь записать 2 последовательные команды:

F1=Ax2+Bx+C
F2=A(x+1)2+B(x+1)+C

Весьма ясно, как взломать пароль. В нашем случае достаточно записать две последовательные команды брелка, решить систему уравнений и получить пароль производителя «А». Для системы другого производителя — другое решение, другой пароль. И так далее. Все что осталось — это занести список паролей в чудо-устройство под названием «адаптирующийся брелок» — вуаля! Задача решена.
Комментарий пока отложим.

Этап второй: применение «адаптирующегося брелка». Заметьте, что он не является в истинном смысле адаптирующимся, а он заранее адаптирован под некоторые уже вскрытые системы. Если это для Вас пока не очевидно, дочитайте до конца. Станет чуть понятнее, почему. И еще. Самое время заменить его название в соответствии с его предназначением. Назовем его лучше «граббером для некоторых заранее взломанных систем с плавающим кодом». Еще короче: граббер (но не простой, как для систем с фиксированным кодом, а высокоинтеллектуальный).
Как только граббер ловит из эфира (синхронно с атакуемой охранной системой) кодовую комбинацию, он начинает ее анализ. Граббер последовательно пытается применить все имеющиеся в его памяти пароли к записанному коду. Анализ может проводиться по нескольким параметрам, поэтому осуществляется достаточно быстро. В качестве примера вспомним, что номер нажатой кнопки передается как в открытой, так и в закрытой части. Если не совпало — переходим к следующему паролю, если совпало — продолжаем анализ. При неудаче (пароль не подобран), будем считать, что хозяину повезло. Скорее всего, для угона его автомобиля понадобятся другие средства, например утюг. В случае успеха (пароль подобран) граббер извещает автомобильного вора тихим зуммером или миганием лампочки. Второй этап пройден.
Комментарий ко второму этапу. В отличие от «замещающих» или «блокирующих» грабберов хозяин автомобиля никак не подозревает об успешности проведенной атаки. Нет никаких затруднений в постановке автомобиля в охрану (или снятии — не важно!). Граббер работал как простой приемник.

Последний этап: угон. Как мы помним, хозяин и злоумышленник расстались. Но злоумышленник знает, что автомобиль марки «ХХХ» гос. номер у000уу00RUS оснащен вскрытой сигнализацией, записанной в ячейку номер Z граббера. В зависимости от условий автомобиль может быть угнан немедленно или через неделю. Или через год. До этого момента хозяин мог пользоваться автомобилем, нажимать на кнопки брелка. Счетчик нажатия, записанный в память, увеличился, поэтому и граббер должен передать гарантированно будущий код (например, со счетчиком x+15, т.е. отключающую охрану команду F15). Не получилось — попробовать F30 или F60. Или просто запустить перебор пока счетчик нажатия граббера не догонит счетчик нажатия системы. Поехали! Комментарии не требуются.

Отложенный комментарий к первому этапу (вычисление пароля). Пожалуйста, не пугайтесь видимой простоты. Это в нашем случае, когда функция шифрования примитивно проста, подбор пароля был произведен «в две строчки», чисто, решением системы двух уравнений.
Придется чуть-чуть отойти от простейших арифметических примеров. В реальном Keeloq’е алгоритм сложнее, а переменные в функции не разделяются. Более того, сам алгоритм не описывается одной функцией, а представляет собой целый класс функций.
Разумеется, можно попытаться записать не две последовательных команды, а больше. Например, F1, F2, F3, F4, F5, F6, F7, F8, F9 и так далее. Но в случае нелинейной функции шифрования со сложным алгоритмом каждое новое уравнение приводит к геометрическому нарастанию времени на поиск точного решения. Не спасает даже то, что решение ищется в целых числах! Общее решение не достижимо. На этом основании Keeloq победил всех конкурентов и на долгое время стал негласным стандартом шифрования в автомобильных сигнализациях. Ведь его лобовой взлом невозможен. Если бы…

• Если бы система Keeloq (в его наиболее простом, стандартном виде) из-за своей простоты применения не выдавила бы с рынка почти все способы шифрования и именно на нее не были бы направлены все атаки.
• Если бы фирма Microchip не сделала бы общедоступным алгоритм генерации шифра.
• Если бы с каждым днем не росли вычислительные мощности современных компьютеров.
• Если бы фирмы-производители старались выпускать системы, в которых пароль образовывался бы не только из букв и цифр, а из всех 256 разрешенных символов.
• Если бы не была сформулирована простая и очевидная мысль: искать общее решение и не нужно! Достаточно найти частное, но конкретное решение. Достаточно вскрыть (подобрать) конкретный пароль.

Вскрытие пароля можно произвести, используя относительно недорогое оборудование. Записав подряд несколько кодовых комбинаций F1, F2, F3, F4, F5… начинаем простой перебор. Берем номер брелка, шифруем его паролем «00000001», сравниваем код с записанным. Не получилось, применяем пароль «00000002». И так далее до «ZZZZZZZZ». Несколько комбинаций понадобится как для ускорения процедуры подбора, так и для проверки подобранного пароля. Знание системы кодирования позволит нам слегка облегчить задачу:

• Можно пытаться подобрать код для новой системы, когда заранее известно, что счетчик нажатий невелик.
• Можно начать с наиболее простых (смысловых) паролей: имена фирм, названия брендов, названия моделей, клички разработчиков или их собак.
• Можно попытаться использовать наиболее употребительные символы, т.е. цифры и латинские буквы.
• Можно максимально быстро проводить анализ, например: сравнивая полученный из эфира номер кнопки с его зашифрованным значением и сразу отбрасывая неверный пароль.
• И так далее. Хакеры все это уже успешно проходили и не один раз.

К сожалению, есть еще один способ узнать пароль. Его можно украсть…

Еще раз. Означает ли это, что «Keeloq вскрывается»? Данное утверждение абсолютно бессмысленно. Keeloq — это система кодирования (принцип шифрования). Ее не надо вскрывать: она и так опубликована в открытой печати. «Вскрываются» всегда конкретные бренды. Это происходит в том случае, когда разработчики охранных систем ленятся усложнить доступ к паролям (программно или организационно).

Что же делать? Во-первых, знать методику взлома и соответственно выбирать пароль. Простой расчет показывает, что замена пароля на псевдослучайный, когда используются не только цифро-буквенные комбинации, а все разрешенные символы (напомним, их 256), повышает крипкостойкость шифрования в миллионы раз. Ситуация моментально возвращается на исходную позицию, и для подбора пароля понадобится вполне достаточное время, чтобы плюнуть на него и попытаться разгадать другой.
Во-вторых, использование «полного Keeloq’a», когда каждый брелок шифруется своим паролем. Тем самым, даже если вскрыть один пароль (а, как мы видим, это задача может и должна быть усложнена), то на выходе получится алгоритм шифрования для этого брелка и только! Другой брелок будет зашифрован по-другому! Тем самым вскрытие пароля становится бессмысленным мероприятием. Да и красть, строго говоря, нечего.
Остается только дождаться, когда фирмы-производители в массовом порядке начнут менять систему кодирования, переходя на «полный Keeloq» (он же «супер-Keeloq» или «усовершенствованный Keeloq»). Процесс уже начался. Прелесть ситуации состоит в том, что нет необходимости заменять сами платы охранных систем. Нужно поменять только процессоры, а также программу прошивки брелков. Это будет концом нынешнего «граббера = адаптирующегося брелка». А пока остается надеяться, что пароль именно Вашей системы еще не вскрыт и не украден.

А что же дальше? Неужели на этом закончится извечное противостояние брони и снаряда? Разумеется, нет! Теперь при применении «полного Keeloq’а» всякий раз интеллектуальный угон автомобиля должен будет происходить индивидуально, с подбором конкретного пароля. Соответствующие программы (пока еще?) не написаны. Но точки приложения усилий известны. Это — фиксированный формат передачи данных (см. выше раздел «система кодирования Keeloq»), в котором заранее известно, где что расположено и присутствует открытая часть, на которую можно опереться при расшифровке. Кроме того, даже «полный Keeloq» может не выдержать атаки с применением «замещающего граббера». Стоит заметить, что атаки с помощью такого устройства весьма заметны пользователю; о том, как с ними бороться, мы писали в статье проблемы одностороннего доступа. При этом разработчикам нельзя утешаться тем, что «замещающий граббер» обманывает не систему кодирования, а человека, пользующегося брелком. Итог один — угон автомобиля.

Можно ли верить нам? Проблемы, связанные с возможными покушениями на систему кодирования Keeloq мы осознали на рубеже веков. В 2001 году мы намекнули об их существовании. В 2002 году было разработано новое семейство Excellent evolution2, достаточно защищенное от этих (тогда еще — во многом потенциальных) угроз. Мы решительно отказались от стандартных микросхем кодирования HCS-xxx, и перешли на специальные процессоры. В попытке объяснить наш подход мы внятно и публично объявили обо всех проблемах в начале 2003 года. Долгое время нас упрекали, что все это выдумки, а мы напрасно переусложняем систему кодирования. Похоже, мы оказались правы?