Design of intelligent locks based on the triple KeeLoq algorithm

Abstract

KeeLoq algorithm with high security was usually used in wireless codec. Its security lack is indicated in this article according to the detailed rationale and the introduction of previous attack researches. Taking examples from Triple Data Encryption Standard algorithm, the triple KeeLoq codec algorithm was first proposed. Experimental results showed that the algorithm would not reduce powerful rolling effect and in consideration of limited computing power of embedded microcontroller three 64-bit keys were suitable to increase the crack difficulties and further improved its security. The method was applied to intelligent door access system for experimental verification. 16F690 extended Bluetooth or WiFi interface was employed to design the lock system on door. Key application was constructed on Android platform. The wireless communication between the lock on door and Android key application employed triple KeeLoq algorithm to ensure the higher security. Due to flexibility and multiformity (an Android key application with various keys) of software-based keys, the solution owned overwhelmed advantages of low cost, high security, humanity, and green environmental protection.

Introduction

The wireless encryption and decryption technology with low cost and high security was greatly promoted along with the development of codec algorithm and highly integrated circuit.^1,2 Due to low security, the market shares of chip with fixed codec ³ gradually decreased. Meanwhile, the rolling codec circuits with high security increasingly occupied the mainstream of the market.^4,5

The Microchip company possessed a series of dedicated integrated chips with rolling codec. The codec employing KeeLoq algorithm was packaged as a core of these chips. It was widely applied as car anti-theft alarm^1,2 and remote control garage. ⁵ KeeLoq was a positive nonlinear bit encryption algorithm, which could generate rolling code with high security. Each transmitted wireless code encoded by KeeLoq was unique, irregular, and non-repetitive. It contributed to preventing illegal capture and copy protect.

Although the KeeLoq algorithm was published in the 1980s, Bogdanov ⁶ first attacked it until 2007. Guess-decisions and sliding technology were used to perform the attack. The time complexity of the attack was 252, and the space complexity was 16 GB. Courtois et al. ⁷ proposed four kinds of sliding-algebraic methods in 2008. Replacement formed by 64 consecutive circle functions and the difference between random replacement and circle structure were employed to first attack 64-bit seed key. It needed computational complexity no less than O(243). Jianxiong et al. ⁸ put forward three various types of attacking methods based on byte-oriented differential fault in 2010. The best efficient attacking methods need 0.707617 error on average to recover 1-bit key. Just total of all 46 errors was adopted to recover 64-bit seed key. KeeLoq algorithm has achieved many effective attacks since it was published. Although the time complexity of attacks decreased dramatically, the attacks still needed much more space complexity, besides a certain number of given premises. These factors led to the high difficulty coefficient or actual password cracking. Therefore, its security was excellent enough to be applied in practice and few novel cracking methods were reported recently.

This article first discussed implementation of KeeLoq algorithm and further analyzed its defects. The improvement was put forward to enhance its security. Experimental simulation was performed to illuminate the rolling effects. Results were discussed to reveal its advantages in applicable scope. Finally, based on Bluetooth or WiFi wireless communication using KeeLoq codec, an intelligent key application on Android smart phone was designed. After the intelligent lock on door certificated the wireless ciphertext, it could perform opening door.

KeeLoq algorithm

KeeLoq operational rule

The core of KeeLoq algorithm was that the 32-bit plaintext on encipherer was encrypted by 64-bit seed key to be a 32-bit ciphertext. After the wireless transmission of the ciphertext, the receiver decrypted 32-bit ciphertext to be 32-bit plaintext using the same 64-bit seed key and then the user’s operation could be successfully performed. When the KeeLoq algorithm was executed, it needed a 32-bit data register to store 32-bit plaintext x_31-0 or 32-bit ciphertext y_31-0 and a 64-bit seed key register to store the 64-bit seed key k_63-0.

The KeeLoq data encryption process is shown in Figure 1. First, a nonlinear table was defined, which included 5-bit input code and 1-bit output code. A 5-bit input code including x31, x26, x20, x9, and x1 was intermittently extracted from the data register of 32-bit plaintext. A 1-bit output code was generated after equation (1) nonlinear logic function (NLF) operation. The 1-bit output code XORed x₁₆ and x₀ in the data register as well as k₀ in the key register generated 1-bit data encryption code. Subsequently, the key register circularly right shifted 1 bit, while the data register right shifted 1 bit and 1-bit output code appended on the head of the data register. The process repeated 528 times to generate 32-bit ciphertext

$$\begin{array}{c}\mathrm{NLF}(b_4,b_3,b_2,b_1,b_0)=b_4{b}_3{b}_2\oplus b_4{b}_3{b}_1\hfill \\ \oplus b_4{b}_2{b}_0\oplus b_4{b}_1{b}_0\oplus b_4{b}_2\oplus b_4{b}_0\oplus b_3{b}_2\hfill \\ \oplus b_3{b}_0\oplus b_2{b}_1\oplus b_1{b}_0\oplus b_1\oplus b_0\hfill \end{array}$$

(1)

Figure 1.

KeeLoq encryption model diagram.

Figure 2 describes KeeLoq data decryption process slightly different from encryption process. The 5-bit input code including y30, y25, y19, y8, and y0 was intermittently extracted from the data register of 32-bit ciphertext. A 1-bit output code was generated after equation (1) NLF operation. The 1-bit output code XORed y₃₁ and y₁₅ in the data register as well as k₁₅ in the key register generated 1-bit data encryption code. Subsequently, the key register circularly left shifted 1 bit, while the data register left shifted 1 bit and 1-bit output code appended on the rear of the data register. The process repeated 528 times to restore 32-bit plaintext.

Figure 2.

KeeLoq decryption model diagram.

KeeLoq implementation

KeeLoq was usually employed to realize wireless codec. The communication process must be carried out strictly in accordance with the following procedure. First, the encipherer and receiver needed a nonvolatile memory to store the 64-bit seed key (could be programmed and could not be sent or leaked in the process of encryption and decryption), 28-bit serial code (discriminated various encipherer), 16-bit synchronized counter (generated the rolling effect of encryption code, its value was increased by 1 after each data transmission), 10-bit identification code (the rear 10-bits of serial code), and 32-bit seed code (produced key under safe mode).

When user pressed a key on encipherer, KeeLoq encipherer assembled 4-bit function keys, 10-bit identification code, 16-bit synchronized counter, and 2-bit overflow as a 32-bit plaintext. It was encrypted to be 32-bit ciphertext according to the NLF operational rule in Figure 1. Affiliating 34-bit fixed code (28-bit serial code, 4-bit function keys, and 2-bit state bit), 66-bit encryption data were formed for transmission. Since synchronized counter was increased by 1 after each data transmission, the encrypted 32-bit ciphertext named as rolling code was unique, irregular, and non-repetitive. It could effectively prevent password capture and copy. It also could availably guard against password scanning because 66-bit binary ciphertext included $2^{66}=7.38\times {10}^{19}$ coding assembly.

After the receiver accepted the 66-bit ciphertext data, it matched the serial code of encipherer. If the match was successful, 32-bit plaintext would be recovered according to the NLF operational rule shown in Figure 2. Then, identification code and function keys in recovered plaintext would be extracted to match those in fixed code. If the match was successful, rational increments of synchronized counter would be estimated. Evaluation criteria were that the difference values of synchronized counter between encipherer and receiver were less than 4 and greater than zero. On condition that all rules are satisfied, the receiver would perform the corresponding executive action according to function keys.

Improvements and results

Improvements

Due to NLF operation rules of KeeLoq algorithm, output ciphertext data observably changed along with a small change in input plaintext data. It led to rolling effect of encryption code, which was difficult to observe and analyze the change of output ciphertext data for key crack. It endowed the KeeLoq algorithm with the advantage of high security. ⁴

The KeeLoq encryption algorithm belonged to 32-bit block cipher. Due to its short 64-bit seed key, KeeLoq algorithm has achieved above-mentioned effective attacks since it was published. In order to further enhance its security, the process of encryption and decryption would be improved in this article.

Because incensement of synchronized counter resulted in changes of plaintext data, each transmitted wireless code encoded by KeeLoq was unique, irregular, and non-repetitive. The characteristics contributed to preventing illegal capture and copy protect. Referencing to the core idea of 3DES (Triple Data Encryption Standard) algorithm, ⁹ the triple KeeLoq codec algorithm shown in Figure 3 was proposed to improve its security. Three different keys were employed in the process of encryption. According to the NLF coding process demonstrated in Figure 1, the plaintext, the first ciphertext, and the second ciphertext were encrypted, respectively, by three different keys and the ultimate 32-bit ciphertext was the output. Since data bits in the first ciphertext and second ciphertext changed more than the synchronized counter in plaintext, changes of data bits in the ultimate key became much more randomized. Compared with single encryption, it would need triple time complexity for a certain crack method, which could further ensure the security of the KeeLoq more effectively. The decryption process was inverse. In accordance with the decryption process shown in Figure 3, three corresponding keys were employed to decrypt the ultimate ciphertext, the second ciphertext, and the first ciphertext, respectively. After the 32-bit plaintext was output, the identification code, function key, and serial number were matched. Then, the corresponding executive action would be executed.

Figure 3.

Triple KeeLoq encryption diagram.

Experimental results

Based on NLF operation rules, a KeeLoq encryption executable program was designed on Visual C++ platform of PC. Typical groups of plaintext were chosen to be encrypted. The same hexadecimal value was assigned to KEY1, KEY2, and KEY3. Plaintext was encrypted after sequentially using these keys. The results of first ciphertext, second ciphertext, and third ciphertext are listed in Table 1. Amount of changed bits between the plaintext and each round ciphertext was counted to illustrate rolling effect after each encryption. It could be concluded that most amount of changed bits increased after two more encryption. It helped to produce powerful rolling effect. Although some cases maintained the same rate of change or changed faintly, triple KeeLoq encryption provided two more 64-bit keys to enhance crack difficulty. Thanks to three 64-bit keys, it needed $2^{192}\approx 6.277\times {10}^{57}$ times of crack attempt to triple KeeLoq encryption using brute force, which was much more than that of single KeeLoq encryption. The more and more bits of keys contributed to enhancing crack difficulty, but triple KeeLoq encryption with three 64-bit keys was an eclectic project in consideration of limited computing power of embedded microcontroller.

Table 1.

Each encryption of triple KeeLoq encryption.

Plaintext	KEY1/KEY2/KEY3	First ciphertext	Amount of changed bits	Second ciphertext	Amount of changed bits	Third ciphertext	Amount of changed bits
00000000	0123456789ABCDEF	0D326BF8	16	FC344AAA	16	BDEF865E	21
AAAAAAAA	0123456789ABCDEF	54E04EAE	15	E2FBD711	17	3F20352E	15
BBBBBBBB	0123456790ABCDEF	A2A68FB3	11	E68D1A66	18	E9983A01	13
01234567	0123456792ABCDEF	09029507	8	70D49556	17	E7359B9E	20
89ABCDEF	0123456793ABCDEF	BF4140EA	15	96F84674	18	4E048298	22
AAAA5555	0123456794ABCDEF	A6B1A63D	15	D409E8D3	19	265EDC06	15

Intelligent door access system

The system’s structure is shown in Figure 4. Intelligent door access system was composed of the intelligent key application on Android smart phone and intelligent lock on door. The intelligent key application of Android mobile performed door-open operation after button control on application panel was clicked. It also saved three 64-bit KeeLoq keys that belong to user. The synchronized counter was increased by 1 after click operation. The button function was also defined in one of 4-bit function keys. After user’s operation was encrypted by triple KeeLoq, the ciphertext was transmitted via Bluetooth or WiFi wireless communication. The intelligent lock on door received the wireless code using matched Bluetooth or WiFi module. Accordingly, the ciphertext could be decrypted to be plaintext employing the same triple KeeLoq keys stored in the intelligent lock. The intelligent lock finished unlocking operation after successful match.

Figure 4.

Structure of lock access system.

Key application on Android

Based on the Eclipse development platform and JAVA language, the intelligent key application on Android4.1 was designed. The main procedure of designed application is shown in Figure 5. Graphic or digital decoding in Figure 6 was necessary before the application software started, which further ensured the security of door access system. The user’s interface in Figure 6 would be present after certification access. Functions including BluetoothAdapter.getDefaultAdapter and BluetoothDevice on background program were applied to obtain the default local Bluetooth device (on smart phone) and remote Bluetooth device (on lock). By means of the Bluetooth communication socket or ethernet socket, key application could communicate with lock via Bluetooth or WiFi. And then three groups of 64-bit seed keys and 16-bit synchronized counter value were read out from the structured query language (SQL) light database, which would encrypt the user’s unlocked operation using the triple KeeLoq shown in Figure 4. Function of OutputStream is employed, and the final ciphertext was transmitted from Bluetooth or WiFi interface to the intelligent lock on door. Meanwhile, the synchronized counter value saved in database should be increased by 1 and be updated. When the user kept pressing the unlocked button for more than 5 s, learning mode program was executed. The learning code on safe mode would be transmitted immediately to update keys on lock under permission.

Figure 5.

Operational flow of Android key application.

Figure 6.

Login interface and user’s interface.

On the occasion that triple 64-bit seed keys of phone and lock were matched in unlocking procedure, the intelligent lock on door would register the user’s information including triple 64-bit seed keys, synchronized counter, and 28-bit serial code on mobile phone client. Several triple KeeLoq keys could be defined on the intelligent key application. The function helped to support various “keys,” such as family key and office key.

Intelligent lock on door

KeeLoq rolling encryption technology was a patent belonging to Microchip. Microchip has provided series of dedicated solutions and technical support for KeeLoq codec. 16F690 provided by Microchip was a 20-Pin, flash-based, 8-bit CMOS Microcontroller with nanoWatt technology. It included 4K program memory space and an enhanced USART (Universal Synchronous/Asynchronous Receiver and Transmitter) module. The merits contributed to constructing low-power lock system with triple KeeLoq codec algorithm, which could communicate with smart phone via Bluetooth or WiFi interface equipped with USART. The system’s hardware schematic is shown in Figure 7. BK3211 Bluetooth module and USR-WIFI232-B WiFi module were extended to receive ciphertext data. Lock driving circuit was equipped to perform lock action. Sound and light circuit was offered for alarm.

Figure 7.

Hardware schematic of lock system.

The operation procedure of system is shown in Figure 8. First, the system reset and peripheral was initialized after power-on. Meanwhile, it would real timely detect whether the learning key was pressed or the data from Bluetooth or WiFi module emerged. If the learning key was retentively pressed for more than 5 s, the lock on door erased the previous information saved in the electrically erasable programmable read-only memory (EEPROM) and entered learning mode. Then, intelligent key application transmitted the key’s information including triple 64-bit seed keys, 16-bit synchronized counter, and 28-bit serial code to the lock on door via the Bluetooth or WiFi. It could rematch a new key and achieve parameter synchronization on lock. In normal mode, if data output from Bluetooth or WiFi was detected, the micro control unit (MCU) would match the serial code in fixed code of ciphertext and then it was saved in EEPROM. After successful match, the ciphertext was decrypted employing triple KeeLoq decryption. If identification code and function key in the decrypted plaintext, respectively, matched the low 10-bit serial number and the function key in fixed code, rational increments of synchronized counter in plaintext should be estimated. According to above-mentioned criteria, the difference value of synchronized counter between intelligent key application and the lock on door was less than 4 and greater than zero. If it is satisfied, synchronized counter in the lock on door was increased by 1 and updated in EEPROM. The door would be unlocked with 1-s short sound from speaker and three times rapid flash from light-emitting diode (LED). Otherwise, the lock on door kept off with 5-s short sound from speaker and three times slow flash from LED.

Figure 8.

Operational flow of lock on door.

Conclusion

In this article, the core idea of 3DES was referred to propose the triple KeeLoq codec algorithm, which could obviously improve its security and reliability. Experimental simulation was performed to illuminate the rolling effects. Results showed that the algorithm would not reduce powerful rolling effect and in consideration of limited computing power of embedded microcontroller three 64-bit keys were suitable to increase the crack difficulties and further improved its security. Then, the triple KeeLoq algorithm was successfully applied to intelligent door access system. It not only met the intelligent trend of locks but also guaranteed high performance of security. It owned advantage of convenience, copy protect, and preventing loss. Meanwhile, since it could integrate various kinds of keys in a software application on mobile phone, it bore merits of low cost, high security, humanization, and environmental protection. In sum, the solution owned a good promotional value and potential prospect of market application.