Cryptanalysis of KeeLoq with COPACOBANA

Martin Novotny, Timo Kasper

Special-purpose Hardware for Attacking Cryptographic Systems 2009, SHARCS 2009, Lausanne, Switzerland. September 9-10, 2009.


Abstract

Many real-world car door systems and garage openers are based on the KeeLoq cipher. Recently, the block cipher has been extensively studied. Several attacks have been published, including a complete break of a KeeLoq access control system. It is possible to instantly override the security of all KeeLoq code-hopping schemes in which the secret key of a remote-control is derived from its serial number. The latter can be intercepted from the communication between a receiver and a transmitter. In contrast, if a random SEED is used for the key derivation, the cryptanalysis demands for higher computation power and may become infeasible with a standard PC. In this paper we develop a hardware architecture for the cryptanalysis of KeeLoq. Our brute-force attack, implemented on the Cost-Optimized Parallel Code-Breaker COPACOBANA, is able to reveal the secret key of a remote control in less than 0.5 seconds if a 32-bit seed is used and in less than 6 hours in case of a 48-bit seed. To obtain reasonable cryptographic strength against this type of attack, a 60-bit seed has to be used, for which COPACOBANA needs in the worst case about 1011 days for the key recovery. However, the attack is arbitrarily parallelizable and could thus be run on multiple COPACOBANAs to decrease the attack time.

[pdf] [bib]

tags: