KeeLoq on NLFSR - ohjelmistokomponenttiin perustuva lohkosalaus . NLFSR on epälineaarinen takaisinkytkentäsiirtorekisteri. Yksisuuntaisen komennonsiirtoprotokollan on kehittänyt Frederic Brouwer, joka on Nanoteq Pty Ltd:n toimitusjohtaja.
Itse salausalgoritmin kehitti 80-luvun puolivälissä Gideon Kuhn Nanoteq Pty Ltd:n (Etelä-Afrikan divisioona) Willem Smithin pii-toteutuksen kanssa, ja se myytiin Microchip Technology , Inc: lle. vuonna 1995 10 miljoonalla dollarilla. Algoritmi on "kelluva koodi", joka on koodattu ja dekoodattu käyttämällä NTQ105/106/115/125D/129D- ja HCS2XX/3XX/4XX/5XX-siruja. KeeLoqia käytetään useimmissa kauko-ohjausjärjestelmissä yrityksissä, kuten Chrysler , Daewoo , Fiat , General Motors , Honda , Toyota , Volvo , Volkswagen Group , Clifford , Shurlok., Jaguar .
Salaus tapahtuu 32-bittisissä lohkoissa 64-bittisellä avaimella, yksi tekstilohko salataan 528 kierroksella. NLF-funktio on epälineaarinen takaisinkytkentä, joka saa arvon 0x3A5C742E tai F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ab ace abc. Algoritmi käyttää NLFSR:n bittejä 1, 9, 20, 26 ja 31 tulostukseen salauksen aikana ja bittejä 0, 8, 19, 25 ja 30 salauksen purkamisen aikana. Lähtö on XORed kahdella NLFSR-tilabitillä (bitit 0 ja 16 salauksessa ja bitit 31 ja 15 salauksen purkamisessa) ja avainbitillä (bitti 0 avaimen tilasta salauksessa ja bitti 15 avaimen tilasta salauksen purkamisessa) ja tämä operaatio syötettiin takaisin NLFSR-tilaan jokaisella kierroksella.
NLF 0x3A5C742E - palautetoiminto, F
F(a,b,c,d,e) = d⊕e⊕ac⊕ae⊕bc⊕be⊕cd⊕de⊕ade⊕ace⊕abd⊕abc
Palaute:
👖 = _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Teksti: 𝑅 𝑖+1 =(𝜑,𝑦 𝑖 31 ,…,𝑦 𝑖 1 )
Avain: 𝐾 𝑖+1 =(𝑘 𝑖 0,𝑘 𝑖 63,…,𝑘 𝑖 1)
Palaute : _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Teksti: 𝑅 𝑖+1 =(𝑦 𝑖 30,…,𝑦 𝑖 0,𝜑)
Avain: 𝐾 𝑖+1 =(𝑘 𝑖 62,…,𝑘 𝑖 0,𝑘 𝑖 63)
Esimerkkejä C:n algoritmin toteutuksesta on kuvattu tässä.
Salaus:
# määrittele KeeLoq_NLF 0x3A5C742E # määrittele bitti(x,n) (((x)>>(n))&1) # määrittele 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 avain ){ u32 x = data , r ; for ( r = 0 ; r < 528 ; r ++ ) x = ( x >> 1 ) ^ ( ( bitti ( x , 0 ) ^ bitti ( x , 16 ) ^ ( u32 ) bitti ( avain , r & 63 ) ^ bitti ( KeeLoq_NLF , g5 ( x , 1 , 9 , 20 ) , 26 , 31 ))) << 31 ); paluu x ; }Salauksen purku:
u32 KeeLoq_Decrypt ( const u32 data , const u64 avain ){ u32 x = data , r ; for ( r = 0 ; r < 528 ; r ++ ) x = ( x << 1 ) ^ bittiä ( x , 31 ) ^ bittiä ( x , 15 ) ^ ( u32 ) bittiä ( avain , ( 15 - r ) & 63 ) ^ bittiä ( KeeLoq_NLF , g5 ( x , 0 , 8 ) , 19 , 25 , 30 )); paluu x ; }KeeLoqin analysoi ensimmäisenä Andrey Bogdanov, joka käytti liukuvan keskiarvon menetelmää ja tehokkaita lineaarisia approksimaatioita. Nicholas Courtois hyökkäsi KeeLoqin kimppuun käyttämällä liukuvaa keskiarvoa ja algebrallisia menetelmiä. Bogdanovin ja Courtoisin hyökkäykset eivät muodostaneet uhkaa algoritmin nykyisille toteutuksille, jotka ovat todennäköisimmin haavoittuvampia avaruusraakavoimalle. Erillinen "kelluvan koodin" toteutus on myös usein alttiina toistohyökkäykselle, joka häiritsee kanavaa, katkaisee ja kaappaa itse koodin ja lisää suoritusaikaa edelleen 4 kertaa normaaliaikaan verrattuna. Tämä KeeLoq-haavoittuvuus mahdollisti niin kutsuttujen "kaappaajien" luomisen, jotka ovat suosittuja kaappaajien keskuudessa ja jotka käyttävät FPGA -siruja KeeLoqin pääavaimen luettelemiseen.
Vuonna 2007 Leuvenin yliopiston ( Belgia ) COSIC-ryhmän tutkijat löysivät yhteistyössä israelilaisten kollegoiden kanssa uuden tavan hyökätä järjestelmää vastaan [1] . Vuonna 2006 suurelle yleisölle vuotaneiden algoritmin yksityiskohtien avulla tutkijat alkoivat tutkia algoritmin haavoittuvuuksia. Tietyistä automalleista vastaavan avaimen osan määrittämisen jälkeen avaimen yksilöllinen bitti voidaan murtaa katkaisemalla avaimen ja auton synkronointi.
On neljä tapaa hyökätä KeeLoq-salausta vastaan: liukuhyökkäys, korrelaatiomenetelmä, linjaaskel ja sivukanavahyökkäys .
Tämän tyyppistä hyökkäystä ehdottivat ensimmäisenä [D. Wagner] (David Wagner) ja [A. Biryukov] (Alex Biryukov). Se koskee ensisijaisesti monikierroskoodeja, joiden jokainen kierros on yksinkertainen muunnos alkuperäisestä lohkosta käyttämällä vain yhtä näppäintä. Avain voidaan joko toistaa tai olla erilainen jokaisella kierroksella. Tärkeää on, että kierrosten tulee olla identtisiä ja helposti käännettäviä.
Ensimmäisessä vaiheessa on valittava noin 2 𝑛/2 (missä n on arvatun avaimen pituus bitteinä) pelkkää salakirjoitusta paria. Tämä osoittautuu syntymäpäiväparadoksin mukaan riittäväksi törmätä "liukupareihin" merkittävällä todennäköisyydellä.
Lisäksi (M,C) on yksi sellaisista pareista. F on pyöreä muunnosfunktio. Menetelmän ydin: jos (M',C') on sellainen, että P'= F(K,M) ja C'= F(K,C), niin K on haluttu avain.
Keeloqissa ensimmäiset 32 bittiä ovat palautuvia. Siksi avainosa (<=32b) voidaan määrittää tällä tavalla.
Voit määrittää avaimen tarkemmin käyttämällä ominaisuutta NLF-Cor(F)=1.
Osoittautuu, että tasaisesti jakautuneille 𝑥2,𝑥3,𝑥4 pätee seuraava:
– 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
Käyttämällä tätä ja likimääräistä NLF:ää todennäköisyyden suhteen voidaan saavuttaa avaimen seuraavan osan määrittäminen.
Avaimen viimeiset 16 bittiä määritetään yksinkertaisesti, jos kaikki edelliset tunnetaan. Perustuu siihen tosiasiaan , että jos tiedämme syklin 48 tilan kokonaisuudessaan , voimme kirjoittaa : 48 16⊕𝑘48
Täältä löydämme - 𝑘48. Täysin samanlainen kuin 𝑘49…𝑘63
Andrey Bogdanov arvioi kaikkien kolmen hyökkäyksen monimutkaisuuden yhdessä olevan ~2 52
Maaliskuussa 2008 Bochumissa ( Saksa ) sijaitsevan Ruhrin yliopiston sulautetun turvallisuuden laitoksen tutkijat esittelivät täydellisen KeeLoq RFID -teknologiaan perustuvan etäavainhakkeroinnin . Heidän hyökkäyksensä toimii kaikissa tunnetuissa ajoneuvoissa ja kulunvalvontajärjestelmissä Keeloq-salauksella. Bochum-hyökkäys mahdollistaa sekä vastaanottimeen että kaukosäätimeen upotetun salaisten salausavainten palauttamisen . Niiden menetelmä perustuu laitteen virrankulutuksen hallintaan salauksen aikana. Käyttämällä niin sanottua "sivukanavahyökkäystä" virranjakelua vastaan, tutkijat voivat poimia vastaanottimien valmistajilta oikean avaimen, jota voidaan käyttää "pääavaimena" oikean avaimen luomiseen tietyn valmistajan kaukosäätimelle.
Toisin kuin yllä kuvatut kryptografiset hyökkäykset, jotka vaativat noin 65 536 teksti-salakirjoitusparin raa'aa voimaa ja useiden päivien laskentaa henkilökohtaisella tietokoneella avaimen palauttamiseksi, niin sanottuun KeeLoqin "kelluvaan" voidaan soveltaa sivukanavahyökkäystä. koodi"-tila, jota käytetään laajalti "etäavaimen" järjestelmissä (autotallit, autot).
Sivukanavahyökkäyksen vakavin seuraus on, että hyökkääjä, joka on aiemmin oppinut järjestelmän pääavaimen, voi kopioida minkä tahansa laillisen kooderin ja siepata vain kaksi tarpeellista viestiä kyseiseltä anturilta 100 metrin etäisyydeltä. Toinen hyökkäys mahdollistaa vastaanottimen sisäisen laskurin (autotallin ovi, auton ovi) nollaamisen, jolloin lailliset käyttäjät eivät voi avata ovia.
Vuonna 1996 esitelty KeeLoq IC:hen perustuva mikrosiru käyttää 60-bittistä aloitusoffsetia. Jos käytetään 60-bittistä aloituspoikkeamaa, hyökkääjä tarvitsee noin 100 päivää käsitelläkseen erikoislaitteita "raakaa voimaa" varten ennen kuin järjestelmä hakkeroidaan.