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 раундів. Функція 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 університету в місті Левен (Бельгія), у співпраці з колегами з Ізраїлю, виявили новий спосіб атаки на систему. Використовуючи деталі алгоритму, які витекли в широкі маси в 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 днів на обробку на спеціальному обладнанні для «брутфорса», перш ніж система буде зламана.

Посилання

• Приклад реалізації алгоритму на мові С [Архівовано 10 квітня 2018 у Wayback Machine.]
• Кафедра "вбудовуваної безпеки" університету у Бохум [Архівовано 10 квітня 2018 у Wayback Machine.]
• Спецификация алгоритма шифрования KeeLoq (PDF) (рос.). Архів оригіналу (PDF) за 23 квітня 2007. Процитовано 10 квітня 2018.
• Andrey Bogdanov, 'Криптоаналіз of the KeeLoq block cipher' [Архівовано 11 квітня 2018 у Wayback Machine.]
• N. T. Courtois and G. V. Bard, 'Алгебраїчні і "зміщені" атаки на KeeLoq' [Архівовано 11 квітня 2018 у Wayback Machine.]
• HGI press release on the complete break of KeeLoq based entry systems (PDF). University of Bochum.
• Physical Cryptoanalysis of KeeLoq code-hopping applications [Архівовано 11 квітня 2018 у Wayback Machine.]
• Security Keyless Systems (PDF).