KeeLoq

KeeLoq — это блочный шифр, основанный на программном компоненте "NLFSR". NLFSR — регистр сдвига с нелинейной обратной связью. Однонаправленный протокол передачи команды был разработан Фредериком Брувером, который является генеральным директором компании Nanoteq Pty Ltd.

Сам криптографический алгоритм был разработан в середине 80-х Джидеоном Куном с кремниевой реализацией Виллиема Смитта в Nanoteq Pty Ltd (подразделение Южной Африки) и был продан Microchip Technology, Inc. в 1995 году за 10 млн долларов. Алгоритм представляет собой «плавающий код», кодируется и декодируется с помощью микросхем NTQ105/106/115/125D/129D и HCS2XX/3XX/4XX/5XX. KeeLoq используется в большинстве дистанционных систем управления замком в таких компаниях как Chrysler, Daewoo, Fiat, General Motors, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, Jaguar.

Описание

Шифрование

Шифрование происходит блоками по 32 бита с использованием 64 битного ключа, один блок текста шифруется за 528 раундов. Функция NLF является нелинейной обратной связью, которая принимает значение 0x3A5C742E или F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ abd ⊕ abc. Алгоритм использует 1, 9, 20, 26 и 31 биты из NLFSR для вывода во время шифрования и 0, 8, 19, 25 и 30 биты во время расшифровывания. На выходе выполняется операция XOR с двумя из битов состояния NLFSR (биты 0 и 16 на шифровании и 31 и 15 биты на расшифровке) и с ключевым битом (бит 0 из ключевого состояния на шифровании и бит 15 из ключевого состояния на расшифровке) и данная операция подается обратно в состояние NLFSR на каждом раунде.

Шифрование

Расшифрование

NLF 0x3A5C742E - feedback function, F

F(a,b,c,d,e) = d⊕e⊕ac⊕ae⊕bc⊕be⊕cd⊕de⊕ade⊕ace⊕abd⊕abc

Feedback:

𝜑=𝐹(𝑦^𝑖31,𝑦^𝑖26,𝑦^𝑖20,𝑦^𝑖9,𝑦^𝑖1)⊕𝑦^𝑖16 ⊕ 𝑦^𝑖0 ⊕𝑘^𝑖0

Text: 𝑅^𝑖+1=(𝜑,𝑦^𝑖31,…,𝑦^𝑖1)

Key: 𝐾^𝑖+1=(𝑘^𝑖0,𝑘^𝑖63,…,𝑘^𝑖1)

Расшифровывание

Feedback: 𝜑=𝐹(𝑦^𝑖30,𝑦^𝑖25,𝑦^𝑖19,𝑦^𝑖8,𝑦^𝑖0)⊕𝑦^𝑖15 ⊕ 𝑦^𝑖31 ⊕𝑘^𝑖15

Text: 𝑅^𝑖+1=(𝑦^𝑖30,…,𝑦^𝑖0,𝜑)

Key: 𝐾^𝑖+1=(𝑘^𝑖62,…,𝑘^𝑖0,𝑘^𝑖63)

Пример реализации

Здесь описаны примеры реализации алгоритма на языке C.

Шифрование:

# define KeeLoq_NLF		0x3A5C742E
# define bit(x,n)		(((x)>>(n))&1)
# define g5(x,a,b,c,d,e)	(bit(x,a)+bit(x,b)*2+bit(x,c)*4+bit(x,d)*8+bit(x,e)*16)

u32 KeeLoq_Encrypt (const u32 data, const u64 key){
	u32	x = data, r;
	for (r = 0; r < 528; r++)
		x = (x>>1)^((bit(x,0)^bit(x,16)^(u32)bit(key,r&63)^bit(KeeLoq_NLF,g5(x,1,9,20,26,31)))<<31);
	return x;
}

Расшифровка:

u32 KeeLoq_Decrypt (const u32 data, const u64 key){
	u32	x = data, r;
	for (r = 0; r < 528; r++)
		x = (x<<1)^bit(x,31)^bit(x,15)^(u32)bit(key,(15-r)&63)^bit(KeeLoq_NLF,g5(x,0,8,19,25,30));
	return x;
}

Криптоанализ

KeeLoq впервые был проанализирован Андреем Богдановым, который использовал метод «скользящей средней» и эффективные линейные приближения. Николай Куртуа атаковал KeeLoq, используя метод «скользящей средней» и алгебраические методы. Атаки Богданова и Куртуа не представляли угрозы актуальным реализациям алгоритма, которые, вероятнее всего, более уязвимы для «брутфорса» ключевого пространства. Отдельная реализация «плавающего кода» также часто уязвима для атаки с повторением отправки пакетов, которая создает помехи на канале, прерывает и захватывая сам код и в дальнейшем увеличивая время выполнения в 4 раза от стандартного времени. Эта уязвимость KeeLoq позволила создать так называемые «грабберы», популярные у угонщиков, которые используют микросхемы FPGA для перебора основного ключа KeeLoq.

В 2007 году исследователи из группы COSIC университета в городе Лёвен (Бельгия), в сотрудничестве с коллегами из Израиля, обнаружили новый способ атаки на систему. Используя детали алгоритма, которые утекли в широкие массы в 2006 году, исследователи начали изучать уязвимые места алгоритма. После определения части ключа, которая отвечает за определенные модели автомобиля, уникальный бит ключа может быть взломан при перехвате синхронизации ключа и автомобиля.

Способы атаки на KeeLoq

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

Слайд атака

Слайд атака

Впервые такой тип атаки предложили [Д.Вагнер] (David Wagner) и [А.Бирюков] (Alex Biryukov). Она применима, преимущественно, к многораундовым кодам, каждый раунд которых представляет собой несложное преобразование исходного блока с использованием лишь одного ключа. Ключ может как повторяться, так и быть разным для каждого раунда. Важным является то, что раунды должны быть идентичны и легко обратимы.

На первом этапе необходимо набрать порядка 2^𝑛/2 (где n- длина угадываемого ключа в битах) пар открытый-зашифрованный текст. Этого оказывается достаточно, согласно парадоксу дней рождений, чтобы со значительной вероятностью наткнуться на ―slide pairs”.

Далее (M,C) – одна из таких пар. F – функция преобразования раунда. Суть метода: если (M’,C’) такая, что P’= F(K,M) и C’= F(K,C), то K и есть искомый ключ.

Для Keeloq обратимы первые 32 бита. Следовательно, часть ключа (<=32b ) можно определить таким методом.

Корреляционный подход

Для дальнейшего определения ключа возможно использование свойства NLF-Cor(F)=1.

Оказывается, что для равномерно распределенных 𝑥2,𝑥3,𝑥4 имеет место следующее:

– Pr {NLF(𝑥4, 𝑥3, 𝑥2, 𝑥1, 𝑥0) = 0 | 𝑥0 ⊕ 𝑥1 = 0} = 5/8

– Pr {NLF(𝑥4, 𝑥3, 𝑥2, 𝑥1, 𝑥0) = 1 | 𝑥0 ⊕ 𝑥1 = 1} = 5/8

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

Линейный шаг

Последние 16 бит ключа определяются весьма просто если известны все предыдущие. Основываясь на том, что если мы знаем полностью 48 состояние в цикле,то можем записать: 𝑦⁶⁴16=𝑁𝐿𝐹(𝑦⁴⁸31,𝑦⁴⁸26,𝑦⁴⁸20,𝑦⁴⁸9,𝑦⁴⁸1)⊕𝑦⁴⁸0⊕𝑦⁴⁸16⊕𝑘48

Отсюда находим - 𝑘48. Совершенно аналогично 𝑘49…𝑘63

Андрей Богданов оценивает сложность всех трех атак вкупе как ~2⁵²

Атака по сторонним каналам

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

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

Самым серьёзным последствием атаки по сторонним каналам, является то, что атакующий, изучив ранее главный ключ системы, может скопировать любой законный кодировщик и перехватывать только два необходимых сообщения от этого датчика на расстоянии 100 метров. Другая атака позволяет сбрасывать внутренний счетчик получателя (дверь гаража, автомобиля), которая лишает законного пользователи возможности открывать двери.

Микрочип, на базе KeeLoq IC представленный в 1996 году, использует 60-битное начальное смещение. Если используется 60-битное начальное смещение, то злоумышленнику потребуется примерно 100 дней на обработку на специальном оборудовании для «брутфорса», прежде чем система будет взломана.

Ссылки

• Пример реализации алгоритма на языке С
• Кафедра "встраиваемой безопасности" университета в Бохум
• Спецификация алгоритма шифрования KeeLoq
• Andrey Bogdanov, 'Cryptanalysis of the KeeLoq block cipher'
• N.T. Courtois and G.V. Bard, 'Алгебраические и "смещенные" атаки на KeeLoq'
• University of Bochum / HGI press release on the complete break of KeeLoq based entry systems
• Physical Cryptanalysis of KeeLoq code-hopping applications
• Security Keyless Systems. Keeloq.