KeeLoq este un cifru bloc bazat pe componenta software „ NLFSR ”. NLFSR este un registru de deplasare cu feedback neliniar. Protocolul de transfer de comandă unidirecțional a fost dezvoltat de Frederic Brouwer, care este CEO-ul Nanoteq Pty Ltd.
Algoritmul criptografic în sine a fost dezvoltat la mijlocul anilor 80 de Gideon Kuhn cu o implementare de siliciu de către Willem Smith la Nanoteq Pty Ltd (o divizie a Africii de Sud) și a fost vândut către Microchip Technology , Inc. în 1995 pentru 10 milioane de dolari. Algoritmul este un „cod flotant”, codificat și decodat folosind cipuri NTQ105/106/115/125D/129D și HCS2XX/3XX/4XX/5XX. KeeLoq este folosit în majoritatea sistemelor de control de la distanță de la Chrysler , Daewoo , Fiat , General Motors , Honda , Toyota , Volvo , Volkswagen Group , Clifford , Shurlok , Jaguar .
Criptarea are loc în blocuri de 32 de biți folosind o cheie de 64 de biți, un bloc de text este criptat în 528 de runde. Funcția NLF este un feedback neliniar care ia valoarea 0x3A5C742E sau F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ ab ⊕ abc. Algoritmul folosește biții 1, 9, 20, 26 și 31 de la NLFSR pentru ieșire în timpul criptării și biții 0, 8, 19, 25 și 30 în timpul decriptării. Ieșirea este XORed cu doi dintre biții de stare NLFSR (biții 0 și 16 la criptare și biții 31 și 15 la decriptare) și cu un bit de cheie (bitul 0 din starea cheii la criptare și bitul 15 din starea cheii la decriptare) iar această operațiune a reintrodus statul NLFSR la fiecare rundă.
NLF 0x3A5C742E - funcție de feedback, F
F(a,b,c,d,e) = d⊕e⊕ac⊕ae⊕bc⊕be⊕cd⊕de⊕ade⊕ace⊕abd⊕abc
Părere:
𝜑=𝐹(𝑦 𝑖 31,𝑦 𝑖 26,𝑦 𝑖 20,𝑦 𝑖 9,𝑦 𝑖 1)⊕𝑦 𝑖 16 ⊕ 𝑖 𝑖 𝑖 𝑖 𝑖
Text: 𝑅 𝑖+1 =(𝜑,𝑦 𝑖 31 ,…,𝑦 𝑖 1 )
Cheie: 𝐾 𝑖+1 =(𝑘 𝑖 0,𝑘 𝑖 63,…,𝑘 𝑖 1)
Feedback : _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Text: 𝑅 𝑖+1 =(𝑦 𝑖 30,…,𝑦 𝑖 0,𝜑)
Cheie: 𝐾 𝑖+1 =(𝑘 𝑖 62,…,𝑘 𝑖 0,𝑘 𝑖 63)
Exemple de implementare a algoritmului în C sunt descrise aici.
Criptare:
# definește KeeLoq_NLF 0x3A5C742E # definește bit(x,n) (((x)>>(n)))&1) # definește 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 = date , r ; pentru ( r = 0 ; r < 528 ; r ++ ) x = ( x >> 1 ) ^ (( bit ( x , 0 ) ^ bit ( x , 16 ) ^ ( u32 ) bit ( cheie , r & 63 ) ^ bit ( KeeLoq_NLF , g5 ( x , 1 , 9 , 20 ) , 26 , 31 ))) << 31 ); întoarce x ; }Decriptare:
u32 KeeLoq_Decrypt ( const u32 data , const u64 key ){ u32 x = date , r ; pentru ( r = 0 ; r < 528 ; r ++ ) x = ( x << 1 ) ^ bit ( x , 31 ) ^ bit ( x , 15 ) ^ ( u32 ) bit ( cheie ,( 15 - r ) & 63 ) ^ bit ( KeeLoq_NLF , g5 ( x , 0 , 8 ) , 19 , 25 , 30 )); întoarce x ; }KeeLoq a fost analizat pentru prima dată de Andrey Bogdanov, care a folosit metoda mediei mobile și aproximări liniare eficiente. Nicholas Courtois a atacat KeeLoq folosind o medie mobilă și metode algebrice. Atacurile Bogdanov și Courtois nu au reprezentat o amenințare pentru implementările actuale ale algoritmului, care sunt cel mai probabil mai vulnerabile la forța brută a spațiului cheie. O implementare separată a „codului flotant” este, de asemenea, adesea vulnerabilă la un atac de reluare care interferează cu canalul, întrerupe și deturnează codul în sine și crește și mai mult timpul de execuție de 4 ori mai mult decât timpul standard. Această vulnerabilitate KeeLoq a permis crearea așa-numitelor „grabbers”, populare în rândul atacatorilor, care folosesc cipuri FPGA pentru a enumera cheia principală KeeLoq.
În 2007, cercetătorii din grupul COSIC al Universității din Leuven ( Belgia ), în colaborare cu colegii din Israel, au descoperit o nouă modalitate de a ataca sistemul [1] . Folosind detalii ale algoritmului care au fost divulgate publicului larg în 2006, cercetătorii au început să studieze vulnerabilitățile algoritmului. După determinarea părții cheii care este responsabilă pentru anumite modele de mașini, bitul unic al cheii poate fi spart prin interceptarea sincronizării cheii și mașinii.
Există patru moduri de a ataca cifrul KeeLoq: atac cu slide, abordare prin corelare, pas de linie și atac pe canal lateral .
Acest tip de atac a fost propus pentru prima dată de [D. Wagner] (David Wagner) și [A. Biryukov] (Alex Biryukov). Se aplică în primul rând codurilor cu mai multe runde, fiecare rundă fiind o simplă transformare a blocului original folosind o singură cheie. Cheia poate fi fie repetată, fie diferită pentru fiecare rundă. Important este că rundele trebuie să fie identice și ușor reversibile.
În prima etapă, este necesar să formați aproximativ 2 𝑛/2 (unde n este lungimea cheii ghicite în biți) perechi de text simplu. Acest lucru se dovedește a fi suficient, conform paradoxului zilei de naștere, pentru a da peste „perechi de diapozitive” cu o probabilitate semnificativă.
Mai mult, (M,C) este una dintre astfel de perechi. F este funcția de transformare rotundă. Esența metodei: dacă (M',C') este astfel încât P'= F(K,M) și C'= F(K,C), atunci K este cheia dorită.
Pentru Keeloq, primii 32 de biți sunt reversibile. Prin urmare, partea cheie (<=32b) poate fi determinată în acest fel.
Pentru a defini în continuare cheia, puteți utiliza proprietatea NLF-Cor(F)=1.
Se dovedește că pentru 𝑥2,𝑥3,𝑥4 distribuit uniform:
– 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
Folosind aceasta și aproximând NLF în termeni de probabilitate, se poate obține determinarea următoarei părți a cheii.
Ultimii 16 biți ai cheii sunt determinați destul de simplu dacă toți cei anteriori sunt cunoscuți. Pe baza faptului că , dacă cunoaștem starea completă 48 din ciclu , atunci putem scrie : 48 16⊕𝑘48
De aici găsim - 𝑘48. Complet similar cu 𝑘49…𝑘63
Andrey Bogdanov estimează complexitatea tuturor celor trei atacuri împreună la ~2 52
În martie 2008, cercetătorii de la Departamentul de Securitate încorporată de la Universitatea Ruhr din Bochum ( Germania ) au prezentat un hack complet de control de la distanță bazat pe tehnologia KeeLoq RFID . Atacul lor funcționează asupra tuturor vehiculelor și sistemelor de distribuție de control al accesului cunoscute folosind cifrul Keeloq. Atacul Bochum permite recuperarea cheilor criptografice secrete încorporate atât în receptor, cât și în telecomandă . Metoda lor se bazează pe gestionarea consumului de energie al dispozitivului în timpul criptării. Folosind un așa-numit „atac pe canalul lateral” asupra distribuției de energie, cercetătorii pot extrage cheia potrivită de la producătorii de receptor, care poate fi folosită ca „cheie principală” pentru a genera cheia potrivită pentru telecomanda unui anumit producător.
Spre deosebire de atacurile criptografice descrise mai sus, care necesită forță brută de ordinul a 65536 de perechi text-cifrare și câteva zile de calcul pe un computer personal pentru a recupera cheia, un atac pe canal lateral poate fi aplicat așa-numitului KeeLoq „floating”. cod”, care este utilizat pe scară largă pentru sistemele de „cheie de la distanță” (garaje, mașini).
Cea mai gravă consecință a unui atac pe canal lateral este că un atacator, după ce a învățat anterior cheia principală a sistemului, poate copia orice codificator legitim și poate intercepta doar cele două mesaje necesare de la acel senzor la o distanță de 100 de metri. Un alt atac permite resetarea contorului intern al receptorului (usa de garaj, usa masinii), ceea ce face imposibila deschiderea usilor de catre utilizatorii legitimi.
Microcipul, bazat pe KeeLoq IC, introdus în 1996, utilizează un offset de pornire de 60 de biți. Dacă se folosește un offset de pornire de 60 de biți, atunci atacatorul va avea nevoie de aproximativ 100 de zile pentru a procesa pe echipamente speciale pentru „forță brută” înainte ca sistemul să fie piratat.