This paper presents two new message authentication schemes, NMAC and HMAC, based on cryptographic hash functions. These schemes are proven to be secure as long as the underlying hash function has reasonable cryptographic strength. The schemes retain almost all the security of the underlying hash function and have performance essentially equivalent to that of the hash function. They use the hash function as a black box, allowing for easy implementation and replacement of the hash function. NMAC is a nested construction that uses two keys to key the hash function. HMAC is a hash-based MAC that uses a single key and is more convenient to implement. Both schemes are secure under the assumption that the underlying hash function is collision-resistant. The security of NMAC is formally analyzed and shown to be related to the security of the hash function. HMAC is shown to be a particular case of NMAC, where the keys are derived from the hash function. The paper also discusses the security of these schemes against various attacks, including birthday attacks and collision attacks. It shows that these schemes are resistant to such attacks, especially when the underlying hash function is strong. The paper also compares these schemes to other proposals and shows that they offer better security and efficiency. HMAC has been adopted as the mandatory authentication transform for Internet security protocols.This paper presents two new message authentication schemes, NMAC and HMAC, based on cryptographic hash functions. These schemes are proven to be secure as long as the underlying hash function has reasonable cryptographic strength. The schemes retain almost all the security of the underlying hash function and have performance essentially equivalent to that of the hash function. They use the hash function as a black box, allowing for easy implementation and replacement of the hash function. NMAC is a nested construction that uses two keys to key the hash function. HMAC is a hash-based MAC that uses a single key and is more convenient to implement. Both schemes are secure under the assumption that the underlying hash function is collision-resistant. The security of NMAC is formally analyzed and shown to be related to the security of the hash function. HMAC is shown to be a particular case of NMAC, where the keys are derived from the hash function. The paper also discusses the security of these schemes against various attacks, including birthday attacks and collision attacks. It shows that these schemes are resistant to such attacks, especially when the underlying hash function is strong. The paper also compares these schemes to other proposals and shows that they offer better security and efficiency. HMAC has been adopted as the mandatory authentication transform for Internet security protocols.