Symmetric Cryptography 1

Symmetric Cryptography 1

Speakers: Yusuke Naito, Mitsubishi Electric Corporation Japan

Conference: RSAC 2024

YouTube: https://www.youtube.com/watch?v=l4Jvw2Rvbeo

Overview

In an era where digital services routinely handle data for millions of users, understanding the security implications of cryptographic primitives in a multi-user context is paramount. This talk by Yusuke Naito from Mitsubishi Electric Corporation Japan delves into the multi-user security of Message Authentication Codes (MACs), specifically focusing on Hash-then-Encrypt (HtE) and its variant, HtXE, within the ideal cipher model. The research addresses a critical gap in existing security proofs by introducing new notions for universal hashing that adequately cover block cipher-based hash functions, which are prevalent in real-world MAC constructions.

The core problem Naito tackles is the degradation of MAC security when an adversary targets a service with multiple users, rather than a single, isolated user. Traditional security analyses often focus on single-user scenarios, which may not accurately reflect the attack surface of modern applications. By rigorously analyzing HtE and HtXE structures, the talk demonstrates how widely adopted MACs like EMAC, XCBC, and TMAC can maintain their robust security guarantees even in multi-user environments, provided certain design principles are followed, particularly the independence of keys. This work is crucial for cryptographic engineers and security architects designing or evaluating systems that rely on MACs for data integrity and authenticity in large-scale deployments.

Background

▶ Watch: Introduction and Message Authentication Code (MAC) definition (0:00)

Message Authentication Codes (MACs) are fundamental cryptographic primitives used to ensure the integrity and authenticity of data. A MAC algorithm takes an arbitrary-length message and a secret key as input, producing a fixed-length tag. This tag allows a receiver, sharing the same secret key, to verify that the message has not been tampered with and originated from a legitimate sender. For instance, in an authentication protocol, Alice generates a tag T = MAC(Key, M) and sends (M, T) to Bob. Bob then re-computes T' = MAC(Key, M) and authenticates the message if T = T'.

Many MACs are designed using block ciphers like AES and often follow a Hash-then-Encrypt (HtE) structure. This structure, represented as E_K(H_L(M)), involves a key hash function H_L (keyed by L) applied to the message M, followed by an outer block cipher E_K (keyed by K) to produce the final tag T. Examples of HtE-type MACs include CBC-MAC, CMAC, and GMAC. The HtE structure is favored for its design simplicity, efficiency (typically calling the block cipher only once per message block), and the relative ease of security proofs, especially when the underlying hash function is a universal hash function.

Traditionally, the Pseudo-Random Function (PRF) security of HtE-based MACs has been analyzed primarily in the single-user setting. In this setting, an adversary attempts to distinguish the HtE construction from a truly random function by making online queries. The security is typically bounded by factors related to the block size N and key size K (e.g., N/2 bits for online queries, K bits for offline key recovery). This analysis assumes the block cipher acts as a secure pseudo-random permutation (SPRP).

However, the real world often involves multi-user scenarios, where an adversary might target a service that manages multiple users, each with their own MAC instance and key. In this setting, an adversary can access U instances of the HtE scheme (or U random functions in the ideal world). Compared to single-user adversaries, multi-user adversaries can gather significantly more information, leading to potential security degradation. Indeed, studies have shown that the multi-user security of some MACs can be considerably weaker than their single-user counterparts. Mitigating this degradation is a crucial research objective in symmetric key cryptography.

A significant challenge in multi-user security is the existence of generic attacks. For instance, a generic attack can recover one user's key with an offline complexity of 2^S / U, where S is the key size of the MAC and U is the number of users. This attack involves making online queries to each user with a simple message (e.g., a zero string) to obtain U tags. The adversary then guesses 2^S / U potential keys, computes the tag for the zero message with each guess, and checks for collisions with the observed online tags. This demonstrates that for single-key HtE schemes (where key size S equals block cipher key size K), K-bit security cannot be achieved in a multi-user setting due to this U-factor degradation. To achieve K-bit security in a multi-user context, HtE schemes must employ at least two independent keys, typically one for the hash function (L) and another for the block cipher (K).

Furthermore, relying on the SPRP assumption for the block cipher in a multi-user setting can introduce U security loss. If U block ciphers are replaced with U random permutations in the security proof, U PRF advantage functions are introduced, diminishing the offline security proportionally to the number of users. To circumvent this degradation, prior research has increasingly evaluated multi-user security in the ideal cipher model. In this model, the block cipher is assumed to be an ideal cipher, meaning the adversary has direct access to its oracle (including inverse operations) through offline queries.

Bose et al. previously proved that in the ideal cipher model, the multi-user security of HtE does not degrade from single-user security, achieving 2^N/2 online security and 2^K offline security. Their proof, however, assumed the underlying hash function was an epsilon-universal hash function. A critical limitation of their work was that their definition of a universal hash function did not encompass ideal cipher queries. This meant their security bounds only applied to non-block cipher-based hash functions (e.g., polynomial hash functions) and could not be extended to common block cipher-based hash functions like the CBC hash function. This gap highlighted the need for new security notions for hash functions that account for offline queries to the ideal cipher, especially when evaluating block cipher-based MACs in the multi-user ideal cipher model.

Key Findings

▶ Watch: Shift to multi-user security and its importance (4:20)

Yusuke Naito's research successfully addresses the limitations of prior multi-user security analyses by introducing novel security notions for hash functions in the ideal cipher model that explicitly account for adversary access to an ideal cipher via offline queries. This advancement allows for a more comprehensive security evaluation of widely used block cipher-based MACs.

The primary key findings include:

1. New Security Notions for Hash Functions: Naito defined two new security notions for hash functions operating within the ideal cipher model:

• Epsilon-1 Regular Hashing in the Ideal Cipher Model: This notion quantifies the adversary's ability to find a message and its valid output from the hash function, even with access to an ideal cipher oracle.
• Epsilon-2 Almost XOR Universal Hashing in the Ideal Cipher Model: This notion measures the adversary's success in finding a pair of messages that result in a specific type of collision (XOR collision) within the hash function's output, again while having ideal cipher query capabilities. These definitions are crucial as they bridge the gap left by previous universal hash definitions, which did not consider ideal cipher queries.

1. Derived Multi-User Security Bounds for HtE and HtXE: Using these new notions, Naito derived general multi-user security bounds for both the standard HtE structure and its more efficient variant, HtXE. These bounds incorporate parameters for the maximum number of online queries to a single user (Q_U), total online queries (Q), and maximum offline queries (P), and notably ensure 2^K-bit security for offline queries, where K is the block cipher key size.

1. Specific Security Bound for CBC Hash Function: The research provides a concrete security bound for the widely used CBC hash function when evaluated under the new ideal cipher model notions. This is a significant contribution, as it validates the security properties of a common hash construction.

1. Proof of Non-Degradation for EMAC, XCBC, and TMAC: By combining the general bounds for HtE and HtXE with the specific bound for the CBC hash function, Naito conclusively demonstrated that the multi-user security of EMAC (an HtE variant using CBC hash), XCBC, and TMAC (HtXE variants using CBC hash) does not degrade from their single-user security levels. Specifically, these MACs achieve K-bit offline security and N/2-bit online security in multi-user settings, provided the hash key L and block cipher key K are independent.

1. Validation of HtXE Efficiency: The talk introduced HtXE as an optimized variant of HtE that uses only a single block cipher key, improving efficiency in terms of memory footprint and speed. Despite this optimization, the research proved that HtXE achieves the same robust multi-user security level as HtE, making it an attractive choice for resource-constrained environments.

Technical Deep Dive

▶ Watch: Generic attack degrading multi-user MAC security (5:00)

The technical core of Naito's research lies in extending the analysis of MAC security from the single-user to the multi-user setting, particularly within the ideal cipher model, to address real-world attack scenarios and ensure robust cryptographic guarantees.

A MAC, fundamentally, is a secret key algorithm MAC(Key, M) -> T. The talk focuses on Hash-then-Encrypt (HtE) constructions, denoted as E_K(H_L(M)). Here, H_L is a keyed hash function with hash key L, and E_K is a block cipher with block cipher key K. Examples include CBC-MAC, CMAC, and GMAC. The efficiency of HtE structures stems from calling the block cipher only once per message block.

In the single-user PRF security game, an adversary aims to distinguish between an HtE instance and a truly random function. The security is typically bounded, achieving K-bit offline security (for key recovery) and N/2-bit online security (for forging tags or distinguishing behavior), assuming the block cipher is a secure Pseudo-Random Permutation (SPRP).

The transition to the multi-user setting introduces significant challenges. Here, an adversary interacts with U independent instances of the MAC algorithm, each with its own key. A critical concern is the generic attack that can recover one of U user keys with an offline complexity of 2^S / U, where S is the key size. This attack proceeds as follows:

1. Online Phase: The adversary queries each of the U users with a predefined message (e.g., a zero string 0^N) to obtain U MAC tags, T_1, ..., T_U.
2. Offline Phase: The adversary guesses 2^S / U possible keys. For each guessed key K_guess, they compute T_guess = MAC(K_guess, 0^N).
3. Collision Check: The adversary checks if any T_guess matches any of the observed T_i. If a match is found, the corresponding K_guess is a candidate for one of the user keys.

This attack demonstrates that if a single key S is used for the entire MAC (i.e., S = K), then K-bit security cannot be maintained in the multi-user setting, as the security degrades by a factor of U. To counter this, HtE schemes must employ at least two independent keys: one for the hash function (L) and one for the block cipher (K).

Another source of degradation comes from the SPRP assumption itself in a multi-user context. When U instances of a block cipher are modeled as U independent random permutations for the security proof, this leads to a U-fold security loss in the bound, reducing the offline security. To circumvent this, cryptographic researchers often resort to the ideal cipher model. In this model, the block cipher E is considered an ideal cipher, meaning the adversary has oracle access to E and its inverse E^-1 for any key and input. This allows for stronger security proofs by abstracting away the specific algebraic properties of a real block cipher.

Previous work by Bose et al. in the ideal cipher model showed that HtE could achieve 2^K offline security and 2^N/2 online security in a multi-user setting, provided the underlying hash function H was epsilon-universal. However, their definition of epsilon-universality did not account for queries to the ideal cipher. This meant their proofs did not cover block cipher-based hash functions like the CBC hash function, which are common in practical MACs.

Naito's key technical contribution is the introduction of two new security notions for hash functions in the ideal cipher model to bridge this gap:

1. Epsilon-1 Regular Hashing in the Ideal Cipher Model: This notion captures the probability that an adversary, with access to an ideal cipher oracle, can find a message M and a hash key L such that H_L(M) produces a specific valid output.
2. Epsilon-2 Almost XOR Universal Hashing in the Ideal Cipher Model: This notion quantifies the probability that an adversary, with ideal cipher access, can find two distinct messages M and M' and a hash key L such that H_L(M) XOR H_L(M') equals a specific target value (typically zero, representing a collision).

Using these refined notions, Naito derived a general multi-user security bound for HtE constructions. The bound for distinguishing HtE from a random function, in the ideal cipher model, is given by a complex formula involving:

• epsilon_1 and epsilon_2 (from the new hash function notions)
• Q_U: maximum number of online queries to a single user.
• Q: total number of online queries across all users.
• P: maximum number of offline queries to the ideal cipher.

Crucially, a term in this bound, proportional to Q^2 / 2^N and P / 2^K, ensures that the offline security is 2^K bits (meaning K-bit security for key recovery) and online security is 2^N/2 bits (meaning N/2-bit security against forgery or distinguishing attacks).

The research then applied these notions to the CBC hash function, proving specific bounds for its epsilon_1 and epsilon_2 values. By combining these with the general HtE bound, Naito demonstrated that EMAC (which is HtE with a CBC hash) achieves K-bit offline security and N/2-bit online security in the multi-user setting. This confirms that EMAC's multi-user security does not degrade from its single-user security, provided L and K are independent.

Furthermore, Naito introduced HtXE, a variant of HtE designed for improved efficiency. HtXE uses a single block cipher key K for the outer encryption, but incorporates an independent key L into the middle state of the hash function. This structure maintains the efficiency benefits of a single block cipher key while introducing the necessary key independence to thwart multi-user generic attacks. Examples of HtXE-like constructions include XCBC and TMAC. Naito derived a multi-user security bound for HtXE, demonstrating that it achieves the same security level as HtE. When combined with the CBC hash function bounds, it was proven that XCBC and TMAC also achieve K-bit offline security and N/2-bit online security in multi-user scenarios, again without degradation from their single-user guarantees.

The technical rigor of Naito's work lies in carefully defining cryptographic notions to match real-world attack capabilities (multi-user, ideal cipher access) and then applying these to prove the enduring security of practical MAC constructions.

Demo / Proof of Concept

▶ Watch: Addressing security degradation with the Ideal Cipher Model (8:00)

The provided transcript does not mention any demonstration, proof of concept, or practical implementation. The talk focuses purely on theoretical cryptographic analysis, the definition of new security notions, and the derivation of security bounds for MAC constructions.

Defensive Implications

▶ Watch: Limitations of existing universal hash function definitions (9:00)

Yusuke Naito's research offers critical insights for practitioners involved in designing, implementing, and evaluating secure systems, particularly those relying on Message Authentication Codes in multi-user environments.

1. Prioritize Multi-User Security: The most fundamental implication is that multi-user security analysis is indispensable for MACs deployed in services that handle multiple users. Relying solely on single-user security proofs can lead to a false sense of security, as generic attacks can significantly degrade security in a multi-user context (e.g., 2^S / U key recovery complexity). Defenders should always consider the number of users (U) and its impact on the effective security level.

1. Ensure Key Independence: To achieve K-bit security for MACs like EMAC, XCBC, and TMAC in multi-user settings, it is paramount to ensure that the hash key (L) and the block cipher key (K) are independent. If these keys are derived from a single master key in a way that makes them interdependent, or if they are simply the same key, the multi-user security guarantees demonstrated in this research may not hold. Key derivation functions should be used to generate distinct and independent L and K values.

1. Confidence in EMAC, XCBC, and TMAC: The research provides strong theoretical backing for the continued use of well-established MACs such as EMAC, XCBC, and TMAC in multi-user systems. It confirms that these constructions, when properly keyed, maintain their expected security levels (K-bit offline and N/2-bit online security) without degradation, even when facing adversaries with significant computational power and access to multiple instances. This validation is crucial for cryptographic engineers making design choices for robust systems.

1. Consider HtXE for Efficiency: The HtXE structure, exemplified by XCBC and TMAC, offers an efficient alternative to HtE by using a single block cipher key while still achieving the same strong multi-user security. For resource-constrained environments or applications where performance is critical, HtXE variants provide a validated path to both efficiency and robust security.

1. Hash Function Security in Depth: The introduction of epsilon-1 Regular Hashing in the Ideal Cipher Model and epsilon-2 Almost XOR Universal Hashing in the Ideal Cipher Model highlights the need for a deeper understanding of hash function properties, especially when they are block cipher-based and operate within a larger cryptographic construction. Defenders should be aware that the security of the hash component is not merely about collision resistance but also about its behavior when an adversary has powerful query capabilities to the underlying block cipher. When choosing or designing hash functions for MACs, ensure their security has been rigorously analyzed in appropriate threat models.

In summary, this research reinforces the importance of meticulous cryptographic design and analysis, particularly concerning key management and the choice of primitives, to ensure that MACs provide their intended security guarantees in the complex, multi-user environments prevalent in modern digital infrastructure.

Key Takeaways

• Multi-user security is a distinct and critical concern for MACs, as adversaries targeting services with multiple users can exploit weaknesses not apparent in single-user analyses, potentially leading to significant security degradation.
• Generic attacks can compromise MAC keys in multi-user settings with 2^S / U offline complexity, demonstrating that K-bit security cannot be achieved for single-key MACs when U users are involved.
• Independent keys for hashing (L) and block ciphering (K) are essential for MACs like HtE and HtXE to maintain K-bit security in multi-user environments.
• New security notions for hash functions in the Ideal Cipher Model were introduced, specifically epsilon-1 Regular Hashing and epsilon-2 Almost XOR Universal Hashing, which correctly account for adversary access to ideal cipher queries and enable rigorous analysis of block cipher-based hash functions.
• EMAC, XCBC, and TMAC are robust in multi-user settings, with this research conclusively proving that their multi-user security does not degrade from their single-user security levels (K-bit offline, N/2-bit online) when properly keyed.
• HtXE structures (like XCBC and TMAC) offer an efficient, single-block-cipher-key alternative to HtE while providing equivalent strong multi-user security, making them suitable for performance-sensitive applications.

About the Speaker(s)

Yusuke Naito is a researcher affiliated with Mitsubishi Electric Corporation Japan. His work, as presented in this talk at RSAC 2024, focuses on the foundational aspects of symmetric key cryptography, particularly the multi-user security of Message Authentication Codes (MACs). Naito's research delves into the theoretical underpinnings of cryptographic constructions like Hash-then-Encrypt (HtE) and HtXE, employing advanced security models such as the ideal cipher model to derive rigorous proofs and establish security bounds for practical MAC algorithms. His contributions include defining novel security notions for hash functions to address limitations in existing cryptographic analyses, thereby enhancing the understanding and assurance of MAC security in complex, multi-user environments.