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

We study the tight multi-user (mu) security of 2-key triple encryption (2kTE) with its application to 2-key TDES. With an n-bit block and k-bit key primitive block cipher, our new mu lower bound regarding the number of primitive queries is \(2^{\min \{2k,k+n\}}/q\) with \(q\) construction queries, which matches the previous best attacks and is tight. The bound ensures \((112 - \log _2 q)\) -bit security with 2-key TDES, and this can be used to evaluate and predict the security of systems supporting 2-key TDES for legacy use. We finally show that the FX construction does not efficiently improve the mu security with 2kTE, unlike the previous result with 3-key triple encryption appeared in CCS 2022. We show a concrete key-recovery attack with \(O(2^{n+k}/q)\) primitive queries.