Data storage using encoded hash message authentication code

Data storage and message processing using an encoded hash message authentication code is described. In one embodiment, a data processing apparatus comprises one or more processors; logic coupled to the one or more processors for execution and which, when executed by the one or more processors, causes receiving a data set at the one or more processors; creating and storing a hash output value by applying the data set to a collision-resistant hash operation that provides the hash output value as output; encoding the hash output value using a uniquely invertible keyed pseudo-random permutation operation based on a first shared key, to result in creating an encoded authentication code; and associating the encoded authentication code with the data set.

FIELD OF THE INVENTION

The present disclosure generally relates to secure data storage systems and the use of cryptographic authentication of messages that are stored on, and communicated between, computers and other devices.

BACKGROUND

When data must be stored on a computer that is not trusted, it is often desirable to provide cryptographic authentication of that data using a message authentication code (MAC). For example, when a file server is accessible to a wide group of users, one or more of those users can apply a MAC with a shared secret key to a particular file, and store the MAC tag with the file. The users that also have that same shared secret key then can detect any unauthorized alteration of that file by re-computing the MAC and comparing the re-computed value to a copy of the previously stored MAC tag.

As in any cryptosystem, changing secret keys is sometimes necessary. For example, when multiple users share a secret key, it may be necessary to change a key because one of the users becomes untrusted. If a device containing the key has been stolen or compromised, then a user may no longer be trusted. When a MAC key is changed, the MAC tags for each authenticated data element must be recomputed using the new key. This operation is potentially very costly, because with conventional MAC operations the entire set of authenticated data must be run through a cryptographic function. Using this operation with large data storage systems might require processing gigabytes or terabytes of data using the cryptographic function, which consumes considerable time and processing resources.

An alternative to re-computing the MAC tags is “lazy revocation”, which postpones re-computation of a MAC until a user or other computer requests or fetches the associated data.

Lazy revocation is only useful when it is acceptable to make the assumption that all adversaries seeking to break into the system have limited access to the stored data and MAC tags. A lazy revocation technique is described in “Lazy Revocation in Cryptographic File Systems,” http://www.zurich.ibm.com/4cca/papers/lazyfs.pdf.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Embodiments are described herein according to the following outline:1.0 General Overview2.0 Structural and Functional Overview3.0 Data Storage Using Encoded Hash MAC3.1 Overview3.2 Collision-Resistant Hash Function3.3 Pseudo-random Permutation3.4 Complete Formal Specification of Example Embodiment3.5 Security Considerations4.0 Implementation Mechanisms—Hardware Overview5.0 Extensions and Alternatives

1.0 General Overview

In one embodiment, a data processing apparatus comprises one or more processors; logic coupled to the one or more processors for execution and which, when executed by the one or more processors, causes receiving a data set at the one or more processors; creating and storing a hash output value by applying the data set to a collision-resistant hash operation that provides the hash output value as output; encoding the hash output value using a uniquely invertible keyed pseudo-random permutation operation based on a first shared key, to result in creating an encoded authentication code; and associating the encoded authentication code with the data set.

In one feature, the logic comprises further sequences of instructions which, when executed by the one or more processors, cause the apparatus to perform receiving a second shared key; retrieving and decoding the encoded authentication code using the first key to result in recovering the hash output value; re-encoding the hash output value using the permutation operation based on the second shared key, to result in creating a second encoded authentication code without re-applying the data set to the hash operation; storing the second encoded authentication code in association with the data set.

In one embodiment, the hash operation is a one-way hash function having a fixed-length output. In another embodiment, the hash operation is SHA-1. In yet another embodiment, the permutation operation is AES in a four-round Luby-Rackoff function. In a further embodiment, the encryption operation is a 256-bit width Rijndael cipher. The Extended Codebook (XCB) or the Encrypt-Mask-Encrypt (EME) block cipher modes of operation may be used as alternatives.

In an embodiment, the data set is a message, and the apparatus is any of a router and a switch in a packet-switched network. Associating, in the context herein, may comprise storing the encoded authentication code with the data set, storing information derived from the data set with the encoded authentication code, storing the data set and the encoded authentication code in separate locations, generating and sending a message containing the data set and the encoded authentication code to a networking device or endpoint, or other association operations.

In other embodiments, a data storage system, a method, and a computer-readable medium are provided.

2.0 Structural and Functional Overview

When message authentication codes (MACs) are used to enforce access control on stored data, it is necessary to re-compute the MAC values whenever a key is updated, for example, to revoke the privileges of one or more users. However, when large amounts of stored data are authenticated, the re-computation operation can require an unreasonably long time.

For example, assume that a set of files is authenticated using a symmetric MAC and the authentication tags are stored along with the files. The key used to authenticate the files is given to all the users who have permission to read and/or write the files. If write permission is removed from one user, then the authentication key must be changed. A new key must be chosen and securely communicated to the users with read and/or write permission, the authentication tags for all of the files must be recomputed with the new key, and the old authentication tags must be replaced with the new ones. In modern data storage systems that store very large amounts of data, the problem of computing the new tags becomes acute.

The present disclosure solves the problem of efficient re-keying, by introducing a method for re-computing authentication tags in which the computational cost per tag is constant, independent of the amount of data. According to an embodiment, an encoded hash MAC can be re-keyed with minimal work. The encoded hash MAC is secure even when an adversary can affect the inputs to the re-keying operation.

In an embodiment, the data set is a file stored in a file system. In an alternative embodiment, the data set is stored in a database that an application program manages. In a further alternative, the data set is a message, and the apparatus is any of a router and a switch in a packet-switched network.

Thus, a message authentication code is constructed by applying a reversible encryption function to the hash of the message, where the hash is collision-resistant. The secret key of the encryption function is the secret key of the MAC. As a result, re-keying requires a constant amount of computation per tag, rather than an amount proportional to the length of the authenticated data.

Further, techniques for re-performing MAC generation for a large number of files are provided. A key updating technique is provided that does not require re-computing the MAC over all the data. In an embodiment using a router in a packet-switched network, the MAC can be re-generated hop by hop without re-computing the MAC over all of a large message payload.

The approach herein can be used in a networked data storage system. The approach herein also could be used in security software products that need to secure their own data stores. The approach can be used by a vendor of data storage devices, networked storage, etc.

FIG. 1Aillustrates a data storage system using encoded hash message authentication codes. A computer102is coupled directly or indirectly through one or more networks104to a second computer106. In an embodiment, second computer106is a storage controller that manages a storage system110. Alternatively, second computer106is a networking device such as a router or switch. The computer102may comprise any general purpose data processing system such as a personal computer, workstation, server, or other processing system. The computer102comprises a data set112to be stored in the storage system110. The data set112may comprise one or more messages, data files, records, objects, or other form of information or data.

In one embodiment, network104comprises one or more local area networks, storage area networks, wide area networks, internetworks, or any combination thereof. Computer106may comprise a storage controller that arbitrates requests to read and write data from or to storage system110. Storage system110may comprise electronic memory, non-volatile storage such as magnetic or optical disk storage, tape storage, or other computer storage, structured as a single drive, multiple drives, and/or one or more shared memory systems. In an embodiment, computer106is a SCSI controller and storage system110is one or more SCSI drives. In an embodiment, storage system110is a RAID disk array. In one embodiment, computer106and storage system110may be integrated or may comprise a server or storage area network. In another embodiment, the storage controller and/or the storage system may be physically or logically in the computer102. Thus,FIG. 1Abroadly represents many different arrangements of a computer that is coupled to storage.

In one embodiment, computer106comprises message authentication logic108. In an embodiment, the message authentication logic108can receive data set112from computer102, and generate a hash message authentication code114. A property of the hash message authentication code114is that re-keying operations and re-computing a new message authentication code do not require applying a hash function to the data set112another time. The data set112is stored in association with hash message authentication code114in storage system110under control of computer106.

In another embodiment, message authentication code logic108is implemented in a network infrastructure device, such as a router or switch. In such an embodiment, computer106receives the data set112in the form of a data frame, segment, packet, or message, the message authentication code logic108generates the hash message authentication code, the message authentication code logic stores or packages the hash message authentication code with the data set in a message130, and the router forwards the message with the data set and the hash message authentication code to a next hop or to an endpoint.

FIG. 1Billustrates logic for generating encoded hash message authentication codes and performing re-keying. In one embodiment, message authentication logic108comprises a collision-resistant hash function120, a uniquely invertible pseudo-random permutation122, and re-key logic124. The message authentication logic108and its elements may comprise one or more computer programs, methods, or other software elements that implement the processing logic that is described further herein. In other embodiments, message authentication logic108may be implemented in firmware or hardware.

FIG. 2illustrates storing data in a data storage system. In an embodiment, at step202a data set is received, and at step204a hash output value is created and stored by applying the data set to a collision-resistant hash operation or hash function. In step206, the hash output value is encoded using a uniquely invertible keyed pseudo-random permutation operation based on a shared key. In this context, “shared” means that the same key is initially used for the hash operation or hash function and the pseudo-random permutation operation. The result of step206is an encoded authentication code, as shown in step208.

In step210, the encoded authentication code is associated with the data set that was received at step202. Step210may comprise storing authenticated data in a data storage system or forwarding a message containing the data set and encoded authentication code to a networking device or to an endpoint. Step210may comprise storing the encoded authentication code separately from the data, though it is often convenient to store the data and encoded authentication code together. Thereafter, the encoded authentication code may be re-generated and compared to the stored encoded authentication code for purposes of determining whether the data set was altered after storage. In such a verification operation, the message authentication logic108may retrieve a previously used key from a secure key management system that is coupled or accessible to the message authentication logic.

Step210may comprise performing a storage operation in computer storage in a storage system. Alternatively, step210comprises forwarding a message with an authentication code to a networking device or to an endpoint. Step210may include transiently storing the message and code in main memory, forwarding memory, buffers, and other elements of a router, switch, or other networking device.

A need may arise to change the shared key, and if the shared key is generated, then the stored encoded authentication code may become unintelligible in future verification operations. Therefore, a new encoded authentication code may be created using a new shared key, and stored with the data set to replace the original encoded authentication code. In an embodiment, a re-keying operation may be performed without re-applying the data set to the hash operation of step204, which is relatively computationally intensive.

Proper validation of a previously generated hash value requires the system to store each key with information about the time during which it was used. Thus, a secure key management system may be provided to store keys. Specific key management techniques are beyond the scope of this disclosure, and any key management technique may be used to securely maintain and provide past keys.

FIG. 3illustrates re-keying a code in a data storage system. In step302, a second shared key is received. The second shared key is a new key or replacement key. Techniques for distributing new keys or replacement keys to the message authentication logic or other elements ofFIG. 1are beyond the scope of this disclosure, and any distribution mechanism may be used.

In step304, the existing encoded authentication code is retrieved from storage and decoded, resulting in recovering the hash output value of step204. Techniques for decoding are described further herein.

In step306, the hash output value is re-encoded using the same pseudo-random permutation operation that was used at step206, but using the second shared key. As shown in step312, it is not necessary to re-generate the hash output value, for example, by re-applying the stored data set to the hash function. The property of step312has several benefits. For example, using the techniques herein, a large number of MAC values for a large number of stored files, each occupying a large amount of storage, may be re-computed rapidly without hashing the large files. Further, when the data set is a message and the logic is implemented in a network infrastructure device such as a router or switch, a new MAC value may be re-computed “on the fly” without excessive delay during message transmission.

As a result of step306, a new encoded authentication value is produced. In step310, the new encoded authentication code is associated with the previously stored data set. Step310may comprise performing a storage operation in computer storage in a storage system. Alternatively, step310may comprise forwarding a message with an authentication code to a networking device or to an endpoint. Step310may include transiently storing the message and code in main memory, forwarding memory, buffers, and other elements of a router, switch, or other networking device.

3.0 Data Storage Using Encoded Hash Mac

The Encoded Hash MAC (EHM) disclosed herein is a message authentication code that supports an efficient re-keying operation. In an embodiment, the EHM is mathematically defined as T=EK(h(M)), where EK(X) denotes the encryption of X with a pseudo-random permutation E using the key K, and h(M) denotes the application of a collision-resistant hash function h to the message M. Further, the function E:{0,1}k×{0,1}w→{0,1}wmaps a k-bit key and a w-bit string to a w-bit string. The function E is uniquely invertible, and its inverse is denoted as EK−1. Therefore, EK(EK−1(X))=X for all Xε{0,1}w.

In an embodiment, E is selected as indistinguishable from a random permutation to a computationally limited adversary. In an embodiment, E may comprise an implementation of a block cipher such as the Advanced Encryption Standard, or a block cipher mode of operation that implements a permutation.

In an embodiment, a function h: {0,1}*→{0,1}wmaps arbitrary length bit strings onto strings of w bits. The function h is collision resistant. Thus, it is computationally infeasible for an adversary to find two inputs M, M′ such that M≠M′ and h(M)=h(M′).

In an embodiment, a re-keying process is provided. In re-keying, given a message M and a MAC tag T computed under a given key K, a new MAC tag T′ corresponding to a new key K′ is determined as T′=EK′(EK−1(T)). Since the tag T contains enough information to compute the value of h(M), there is no need to run the hash over the entire message during the re-key operation. Further, the new tag can be computed using small, constant amount of effort, independent of the length of the message M. Since the computational cost of re-keying is constant, rather than linear in the length of data that is authenticated, the present approach provides considerable performance advantages over prior approaches.

Still further, an adversary who surreptitiously alters the old tag value T still cannot trick the re-keying operation into creating a tag that corresponds to a message that the adversary has selected, as further described herein.

A specific example of an EHM MAC process is now described with respect toFIG. 4, which illustrates generating an encoded hash message authentication code using particular logical operations for one embodiment.

In step112ofFIG. 4, a data set is received. In an embodiment, an EHM MAC value is computed by hashing the data set with a collision-resistant hash function, then encoding the result using a keyed pseudo-random permutation (PRP).

In step402, the SHA-256 hash operation is used to hash the data set112, based on a shared key408, resulting in creating a hash value404. In various embodiments, the hash operation comprises SHA-1, SHA-256, MD5, or MD2. SHA-1, SHA-256, MD5, and MD2 are intended only as examples and not as limitations to this disclosure, and other hash operations may be used. SHA-1 produces a 160-bit output, providing 2160permutations. SHA-256 produces a 256-bit output for 2256collision-free permutations. In other embodiments, other hash operations can be used, and to ensure that the MAC provides security against an adversary who can perform 2ccomputation, the hash operations are implemented using w≧2c. Thus, when w=256, h may be SHA-256.

For the PRP or E, the Advanced Encryption Standard is not directly usable because it does not support 256-bit widths; its block size is 128 bits. However, a pseudo-random permutation with a 256-bit input can be implemented using other cryptographic elements. A suitable pseudo-random permutation can be constructed using AES in a four-round Luby-Rackoff function. The MAC key is used as the pseudo-random permutation key. As shown in step406, AES encryption using a four-round Fesitel-Luby-Rackoff process is applied to the hash value404using shared key408, resulting in generating an encoded hash MAC410. Alternatively, the encryption operation is a 256-bit width Rijndael cipher. The XCB or EME block cipher modes of operation also may be used as alternatives.

3.4 Formal Specification of Example Embodiment

In an embodiment, an encrypted hash MAC is defined as follows, based on the SHA-256 hash function and AES. The EHM authentication tag computed on the message M with the key K is denoted as EHM(K,M). The inputs K and M have the definitions given in section 3.1 above, with the parameters w=128 and k=128, 196, or 256. In the following specification, the functions MSBn(X) and LSBn(X) return the leftmost n bits of X and the rightmost n bits of X, respectively. The values 0 and 1 denote a single zero or one bit, and 0ndenotes a string of n successive zero bits. The concatenation of two bit strings X and Y is written as X∥Y.

Based on the foregoing, in an embodiment, the MAC is defined as
EHM(K,T)=E(K,SHA-256(M)),

The variables A, B, C, and D are identical for each invocation of EHM with the same key, and can be cached between invocations.

The function E may be based upon Fesitel-Luby-Rackoff design with four rounds, using round keys that are generated from the block cipher key. The security of such a design is sufficient provided that the number of invocations of E, for a fixed key, is less than 2−w/2=2−64.

3.5 Security Considerations

In an embodiment, E is a pseudo-random permutation such that an adversary's advantage at distinguishing the output of E from a truly random permutation is low. In an embodiment, the advantage A is defined by an experiment in which the adversary is presented with oracle access to a permutation, is allowed to query the oracle with inputs, and is challenged to distinguish whether the oracle is either E with a randomly chosen key K (and this event is denoted B) or is a random permutation (and this event is denoted Bc). The adversary is allowed q queries to the oracle, and then must indicate its guess as to the nature of the oracle. The event that it guesses that the oracle interfaces to E is denoted as D. The advantage is given by the difference between the true positive probability and the false positive probability:
A=P[D|B]−P[D|Bc]

In an embodiment, the security of a MAC is measured by the probability that an adversary can forge a message-tag pair. An adversary is allowed to choose a set of n messages that are authenticated under a random key K that is unknown to the adversary. Then another secret key K′ is chosen at random, and the re-key operation is performed on each message in the set. The adversary controls each tag T that is entered into the re-key operation. Based on the foregoing, a “forgery” consists of the event that the attacker is able to produce a message-tag pair (M,T) such that MAC(K′,M)=T, where M is not in the set of messages chosen by the adversary.

In an embodiment, the re-key operation is secure even if the adversary can manipulate both the stored messages and the stored tags. The computation of each tag is assumed to include information identifying each message. For example, if each message is a file, then the identifying information could comprise a full pathname of the file in a file system. The identifying information can be included in the tag computation by prepending it to the message prior to authentication.

In this context, the security of EHM during a re-key operation derives from whether an attacker, who can compute the tag for a new key, for any message, can distinguish E from a random permutation (and thus cannot break AES), or can find a collision in SHA-256. The likelihood that an attacker can do either is exceedingly low, or computationally infeasible, and therefore EHM is secure within the foregoing constraints.

FIG. 5is a block diagram that illustrates a computer system500upon which an embodiment of the invention may be implemented. Computer system500includes a bus502or other communication mechanism for communicating information, and a processor504coupled with bus502for processing information. Computer system500also includes a main memory506, such as a random access memory (“RAM”) or other dynamic storage device, coupled to bus502for storing information and instructions to be executed by processor504. Main memory506also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor504. Computer system500further includes a read only memory (“ROM”)508or other static storage device coupled to bus502for storing static information and instructions for processor504. A storage device510, such as a magnetic disk or optical disk, is provided and coupled to bus502for storing information and instructions.

The invention is related to the use of computer system500for data storage using an encoded hash message authentication code. According to one embodiment of the invention, data storage using an encoded hash message authentication code is provided by computer system500in response to processor504executing one or more sequences of one or more instructions contained in main memory506. Such instructions may be read into main memory506from another computer-readable medium, such as storage device510. Execution of the sequences of instructions contained in main memory506causes processor504to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

5.0 Extensions and Alternatives