Secure access key control through challenge & response
For millennia people have used locks and keys to control access to their dwellings and treasures. As technology changed, so did the locks. Today mechanical locks still dominate the world. However, as a close look at your car key or employee badge most likely reveals, electronics has already entered the access control territory.
This article reviews keys for access control: mechanical, magnetic, contact, RFID. It describes challenge and response authentication (the challenge, secret, and message authentication code or MAC) and the important role of the SHA-1 algorithm. Finally, the article explains why challenge and response authentication is more secure.
The key as an IT device
From a strictly logical perspective, any key stores information like a ROM (read only memory). The lock “reads” the key’s data and, if it matches the lock’s criteria, gives access.
The physical size and the smallest dimension detail (i.e., an increment) of a mechanical key limit the available code space. For a given key style, hundreds or thousands of keys can be manufactured without duplication; the exact number depends on the style. Magnetic stripe key cards store information with tiny iron-based magnetic particles.
The magnetic stripe can be written in multiple parallel tracks of more than 500 bits each. Contact-based electronic token keys (e.g., iButton® devices, chip cards) store information in silicon chips.
The number of bits available can be as low as 64 (DS1990A) or virtually unlimited. Contactless keys start with models featuring only 26 bits (see Wiegand Public Format) and have practically no upper limit. Magnetic stripe key cards are popular for room access in hotels. Electronic token keys, with and without contact, are popular for employee badges.
Status quo and its issues
The actual opening of the lock, be it mechanical or electronic, is solely based on the presence of static data that satisfies the lock’s built-in criteria. With electronic locks, this data could be a simple identification number, hundreds or thousands of memory bits (e.g., a magnetic stripe or memory chip card), or a combination of both. The less information that a key carries, the more keys a given lock can memorize.
Mechanical keys are available in many styles and sizes.The “owner” of the lock has no protection against unauthorized key duplications. In addition, inexpensive tools are available to open the lock without the right key . Due to the limited code space, moreover, the uniqueness of a key is not guaranteed. Over time the fine structures of a key wear off, making it increasingly more difficult to open the lock.
Although code space is not an issue with magnetic stripe key cards, they can easily be duplicated2 or erased. These magnetic stripe cards also deteriorate from wear and tear.
ROM-based electronic keys are subject to emulation (replay) and copying. This is true for contact keys2 and RFID keys.2 Except for applications based on the Wiegand format and derivatives (26 bits or 36 bits), electronic keys have enough code space to guarantee a unique code for every key.
The next level of security: challenge/response authentication
Traditional electronic locks rely on static data that the key needs to produce to gain access. This unchanging criterion makes it easy to succeed with cloned keys.
A much higher level of security is achieved if the key can receive an unpredictable data inquiry from the lock and respond with a data pattern that depends on the data received. The process involves openly readable data and hidden data that is known only to the key and the lock.
The technical term for the unpredictable data that the lock sends to the key is a random challenge. The hidden data is called the secret, and the response is commonly referred to as the message authentication code, or MAC. The message consists of the challenge, openly readable data, the secret, and constants (padding).
To verify the authenticity of a key, the lock computes a MAC using the same challenge, data read from the key, the secret, and constants. If the MAC computed by the lock matches the MAC from the key’s response, the lock knows that the key is authentic.
The technical term for this process, illustrated in Figure 1 below, is challenge and response authentication. If, in addition to the authenticity, the openly readable data in the key also matches the lock’s criteria, the lock gives access.
Figure 1. Challenge and response authentication data flow.
In cryptography, an algorithm that generates a fixed-length MAC from a message is called a one-way hash function. "One-way" indicates that it is extremely difficult to conclude from the fixed-length MAC output the usually larger message. With encryption, in contrast, the size of the encrypted message is proportional to the original message.
A thoroughly scrutinized and internationally certified one-way hash algorithm is SHA-1, which was developed by the National Institute of Standards and Technology (NIST). SHA-1 has evolved into the international standard ISO/IEC 10118-3:2004.
The math behind the algorithm is publicly available through the NIST website. Distinctive characteristics of the SHA-1 algorithm are:
1) Irreversibility. It is computationally infeasible to determine the input corresponding to a MAC.
2) Collision resistance. It is impractical to find more than one input message that produces a given MAC.
3) High avalanche effect. Any change in input produces a significant change in the MAC result.
For these reasons, as well as the international scrutiny of the algorithm, Maxim selected SHA-1 for challenge and response authentication.