KeeLoq и с чем его едят
Итак, начнём с выдержки из Википедии:
KeeLoq - блочный шифр, основанный на NLFSR (регистр сдвига с нелинейной обратной связью), разработан компанией Nanoteq Pty Ltd. и продан компании Microchip Technology Inc. Шифрование происходит блоками по 32 бита с помощью 64 битного ключа за 528 итераций. Ранее использовался в автомобильных сигнализациях, а ныне используется в автоматических воротах, гаражных дверях и т.п
Принцип работы
KeeLoq реализует так называемый code hopping (переключение кода), то есть генерирует уникальный пакет данных для каждой передачи.
Первые 4 байта - это фиксированная часть (т.н fix), содержит в себе ID нажатой кнопки на пульте (в нашем случае 2) и 28'ми битный серийный номер пульта (39B3DEB)
Следующие 4 байта - динамическая часть (т.н hop), зашифрована мануфактурным ключом (ключом производителя). В расшифрованном виде выглядит так:
Здесь мы видим всё тот же ID нажатой кнопки (2), 12 бит дополнительной информации (зачастую это serial & 0x3FF) и сам 16 битный счётчик нажатий (000A)
- Если переданное значение счётчика соответствует значению в EEPROM приёмника то приёмник подаёт сигнал контроллеру, что всё хорошо (и контроллер например открывает ворота)
- Если переданное значение больше значения в EEPROM то приёмник синхронизируется с переданным значением и соответственно после следующей передачи значения начнёт работать штатно
- Если переданное значение меньше значения в EEPROM то приёмник игнорирует переданную команду, а в некоторых случаях после нескольких отправок "устаревшего" значения и вовсе отвязывает пульт. (Собственно говоря это и есть опасность при экспериментах с KeeLoq)
Режимы безопасности
В стандарте KeeLoq есть 3 режима безопасности (также известны как KDF, learnings):
- Простой режим (Simple learning)
Наименее защищённый режим, при котором мануфактурный ключ никак не преобразуется и используется в шифровании as is. - Классический режим (Normal learning)
Улучшенная версия, где мануфактурный ключ изменяется с помощью серийного номера пульта с помощью побитовых операций
- Безопасный режим (Secure learning)
Модифицированная версия классического режима, использующая вместо побитовых операций над серийным номером, дополнительное значение (он же seed), уникальное для каждого пульта и передающееся при первоначальной привязке пульта к приёмнику. На данный момент самый защищённых режим из представленных в стандарте
Однако некоторые производители отклоняются от стандартных режимов безопасности и реализуют свои собственные, давайте рассмотрим некоторые из них:
- Magic XOR Type-1 learning
Используется производителем Beninca, представляет из себя XOR серийного номера пульта на мануфактурный ключ
- FAAC SLH (SPA) learning
Как понятно из названия, данный алгоритм используется производителем FAAC и по моему мнению является самым продуманным. Представляет из себя серию побитовых операций и шифрования
Теоретические атаки
Слайд-атака
Атака применима, преимущественно, к многораундовым кодам, каждый раунд которых представляет собой несложное преобразование исходного блока с использованием лишь одного ключа.
На первом этапе набрать порядка 2^32 пар открытый-зашифрованный текст
Далее (M,C) - одна из таких пар, F - функция преобразования. Суть такова:
если (M’,C’) такая, что P’= F(K,M) и C’= F(K,C), то K и есть искомый ключ.
В теории данная атака позволяет получить первые 32 бита ключа.
Корреляционный подход
Атака базируется на свойстве NLFSR - Cor(F) = 1
Оказывается, что для равномерно распределенных x2,x3,x4 имеет место следующее:
{NLFSR(x4, x3, x2, x1, x0) = 0 | x0 ^ x1 = 0} = 5/8{NLFSR(x4, x3, x2, x1, x0) = 1 | x0 ^ x1 = 1} = 5/8
Используя это и аппроксимируя NLFSR вероятности, можно добиться определения очередной части ключа.
Линейный шаг
Последние 16 бит ключа определяются, если известны все предыдущие. Основываясь на том, что если мы знаем полностью 48 состояние в цикле,то можем записать:
Отсюда находим key^48 и аналогично key^49 ... key^63
Общая сложность всех теоретических атак - ≈2^52 (≈4503599627370496)
Практические атаки
Здесь я хочу поблагодарить Derek Jamison за прекрасные материалы по практическим атакам на KeeLoq
Replay-атака
Очень распространённая атака работающая, преимущественно, для статических кодов, и для уявизмых приёмников, которые не проверяют значение счётчика
Клонирование пульта
Если мы знаем мануфактурный ключ пульта то без проблем можем сделать копию, которая будет работать, однако делать так не рекомендуется т.к будет конфликт значения счётчика у оригинального пульта и у копии, и в результате при использования двух пультов (оригинального и копии) приёмник может просто отвязать ваш пульт
Future-атака
Если мы знаем мануфактурный ключ пульта то можно воспользоваться логикой работы счётчика и отправить "будущее" значение счётчика (было 0001 - стало 3E91), приёмник может подумать, что пульт "убежал" далеко вперёд и синхронизироваться с переданным значением и штатно работать со следующими значениями (3E92, 3E93 и т.п). При данной атаке оригинальный пульт полностью рассинхронизируется и дальнейшее его использования не рекомендуется по описанным выше причинам.
Rollback-атака
Данная атака весьма редкая, однако всё же возможна с некоторыми приёмниками. Она похожа на Future-атаку, однако вместо последующих значений, мы откатываем состояние счётчика после нескольких использований и приёмник может заново синхронизироваться с этими значениями.
Rolljam-атака
Вся суть атаки в том, что вы записываете сигналы с оригинального пульта и не даёте приёмнику получить их (например создавая помехи рядом с приёмником), после чего вы можете использовать записанные сигналы.
Однако следует учесть, что почти во всех странах (например в США, странах ЕС, РФ) глушение сигналов является незаконным.
Атака на мануфактурные ключи (KGB attack)
Идея заключается в том, что, возможно, приёмник умеет работать с несколькими мануфактурными ключами, а не только с одним. Если мы отправим fix от оригинального пульта, но закодируем счётчик с помощью другого мануфактурного ключа, то, возможно, оно откроется (обычно эту атаку комбинируют с Future-атакой, потому что вы не знаете, каким должно быть значение счётчика).
Enc00-атака
Атака представляет собой подмену fix оригинального пульта на fix другого пульта (также привязанного к приёмнику) и использование hop с оригинального пульта.
Важно, что после подмены, пульт, fix которого использовали, рассинхронизируется и перестаёт работать
Unknown-атака
Суть в том, что, когда приёмник не может декодировать hop, он использует значение 0. Для универсальных приёмников есть вероятность, что они откроются при значении 0.
Заключение
Не смотря на все описанные выше уязвимости, KeeLoq, также как и Mifare Classic (чей шифр Crypto-1 был взломан в далёких 200x) остаётся популярным выбором для бюджетных систем безопасности (автоматические ворота, гаражные двери и т.п). Возможно в будущем все производители перейдут на более стойкие алгоритмы шифрования (например на AES), как это сделали Beninca и Hormann
Кстати, имея на руках мануфактурный ключ вы можете "поиграться" с KeeLoq онлайн в моём мини-приложении.