KeeLoq

KeeLoq – własnościowy, przeznaczony do implementacji sprzętowej szyfr blokowy oparty na NLFSR. Jednokierunkowy protokół przesyłania został zaprojektowany przez Fredericka Bruwera, doktora, dyrektora operacyjnego w firmie Nanoteq (Pty) Ltd, zaś algorytm kryptograficzny został stworzony przez profesora Gideona Kuhna. Jego sprzętowa implementacja została zrealizowana przez Willema Smita, doktora z firmy Nanoteq Pty Ltd (Południowa Afryka) w połowie lat 80., a następnie została sprzedana firmie Microchip Technology Inc w 1995 roku za 10 milionów dolarów. Szyfr ten jest używany w koderach i dekoderach o zmiennym kodzie, takich jak NTQ105/106/115/125D/129D i HCS101/2XX/3XX/4XX/5XX. KeeLoq jest lub był używany w wielu bezkluczowych systemach wprowadzania hasła przez takie firmy jak Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, Jaguar itd.

Opis

Szyfrowanie KeeLoq

Kodery „o zmiennym kodzie” szyfrują 32-bitowy blok dopełniany zerami za pomocą szyfratora KeyLoq w celu otrzymania 32-bitowego kodu przeskoku. 32-bitowy wektor inicjalizacyjny jest liniowo dodawany (funkcja XOR) do najmniej znaczącego bitu klucza kryptograficznego poprzedzającego szyfrowanie lub deszyfrowanie.

Szyfr KeeLoq akceptuje 64-bitowe klucze i szyfruje 32-bitowe bloki poprzez uruchomienie swojego jednobitowego NLFSR z wykorzystaniem 528 rund. Funkcja zwrotna NLFSR to 0x3A5C742E lub F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ abd ⊕ abc. Wykorzystuje ona bity 1, 9, 20, 26 oraz 31 stanu NLFSR jako wejścia podczas szyfrowania, oraz bity 0, 8, 19, 25 i 30 podczas deszyfrowania. Dane wyjściowe z niej są liniowo łączone (funkcja XOR) z dwoma bitami stanu NLFSR (bity 0 i 16 przy szyfrowaniu oraz bity 31 i 15 przy deszyfrowaniu), a następnie bit klucza (bit 0 stanu klucza przy szyfrowaniu oraz bit 15 stanu klucza przy deszyfrowaniu). Potem jest zwracany do stanu NLFSR podczas każdej z rund.

Kryptoanaliza

KeeLoq Decryption

KeeLoq został po raz pierwszy przeanalizowany kryptograficznie przez Andrieja Bogdanowa przy użyciu techniki ślizgowej oraz wydajnej aproksymacji liniowej. Nicolas Courtois dokonał ataku na KeeLoq przy użyciu metody ślizgowej oraz metod algebraicznych. Ataki wykonane przez Bogdanowa i Courtoisa nie wskazały na żadne zagrożenie przy aktualnych implementacjach świadczące, że algorytm jest nieodporny na pojedyncze ataki typu „brute-force” w przestrzeni kluczy kryptograficznych, która jest gorsza niż wszystkie implementacje „szyfrów przeskakujących” znanych w tym czasie. Pojedyncze implementacje „kluczy przeskakujących” są także często wrażliwe na „ataki ponowienia” ujawniane poprzez zagłuszanie kanału podczas przechwytywania kodu, podczas gdy przeskok klucza został wykonany przez urządzenie jako zwiększenie wektora inicjalizacyjnego przy każdym użyciu zamiast używania czasu bieżącego. Ta technika czyniła ze sprzętowych „przechwytywaczy kluczy” KeyLoq bardzo popularne urządzenia wśród złodziei samochodów. Niektórzy z nich używali urządzeń programowalnych FPGA w celu złamania kluczy opartych na KeyLoq, na co były potrzebne dwa tygodnie dzięki zredukowaniu długości klucza w rzeczywistych implementacjach sprzętowych szyfru.

W 2007 badacze z grupy COSIC Uniwersytetu Katolickiego w Leuven w Belgii we współpracy ze swoimi kolegami z Izraela odkryli skuteczną metodę ataku na system. Przy użyciu szczegółowego algorytmu, który wyciekł w 2006 roku, badacze rozpoczęli pracę nad analizą słabości algorytmu. Po określeniu części klucza wspólnej dla samochodów wybranego modelu unikatowe bity w kluczu mogą zostać złamane poprzez jedynie podsłuchanie komunikacji pomiędzy kluczem a samochodem.

Ataki bocznym kanałem

W marcu 2008 badacze z Zarządu Embedded Security Uniwersytetu Ruhry w Bochum w Niemczech zaprezentowali pełne złamanie zdalnych systemów wprowadzania bezkluczowego opartych na technologii KeyLoq RFID. Ich atak działał dla wszystkich samochodów oraz systemów kontroli dostępu, które były oparte na szyfrze KeeLoq.

Atak dokonany przez zespół z Bochum umożliwił odkrycie sekretnego klucza kryptograficznego osadzonego zarówno w kontroli odbiornika, jak i od strony zdalnej. Jest on oparty na pomiarze zużycia prądu elektrycznego zasilającego urządzenie podczas szyfrowania. Stosując technikę zwaną analizą bocznego ataku na kanał w celu śledzenia poboru mocy, badacze mogą pobrać klucz producenta z odbiorników, co może być uważane za klucz główny do generacji prawidłowych kluczy generowanych dla strony zdalnej wybranego producenta. W przeciwieństwie do ataków kryptograficznych opisanych powyżej, które wymagają około 65536 par tekst jawny-tekst zaszyfrowany w celu wykonania obliczeń na komputerze, aby odkryć klucz, atak bocznym kanałem może być także zastosowany w tzw. trybie przeskoku kodu KeeLoq operacji (tzw. rolowanie kodu), co jest często używane w bezkluczowych systemach wprowadzania (samochody, garaże, budynki itd.).

Najbardziej dewastującą praktyczne zastosowania jest analiza ataku bocznym kanałem, w którym atakujący, znający wcześniej klucz główny, może sklonować każdy uwierzytelniony koder poprzez przechwycenie tylko dwóch komunikatów z kodera z odległości aż do 100 m. Inny atak pozwala na ponowne ustawienie licznika wewnętrznego odbiornika (drzwi garażowe, drzwi samochodu itd.), co uniemożliwia właściwemu użytkownikowi otwarcie drzwi.

Microchip wprowadzony w 1996 w wersji KeeLog IC używa ziarna 60-bitowego. Jeśli używane jest ziarno o tej długości, atakujący potrzebuje około 100 dni na przetworzenie na równoległej maszynie przeprowadzającej analizę „brute force” w celu złamania systemu.

Linki zewnętrzne

• Andrey Bogdanov, 'Cryptanalysis of the KeeLoq block cipher'
• N.T. Courtois and G.V. Bard, 'Algebraic and Slide Attacks on KeeLoq'
• University of Bochum / HGI press release on the complete break of KeeLoq based entry systems
• Physical Cryptanalysis of KeeLoq code-hopping applications