How does the KeeLoq block cipher work?

Question

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.

Answer 1

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:

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:

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: