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 університету в місті Левен (Бельгія), у співпраці з колегами з Ізраїлю, виявили новий спосіб атаки на систему[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 днів на обробку на спеціальному обладнанні для «брутфорса», перш ніж система буде зламана.
Посилання
- Приклад реалізації алгоритму на мові С
- Кафедра "вбудовуваної безпеки" університету у Бохум
- Спецификация алгоритма шифрования KeeLoq (рос.).
- Andrey Bogdanov, 'Криптоаналіз of the KeeLoq block cipher'
- N. T. Courtois and G. V. Bard, 'Алгебраїчні і "зміщені" атаки на KeeLoq'
- HGI press release on the complete break of KeeLoq based entry systems. University of Bochum.
- Physical Cryptoanalysis of KeeLoq code-hopping applications
- Security Keyless Systems.