1

Note: This question is follow-on from comments on this answer that were broad enough to be a separate question.

As far as I understand, KeeLoq is a block cipher designed for use in the automotive industry, specifically for keyless entry systems where one master receiver (the car?) needs to be able to register and authenticate transmitters (key fobs) in the field.

Re-quoting manufacturer documentation from the linked answer:

The Normal key generation scheme is the common key generation scheme for KEELOQ technology systems. During Normal Learn, a master key is used (known as the “manufacturer code”). When using the normal learning mechanism, the decoder uses the manufacturer code and the serial number to calculate the decryption key for each transmitter. Using the serial number of each encoder and the manufacturer code, the unique encryption key for each encoder is calculated. The encoder stores only the serial number and the calculated encryption key. The decoder needs to be programmed with this manufacturer code in order to be able to calculate individual encryption keys.

So my question is: how does this cipher work? More specifically:

  • How is a derived key calculated from the master key and serial number?
  • Serial number of what? Does the receiver need to be told the serial number of each key fob that it is paired with?
  • Any other details that make KeeLoq unique and interesting.

I am aware of wikipedia/KeyLoq, but it's a bit of a stub article.

  • @Zeke, here's the follow-on question. Pressure's on to provide a good answer ;) – Mike Ounsworth Feb 4 at 17:12
  • 2
    Isn't is broken? Algebraic and Slide Attacks on KeeLoq – kelalaka Feb 4 at 18:35
  • 1
    @kelalaka it is but this question is about how keeloq works. – silverduck Feb 4 at 22:19
  • @Zeke yes, But I want to add it FYI. The AES versions are secure AFAIK – kelalaka Feb 4 at 22:25
  • 2
    @kelalaka yes I know :) I'll be sure to put up the common warnings. Don't use KeeLoq because it's very broken and should not be used to secure anything, don't roll your own crypto, this is only for academic understanding, etc... – silverduck Feb 4 at 22:51
2

how does this cipher work?

Assuming you are talking about the classic (broken) algorithm, KeeLoq is a 528-round block cipher utilizing a 32-bit non-linear feedback shift register (NLFSR) and 64-bit circular shift register (the key register, initialized with the key data). It has a 32-bit block size and takes a 64-bit key. Below is a diagram of a single KeeLoq encryption round, showing the NLFSR and key register:

KeeLoq cipher schematic

How is a derived key calculated from the master key and serial number?

The key is derived from the seed, a more-or-less random value usually including bits from the non-secret serial number and some padding, and the hardcoded master key. Depending on the version of the protocol, the key may be derived either by directly XORing the master key and the seed, or by decrypting the first and second half of the seed with the master key using the KeeLoq algorithm itself:

xor decrypt

The seed, depending on the version, may contain 0, 32, 48, or 60 random bits. This seed is shared out-of-band with the remote when it is programmed during the "learning" process. If the manufacturer key is known, then decryption is as easy as brute forcing the seed which, as mentioned, contains anywhere from 0 to 60 bits. However, according to this paper, where much of the above information was found, all ICs analyzed by Eisenbarth et al. used a seed composed of only the serial number, with no random bits. As a result, the key used by those ICs is based only on the hardcoded manufacturer key with the unique per-device serial number, making theft of that key sufficient to decrypt communications.

Section 2.2 of another paper goes into more detail about the key derivation scheme.

Serial number of what? Does the receiver need to be told the serial number of each key fob that it is paired with?

The serial number is that of the remote. It is encoded in plaintext with every transmitted packet. The receiver obtains the serial number each time a button on the remote is pressed. Below is a diagram of the 66-bit packet used by the protocol showing the 28-bit serial number being transmitted in plaintext:

packet structure

  • Where does 8 come from? In the pdf you reference it states "There are 3 possible random seed lengths: 32, 48 or 60 bits" – silverduck Feb 5 at 19:50
  • I was going to post my own answer but it looks like you beat me to it. I could elaborate but I feel like that would belong on the cryptography stack exchange. – silverduck Feb 5 at 22:25
  • @silverduck It was supposed to be a 0. Not sure how an 8 got in there. – forest Feb 6 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.