KeeloQ

Summary

This article provides an overview of KeeloQ and three popular attacks.

Requirements

• Basic knwoledge of blockcipher

Description

KeeloQ

KeeloQ is used for access authorization in electronic access systems, distributed by Microchip Technology Inc. The system consists of a sender and a receiver, like a car remote key and a car. In order to get access with the remote key, the receiver must first learn about the remote key. To perform the registration process, the sender has a unique serial number and secret key and the receiver has a secret manufacturer key. This process can be described as followed:

• 1) The sender sends his serial number in plaintext to the receiver
• 2) The receiver’s secret manufacturer key will then be used for the encryption of the serial number.
• 3) The decrypt the message, the sender’s secret key works as a pair to the manufacturer key. From this point on, the sender’s key is used to encrypt and decrypt the messages.

Encrypted 32-bit blocks are used for communication. Each block contains a code for a specific action. As these codes remain unchanged during a communication, every encrypted message would technically be identical. To prevent this behavior, the hopping code algorithm is used.

The hopping code adds a counter to the encrypted messages. When the receiver decrypts a message, the counter is read. If the received counter, is a number within a range of 16 values difference from the last received counter, the action is executed.

To ensure that the received message is from the same remote key and is not a resent message from someone else, the friend or foe algorithm is used. This algorithm is a challenge response algorithm. To verify the remote key, the receiver first sends a message in plaintext to the sender. The sender encrypts the message and sends it back. If the receiver can successfully decrypt the message, the remote key is verified.

KeeloQ is a block cipher that uses 64-bit keys on 32-bit plaintext blocks. To encrypt messages, KeeloQ uses a 64-bit long secret key on a 32-bit long plaintext message. The encryption process takes 5bits from the plaintext register and uses them to calculate a single bit with a nonlinear function. To create a single bit for an encrypted message, a nonlinear function is applied, that XORs with one bit from the key, and two bits from the plaintext register. After that, the plaintext register, and the key register are shifted one bit to the right. This process is repeated 527 more times to create one block of an encrypted message. To decrypt a message a similar routine is used.

Security Threats

Side channel

In this attack, a side channel is used to obtain the secret sender key. This side channel can be applied on the entirety of the hardware. Some side channel attacks measure the current consumption of a semiconductor chip through analyzing the emitting electromagnetic field.

Slide attack

This attack uses the weakness of the block cipher, that is the 528 cycles long process to decrypt or encrypt a message. With enough slide pairs, which is essentially plaintext and the matching encrypted text, the steps to get the encrypted message can be traced back to get the sender secret key.

Algebraic attack

In this approach the attacker tries to solve multivariate equations. These equations must be solved for every encryption step.

References

• https://www.microchip.com