KeeLoq

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание[править | править вики-текст]

Шифрование

Шифрование происходит блоками по 32 бита с использованием 64 битного ключа, один блок текста шифруется за 528 раундов. Функция NLFSR является нелинейной обратной связью, которая принимает значение 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 университета в городе Лёвен (Бельгия), в сотрудничестве с коллегами из Израиля, обнаружили новый способ атаки на систему[1]. Используя детали алгоритма, которые утекли в широкие массы в 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 состояние в цикле,то можем записать: 𝑦6416=𝑁𝐿𝐹(𝑦4831,𝑦4826,𝑦4820,𝑦489,𝑦481)⊕𝑦480⊕𝑦4816⊕𝑘48

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

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

Атака по сторонним каналам[править | править вики-текст]

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

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

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

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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]