KeeloQ

Summary

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

Requirements

• Basic knowledge 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 counted 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 or analyze 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

• microchip. Keeloq R decryption routines in c tb041. microchip.https://www.microchip.com
• Nicolas T. Courtois, Gregory V. Bard, and David Wagner. Algebraic and slide attacks on keeloq. In Kaisa Nyberg, editor, Fast Software Encryption, pages 97{115, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
• Thomas Eisenbarth, Timo Kasper, Amir Moradi, Christof Paar, Mahmoud Salmasizadeh, and Mohammad T. Manzuri Shalmani. On the power of power analysis in the real world: A complete break of the keeloq code hopping scheme. In David Wagner, editor, dvances in Cryptology { CRYPTO 2008, pages 203{220, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
• Sebastiaan Indesteege, Nathan Keller, Orr Dunkelman, Eli Biham, and Bart Preneel. A practical attack on keeloq. In Nigel Smart, editor, Advances in Cryptology { EUROCRYPT 2008, pages 1{18, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg
• C. Paar, T. Eisenbarth, M. Kasper, T. Kasper, and A. Moradi. Keeloq and side-channel analysis-evolution of an attack. In 2009 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), pages 65{69, Sep. 2009.
• Orr Dunkelman Eli Biham Sebastiaan Indesteege, Nathan Keller and Bart Preneel. A practical attack on keeloq. Computer Science Department, Technion. Haifa 32000, Israel, 8(1):1{18, Oktober 2008.
• Christof Paar Thomas Eisenbarth, Timo Kasper. Sicherheit moderner funkt?ur?o�nersysteme. Datenschutz und Datensicherheit, 28(1):508{510, Oktober 2008.
• Nicolas T. CourtoisGregory V. BardDavid Wagner. Algebraic and Slide Attacks on KeeLoq. International Workshop on Fast Software Encryption. Springer-Verlag Berlin Heidelberg 2008, 2008.