×

A practical attack on KeeLoq. (English) Zbl 1279.94049

Summary: KeeLoq is a lightweight block cipher with a 32-bit block size and a 64-bit key. Despite its short key size, it is used in remote keyless entry systems and other wireless authentication applications. For example, there are indications that authentication protocols based on KeeLoq are used, or were used by various car manufacturers in anti-theft mechanisms. This paper presents 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 principle of slide attacks and a novel approach to meet-in-the-middle attacks.
We investigated the way KeeLoq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. In some scenarios the adversary may even reveal the master secret used in an entire class of devices from attacking a single device. Our attack has been fully implemented. We have built a device that can obtain the data required for the attack in less than 100 minutes, and our software experiments show that, given the data, the key can be found in 7.8 days of calculations on 64 CPU cores.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] W. Aerts, Application specificities of array antennas: satellite communication and electromagnetic side channel analysis, Ph.D. thesis, K.U. Leuven (2009)
[2] G. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields with applications to cryptanalysis, Ph.D. thesis, Department of Mathematics, University of Maryland, College Park (2007)
[3] Biham, E., New types of cryptanalytic attacks using related keys, J. Cryptol., 1, 4, 229-246 (1994) · Zbl 0812.94012
[4] Biham, E., A fast new DES implementation in software, Proceedings of Fast Software Encryption’97, 260-272 (1997), Berlin: Springer, Berlin · Zbl 1385.94014
[5] Biryukov, A.; Mukhopadhyay, S.; Sarkar, P., Improved time-memory tradeoffs with multiple data, Proceedings of Selected Areas in Cryptography 2005, 245-260 (2006), Berlin: Springer, Berlin
[6] Biryukov, A.; Wagner, D., Slide attacks, Proceedings of Fast Software Encryption’99, 245-259 (1999), Berlin: Springer, Berlin · Zbl 0942.94020
[7] Biryukov, A.; Wagner, D., Advanced slide attacks, Advances in Cryptology, Proceedings of EUROCRYPT 2000, 586-606 (2000), Berlin: Springer, Berlin · Zbl 1082.94506
[8] A. Bogdanov, Cryptanalysis of the KeeLoq block cipher, Cryptology ePrint Archive, Report 2007/055, 16 February 2007, http://eprint.iacr.org/2007/055/
[9] A. Bogdanov, Attacks on the KeeLoq block cipher and authentication systems, in 3rd Conference on RFID Security 2007 (RFIDSec 2007), available online at http://rfidsec07.etsit.uma.es/slides/papers/paper-22.pdf
[10] Bogdanov, A., Linear slide attacks on the KeeLoq block cipher, Proceedings of Inscrypt 2007, 66-80 (2008), Berlin: Springer, Berlin · Zbl 1166.94304
[11] N.T. Courtois, G.V. Bard, Algebraic and slide attacks on KeeLoq, Cryptology ePrint Archive, Report 2007/062, 8 May 2007, http://eprint.iacr.org/2007/062/
[12] N.T. Courtois, personal communication, 31 May 2007
[13] Courtois, N. T.; Bard, G. V.; Wagner, D., Algebraic and slide attacks on KeeLoq, Proceedings of Fast Software Encryption 2008, 97-115 (2008), Berlin: Springer, Berlin · Zbl 1154.68388
[14] Courtois, N. T.; Bard, G. V.; Bogdanov, A., Periodic ciphers with small blocks and cryptanalysis of KeeLoq, Tatra Mt. Math. Publ., 41, 167-188 (2008) · Zbl 1240.94059
[15] N.T. Courtois, Self-similarity attacks on block ciphers and application to KeeLoq. International Workshop on Coding and Cryptography (WCC 2009) (2009) · Zbl 1285.94051
[16] Eisenbarth, T.; Kasper, T.; Moradi, A.; Paar, C.; Salmasizadeh, M.; Manzuri Shalmani, M. T., On the power of power analysis in the real world: a complete break of the KeeLoq code hopping scheme, Advances in Cryptology, Proceedings of CRYPTO 2008, 203-220 (2008), Berlin: Springer, Berlin · Zbl 1183.94032
[17] Furuya, S., Slide attacks with a known-plaintext cryptanalysis, Proceedings of Information and Communication Security 2001, 214-225 (2002), Berlin: Springer, Berlin · Zbl 0994.68594
[18] Hellman, M. E., A cryptanalytic time-memory trade-off, IEEE Trans. Inform. Theory, 26, 401-406 (1980) · Zbl 0436.94016 · doi:10.1109/TIT.1980.1056220
[19] Kasper, M.; Kasper, T.; Moradi, A.; Paar, C., Breaking KeeLoq in a flash: on extracting keys at lightning speed, Proceedings of AFRICACRYPT 2009, 403-420 (2009), Berlin: Springer, Berlin
[20] Kumar, S.; Paar, C.; Pelzl, J.; Pfeiffer, G.; Schimmler, M., Breaking ciphers with COPACOBANA—a cost-optimized parallel code breaker, Proceedings of Cryptographic Hardware and Embedded Systems 2006, 101-118 (2006), Berlin: Springer, Berlin
[21] Microchip Technology Inc. KeeLoq^® authentication products, http://www.microchip.com/keeloq/
[22] Microchip Technology Inc., HCS410 KeeLoq^® code hopping encoder and transponder data sheet, http://ww1.microchip.com/downloads/en/DeviceDoc/40158e.pdf
[23] Microchip Technology Inc., AN642: code hopping decoder using a PIC16C56, http://www.keeloq.boom.ru/decryption.pdf
[24] Microchip Technology Inc., TB001: secure learning RKE systems using KeeLoq encoders, http://ww1.microchip.com/downloads/en/AppNotes/91000a.pdf
[25] Osvik, D. A., Speeding up serpent, The Third Advanced Encryption Standard Candidate Conference, 317-329 (2000)
[26] Paar, C.; Eisenbarth, T.; Kasper, M.; Kasper, T.; Moradi, A., KeeLoq and side-channel analysis-evolution of an attack, Fault Diagnosis and Tolerance in Cryptography (FDTC 2009), 65-69 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.