Abstract:

KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit
key. Despite its short key size, it is widely used in remote keyless entry
systems and other wireless authentication applications. For example,
authentication protocols based on KeeLoq are used by various car
manufacturers in anti-theft mechanisms.

In this talk, we present a practical key recovery attack against KeeLoq that 
requires 2^{16} known plaintexts and has a time complexity of 2^{44.5} KeeLoq 
encryptions. It is based on the slide attack and a novel approach to 
meet-in-the-middle attacks. The fully implemented attack requires 65 minutes to 
obtain the required data and 7.8 days of calculations on 64 CPU cores. A 
variant which requires 2^{16} chosen plaintexts needs only 3.4 days on 64 CPU 
cores. Using only 10,000 euro, an attacker can purchase a cluster of 50 dual 
core computers that will find the secret key in about two days. We investigated 
the way KeeLoq is used in practice and conclude that our attack can be used to 
subvert the security of real systems.

This is a joint work with Eli Biham, Sebastiaan Indeestege, Nathan Keller, 
and Bart Preneel.