International Association
for Cryptologic Research

The XEX/XE scheme has been widely used to realize authenticated encryptions (AEs), message authentication codes (MACs), and storage encryptions, such as OCB, PMAC, and XTS. Although these schemes have been extensively deployed in the real world, limited studies have evaluated side-channel attacks (SCAs) on them. In this study, we propose an efficient SCA that can be applied to the XEX/XE scheme. Despite the fact that the offset generated in these modes is guaranteed to have no full offset collision with an overwhelming probability, we analyze their offset-generating routines to exploit the partial offset collisions. Then, we propose a new profiled SCA named XOR-convoluting collision analysis (XCCA), which estimates the sum of keys from two leakages by XOR-convoluting probability distributions that model the leakages. The proposed collision SCA effectively erases the effect of random offsets by using XOR-convolution, whereas conventional collision SCAs are ineffective in this scenario. We validated the proposed SCA through simulations and experimental attacks using real traces. The results confirmed that the proposed SCA reduces the number of traces by up to 90% to achieve a success rate identical to that of a state-of-the-art SCA on OCB in TCHES 2022. Furthermore, we show that the proposed SCA distinguisher (XCCA distinguisher) is a generalization of higher-order SCAs, including non-collision SCAs on masked implementations. The profiled higher-order SCAs on masked implementations can be written in the form of an XCCA distinguisher using XOR-convolution with the new concept of leaking and target selection functions. The generalized representation clarifies how and why a higher-order SCA has better or worse performance from the theoretical viewpoint of noise amplification, which is also demonstrated through experiments and a spectrum analysis based on Walsh–Hadamard transform (WHT). Our analysis reveals that the random offsets of XEX/XE would work as masking from an SCA perspective, and XEX/XE-based encryption would have an inherent first-order SCA resilience under certain conditions.