Breaking the IEEE Encryption Standard – XCB-AES in Two Queries

Tweakable enciphering modes (TEMs) provide security in various storage and space-critical applications, including disk and file-based encryption and packet-based communication protocols. XCB-AES (originally introduced as XCBv2) is specified in the IEEE 1619.2 standard for encryption of sector-oriented storage media and comes with a formal security proof for block-aligned messages. In this work, we present the first plaintext recovery attack on XCB-AES $-$ the shared difference attack, demonstrating that the security of XCB-AES is fundamentally flawed. Our plaintext recovery attack is highly efficient and requires only two queries (one enciphering and one deciphering), breaking the claimed $\mathsf{vil\text{-}stprp}$, $\mathsf{stprp}$ as well as the basic $\mathsf{sprp}$ security. Our shared difference attack exploits an inherent property of polynomial hash functions called separability. We pinpoint the exact flaw in the security proof of XCB-AES, which arises from the separability of polynomial hash functions. We show that this vulnerability in the XCB design strategy has gone unnoticed for over 20 years and has been inadvertently replicated in many XCB-style TEM designs, including the IEEE 1619.2 standard XCB-AES. We also apply the shared difference attack to other TEMs based on XCB $-$ XCBv1, HCI, and MXCB, invalidating all of their security claims, and discuss some immediate countermeasures. Our findings are the first to highlight the need to reassess the present IEEE 1619.2 standard as well as the security and potential deployments of XCB-style TEMs.