Paper 2024/1554

Breaking, Repairing and Enhancing XCBv2 into the Tweakable Enciphering Mode GEM

Abstract

Tweakable enciphering modes (TEMs) provide security in a variety of storage and space-critical applications like disk and file-based encryption, and packet-based communication protocols, among others. XCB-AES (known as XCBv2) is specified in the IEEE 1619.2 standard for encryption of sector-oriented storage media and it comes with a proof of security for block-aligned input messages. In this work, we demonstrate an attack on XCBv2. We show that XCBv2 is $\textit{insecure}$ also for full block messages by presenting a $\textit{partial}$ plaintext recovery attack using $\textit{only}$ two queries. We demonstrate that our attack further applies to the HCI and MXCB TEMs, which follow a similar design approach to XCBv2. Following the responsible disclosure process, we communicated the attack details to IEEE and the authors of XCB-AES. The authors have confirmed the validity of our attack on 02/09/2024. In a recent work, Wang et al. also presented stronger attacks on all XCB variants that can recover $\textit{full}$ plaintext and proposed a fixed variant called XCB*. We highlight that our attack is not applicable on XCB*. Our next contribution is to strengthen the provable security of XCB* (currently $n/3$ bits in queried blocks). We propose a new modular TEM called GEM which can be seen as a generalization of the Hash-CTR-Hash approach as used in XCB-style and HCTR-style TEMs. We are able to prove that GEM achieves full $n$-bit security using $\textit{only}$ $n$-bit PRP/PRF. We also give two concrete GEM instantiations: $\mathsf{KohiNoor}$ and $\mathsf{DaryaiNoor}$, both of which are based on AES-128 and GHASH-256, and internally use variants of the CTR-based weak pseudorandom functions GCTR-3 and SoCTR, respectively. SoCTR uses AES-128 and GCTR-3 is based on $\mathsf{ButterKnife}$-256. Our security proofs show that both $\mathsf{KohiNoor}$ and $\mathsf{DaryaiNoor}$ provide full $n$-bit security. From applications perspective, $\mathsf{DaryaiNoor}$ addresses the need for reusing classical components, while $\mathsf{KohiNoor}$ enhances performance by leveraging a more modern primitive based on the AES/Deoxys round function. Our implementation demonstrate competitive performance: For typical 4KiB sector size, $\mathsf{KohiNoor}$'s performance is on par with AES$_6$-CTET+, yet achieving higher standard security guarantees. $\mathsf{DaryaiNoor}$ is on par with AES-CTET+ performance-wise while also maintaining higher security with standard components. Our GEM instances triple the security margin of XCB* and double that of HCTR2 at the cost of performance loss of only $12\%$ ($\mathsf{KohiNoor}$) and $68\%$ ($\mathsf{DaryaiNoor}$) for 4KiB messages.

Note: In the previous version of this ePrint, alongside the XCBv2 attack and GEM mode, we proposed a simple fix for XCBv2, referred to as XCBv3, and analyzed its security. However, as Wang et al. pointed out in their recently updated work (How to Recover the Full Plaintext of XCB, https://eprint.iacr.org/2024/1527), XCBv3 remains vulnerable to their attacks. Accordingly, we have revised the text and included a discussion in Appendix E, where we generalize their Attack 2 and apply it to XCBv3 to point out the exact flaw.