Locked History Actions

KeeLoq

Žodis angliškai

KeeLoq

Žodis lietiviškai

KeeLoq šifravimas


Apibrėžimas

Tai yra blokinis šifras, jis paremtas „NLFSR“ programiniu komponentu. „NLFSR“ – perėjimo registas su netiesiniu atgaliniu ryšiu.


Istorija

Pats kriptografinis algoritmas buvo sukurtas profesoriaus Gideon Kuhn, su Willem Smith silicio implementacija ir buvo parduotas „Microchip Technology“ 1995 metais už 10 milijonų dolerių. Tai „Plaukėjančio kodo“ algoritmas, koduojamas ir dekoduojamas su NTQ105/106/115/125D/129D ir HCS101/2XX/3XX/4XX/5XX pagalba.


KeeLoq kodo formatas

Kodą sudaro 34 bitų fiksuota dalis ir 32 bitų šifruota dalis. Vyriausieji 2 bitai tai maitinimo elemento būsena ir pakartotinio signalo siuntimo bitas. Sekantis 4 bitai yra komandos kodas ir 28 bitų kiekvieno įrenginio unikalus serijos numeris. Šifruotą kodo dalį sudaro 4 bitų komandos kodas, 2 skaitiklio perpildymo bitai, 10 diskriminavimo bitai ir 16 skaitiklio sinchronizacijos bitai. KeeLoq kodo formatas.jpg


Veikimo principas

Keeloq algoritmas naudoja 32 bitų ilgio duomenų blokus ir 64 bitų ilgio raktai. Jame naudojama du perėjimo registrai: vienas iš jų yra 64 bitų be grįžtamo ryšio funkcijos (tam, kad sugeneruoti pagrindinį raktą), kitas 32 bitų ilgio perkėlimo registras su netiesine grįžtamojo ryšio funkcija NLF iki penkiu pasikeitimų (skirtas šifravimui). Jei atitinka ši funkcija: NLF(y4, y3, y2, y1, y0) = y0 ⊕ y1 ⊕ y0y1 ⊕ y1y2 ⊕ y2y3 ⊕ y0y4 ⊕ y0y3⊕ ⊕y2y4 ⊕ y0y1y4 ⊕ y0y2y4 ⊕ y1y3y4 ⊕ y2y3y4. 528 ciklų Keeloq šifravima galima įsivaizduoti kaip 8+ ¼ raudų, kur kiekvienas raundas turi 64 ciklų ilgį. Vienas raundas turi visą 64 bitų raktą, o ¼ pirmąjį 16 bitų raktą. Tuo yra suformuluota pirma šio algoritmo silpnybė kuri leidžia panaudoti šoninio kanalo ataką (visss atakas yra aptartos apačioje). Antra silpnybė yra surišta su geru tiesiniu priartėjimu, nelinijinei funkcijai NLF.

  • Sifravimo algoritmas.jpg


Žinomos Keeloq atakos

*Slapto pasiklausymo ir slopinimo ataka (Eavesdropping-and-jamming). Ši ataka naudojama norint įsilaužti į mašinas. Ją galima lengvai suprasti pagal pavyzdį. Tarkime, kad mašinos šeimininkas su nuotoliniu pulteliu bando užrakinti ar atrakinti savo mašiną. Tuo metu, netoliese esantis vagis su savo imtuvu priima radijo bangomis siunčiamą raktą ir parinkęs tinkamą dažnį su savo siųstuvu slopina šeimininko siunčiamą signalą, kad mašina jo nepriimtų. Jei tai pavyksta, jis turi veikiantį raktą, kurį galima bus panaudoti tik vieną kartą. Tačiau, jei po to šeimininkas dar bent kartą atrakintų ar užrakintų savo mašiną, vagies turimas raktas nebetektų prasmės.

*Šoninio kanalo (Side-channel) ataka. Šios atakos remiasi informacija, gauta iš kriptografinės sistemos fizinės realizacijos, vietoj matematinių rakto išskaičiavimų ar teorinių algoritmo trūkumų ieškojimo. Naudinga informacija gali būti gaunama stebint įtaiso atliekamų veiksmų laikus, galios sunaudojimą, skleidžiamą elektromagnetinį lauką, ar netgi skleidžiamą garsą. Viena iš dažniausiai naudojamų šio tipo atakų yra galios analizės ataka.

*Atakos, paremtos matematiniais skaičiavimais. Yra naudojamos kelios technikos išanalizuoti KeeLoq šifravimą pasitelkiant matematinius skaičiavimus, tačiau apžvelgtuose darbuose rašoma, kad šifravimui naudojant 64 bitų ilgio raktą iššifruoti pranešimą užtrunka mažiausiai 3 valandas, o gali užtrukti ir iki kelių dienų. Taip pat šie skaičiavimai reikalauja didelių skaičiavimo pajėgumų. Daugeliui reikia atlikti apie 240 – 250 KeeLoq užšifravimų. Dar vienas matematiniais skaičiavimais paremtų atakų trūkumas yra tas, kad norint pasiekti anksčiau paminėtą užšifravimų skaičių, joms yra reikalingas didelis užšifruotų ir dešifruotų pranešimų porų skaičius. Net ir efektyviausiems metodams reikia atlikti 244,5 užšifravimus ir žinoti 216 užšifruotų ir nešifruotų pranešimų porų.


Literatūra

*M. Kasper, T. Kasper, A. Moradi, C. Paar. Breaking KeeLoq in a Flash. AFRICACRYPT 2009, 2009, 403-420. *T. Eisenbarth, T. Kasper, A. Moradi, C. Paar, M. Salmasizadeh, M. Shalmani. On the Power of Power Analysis in the Real World: A Complete Break of the KeeLoq Code Hopping Scheme. Advances in Cryptology, CRYPTO 2008, 2008, 203-220. *Keeloq aprašymas, [žiūrėta 2014.04.06], prieiga per Internetą: <http://www.math.msu.su/department/dm/dmmc/CONF/dmsc8_part1.pdf >. *KeeLoq kodo formatas [žiūrėta 2018.03.23], prieiga per Internetą: < https://reverseengineering.stackexchange.com/questions/11988/question-about-keeloq-a-car-remote-control-standard >. *KeeLoq šifravimas [žiūrėta 2018.03.23], prieiga per Internetą: < https://www.semanticscholar.org >;