Det har dykt upp än ny attack mot KeeLoq.
I höstas blev det en hel del uppmärksamhet om den attack som Biham & Co lyckades genomföra mot kryptot i KeeLoq. Jag postade flera gånger om denna attack, bland annat om att KeeLoq-användaren Volvo noga följde utvecklingen.
KeeLoq är alltså en krets från Microchip som används i trådlösa autenticieringsmekaniser och KeeLoq är väldigt vanlig i trådlösa lås på bilar, speciellt dyrare bilar exempelvis från Jaguar och Volvo.
Det Biham & Co visade var att det finns fundamentala brister i kryptomekanismerna som gör att det går att räkna ut nycklar, både enskilda nycklar och de huvudnycklar som används i samtliga bilar av en viss modell. Den här attacken krävde inte heller årtionden av beräkningstid, utan går så fort att man bör kunna anse attacken som praktiskt genomförbar.
Och som det brukar vara i sÃ¥dana här sammanhang – hittar nÃ¥gon en brist, ett fult sÃ¥r och varböld dyker det raskt upp fler som vill dit och peta och rota. Eftersom nÃ¥gon visat att det finns nÃ¥got värt att publicera och fÃ¥ uppmärksamhet kring finns det säkert mer att gräva fram och fÃ¥ del av uppmärksamheten. Liknande beteende tycker jag mig bla se vad gäller attacker mot hashfunktioner.
Några som inte tvekade att peta på KeeLoq är Thomas Eisenbarth, Timo Kasper, Amir Moradi, Christof Paar, Mahmoud Salmasizadeh och Mohammad T. Manzuri Shalmani. Vad de upptäckte var att det finns problem med inte bara de bakomliggande algoritmerna hos KeeLoq, utan det brister även i implementationen. Mer specifikt finns det brister som öppnar upp för sidoattacker.
Deras artikel Physical Cryptanalysis of KeeLoq Code Hopping Applications beskriver det här:
Recently, some mathematical weaknesses of the KeeLoq algorithm have been reported. All of the proposed attacks need at least $2^{16}$ known or chosen plaintexts.
In real-world applications of KeeLoq, especially in remote keyless entry systems using a so-called code hopping mechanism, obtaining this amount of plaintext-ciphertext pairs is rather impractical.
We present the first successful DPA attacks on numerous commercially available products employing KeeLoq code hopping. Using our proposed techniques we are able to reveal not only the secret key of remote transmitters in less that one hour, but also the manufacturer key of receivers in less than one day. Knowing the manufacture
(Notera att artikeln ligger på IACR och den behöver därmed inte varit granskad.)
Författarna skriver om tidigare presenterade attacker mot KeeLoq att:
To our knowledge, most of the commercial implementations of KeeLoq as a remote keyless entry system employ the code hopping mechanism. Thus, the described attacks are not considered as a big threat for their security.
Artikeln beskriver två olika attacker. Båda attackerna bygger på att man mäter förändringar i strömförbrukningen som en effekt av att kretsarna utför sina KeeLoq-operationer.
In 1999, Kocher et. al [5] proposed several methods for analyzing the information leakage of implementations of security related systems. The most powerful attack in this area is called DPA (Differential Power Analysis) and exploits power consumption traces of cryptographic hardware to reveal conï¬dential information.
Almost ten years later, DPA remains an attack mostly performed in smart card evaluation labs and universities, only targeting their own known implementations.
...
We introduce two DPA attacks on KeeLoq code hopping systems. The ï¬rst reveals the secret device key from an integrated circuit that performs the encryption in a transmitter. The second attack is executed on the receiver to recover the manufacturer key from a software implementation running on a microcontroller.
För det första artikeln skriver författarna:
By analyzing the power traces, we found out that there is a speciï¬c hardware inside the chip to perform the KeeLoq encryption.
...
We performed this attack on several chips with different part numbers in DIP or SOIC packages. We are able to recover the secret key of KeeLoq encoders in DIP packages from only 10 power traces. Clearly, SOIC packages beneï¬t from a smaller process technology so the power consumption values are smaller than DIP packages. Hence, the SNR (signal-to-noise ratio) is decreased and we need more power traces. Still, at most 50 power traces are sufficient to reveal the secret key of a device in an SOIC package.
Författarna går sedan vidare och visar hur de kan attackera frekvenshoppsmekanismen även i mottagaren. Författarnas slutsats är klar:
lthough some theoretical attacks on the KeeLoq algorithm have recently been reported, none of them is able to break the code hopping systems in a reasonable time. We illustrated the difficulties of those attacks in the presence of different key derivation schemes.
...
In this paper we presented the ï¬rst successful practical attacks on KeeLoq code hopping systems. These very effective attacks represent a real practical threat for many commercial applications employing the KeeLoq algorithm.
Alltså attacker mot verkliga implementationer av KeeLoq som går på rimlig tid och fungerar i verkligheten.
Jag hoppas att Volvo inte bara följer detta med intresse, utan även arbetar med att lösa problemet. Det lär nog behövas…
