The Multi-User Security of Triple Encryption, Revisited: Exact Security, Strengthening, and Application to TDES

We study the security of triple encryption in the multi-user setting with its application to Triple DES (TDES) in mind. Although depreciation of TDES is a global trend, the migration will take the next decade, considering the billions of TDES hardware the industry has invested so far. The multi-user security captures the reality of practical systems with multiple users, substantially impacts security, and is already considered in practical protocols such as TLS 1.3. The best multi-user lower bound of TDES is 43-(3/2) łog_2 u bits with u users, which is tractable with a standard PC and is unacceptably low. We devise a new proof to improve the multi-user security and show its tightness by giving a concrete attack. The new bound with the TDES parameters is 79-(1/2) łog_2 u bits. We also propose TEFX that strengthens triple encryption with the FX construction while preserving the compatibility with legacy hardware. TDES with TEFX achieves the multi-user security of 114-(1/2) łog_2 q bits with q TEFX calls: it achieves 84.5 bits with 2^40 users and 2^21 TEFX calls for each user, which is comparable to that of AES (128-40=88 bits).