Talk:KeeLoq

Error in the pictures

Can someone please correct the pictures in a nice way? I am currently traveling, don't have the time to do it. Bit 16 is supposed to be added linearly during encryption and bit 15 during decryption (see my C source code or the official documentation). I apologise for this error. Ruptor 09:22, 6 June 2007 (UTC)

There's another error in the pictures. The first input bit to the NLF is supposed to be bit 1 instead of bit 2 of the NLFSR in encryption, and bit 0 instead of bit 1 in decryption. This error is also in your C source code. Sisyphos2000 21:48, 7 June 2007 (UTC)

I have fixed my source code. It's true. One of the bits was off. Ruptor 13:01, 7 September 2007 (UTC)

I have also fixed the pictures. Whoever edited them before had merely changed the font and the shape of the arrows, but forgot to fix the most important thing - the cipher structure. The new pictures match 100% my source code and the official decryption.pdf document. I apologize again for these errors. Ruptor 16:08, 15 October 2007 (UTC)

NLFSR

The NLFSR feedback function is 0x3A5C742E. What does this mean? --Abdull 10:36, 9 March 2007 (UTC)

It's F(a,b,c,d,e) = d ⊕ e ⊕ ac ⊕ ae ⊕ bc ⊕ be ⊕ cd ⊕ de ⊕ ade ⊕ ace ⊕ abd ⊕ abc. A binary function of N variables can be represented as a 2^N value where each bit in each position represents the value of the output and the position itself is the set of input bits. Basically, it's a 5-to-1 look-up table. See Nicolas Courtois paper for clarification. Ruptor 16:21, 9 March 2007 (UTC)

Security section

1. This section states There is no published cryptanalysis of the cipher but we then go on to link to a published paper which presents a cryptanalysis effective in 2⁵³ encryption operations. It is not practicable because it requires 2¹⁶ known plaintexts (a problem because KeeLoq is typically used at the rate of about 4 to 8 plaintexts per day, and further the plaintexts are not easily known), but it is most certainly a published cryptanalysis.
2. What is the source of the claim some of them use FPGA-based devices to break KeeLoq keys by brute force within about two weeks thanks to the short key length? The Courtois and Bard paper merely claims that FPGAs have been used (without giving their source for this claim), not that it can be done in two weeks. And I am a bit skeptical; 2⁶⁴ keys x 528 clocks/key = 9.7e21 clocks, and a fortnight = 1.2e6 seconds, giving 8.1e15 clocks/s. With typical actual clock rates in high end FPGAs being around 500 MHz, that means we require 1.6e7 physical implementations of the algorithm. To take a ballpark guesstimate, it can probably be done in about 100 gates, so we can fit about 2,000 implementations on a Virtex-4, so we need about 8,000 Virtex-4s, costing about USD $320,000. (Sanity check: compare to Deep Crack, a machine which averaged 2.5 days to break a cipher 256 times weaker, and cost $250,000 eight years ago; blindly applying Moore's Law and ignoring the fact that DES and KeeLoq have different computational complexity, that comes out to $285,000 to build a machine today which can crack 64 bit keys in 14 days. Check!) It's more-or-less doable, but I'm somewhat skeptical that car thieves are resorting to something like that -- even if my guesstimates are out by a factor of ten.
3. The line Individual "code hopping" implementations are often vulnerable to a replay attack exploited by jamming the channel while intercepting the code, should note the requirements for this attack to work with a typical KeeLoq protocol, because it requires the victim driver to perform a specific sequence of actions and he can avoid the attack if realises that this is happening. Specifically, if he just abandons his car after finding it won't unlock, he is hosed; but far more likely, he will unlock it with the physical key, and drive away. (Note that for many (most?) recent implementations, intercepting a "lock" signal when he first parks is useless, because usually signals are command specific and the thieves do not want to lock the car.) At that point, the thieves must follow him to the next destination closely enough to jam & intercept him again when he gets back out, because if he successfully relocks, unlocks or pops the trunk with KeeLoq at that point it will resynch and their stored intercept becomes useless. Finally, it should be noted that in general, all this attack allows is the ability to steal stuff off the seats; it won't enable you to start the engine, pop the trunk, open the glovebox (if locked), relock anything, or unlock more than once. That is probably the main reason no-one seems particularly concerned. -- 203.20.101.202 02:38, 21 March 2007 (UTC)

Dear anonymous coward from the Australian Defence Industries Electronics Division,

Dear Ruptor, you seem to have somehow mistaken my questions as personal attacks, because you have responded with a mixture of insults, dismissive statements and misrepresentations of my questions.

My sarcastic jokes imply that I took your questions as personal attacks? Right... Ruptor 14:53, 22 March 2007 (UTC)

I certainly don't want to offend anyone and if you re-read the above you will notice that they are largely requests for clarification on various issues, or address different points to those you defend. I hope we can come to some sort of cordial agreement. (By the way, the reason I used an identifiable IP instead of an anonymous WP account is that I have been on a long wiki-vacation, and can no longer recall my account password unless I happen to have my passwords notebook with me! BTW2, I presume "Australian Defence Industries Electronics Division" is a result of a reverse DNS + whois, if so: cool bizarre! Not only am I not in "Australian Defence Industries Electronics Division", I'm not in anyone's Electronics Division. Maybe somehow I am surfing anonymously!) -- 203.20.101.202

Excuses excuses... ;-) Ruptor 14:53, 22 March 2007 (UTC)

1. The article stated "no published cryptanalysis" way before Nicolas Courtois analysed the cipher.

Ok, I was just wondering why someone added the link to the paper without touching the claim that there was no cryptanalysis. I guess it was an oversight. Thanks for making the update. -- 203.20.101.202

His failure to break the cipher with algebraic attacks does not mean that the cipher is secure. As a general purpose cipher, it cannot be accepted unless it survives all kinds of attacks and even at the first glance it looks vulnerable to slide attacks. But you are right, the section needs to be corrected of course.

I wouldn't say at all that his attack failed. It achieves a work factor less than brute force and hence must be considered at least a certificational attack. Yes, KeeLoq is definitively unsuitable as a general purpose cipher -- even without knowing anything else about it, the short 32 bit block is a "No". However, in the very specific case of the application for which it was designed, codebook attacks on the short blocks are irrelevant, and the Courtois/Bard attack is mildly worrying but a long way from fatal. At present this attack simply cannot be applied in practice; but it remains a concern because "attacks only get better, they never get worse". -- 203.20.101.202

2. What you are describing there about 64-bit keys could be close to some version of the truth, at least the way you see it. I am not going to argue or try to verify your numbers,

Erm, I do not want you to argue or verify my numbers, which are only ballpark guesstimates. My point #2 was asking the author of the numbers in the article to verify theirs. I presented my numbers with the intention of showing that this was a reasonable request and not just being obnoxious. -- 203.20.101.202

but if you cared to study the chip specification in detail (the link is provided)

I have studied the chip(s) specs in detail, for the wide range of products. And no, no link was provided; several levels of navigation are required to get from Microchip's front page to the specs! -- 203.20.101.202

and other supporting documents that are quite easy to find on google, you would see that the secret keys in use are far from 64 bits. The key space in the actual implementations is split on parts, some of which are common to large groups of keys, at least by the same manufacturer, and thus are known to the attackers. I hope that explains the two weeks to you.

Ok, this is an interesting and relevant response to my query. If this is the case, we could certainly amend the current text (which clearly suggests that the entire 2⁶⁴ keyspace is swept in two weeks) to state that the attack is against reduced keyspaces. However, I would also note that if this is the case, it is sort-of in violation to the KeeLoq specs, which recommend (but do not require) that device keys are to be generated by encrypting the device serial number with a "key generation algorithm", under a manufacturer's secret master key (actually, product family key). This is a fairly standard key diversification scheme, and is secure provided the KGA meets certain reasonable properties (one-wayness, reasonably well distributed outputs) and the master key remains secret. If the OEM's product family key does not remain secret, no-one needs any FPGAs to break in; that product family is totally fscked. -- 203.20.101.202

3. Now if on your planet the thieves come forward and admit such things publicly, can I get a visa to move there?

Sure, my planet welcomes visitors 8^). However, the thieves here also tell lies to conceal their real methods 8^(. -- 203.20.101.202

You can rephrase that line yourself if you like by calling it rumours, but the Russian thieves do successfully break KeeLoq-based keys from a couple of responses within two weeks. At least that's what they say in their not so public forums where the first emulators appeared. My source code is derived from one of theirs, just optimising it a bit, although a bitslice implementation would have been faster of course.

There are a range of possible interpretations to such a claim from a thief, from "it's literally true", through "they're exaggerating, it was a 100:1 fluke to get it so fast, usually they give up after a few months", through "they're lying to camouflage they fact they've got a spy in the factory feeding them OEM family keys", and on down to "they're lying, when the box arrives it will be full of obsolete cell phone innards and an instruction manual written in Glagolitic." -- 203.20.101.202

4. Please, feel free to enlighten us from your obvious experience in preventing replay attacks. If you haven't seen yet, those devices are available for sale online. They work quite nicely exploiting the serious flaws in the protocol (again, according to the same thieves who just as you wish to remain anonymous for some reason).

I do not claim otherwise. The KeeLoq protocol is clearly vulnerable to jam-intercept-and-replay (JIR) attacks; in fact the specs even acknowledge this, and it seems reasonably obvious why the designers made the compromise. My point #3 is not that the attack is infeasible, but that to be effective it requires particular actions to be performed in the right sequence, and if a car owner is aware of these he might recognise that an attack is underway and be able to prevent it. -- 203.20.101.202

Most people simply press the button the second time when the car refuses to beep and get on with their business while the happy thieves reuse the second intercepted code

It's slightly more complicated than that. If the user presses the button a 2nd time, either the function now works, or it doesn't. If it works because his new codeword got through then the thieves have lost synch and their intercepted codeword(s) is/are useless. If it works because the thieves retransmit the codeword they intercepted then, once again, they lose synch and have wasted their time. If it doesn't work then the user cannot get on with his business; he is either unable to enter his car (if he was trying to unlock), or apparently obliged to abandon it unlocked (if he was trying to lock it.) He may well continue to fiddle with the remote for a while but eventually it will either work (and desynch the thieves) or he is going to try something else: either call for roadside assistance to move the car a few hundred metres before trying again (since accidental EMI is the most common cause of this scenario) or more likely use the physical, metal key to override the key fob control. This is the "key" point which makes the JIR attack possible: if he uses the metal key, he can lock/unlock the car but does not resynch KeeLoq in the process. So, having got all the way down to here, there are two possibilities, depending on whether he was trying to get in or out of the car: the thieves have a valid "unlock" codeword, but the owner is now driving away; or the car has been left locked in front of them, and they have a valid "lock" codeword -- not useful unless the implementors stuffed up and allow a lock command to toggle state. So to sum up: if the target car contains the implementation error of allowing a "lock" command to "unlock", then the JIR attack can work by blocking KeeLoq commands from someone trying to park his car, then waiting for him to lock up with the metal key and walk away; if this implementation flaw is not present, then the attackers need to block and intercept commands at one location, follow the car as it drives away, then block commands again at the second location before trying their replay. If, at any point (e.g. even en route between the two locations) the legitimate user gets one command through without issuing another that gets blocked and intercepted, then the attack fails. -- 203.20.101.202

(which is not command specific at least according to most of the specifications I've studied myself) to unlock the car. I suggest that you study the protocol. It is possible however, that some of the new implementations have corrected those flaws, but most remain vulnerable.

Sorry, but on this one you're quite mistaken. For all except the lowest level device (which does not use any encryption at all, and is not intended for security applications), the specs state that the transmitted data includes (among other things) a 4 bit "function code" transmitted once in the clear and again bound into the encrypted portion. The application notes suggest that each bit of the function code could be allocated to a button on a transmitter fob, but also specifically recommend that different function codes be used for "lock" and "unlock" commands rather than toggling. Some implementations indeed ignore this advice, and thus are vulnerable to a captured "lock" command being used as an "unlock" command. However in my experience those are all relatively old implementations. I do not claim to be any sort of expert on KeeLoq OEMs and could well be wrong here, but the newest examples I know of dates to about 1998 or 1999 -- bearing in mind that it didn't start to get widely deployed until about 1996 or so. (Back then most manufacturers were still using unencrypted fixed code remotes!) -- 203.20.101.202

Even with command specific codes, when the "lock" button doesn't work, any simple-minded user would just try pressing all the buttons thus sending at least one unlock code to the thief. People normally do that whenever their remote doesn't work. Even those who are educated on the security issues are not sly enough to try to trick an invisible attacker every time their remote doesn't work. Normal people have no guile and do not suffer from excessive paranoya to do that.

Quite possibly. Which is one reason it might be useful for our article to explain in detail how JIR works agaisnt KeeLoq, which was my suggestion. -- 203.20.101.202

Maybe someone can translate this interesting and very funny description of some practical implementations of this attack. Maybe it will clarify a thing or two... ;-) Ruptor 12:39, 30 June 2007 (UTC)

5. The thieves also steal the keys out of the pockets of course. I can introduce you to a friend of mine whose car was stolen recently that way - he was stupid enough to leave the key and the alarm remote in his jacket on the same keyring, take the jacket off in the cafeteria and put it on the chair he sat on. His car was returned a week later though thanks to his connections. Adding fingerprint scanning is of no use either, since the fingerprint is right there on the door handle, on the steering wheel and generally all over the car's interior, and all the other biometric methods are quite frankly not robust enough. And even if they were, their use would do nothing but increase the violence of the less intelligent of the car thieves by leaving them no choice but to start cutting body parts off and forcing people to start the car at a gun point or plain hijacking the driver along with the car more often. Did you really want to discuss security or were you just showing off?

This is true and interesting but not really relevant to a discussion of the protocol and only peripherally to its implementations. If you want to be thorough you could add that any system using a cryptographic token may be vulnerable to physical theft of the token, or coercion. -- 203.20.101.202

6. You know, you really did not have to go through so much trouble writing all this here complaining to us about inconsistencies in the article and could have just improved it yourself, mate. No worries! We wouldn't abuse you too much for it. ;-) Ruptor 17:39, 21 March 2007 (UTC)

You're right, I could have just stamped {{fact}} on the bits I wanted to query, but I consider that a pretty obnoxious thing to do without first discussing it. -- 203.20.101.202

Is that the only other solution you see? Seriously, mate, I thought we were all here to contribute... Why don't you just improve the article? A lot of what you wrote here could seriously improve the remote keyless system, hopping code and even the KeeLoq article itself. You could just add all those things there and correct the articles to make them better. I promise I wouldn't take offense if you edited out anything I wrote there, even if I tried to bring it back worded better. I am also no wiki policeman, I don't care for vandalism or obnoxious {{facts}}. There is enough people to do it. I just see no point in our questions or in our answers here, so I was picking on you, maybe a little too much. If you want me to start taking any of this seriously, I can't, I'm sorry. I only take seriously positive contribution to the articles. Security or who is right and who is wrong is something we can all debate forever, there is no end to that. Ruptor 14:53, 22 March 2007 (UTC)

PS: Hi, Joey! I apologise for my sarcastic jokes. Didn't mean to be offensive. Ruptor 18:13, 21 March 2007 (UTC)

Erm, who is Joey? -- 203.20.101.202 05:39, 22 March 2007 (UTC)

You are. You didn't have a name, so I gave you one. Ruptor 14:53, 22 March 2007 (UTC)

Is there a list of car makes/models that use the KeeLoq system?

Is there a list of car makes/models that use the KeeLoq system?

The Wired article Researchers Crack KeeLoq Code for Car Keys states that Honda, Ford, General Motors, Mercedes Benz and Jaguar use this system. Many readers, such as myself, are curious as to whether cars that I own (or cars owned by my family members) use this system, so that we may evaluate the risks of using the remote keyless entry and other advanced car-features. —Preceding unsigned comment added by 128.173.14.24 (talk) 17:37, 4 September 2007 (UTC)

Algorithm incorrect

Hello, I am employed in a position where I work with KEELOQ on a daily basis. In response to claims from Bogandov, et, al. In the interests of security concerns from customers and shareholders I have been assigned to a project to test the so-called "slide attack" on real-world KEELOQ applications. I have been working on this since late 2008.

The first thing I did was take Ruptor's code and compile it in Borland C++ 5.0.2. Ruptor's code, which is directly derived from the drawings on this wikipedia article, does not generate the correct cryptographic output. The code I myself wrote in C, however, does, as I am decrypting the output of my own RKE products, on a PC, and correctly so. Ruptor's code, whilst appearing correct on the surface, generates different decrypted data for the same key and same encrypted input and is therefore of no value to me.

I have also examined the encoder chip itself and tried various attacks on the HCS301 encoder, which has not yielded much results, except in that I can prevent overwriting of the encryption key using controlled power glitches, but I am powerless to prevent mass erasure, so it is reasonable to conclude that, sort of deep probing the chip surface, the HCS301 is secure enough on its own.

Miyukisan782 (talk) 07:16, 25 February 2009 (UTC)

Thanks for the update - please let us know if you publish your results so that we can reference them here. Failing that, your input must unfortunately be treated as OR. Socrates2008 (Talk) 07:25, 25 February 2009 (UTC)

KeeLoq 3?

Just an observation, but it seems as though this article may have a POV or at least does not give the full story, in that it says nothing about Keeloq 3 technology —Preceding unsigned comment added by 12.231.151.254 (talk) 14:45, 7 October 2009 (UTC)

Keeloq implementation for Atmel microcontrollers

Hi, some time ago I developed an implementation of KeeLoq in C and in assembly language of Atmel microcontroller (much faster than C on the 8-bit MCUs) and also routines in C language which implement the wireless receive/transmit according to the KeeLoq datasheet, and also the programming of HCS Keeloq chips. I published this code recently under GPL and I thought it might be useful for people interested in Keeloq (since google did not reveal anything equivalent), so I added here an external link (http://www.pittnerovi.com/jiri/hobby/electronics/keeloq/index.html). However, somebody removed it quickly as "spam". I never contributed to wiki before, so I wonder what is wrong with such a link, which in my opinion leads to a bigger amount of useful and relevant information than for example the existing external link to Ruptor's implementation in C.

Jiri —Preceding unsigned comment added by 147.231.28.95 (talk) 15:18, 20 October 2009 (UTC)

How to properly exploit the replay attack

Let's say you want to open a garage door without the knowledge and consent of the owner. You set up listening equipment aimed at the location where the owner will be when locking the garage. And you set up a jamming device aimed at the receiver of the garage door opener, such that it will not jam your listening equipment. So he tries to close the door. If you choose to jam all his attempts to close the door, the owner may get suspicious. If you only jam the first attempt and let him close the door on the second attempt, the receiver will no longer recognize the first code you intercepted. Neither of these situations are ideal.

The trick is:

1. The owner tries to close the door. Jam it and intercept the code
2. The owner tries again to close the door. Jam it again and intercept the code. Immediately close the door by replaying the first code you intercepted.
3. When the owner leaves, use the second code to open the door.

-- Nic Roets (talk) 20:14, 1 January 2014 (UTC)

However, after reading part of the above discussion, I'm starting to think that the replay attack can be eliminated if the opener has separate lock and unlock circuits and the receiver can signal it's state to the owner. For example:

1. The KeeLoq receiver has an LED display indicating it's last action (lock / unlock).
2. The owner will not use the lock button if the LED indicates it's already locked.
3. The owner will not use the unlock button if the LED indicates it's already unlocked.
4. If the door does not respond (due to jamming or otherwise) the owner may retry a few times. When he gives up, he should disable the receiver (e.g. engage manual mode using a key). He may temporarily reenable the receiver at a later stage, but only in order to retry the failed action. The receiver may only be permanently reenabled once the failed action has succeeded.

-- Nic Roets (talk) 18:27, 2 January 2014 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on KeeLoq. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

• Added archive https://web.archive.org/20120722105616/http://cryptolib.com/ciphers/keeloq/ to http://cryptolib.com/ciphers/keeloq

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 12:05, 19 February 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on KeeLoq. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070423090909/http://www.keeloq.boom.ru:80/decryption.pdf to http://www.keeloq.boom.ru/decryption.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:03, 31 December 2016 (UTC)