Message authentication code

Last updated

In cryptography, a message authentication code (MAC), sometimes known as an authentication tag, is a short piece of information used for authenticating and integrity-checking a message. In other words, to confirm that the message came from the stated sender (its authenticity) and has not been changed (its integrity). The MAC value allows verifiers (who also possess a secret key) to detect any changes to the message content.

Contents

Terminology

The term message integrity code (MIC) is frequently substituted for the term MAC, especially in communications [1] to distinguish it from the use of the latter as media access control address (MAC address). However, some authors [2] use MIC to refer to a message digest, which aims only to uniquely but opaquely identify a single message. RFC 4949 recommends avoiding the term message integrity code (MIC), and instead using checksum , error detection code , hash , keyed hash, message authentication code, or protected checksum.

Definitions

Informally, a message authentication code system consists of three algorithms:

A secure message authentication code must resist attempts by an adversary to forge tags, for arbitrary, select, or all messages, including under conditions of known- or chosen-message. It should be computationally infeasible to compute a valid tag of the given message without knowledge of the key, even if for the worst case, we assume the adversary knows the tag of any message but the one in question. [3]

Formally, a message authentication code (MAC) system is a triple of efficient [4] algorithms (G, S, V) satisfying:

S and V must satisfy the following:

Pr [ k ← G(1n), V( k, x, S(k, x) ) = accepted ] = 1. [5]

A MAC is unforgeable if for every efficient adversary A

Pr [ k ← G(1n), (x, t) ← AS(k, · )(1n), x ∉ Query(AS(k, · ), 1n), V(k, x, t) = accepted] < negl(n),

where AS(k, · ) denotes that A has access to the oracle S(k, · ), and Query(AS(k, · ), 1n) denotes the set of the queries on S made by A, which knows n. Clearly we require that any adversary cannot directly query the string x on S, since otherwise a valid tag can be easily obtained by that adversary. [6]

Security

While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-message attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages (which were not used to query the oracle) without performing infeasible amounts of computation.

MACs differ from digital signatures as MAC values are both generated and verified using the same secret key. This implies that the sender and receiver of a message must agree on the same key before initiating communications, as is the case with symmetric encryption. For the same reason, MACs do not provide the property of non-repudiation offered by signatures specifically in the case of a network-wide shared secret key: any user who can verify a MAC is also capable of generating MACs for other messages. In contrast, a digital signature is generated using the private key of a key pair, which is public-key cryptography. [4] Since this private key is only accessible to its holder, a digital signature proves that a document was signed by none other than that holder. Thus, digital signatures do offer non-repudiation. However, non-repudiation can be provided by systems that securely bind key usage information to the MAC key; the same key is in the possession of two people, but one has a copy of the key that can be used for MAC generation while the other has a copy of the key in a hardware security module that only permits MAC verification. This is commonly done in the finance industry.[ citation needed ]

Implementation

MAC algorithms can be constructed from other cryptographic primitives, like cryptographic hash functions (as in the case of HMAC) or from block cipher algorithms (OMAC, CCM, GCM, and PMAC). However many of the fastest MAC algorithms, like UMAC-VMAC and Poly1305-AES, are constructed based on universal hashing. [7]

Intrinsically keyed hash algorithms such as SipHash are also by definition MACs; they can be even faster than universal-hashing based MACs. [8]

Additionally, the MAC algorithm can deliberately combine two or more cryptographic primitives, so as to maintain protection even if one of them is later found to be vulnerable. For instance, in Transport Layer Security (TLS), the input data is split in halves that are each processed with a different hashing primitive (SHA-1 and SHA-2) then XORed together to output the MAC.

One-time MAC

Universal hashing and in particular pairwise independent hash functions provide a secure message authentication code as long as the key is used at most once. This can be seen as the one-time pad for authentication. [9]

The simplest such pairwise independent hash function is defined by the random key, key = (a, b), and the MAC tag for a message m is computed as tag = (am + b) mod p, where p is prime.

More generally, k-independent hashing functions provide a secure message authentication code as long as the key is used less than k times for k-ways independent hashing functions.

Message authentication codes and data origin authentication have been also discussed in the framework of quantum cryptography. By contrast to other cryptographic tasks, such as key distribution, for a rather broad class of quantum MACs it has been shown that quantum resources do not offer any advantage over unconditionally secure one-time classical MACs. [10]

Standards

Various standards exist that define MAC algorithms. These include:

ISO/IEC 9797-1 and -2 define generic models and algorithms that can be used with any block cipher or hash function, and a variety of different parameters. These models and parameters allow more specific algorithms to be defined by nominating the parameters. For example, the FIPS PUB 113 algorithm is functionally equivalent to ISO/IEC 9797-1 MAC algorithm 1 with padding method 1 and a block cipher algorithm of DES.

An example of MAC use

MAC.svg

[19] In this example, the sender of a message runs it through a MAC algorithm to produce a MAC data tag. The message and the MAC tag are then sent to the receiver. The receiver in turn runs the message portion of the transmission through the same MAC algorithm using the same key, producing a second MAC data tag. The receiver then compares the first MAC tag received in the transmission to the second generated MAC tag. If they are identical, the receiver can safely assume that the message was not altered or tampered with during transmission (data integrity).

However, to allow the receiver to be able to detect replay attacks, the message itself must contain data that assures that this same message can only be sent once (e.g. time stamp, sequence number or use of a one-time MAC). Otherwise an attacker could – without even understanding its content – record this message and play it back at a later time, producing the same result as the original sender.

See also

Notes

  1. ↑ IEEE Standard for Information Technology - Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks - Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications (PDF). (2007 revision). IEEE-SA. 12 June 2007. doi:10.1109/IEEESTD.2007.373646. ISBN   978-0-7381-5656-9.
  2. ↑ "CS 513 System Security -- Hashes and Message Digests". www.cs.cornell.edu. Retrieved 20 December 2023.
  3. ↑ The strongest adversary is assumed to have access to the signing algorithm without knowing the key. However, her final forged message must be different from any message she chose to query the signing algorithm before. See Pass's discussions before def 134.2.
  4. 1 2 Theoretically, an efficient algorithm runs within probabilistic polynomial time.
  5. ↑ Pass, def 134.1
  6. ↑ Pass, def 134.2
  7. ↑ "VMAC: Message Authentication Code using Universal Hashing". CFRG Working Group. Retrieved 16 March 2010.
  8. ↑ Jean-Philippe Aumasson & Daniel J. Bernstein (18 September 2012). "SipHash: a fast short-input PRF" (PDF).
  9. ↑ Simmons, Gustavus (1985). "Authentication theory/coding theory". Advances in Cryptology – Proceedings of CRYPTO 84. Berlin: Springer. pp. 411–431.
  10. ↑ Nikolopoulos, Georgios M.; Fischlin, Marc (2020). "Information-Theoretically Secure Data Origin Authentication with Quantum and Classical Resources". Cryptography. 4 (4): 31. arXiv: 2011.06849 . doi: 10.3390/cryptography4040031 . S2CID   226956062.
  11. ↑ "FIPS PUB 113 Computer Data Authentication". Archived from the original on 27 September 2011. Retrieved 10 October 2010.
  12. ↑ "Federal Information Processing Standards Publications, Withdrawn FIPS Listed by Number". Archived from the original on 1 August 2010. Retrieved 10 October 2010.
  13. ↑ "The Keyed-Hash Message Authentication Code (HMAC)" (PDF). Retrieved 20 December 2023.
  14. ↑ SHA-3 Derived Functions nvlpubs.nist.gov
  15. ↑ "ISO/IEC 9797-1:2011". ISO. Retrieved 20 December 2023.
  16. ↑ "ISO/IEC 9797-2:2011". ISO. Retrieved 20 December 2023.
  17. ↑ "ISO/IEC 9797-3:2011". ISO. Retrieved 20 December 2023.
  18. ↑ "ISO/IEC 29192-6:2019". ISO. Retrieved 20 December 2023.
  19. ↑ "Mac Security Overview", Mac® Security Bible, Wiley Publishing, Inc., 1 November 2011, pp. 1–26, doi:10.1002/9781118257739.ch1, ISBN   9781118257739

    Related Research Articles

    In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

    <span class="mw-page-title-main">HMAC</span> Computer communications hash algorithm

    In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

    <span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

    Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

    <span class="mw-page-title-main">Digital signature</span> Mathematical scheme for verifying the authenticity of digital documents

    A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.

    In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

    In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

    <span class="mw-page-title-main">Ciphertext</span> Encrypted information

    In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

    <span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

    A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

    CRYPTREC is the Cryptography Research and Evaluation Committees set up by the Japanese Government to evaluate and recommend cryptographic techniques for government and industrial use. It is comparable in many respects to the European Union's NESSIE project and to the Advanced Encryption Standard process run by National Institute of Standards and Technology in the U.S.

    In cryptography, padding is any of a number of distinct practices which all include adding data to the beginning, middle, or end of a message prior to encryption. In classical cryptography, padding may include adding nonsense phrases to a message to obscure the fact that many messages end in predictable ways, e.g. sincerely yours.

    There are a number of standards related to cryptography. Standard algorithms and protocols provide a focus for study; standards for popular applications attract a large amount of cryptanalysis.

    Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.

    <span class="mw-page-title-main">CBC-MAC</span> Message authentication code algorithm

    In cryptography, a cipher block chaining message authentication code (CBC-MAC) is a technique for constructing a message authentication code (MAC) from a block cipher. The message is encrypted with some block cipher algorithm in cipher block chaining (CBC) mode to create a chain of blocks such that each block depends on the proper encryption of the previous block. This interdependence ensures that a change to any of the plaintext bits will cause the final encrypted block to change in a way that cannot be predicted or counteracted without knowing the key to the block cipher.

    The Data Authentication Algorithm (DAA) is a former U.S. government standard for producing cryptographic message authentication codes. DAA is defined in FIPS PUB 113, which was withdrawn on September 1, 2008. The algorithm is not considered secure by today's standards. According to the standard, a code produced by the DAA is called a Data Authentication Code (DAC). The algorithm chain encrypts the data, with the last cipher block truncated and used as the DAC.

    In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.

    In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

    The following outline is provided as an overview of and topical guide to cryptography:

    VMAC is a block cipher-based message authentication code (MAC) algorithm using a universal hash proposed by Ted Krovetz and Wei Dai in April 2007. The algorithm was designed for high performance backed by a formal analysis.

    Crypto++ is a free and open-source C++ class library of cryptographic algorithms and schemes written by Wei Dai. Crypto++ has been widely used in academia, student projects, open-source, and non-commercial projects, as well as businesses. Released in 1995, the library fully supports 32-bit and 64-bit architectures for many major operating systems and platforms, including Android, Apple, BSD, Cygwin, IBM AIX, Linux, MinGW, Solaris, Windows, Windows Phone and Windows RT. The project also supports compilation using C++03, C++11, C++14, and C++17 runtime libraries; and a variety of compilers and IDEs, including Borland Turbo C++, Borland C++ Builder, Clang, CodeWarrior Pro, GCC, Intel C++ Compiler (ICC), Microsoft Visual C/C++, and Sun Studio.

    ISO/IEC 9797-1Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher is an international standard that defines methods for calculating a message authentication code (MAC) over data.

    References

    1. ↑ 11-12-20C8
    This page is based on this Wikipedia article
    Text is available under the CC BY-SA 4.0 license; additional terms may apply.
    Images, videos and audio are available under their respective licenses.