White Paper 8: 1-Wire® SHA-1 Overview

Abstract

While discussions of data security often focus on encryption, an arguably more valuable aspect is authentication. This paper presents a straightforward technique for digital authentication of hardware, data, and users. It goes on to provide an overview of the 1-Wire Secure Hash Algorithm 1 (SHA-1) devices that use this technique. Finally, it provides references to other documents, kits, and examples for continued research and development.

Introduction

Security is a pervasive problem in all things digital. While discussions of data security often focus on encryption, an arguably more valuable aspect is authentication. Since information and communication all boil down to transient ones and zeros, their validity and authenticity can come into question. This paper presents a straightforward technique for authentication of hardware, data, and users. It goes on to provide an overview of the 1-Wire^® Secure Hash Algorithm 1 (SHA-1) devices that use this technique. Finally it provides copious references to other documents, kits, and examples for continued research and development. (Special terms, commands, or codes are shown in italics for clarity. A glossary of terms can be found in application note 1099, "White Paper 4: Glossary of 1-Wire SHA-1 Terms.")

Hash

A hash is a distillation of a message. This distillation is typically much smaller than the message and is a constant size. A cryptographically strong hash must be nonreversible, meaning that by looking at the hash result there is no way to derive any part of the original message. It must also change significantly with any small change, even a single bit, in the input message. This is called the avalanche effect. The hash should also be collision-resistant, meaning that it is impractical to find two messages with the same hash. A hash with these properties can be used to verify that a message has not been altered.

MAC

A MAC (message authentication code) is a hash where a portion of the input message is secret. Only participants that know the secret can re-compute and verify the authenticity of the MAC. See Figure 1 for MAC generation.

Participants in a system (secret known) can therefore verify a message and MAC combination to be authentic. The transient ones and zeros mentioned earlier are now trusted without resorting to encryption. This is a powerful technique that has far-reaching applications (see Applications section below).

SHA-1

Selection of a cryptographically strong hash function is critical for the success of a hash-based authentication scheme. SHA-1 is nonreversible, collision-resistant, and has a good avalanche effect. SHA is a standard specified in Federal Information Publication 180-1 and 180-2 (FIPS 180-1, FIPS 180-2). The SHA series hashes are currently the only FIPS-approved method. SHA-1 is also specified in ISO/IEC 10118-3. According to Bruce Schneier in Applied Cryptography, Second Edition, John Wiley & Sons, 1996, "There are no known cryptographic attacks against SHA". For this reason, SHA-1 was selected. SHA-1 takes in one or more blocks of 512 bits (64 bytes) and creates a 160-bit (20-byte) hash.

Applications

Authentication is the process of proving to a host that a device, person, or message is valid and authentic. The authentication technique that takes advantage of a MAC is called challenge and response. A challenge is random data that is presented by a host to the device to be authenticated. The challenge is then included in the MAC calculation. This allows for every authentication session to be different and non-deterministic.

What can be authenticated? A message between two pieces of equipment could be authenticated if the secret is known by both pieces. A portable token could be authenticated to a door to allow access to a controlled room. See Table 1 below for a list of potential applications including both the host and authentication target.

Creating a Trusted Token

The key component to most of the above applications is some kind of portable electronic token. To perform authentication with an SHA-1 MAC, a trusted client must be created that can securely keep the secret and compute the MAC. The client must be physically secure, rugged, and be able to perform the SHA-1 operation quickly. Analog has been making the iButton® portable tokens for over 10 years and now provides models with SHA-1 capability. Where the iButton form factor is not required a chip version is also available (see Figure 2).

Discussions about applications and use of these tokens are simplified when provided in a context. Figure 3 illustrates a complete service. A service provider (e.g., vending company) would deploy tokens with valid data to their user base. The user would take the token to a service control unit (SCU) (e.g., candy machine) to have it authenticated as part of the service and the data validated (electronic cash, eCash) and optionally updated. The SCU must also be able to compute the SHA-1 MACs. This can be performed in an internal coprocessor. Specific fields and features of the token and the SCU will be explained in the following sections.

There are two different 1-Wire SHA-1 tokens. The DS1963S is the premium part with eight different SHA-1 secrets and 512 bytes of nonvolatile (NV) RAM user data space. The DS1963S can also be used as a coprocessor in the SCU to compute all of the necessary host-side SHA-1 MACs. This has the added security of removing the secrets from the SCU processor entirely. The secrets for both verifying the service data (master signing secret) and authenticating the token (master authentication secret) are securely kept in the DS1963S coprocessor. An internal lithium cell backs up the NV RAM inside the DS1963S. Removing this power source even for a short time (during a physical attack for instance) will clear the secrets and contents.

The DS1963S can support seven different dynamic service records, each with its own secret. The eighth secret is reserved for coprocessor-type functions. This device also contains eight more general-purpose 32-byte data pages that can be used for static service records. These extra pages have a secret associated with them but do not have a write-cycle counter. A write-cycle counter is a read-only, non-rolling-over page write counter that is used for detection of writes. The write-cycle is used to avert certain attacks to the system.

The DS1963S uses two different MACs for each service record. The first one is generated by the 1-Wire token and authenticates it to the system (unique authentication secret). The second MAC is created by the SCU host and included in the service record and is used to validate it. This MAC is called the service data signature. The secret used to create this signature (master signing secret) does not reside on the user device: it only exists within the SCU or its coprocessor.

The other two devices, DS1961S and DS2432, are essentially the same devices in different packages. The DS1961S comes in the standard iButton package and the DS2432 is in a small TSOC package or in the chip-scale package (2.5mm by 1.5mm). These two devices use EEPROM technology instead of NV RAM, thus allowing a package without a lithium cell. They have only one secret associated with all four pages. There is no write restriction on the DS1963S. However, writing to the DS1961S/DS2432 requires presenting an authentication MAC to the device. This effectively write protects the device. Since write access is restricted to SCUs that know the authentication secret, the devices do not have a write-cycle counter and do not need a MAC signature embedded in the data. The DS1961S/DS2432 can only support one service provider since there is only one authentication secret. This service provider could install up to four different services since the device has four pages.

Note that the SHA-1 result created by the 1-Wire devices conforms to the FIPS 180-1 specification, except the additional final constants were removed. In the FIPS-180 specification, these constants are added to the result after each block is computed. Since the 1-Wire devices only do one block, adding these constants don't add any security and was removed to speed up the MAC computation in hardware. If FIPS 180-1 compliance is required, the SCU can add the constants back on.

Figure 3 also shows the pertinent memory and special registers of the 1-Wire tokens that will be used in verification of one service record. Each token contains a 64-bit unique device ID that is lasered into ROM. Since each device has this unique ROM ID, it can be used as one component in the calculation of the secret to make the authentication secret on each device unique (unique authentication secret). A host such as the SCU must re-compute the unique authentication secret from the master authentication secret and the ROM ID when an authentication is done. Each device also contains a temporary memory location to hold the authentication challenge sent by the SCU. A challenge is random data created by the SCU to make each authentication sequence unique. The page number is the physical location in memory that the data message resides in.

The 1-Wire devices take each of the fields and internally run them through the built-in SHA-1 engine, and then return the MAC for authentication. The SCU takes the same information using the calculated unique authentication secret and verifies that the MAC is correct. Figure 4 shows how the authentication MAC is constructed inside the device.

Since the DS1963S has unrestricted write access, the service record must include a service data signature for validation of the data. This MAC is saved along with the service data and used to verify that the account data is valid. Figure 5 shows what information is put in to produce and verify the service data signature. Figure 6 shows a complete transaction with the SCU and a DS1963S token and Figure 7 shows the transaction for the DS1961S token.

More Information

There is a large number of documents available to aid in understanding and implementing a system based on 1-Wire SHA-1 devices. The information in these documents can be divided into three categories: Theory, Implementation Details, and APIs (see Figure 8). The Theory resources discuss how electronic cash can be made secure with the algorithms available. The Implementation Details describe every step and bit of communication to accomplish the authentication and electronic cash operations with 1-Wire devices. The API's resources are useful to jump right in and start using the SHA-1 devices. The source code to the APIs can also be a useful development tool for custom implementations.