View source for KeeLoq

{{Refimprove|date=August 2007}}
'''KeeLoq''' is a proprietary hardware-dedicated [[block cipher]] that uses a [[NLFSR|non-linear feedback shift register]] (NLFSR).  The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was created by Gideon Kuhn at the University of Pretoria, and the silicon implementation was by Willem Smit at Nanoteq Pty Ltd ([[South Africa]]) in the mid-1980s.  KeeLoq was sold to [[Microchip Technology|Microchip Technology Inc]] in 1995 for $10 million.<ref>{{cite patent | country=US| number=5517187 | status=patent | title=Microchips and remote control devices comprising same |assign1=Microchip Technology Inc | invent1=Bruwer, Frederick J.| invent2=Smit, Willem |invent3= Kuhn, Gideon J. | gdate=1996-05-14 }}</ref> It is used in "[[Hopping code|code hopping]]" encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq is or was used in many [[Remote keyless system|remote keyless entry systems]] by such companies as [[Chrysler]], [[Daewoo]], [[Fiat]], [[General Motors|GM]], [[Honda]], [[Toyota]], [[Volvo]], [[Volkswagen Group]], Clifford, Shurlok, and [[Jaguar Cars|Jaguar]].<ref>Some evidence that [[Chrysler]] indeed uses KeeLoq can be found in [https://archive.org/details/tps_episode_04 (this video)].</ref>

==Description==
[[File:Кодировка.png|thumb|KeeLoq Encryption]]
KeeLoq "code hopping" encoders encrypt a 0-filled 32-bit block with KeeLoq cipher to produce a 32-bit "[[hopping code]]".  A 32-bit [[initialization vector]] is linearly added ([[XOR]]ed) to the 32 [[least significant bit]]s of the [[key (cryptography)|key]] prior to [[encryption]] and after [[decryption]].

KeeLoq cipher accepts 64-bit keys and encrypts 32-bit blocks by executing its single-bit NLFSR for 528 rounds. The NLFSR feedback function is <code>0x3A5C742E</code> or
:<math>F(a,b,c,d,e) = d \oplus e \oplus ac \oplus ae \oplus bc \oplus be \oplus cd \oplus de \oplus ade \oplus ace \oplus abd \oplus abc</math>
KeeLoq uses bits 1, 9, 20, 26 and 31 of the NLFSR state as its inputs during encryption and bits 0, 8, 19, 25 and 30 during decryption. Its output is linearly combined (XORed) with two of the bits of the NLFSR state (bits 0 and 16 on encryption and bits 31 and 15 on decryption) and with a key bit (bit 0 of the key state on encryption and bit 15 of the key state on decryption) and is fed back into the NLFSR state on every round.

== Attacks ==

===Replay attack===
For simplicity, individual "code hopping" implementations typically do not use [[cryptographic nonce]]s or [[timestamping]]. This makes the protocol inherently vulnerable to [[replay attack]]s: For example, by jamming the channel while intercepting the code, a thief can obtain a code that may still be usable at a later stage.<ref>[http://people.scs.carleton.ca/~barbeau/Honours/Spencer_Whyte.pdf Analysis of RF Remote Security Using Software Defined Radio]</ref> This sort of "code grabber,"<ref>http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2075&param=en001022#P108_5361 stating, "It is a simple matter to build a circuit to record such transmissions for reply at the later time. Such a system is known as a code or key grabber."</ref> while theoretically interesting, does not appear to be widely used by car thieves.<ref>http://www.snopes.com/autos/techno/lockcode.asp</ref>

A detailed description of an inexpensive prototype device designed and built by [[Samy Kamkar]] to exploit this technique appeared in 2015.  The device about the size of a wallet could be concealed on or near a locked vehicle to capture a single keyless entry code to be used at a later time to unlock the vehicle.  The device transmits a jamming signal to block the vehicle's reception of rolling code signals from the owner's fob, while recording these signals from both of his two attempts needed to unlock the vehicle.  The recorded first code is forwarded to the vehicle only when the owner makes the second attempt, while the recorded second code is retained for future use.<ref name="RollinCode">{{cite news | title=A hacker made a $30 gadget that can unlock many cars that have keyless entry | url=http://www.techinsider.io/samy-kamkar-keyless-entry-car-hack-2015-8 | work=[[Tech Insider]] | first=Cadie | last=Thompson | date=2015-08-06 | accessdate=2015-08-11}}</ref>  A demonstration was announced for [[DEF CON]] 23.<ref name="DC23">{{cite web | title=Drive It Like You Hacked It: New Attacks and Tools to Wirelessly Steal Cars | url=https://www.defcon.org/html/defcon-23/dc-23-speakers.html#Kamkar | work=[[DEF CON]] 23 | first=Samy | last=Kamkar | date=2015-08-07 | accessdate=2015-08-11}}</ref>

===Cryptanalysis===
[[File:Декодировка.png|thumb|KeeLoq Decryption]]
KeeLoq was first [[cryptanalysis|cryptanalyzed]] by Andrey Bogdanov using sliding techniques and efficient [[linear approximation]]s. [[Nicolas Courtois]] attacked KeeLoq using sliding and algebraic methods. The attacks by Bogdanov and Courtois do not pose any threat to the actual implementations that seem to be much more vulnerable to simple [[brute force attack|brute-force]] of the [[key space (cryptography)|key space]] that is reduced in all the code-hopping implementations of the [[cipher]] known to date. Some KeeLoq "code grabbers" use [[Field-programmable gate array|FPGA]]-based devices to break KeeLoq-based keys by brute force within about two weeks due to the reduced key length in the real world implementations.{{Citation needed|date=November 2009}}

In 2007, researchers in the [[COSIC]] group at the university at [[Leuven]], [[Belgium]], (K.U.Leuven) in cooperation with colleagues from [[Israel]] found a new attack against the system.<ref>[http://www.cosic.esat.kuleuven.be/keeloq/ How To Steal Cars — A Practical Attack on KeeLoq<!-- Bot generated title -->]</ref>
Using the details of the algorithm that were leaked in 2006, the researchers started to analyze the weaknesses.  After determining the part of the key common to cars of a specific model, the unique bits of the key can be cracked with only sniffed communication between the key and the car.

Microchip introduced in 1996<ref>(Will be in Web archive backup later): [http://ww1.microchip.com/downloads/pr_archive/en/en013239.pdf a Microchip press release on Dec 11, 1996] Quote: "...HCS410 KEELOQ Code Hopping Transponder and Encoder..."</ref> a version of KeeLoq ICs which use a 60-bit seed. If a 60-bit seed is being used, an attacker would require approximately 100 days of processing on a dedicated parallel [[brute force attack]]ing machine before the system is broken.<ref>{{cite journal|url=http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf|title=Cryptanalysis of KeeLoq with COPACOBANA|publisher=SHARCS 2009 Conference|author1=Martin Novotny |author2=Timo Kasper |pages=159–164}}</ref>

===Side-channel attacks===
In March 2008, researchers from the Chair for Embedded Security of [[Ruhr University Bochum]], Germany, presented a [[Cryptanalysis#Partial breaks|complete break]] of remote keyless entry systems based on the KeeLoq RFID technology.<ref>[http://www.emsec.rub.de/keeloq A complete break of the KeeLoq access control system]</ref><ref name="Bochum">{{cite journal|url=http://eprint.iacr.org/2008/058.pdf|title=Physical Cryptanalysis of KeeLoq Code Hopping Applications|date=2008-02-29|accessdate=2009-03-22|publisher=Ruhr University of Bochum, Germany|author1=Thomas Eisenbarth |author2=Timo Kasper |author3=Amir Moradi |author4=Christof Paar |author5=Mahmoud Salmasizadeh |author6=Mohammad T. Manzuri Shalmani }}</ref> Their attack works on all known car and building access control systems that rely on the KeeLoq cipher.

The attack by the Bochum team allows recovering the secret cryptographic [[key (cryptography)|key]]s embedded in both the receiver and the remote control. It is based on measuring the electric power consumption of a device during an encryption. Applying what is called [[Side channel attack|side-channel analysis]] methods to the power traces, the researchers can extract the manufacturer key from the receivers, which can be regarded as a master key for generating valid keys for the remote controls of one particular manufacturer. Unlike the cryptanalytic attack described above which requires about 65536 chosen plaintext-ciphertext pairs and days of calculation on a PC to recover the key, the side-channel attack can also be applied to the so-called KeeLoq Code Hopping mode of operation (a.k.a. [[rolling code]]) that is widely used for keyless entry systems (cars, garages, buildings, etc.).

The most devastating practical consequence of the side-channel analysis is an attack in which an attacker, having previously learned the system's master key, can clone any legitimate encoder by intercepting only two messages from this encoder from a distance of up to {{Convert|100|m|ft}}.  Another attack allows one to reset the internal counter of the receiver (garage door, car door, etc.), which makes it impossible for a legitimate user to open the door.<ref name="Kasper">{{cite thesis| type=Ph.D.| url=http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/KasperTimo/diss.pdf| title=Security Analysis of Pervasive Wireless Devices—Physical and Protocol Attacks in Practice| date=November 2012| accessdate=2015-08-11|publisher=[[Ruhr University Bochum]], Germany| first=Timo| last=Kasper}}</ref>

==References==
{{Reflist|32em}}

==External links==
*[https://www.microchip.com/keeloq Microchip KeeLoq site]
*[http://ww1.microchip.com/downloads/en/AppNotes/00001683A.pdf Introduction to Ultimate KeeLoq Technology]
*[http://ww1.microchip.com/downloads/en/devicedoc/40209c.pdf HCSXXX Encoder Family - Product Information]
*[http://ww1.microchip.com/downloads/en/DeviceDoc/00001577a.pdf Ultimate KeeLoq Technology,the Next Generation of Security - Featuring MCS3142 Dual KeeLoq Encoder]
*{{cite web|url=http://keeloq.narod.ru/decryption.pdf |title=KeeLoq decryption algorithm specification |url-status=live |archiveurl=https://web.archive.org/web/20070423090909/http://www.keeloq.boom.ru/decryption.pdf |archivedate=2007-04-23 }} 
*[https://web.archive.org/web/20120722105616/http://cryptolib.com/ciphers/keeloq/ C source code by Ruptor] 
*{{citation |url=http://eprint.iacr.org/2007/055 |first=Andrey |last=Bogdanov |title=Cryptanalysis of the KeeLoq block cipher |conference=Information Security and Cryptology: Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers |location=Xining, China |date=August 31 – September 5, 2007}} [https://books.google.com/books?id=siMz55bNnu4C].
*[http://eprint.iacr.org/2007/062 N.T. Courtois and G.V. Bard, 'Algebraic and Slide Attacks on KeeLoq']
*{{cite web |url= http://www.crypto.rub.de/imperia/md/content/projects/keeloq/keeloq_en.pdf |title= University of Bochum / HGI press release on the complete break of KeeLoq based entry systems }}{{dead link|date=December 2017 |bot=InternetArchiveBot |fix-attempted=yes }}
*[http://eprint.iacr.org/2008/058 Physical Cryptanalysis of KeeLoq code-hopping applications]

{{Microchip Technology}}
{{Cryptography navbox | block}}

[[Category:Block ciphers]]
[[Category:Broken block ciphers]]
[[Category:Automotive technology tradenames]]
[[Category:Radio electronics]]
[[Category:Vehicle security systems]]
[[Category:Microchip Technology hardware]]
[[Category:Garage door openers]]