Message Authentication

Message authentication guarantees the authenticity and integrity of a message by ensuring that

A message hasn’t been altered (either maliciously or accidentally) during transmission.

A message isn’t a replay of a previous message.

The message was sent from the origin stated (it’s not a forgery).

The message is sent to the intended recipient.

Checksums, CRC-values, and parity checks are examples of basic message authentication and integrity controls. More advanced message authentication is performed by using digital signatures and message digests.

Digital signatures and message digests can provide message authentication.

Digital signatures

The Digital Signature Standard (DSS), published by the National Institute of Standards and Technology (NIST) in Federal Information Processing Standard (FIPS) 186-1, specifies two acceptable algorithms in its standard: the RSA Digital Signature Algorithm and the Digital Signature Algorithm (DSA, which is based on a modified El Gamal algorithm). Both algorithms use the SHA-1 Secure Hash Algorithm, which we discuss in the section “Message digests,” later in this chapter.

A digital signature is a simple way to verify the authenticity (and integrity) of a message. Instead of encrypting a message with the intended receiver’s public key, the sender encrypts it with his or her own private key. The sender’s public key properly decrypts the message, authenticating the originator of the message. This process is known as an open message format in asymmetric key systems, which we discuss in the section “Asymmetric key cryptography,” earlier in this chapter.

Message digests

It’s often impractical to encrypt a message with the receiver’s public key to protect confidentiality, and then encrypt the entire message again by using the sender’s private key to protect authenticity and integrity. Instead, a representation of the encrypted message is encrypted with the sender’s private key to produce a digital signature. The intended recipient decrypts this representation by using the sender’s public key, and then independently calculates the expected results of the decrypted representation by using the same, known, one-way hashing algorithm. If the results are the same, the integrity of the original message is assured. This representation of the entire message is known as a message digest.

To digest means to reduce or condense something, and a message digest does precisely that. (Conversely, indigestion means to expand . . . like gases . . . how do you spell relief?) A message digest is a condensed representation of a message; think Reader’s Digest. Ideally, a message digest has the following properties:

The original message can’t be re-created from the message digest.

Finding a message that produces a particular digest shouldn’t be computationally feasible.

No two messages should produce the same message digest (known as a collision).

The message digest should be calculated by using the entire contents of the original message — it shouldn’t be a representation of a representation.

Message digests are produced by using a one-way hash function. There are several types of one-way hashing algorithms (digest algorithms), including MD5, SHA-1, and HMAC.

A collision results when two messages produce the same digest or when a message produces the same digest as a different message.

A one-way function ensures that the same key can’t encrypt and decrypt a message in an asymmetric key system. One key encrypts the message (produces ciphertext), and a second key (the trapdoor) decrypts the message (produces plaintext), effectively reversing the one-way function. A one-way function’s purpose is to ensure confidentiality.

A one-way hashing algorithm produces a hashing value (or message digest) that can’t be reversed; that is, it can’t be decrypted. In other words, no trapdoor exists for a one-way hashing algorithm. The purpose of a one-way hashing algorithm is to ensure integrity and authentication.

MD5, SHA-1 and SHA-2, and HMAC are all examples of commonly used message authentication algorithms.

MD family

MD (Message Digest) is a family of one-way hashing algorithms developed by Dr. Ron Rivest that includes MD (obsolete), MD2, MD3 (not widely used), MD4, MD5, and MD6:

MD2: Developed in 1989 and still widely used today, MD2 takes a variable size input (message) and produces a fixed-size output (128-bit message digest). MD2 is very slow (it was originally developed for 8-bit computers) and is highly susceptible to collisions.

MD4: Developed in 1990, MD4 produces a 128-bit digest and is used to compute NT-password hashes for various Microsoft Windows operating systems, including NT, XP, and Vista. An MD4 hash is typically represented as a 32-digit hexadecimal number. Several known weaknesses are associated with MD4, and it’s also susceptible to collision attacks.

MD5: Developed in 1991, MD5 is one of the most popular hashing algorithms in use today, commonly used to store passwords and to check the integrity of files. Like MD2 and MD4, MD5 produces a 128-bit digest. Messages are processed in 512-bit blocks, using four rounds of transformation. The resulting hash is typically represented as a 32-digit hexadecimal number. MD5 is also susceptible to collisions and is now considered “cryptographically broken” by the U.S. Department of Homeland Security.

MD6: Developed in 2008, MD6 uses very large input message blocks (up to 512 bytes) and produces variable-length digests (up to 512 bits). MD6 was originally submitted for consideration as the new SHA-3 standard but was eliminated from further consideration after the first round in July 2009. Unfortunately, the first widespread use of MD6 (albeit, unauthorized and illicit) was in the Conficker.B worm in late 2008, shortly after the algorithm was published!

SHA family

Like MD, SHA (Secure Hash Algorithm) is another family of one-way hash functions. The SHA family of algorithms is designed by the U.S. National Security Agency (NSA) and published by NIST. The SHA family of algorithms includes SHA-1 and SHA-2, and one in the oven — SHA-3:

SHA-1: Published in 1995, SHA-1 takes a variable size input (message) and produces a fixed-size output (160-bit message digest, versus MD5’s 128-bit message digest). SHA-1 processes messages in 512-bit blocks and adds padding to a message length, if necessary, to produce a total message length that’s a multiple of 512.

SHA-2: Published in 2001, SHA-2 consists of four hash functions — SHA-224, SHA-256, SHA-384, and SHA-512 — that have digest lengths of 224, 256, 384, and 512 bits, respectively. SHA-2 processes messages in 512-bit blocks for the 224, 256, and 384 variants, and 1,024-bit blocks for SHA-512.

SHA-3: The new SHA-3 standard is scheduled to be published in 2012.

HMAC

The Hashed Message Authentication Code (or Checksum) (HMAC) further extends the security of the MD5 and SHA-1 algorithms through the concept of a keyed digest. HMAC incorporates a previously shared secret key and the original message into a single message digest. Thus, even if an attacker intercepts a message, modifies its contents, and calculates a new message digest, the result doesn’t match the receiver’s hash calculation because the modified message’s hash doesn’t include the secret key.