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_NLF0x3A5C742E # 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){ u32x = 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){ u32x = 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 стан в циклі,то можемо записати: 𝑦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 днів на обробку на спеціальному обладнанні для «брутфорса», перш ніж система буде зламана.
Примітки
- . Архів оригіналу за 20 грудня 2017. Процитовано 10 квітня 2018.
Посилання
- Приклад реалізації алгоритму на мові С [ 10 квітня 2018 у Wayback Machine.]
- Кафедра "вбудовуваної безпеки" університету у Бохум [ 10 квітня 2018 у Wayback Machine.]
- (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.]
- (PDF).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
KeeLoq ce blokovij shifr zasnovanij na programnomu komponenti NLFSR NLFSR registr zsuvu z nelinijnim zvorotnim zv yazkom Odnospryamovanij protokol peredachi komandi buv rozroblenij Frederikom Bruverom yakij ye generalnim direktorom kompaniyi Nanoteq Pty Ltd Sam kriptografichnij algoritm buv rozroblenij u seredini 80 h Dzhideonom Kunom z kremniyevoyu realizaciyeyu Villiyema Smitta v Nanoteq Pty Ltd pidrozdil Pivdennoyi Afriki i buv prodanij Microchip Technology Inc u 1995 roci za 10 mln dolariv Algoritm yavlyaye soboyu plavayuchij kod koduyetsya i dekoduyetsya za dopomogoyu mikroshem NTQ105 106 115 125D 129D i HCS2XX 3XX 4XX 5XX KeeLoq vikoristovuyetsya v bilshosti distancijnih sistem upravlinnya zamkom v takih kompaniyah yak Chrysler Daewoo Fiat General Motors Honda Toyota Volvo Volkswagen Group Clifford Shurlok Jaguar OpisShifruvannya Shifruvannya vidbuvayetsya blokami po 32 bita z vikoristannyam 64 bitnogo klyucha odin blok tekstu shifruyetsya za 528 raundiv Funkciya NLFSR ye nelinijnim zvorotnim zv yazkom yaka prijmaye znachennya 0x3A5C742E abo F a b c d e d e ac ae bc be cd de ade ace abd abc Algoritm vikoristovuye 1 9 20 26 i 31 biti z NLFSR dlya vivodu pid chas shifruvannya i 0 8 19 25 i 30 biti pid chas rozshifruvannya Na vihodi vikonuyetsya operaciya XOR z dvoma z bitami stanu NLFSR biti 0 i 16 na shifruvanni i 31 i 15 biti na rozshifrovci i z klyuchovim bitom bit 0 z klyuchovogo stanu na shifruvanni i bit 15 z klyuchovogo stanu na rozshifrovci i dana operaciya podayetsya nazad v stan NLFSR na kozhnomu raundi Shifruvannya Rozshifruvannya 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 Rozshifrovuvannya Feedback 𝜑 𝐹 𝑦𝑖30 𝑦𝑖25 𝑦𝑖19 𝑦𝑖8 𝑦𝑖0 𝑦𝑖15 𝑦𝑖31 𝑘𝑖15 Text 𝑅𝑖 1 𝑦𝑖30 𝑦𝑖0 𝜑 Key 𝐾𝑖 1 𝑘𝑖62 𝑘𝑖0 𝑘𝑖63 Priklad realizaciyiTut opisani prikladi realizaciyi algoritmu na movi C Shifruvannya define KeeLoq NLF0x3A5C742E define bit x n x gt gt n amp 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 lt 528 r x x gt gt 1 bit x 0 bit x 16 u32 bit key r amp 63 bit KeeLoq NLF g5 x 1 9 20 26 31 lt lt 31 return x Rozshifrovuvannya u32 KeeLoq Decrypt const u32 data const u64 key u32 x data r for r 0 r lt 528 r x x lt lt 1 bit x 31 bit x 15 u32 bit key 15 r amp 63 bit KeeLoq NLF g5 x 0 8 19 25 30 return x KriptoanalizKeeLoq vpershe bulo proanalizovano Andriyem Bogdanovim yakij vikoristovuvav metod kovznoyi serednoyi i efektivni linijni nablizhennya Mikola Kurtua atakuvav KeeLoq vikoristovuyuchi metod kovznoyi serednoyi i algebrayichni metodi Ataki Bogdanova i Kurtua ne predstavlyali zagrozi aktualnim realizaciyam algoritmu yaki najimovirnishe bilsh urazlivi dlya brutforsa klyuchovogo prostoru Okrema realizaciya plavayuchogo kodu takozh chasto vrazliva dlya ataki z povtorennyam vidpravki paketiv yaka stvoryuye pereshkodi na kanali pererivaye i zahoplyuyuchi sam kod i nadali zbilshuyuchi chas vikonannya v 4 razi vid standartnogo chasu Cya vrazlivist KeeLoq dozvolila stvoriti tak zvani graberi populyarni u vikradachiv yaki vikoristovuyut mikroshemi FPGA dlya pereboru osnovnogo klyucha KeeLoq U 2007 roci doslidniki iz grupi COSIC universitetu v misti Leven Belgiya u spivpraci z kolegami z Izrayilyu viyavili novij sposib ataki na sistemu Vikoristovuyuchi detali algoritmu yaki vitekli v shiroki masi v 2006 roci doslidniki pochali vivchati vrazlivi miscya algoritmu Pislya viznachennya chastini klyucha sho vidpovidaye za pevni modeli avtomobilya unikalnij bit klyucha mozhe buti zlamanij pri perehoplenni sinhronizaciyi klyucha i avtomobilya Sposobi ataki na KeeLoqIsnuye chotiri sposobi ataki na shifr KeeLoq Slajd ataka korelyacijnij pidhid linijnij krok i ataka po inshim kanalah Slajd ataka Slajd ataka Vpershe takij tip ataki zaproponuvali D Vagner David Wagner i A Biryukov Alex Biryukov Vona zastosovuyetsya perevazhno do bagatoraundovih kodiv kozhen raund yakih yavlyaye soboyu skladne peretvorennya vihidnogo bloku z vikoristannyam lishe odnogo klyucha Klyuch mozhe povtoryuvatisya tak i buti riznim dlya kozhnogo raundu Vazhlivim ye te sho raundi povinni buti identichni i legko oborotni Na pershomu etapi neobhidno nabrati blizko 2𝑛 2 de n dovzhina vgaduvanogo klyucha v bitah par vidkritij zashifrovanij tekst Cogo viyavlyayetsya dostatno zgidno paradoksu dniv narodzhen shob zi znachnoyu imovirnistyu natknutisya na slide pairs Dali M C odna z takih par F funkciya peretvorennya raundu Sut metodu yaksho M C taka sho P F K M i C F K C K i ye shukanij klyuch Dlya Keeloq oborotni pershi 32 bita Otzhe chastina klyucha lt 32b mozhna viznachiti takim metodom Korelyacijnij pidhid Dlya podalshogo viznachennya klyucha mozhlive vikoristannya vlastivosti NLF Cor F 1 Viyavlyayetsya sho dlya rivnomirno rozpodilenih 𝑥2 𝑥3 𝑥4 maye misce nastupne 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 Vikoristovuyuchi ce i approksimuyuchi NLF po jmovirnosti mozhna domogtisya viznachennya chergovoyi chastini klyucha Linijnij krok Ostanni 16 bit klyucha viznachayutsya dosit prosto yaksho vidomi vsi poperedni Gruntuyuchis na tomu sho yaksho mi znayemo povnistyu 48 stan v cikli to mozhemo zapisati 𝑦6416 𝑁𝐿𝐹 𝑦4831 𝑦4826 𝑦4820 𝑦489 𝑦481 𝑦480 𝑦4816 𝑘48 Zvidsi znahodimo 𝑘48 Absolyutno analogichno 𝑘49 𝑘63 Andrij Bogdanov ocinyuye skladnist vsih troh atak ukupi 252 Ataka po storonnim kanalah U berezni 2008 roku doslidniki z kafedri vbudovuvanoyi bezpeki Rurskogo universitetu mista Bohum Nimechchina predstavili povnij zlom distancijnogo keruvannya klyuchem zasnovanij na tehnologiyi KeeLoq RFID Yih ataka pracyuye na vsih vidomih avtomobilyah i sistemah rozpodilu kontrolyu dostupu sho vikoristovuyut shifr Keeloq Bohumska ataka dozvolyaye vidnovlyuvati sekretni kriptografichni klyuchi vbudovani v prijmach tak i v pult distancijnogo upravlinnya Yih sposib zasnovanij na upravlinni energospozhivannyam pristroyu pid chas shifruvannya Vikoristovuyuchi tak zvanu ataku po storonnih kanalah do rozpodilu zhivlennya doslidniki mozhut otrimati potribnij klyuch vid virobnikiv prijmacha yakij mozhna vikoristovuvati yak majster klyuch dlya generaciyi potribnogo klyucha dlya distancijnogo pulta pevnogo virobnika Na vidminu vid kriptografichnih atak opisanih vishe yaki vimagayut pereboru poryadku 65536 par tekst shifr i kilka dniv rozrahunku na personalnomu komp yuteri dlya vidnovlennya klyucha ataka po inshim kanalam mozhe buti zastosovana do tak zvanogo rezhimu plavayuchogo kodu KeeLoq yakij shiroko vikoristovuyetsya dlya sistem distancijnogo klyucha garazhi avtomobili Najserjoznishim naslidkom ataki po storonnih kanalah ye te sho atakuyuchij vivchivshi ranishe golovnij klyuch sistemi mozhe skopiyuvati bud yakij zakonnij koduvalnik i perehoplyuvati tilki dva neobhidnih povidomlennya vid cogo datchika na vidstani 100 metriv Insha ataka dozvolyaye skidati vnutrishnij lichilnik oderzhuvacha dveri garazha avtomobilya yakij pozbavlyaye zakonnogo koristuvachi mozhlivosti vidkrivati dveri Mikrochip na bazi KeeLoq IC predstavlenij v 1996 roci vikoristovuye 60 bitne pochatkove zmishennya Yaksho vikoristovuyetsya 60 bitne pochatkove zmishennya to zlovmisnikovi potribno priblizno 100 dniv na obrobku na specialnomu obladnanni dlya brutforsa persh nizh sistema bude zlamana Primitki Arhiv originalu za 20 grudnya 2017 Procitovano 10 kvitnya 2018 PosilannyaPriklad realizaciyi algoritmu na movi S 10 kvitnya 2018 u Wayback Machine Kafedra vbudovuvanoyi bezpeki universitetu u Bohum 10 kvitnya 2018 u Wayback Machine PDF ros Arhiv originalu PDF za 23 kvitnya 2007 Procitovano 10 kvitnya 2018 Andrey Bogdanov Kriptoanaliz of the KeeLoq block cipher 11 kvitnya 2018 u Wayback Machine N T Courtois and G V Bard Algebrayichni i zmisheni ataki na KeeLoq 11 kvitnya 2018 u 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 kvitnya 2018 u Wayback Machine PDF