Symmetric Cryptography 2

The Exact Multi-User Security of 2-Key Triple DES

Speakers: [Speaker Name Not Provided in Transcript/Metadata]

Conference: RSAC 2024

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

Overview

This talk delves into the critical, yet often overlooked, multi-user security of 2-Key Triple DES (2K3DES). While the Data Encryption Standard (DES) is a legacy cipher, its cascaded variant, 2K3DES, astonishingly remains in active use by several major organizations, including ISO and EMVCo, and is accepted by NIST for legacy decryption. The presentation addresses a significant gap in cryptographic understanding: the lack of a tight security proof for 2K3DES in a multi-user setting. Previous analyses provided attack complexities but lacked corresponding security proofs, leaving open the possibility of improved, more efficient attacks.

The research presented here establishes a definitive, tight multi-user security bound for 2K3DES. This groundbreaking work confirms that current attack complexities are optimal, providing a robust mathematical foundation for assessing the real-world resilience of systems still reliant on this older standard. Furthermore, the talk reveals that common security strengthening mechanisms, such as the FX construction, offer only marginal benefits for 2K3DES, contrasting with its effectiveness for 3-Key Triple DES (3K3DES).

The implications of this research are substantial for system architects, security professionals, and compliance officers. By providing a concrete formula (112 - log2 Q bits) to calculate the remaining secure lifetime of 2K3DES implementations based on the total number of queries (Q), the work empowers organizations to make informed decisions regarding migration strategies. It underscores the urgent need to identify and transition away from 2K3DES for new encryption, while offering a clearer understanding of the risks associated with its continued use for legacy decryption.

Background

▶ Watch: Introduction and summary of 2-Key Triple DES security results (0:00)

The Data Encryption Standard (DES) was a groundbreaking symmetric-key block cipher designed in the early 1970s. However, its original 56-bit key size quickly became a critical vulnerability as computational power advanced. To mitigate this, a method called cascaded encryption was introduced, leading to Triple DES (3DES). The core idea is to apply the DES encryption function multiple times with different keys.

There are two primary variants of Triple DES:

1. 3-Key Triple DES (3K3DES): Uses three distinct keys (K1, K2, K3) in an Encrypt-Decrypt-Encrypt (EDE) sequence: E(K1, D(K2, E(K3, plaintext))). This effectively provides a 168-bit key length, though its effective security is closer to 112 bits due to meet-in-the-middle attacks.
2. 2-Key Triple DES (2K3DES): A cost-saving variant that uses only two distinct keys (K1, K2) in an EDE sequence where the first and third keys are identical: E(K1, D(K2, E(K1, plaintext))). While appearing to offer a 112-bit key, 2K3DES has long been known to possess weaker security properties.

The security weaknesses of 2K3DES were identified remarkably early. As far back as 1977, cryptographers pointed out that 2K3DES could be attacked with 2^56 chosen plaintext queries, requiring 2^56 memory and 2^56 offline computations. This meet-in-the-middle attack effectively reduces the security of 2K3DES to that of a single DES encryption, meaning only 56 bits of security. The attack works by fixing an intermediate state (e.g., to zero) and then computing forward from the plaintext using guessed K1 values and backward from the ciphertext using guessed K2 values, looking for a match in the middle.

While 2^56 operations might seem large, it is within the realm of possibility for well-funded adversaries over time, especially for offline computations. Chosen plaintext attacks (CPA) are more challenging to execute in practice than known plaintext attacks (KPA), which for 2K3DES have an even higher complexity of 2^120 / Q, where Q is the number of queries. For example, if 2^40 queries are made, the offline computation is 2^80, still a significant hurdle but stronger than CPA.

Despite these known vulnerabilities and NIST disallowing new 2K3DES encryption in 2015, the standard persists. NIST still accepts 2K3DES for decryption of legacy data, acknowledging the vast amount of existing encrypted information. More surprisingly, international bodies like ISO continue to recommend 2K3DES, and EMVCo, the organization governing credit card transactions, has explicitly stated its continued use. This highlights a critical disconnect between cryptographic best practices and real-world system deployments.

A crucial distinction in cryptographic security analysis is between single-user and multi-user settings.

• Single-user security is the conventional notion where an adversary interacts with a single user operating with a fixed, unknown key.
• Multi-user security is far more realistic for modern systems. In this scenario, multiple users operate concurrently, each with their own distinct key. An adversary can interact with any of these users, in any order, with the goal of attacking at least one of them. Multi-user attacks often provide adversaries with significant advantages, as they can leverage data collected across different users, potentially accelerating key recovery or distinguishing attacks.

Prior work on 2K3DES multi-user security had identified attack costs for both known plaintext and chosen plaintext settings. In the known plaintext setting, multi-user attack costs were found to be similar to single-user costs. However, in the chosen plaintext setting, multi-user attacks offered a slight advantage, reducing the attack complexity. Crucially, no security proofs were known to match these attack complexities in the multi-user context. This left an open question: could future research uncover even more efficient multi-user attacks, rendering 2K3DES practically broken even sooner than anticipated? This research fills that void.

For comparison, 3K3DES already had established tight multi-user security bounds. Furthermore, its multi-user security could be demonstrably strengthened by applying the FX construction, which involves XORing additional keys at the beginning and end of the encryption process. The effectiveness of such strengthening mechanisms for 2K3DES was also an open question prior to this work.

Key Findings

▶ Watch: Why 2-Key Triple DES remains relevant for legacy systems (4:50)

The research presented in this talk yields several pivotal findings that significantly advance our understanding of 2-Key Triple DES (2K3DES) in real-world deployments:

1. Tight Multi-User Security Bound Proven: The most significant contribution is the establishment of a tight multi-user security bound for 2K3DES. This means that, for the first time, cryptographers have a mathematical proof demonstrating that existing multi-user attacks against 2K3DES cannot be significantly improved. The derived bound indicates the minimum amount of computation and queries required to break the scheme, effectively guaranteeing its security up to that point. This alleviates concerns that previously known attack complexities might be underestimated due to a lack of a matching proof.

1. Quantifiable System Lifespan Security: The research provides a practical formula for evaluating the security of systems using 2K3DES: 112 - log2 Q bits, where Q represents the total number of queries made across the entire system. This formula allows organizations to quantitatively assess the remaining secure lifetime of their 2K3DES implementations. By monitoring the rate at which Q increases, system administrators can determine when the effective security level drops below an acceptable threshold, guiding decisions on when to cease new encryptions or initiate full migration. The "112" in the bound relates to the inherent security level of 3DES (112 bits) before accounting for data exposure.

1. Ineffectiveness of FX Construction for 2K3DES: The FX construction, a known method for strengthening block ciphers, particularly 3K3DES, was investigated for its applicability to 2K3DES. The findings reveal that while it does provide a marginal increase in security for 2K3DES, the improvement is only approximately 8 bits. This negligible gain makes the FX construction an inefficient and largely impractical mechanism for enhancing the security of 2K3DES, highlighting a fundamental difference in how this strengthening technique applies to the two Triple DES variants.

These findings provide much-needed clarity for organizations still grappling with legacy 2K3DES systems. They transform the understanding of 2K3DES from a cipher with known attacks but unproven multi-user resilience into one with a mathematically defined and optimal security profile, enabling better risk management and strategic planning.

Technical Deep Dive

▶ Watch: Differentiating single-user and multi-user security in cryptography (6:00)

The core of this research lies in proving the tight multi-user security bound for 2-Key Triple DES (2K3DES), a complex task that previous cryptographic analyses had not fully achieved. The speaker explicitly noted that the paper is purely about proof description and would not delve into the intricate details of the mathematical derivations during the talk. However, they outlined the overarching approach and the key innovations employed.

The methodology is rooted in the Coefficient H technique, a widely recognized approach in the field of symmetric key cryptography for proving the security of block ciphers and hash functions. The Coefficient H technique typically involves the following steps:

1. Ideal World Analysis: Define an "ideal world" where the cryptographic primitive (e.g., the block cipher) behaves as a perfect random permutation or oracle.
2. Bad Events: Identify "bad events" that, if they occur in the ideal world, might allow an adversary to distinguish the real construction from the ideal one.
3. Probability Evaluation: Evaluate the probability of these bad events occurring.
4. Real-to-Ideal Ratio: For cases where bad events do not occur, derive the ratio of the probability of observing a particular sequence of queries and responses in the "real world" (with the actual construction) versus the "ideal world."
5. Bound Combination: Combine the probability of bad events and the real-to-ideal ratio to obtain the final security bound.

A critical adaptation for this research, particularly for multi-user security, is the use of the resampling method. This method was previously devised by the same authors and successfully applied to prove the tight security of 3-Key Triple DES (3K3DES). In this modified approach, the cryptographic game is altered such that, at the end, the adversary not only receives query responses but also gains access to all keys and internal states. This setup allows for a more comprehensive analysis of potential attack vectors.

The general steps for driving the multi-user security bound using this enhanced Coefficient H-based proof are:

1. Define Bad Events: This is a crucial step, and in this work, the definition of bad events is closely tied to the resampling method. A "bad event" typically occurs when an internal value derived from a guessed key matches a response from a primitive query, which could indicate a successful distinguishing attack.
2. Evaluate Probability for Bad Events: Calculate the likelihood of these defined bad events occurring.
3. Evaluate Ratio of Real and Ideal Worlds: Determine how closely the real 2K3DES construction mimics a random permutation when no bad events occur.

The speaker highlighted why previous attempts to achieve tight bounds were unsuccessful, particularly in the context of multi-user scenarios. A naive approach to defining intermediate internal values (e.g., Z1, Z2 in the E(K1, D(K2, E(K1, P))) structure) often relies solely on forward sampling. This means starting from the plaintext, guessing K1 to get Z1, then guessing K2 to get Z2, and so on. While this simplifies probability evaluation by avoiding complex conditional dependencies, it leads to non-tight or overly pessimistic security bounds.

For instance, if one defines dummy values only by forward sampling, the probability that a bad event occurs (where an internal value matches a primitive query response tuple with a user's key) might be bounded by QP / 2^(K+N), where QP is the number of primitive queries, K is the key size (56 for DES), and N is the block size (64 for DES). If an adversary makes a full codebook query (Q = 2^N), this naive method suggests a security level of 2^K, or 2^56, which is not tight for a 2K3DES construction that should offer more. This "dilemma" arises because a more accurate, but significantly more complex, evaluation would require considering all possible orders of queries and their interdependencies, leading to an intractable number of conditional probabilities.

The resampling method addresses this dilemma by introducing a more sophisticated strategy for defining internal values and checking for bad events. Instead of relying solely on forward sampling, it allows for a structured query strategy that can adapt. If a bad event is encountered during a forward-structured evaluation, the method can "resample" or re-evaluate using a backward-structured approach. This means that a bad event effectively needs to occur twice (once in the forward direction, once in the backward direction) for the method to fail its definition of a dummy value. This "double-check" mechanism significantly reduces the probability of a bad event occurring and allows for the derivation of a much tighter security bound.

By carefully defining bad events based on this resampling strategy and meticulously evaluating their probabilities, the researchers were able to overcome the limitations of previous proofs. The result is a mathematically sound, tight multi-user security bound that reflects the true resilience of 2K3DES. The specific bound derived, 112 - log2 Q bits, directly stems from this rigorous analysis, considering the inherent structure of 2K3DES and its interaction with multiple keys in a system.

Demo / Proof of Concept

▶ Watch: Presenting the tight multi-user security bound for 2-Key Triple DES (8:00)

The talk focused exclusively on theoretical cryptographic proofs and security analysis. As such, there was no demonstration or proof of concept (PoC) of an attack or a practical implementation. The work presented is purely mathematical, aimed at establishing rigorous security bounds rather than showcasing practical exploitation.

Defensive Implications

▶ Watch: FX construction ineffective for 2-Key Triple DES security strengthening (8:30)

The findings from this research have profound implications for organizations, particularly those managing legacy systems that still rely on 2-Key Triple DES (2K3DES). While the talk confirms that 2K3DES is not "immediately broken," it strongly advises against its continued use for new encryption and provides actionable insights for managing existing deployments.

1. Inventory 2K3DES Usage: The immediate first step for any organization is to conduct a thorough audit to identify all instances where 2K3DES is employed. This includes not only active encryption processes but also any systems that perform decryption of legacy data that was originally encrypted with 2K3DES. This inventory should span applications, databases, communication protocols, and hardware modules (e.g., payment terminals, smart cards).

1. Monitor Data Flow (Q): Once identified, organizations must establish mechanisms to monitor and quantify the total amount of data processed by each 2K3DES instance. This translates directly to tracking the cumulative number of queries (Q) made to the 2K3DES function. The research's security bound of 112 - log2 Q bits is directly dependent on Q. It's prudent to assume that all data flow contributes to Q, even if not explicitly malicious, as the adversary can potentially collect this data.

1. Calculate Remaining Secure Lifespan: With Q being tracked, organizations can use the derived formula to calculate the current effective security level. For instance, if Q reaches 2^40, the security drops to 112 - 40 = 72 bits. If Q reaches 2^56, the security effectively becomes 112 - 56 = 56 bits, matching the single-DES security. This allows systems to decide when to stop new encryption by setting a threshold for an acceptable security level. For example, if 80-bit security is deemed minimal, an organization can calculate the Q value at which this threshold is crossed and plan accordingly.

1. Prepare for Migration: The overarching message is clear: 2K3DES is a legacy cipher and, despite the new tight security proofs, it is not recommended for long-term use. Organizations should start preparing for migration to modern, stronger block ciphers like AES (Advanced Encryption Standard) with appropriate key lengths (e.g., AES-256). This involves:

• Strategic Planning: Develop a comprehensive migration roadmap, including timelines, resource allocation, and budget.
• Technology Evaluation: Identify and pilot new cryptographic libraries and hardware modules.
• Testing and Validation: Thoroughly test new cryptographic implementations to ensure correct functionality and security.
• Data Conversion: Plan for the secure conversion or re-encryption of existing 2K3DES-encrypted data to a stronger standard.

1. Re-evaluate Strengthening Mechanisms: The finding that the FX construction offers only an 8-bit security improvement for 2K3DES means that organizations should not rely on such mechanisms to significantly extend the life of their 2K3DES implementations. Resources would be better spent on migration efforts.

In essence, this research provides the necessary tools for a data-driven risk assessment of 2K3DES. It moves the conversation beyond "it's old and weak" to "it's old and its weakness is now precisely quantified in a multi-user context, so here's how to manage it responsibly until you can fully replace it."

Key Takeaways

• Tight Multi-User Security Confirmed: This research provides the first tight multi-user security proof for 2-Key Triple DES (2K3DES), confirming that existing attack complexities are optimal and cannot be significantly improved.
• Quantifiable Lifetime Security: The security of systems using 2K3DES can now be precisely evaluated using the formula 112 - log2 Q bits, where Q is the total number of queries made across the system. This enables organizations to predict when 2K3DES will become practically vulnerable.
• FX Construction Ineffective: The FX construction, a method known to strengthen 3-Key Triple DES, offers only a negligible 8-bit security improvement for 2K3DES, making it an impractical strengthening mechanism.
• Continued Legacy Use: Despite its known weaknesses and NIST's disallowance for new encryption, 2K3DES is still recommended by ISO and used by EMVCo, and accepted by NIST for legacy decryption, underscoring the real-world relevance of this security analysis.
• Urgent Call for Migration Planning: Organizations must actively inventory all instances of 2K3DES usage, monitor data flow, and use the new security bound to plan and execute migration to modern, stronger cryptographic standards like AES.
• Advanced Cryptographic Proof Techniques: The research achieved its tight security bound by employing the Coefficient H technique combined with a novel resampling method, which addresses the complexities of multi-user security analysis.

About the Speaker(s)

The speaker's name was not provided in the talk metadata or transcript. However, based on the content of the presentation, they are clearly a distinguished researcher and cryptographer specializing in symmetric key cryptography and security proofs of block ciphers. Their work involves advanced mathematical techniques, such as the Coefficient H technique and the development of the resampling method, indicating a deep expertise in theoretical cryptography and formal security analysis. The speaker's ability to present complex proof methodologies and their practical implications demonstrates their significant contributions to the field of cryptographic security.