Algebraic side-channel attacks on Trivium stream cipher

Algebraic Side-Channel Attacks (ASCAs), first proposed by Renauld and Standaert in 2009, are a potent cryptanalysis method against block ciphers. In this paper, the authors initially utilize ASCAs to analyze the security of the Trivium stream cipher, given its concise algebraic structure. Considering its efficiency in both hardware and software implementations, the authors deploy ASCAs to target Trivium implemented both in application specific integrated circuit (ASIC) under the Hamming Distance Leakage Model (HDLM) (noted as CASE 1) and in microcontrollers of various buses (i.e. some common 8-bit, 16-bit, and 32-bit architectures, noted as CASE 2, CASE 3, and CASE 4, respectively) under the Hamming Weight Leakage Model (HWLM). Here, the authors' attacks are conducted on power-simulated targets and not on real devices. For a single power consumption trace without measurement errors, this paper presents experimental results using MiniSat 2.0. Unfortunately, the authors were unable to break the ASIC implementation of Trivium under HDLM (CASE 1) with a time complexity of 2109 s or so, which is worse than the exhaustive key attack. For CASEs 2 to 4, the authors can find the complete 288-bit state of Trivium within a reasonable timeframe. Specially, the success rate can reach 100% with an average solving time of less than 1 s when only measuring the leakages of the first eight consecutive rounds for CASE 2. Furthermore, the authors can still successfully recover the internal state even when obtaining leakages of the first 41 rounds with a random loss rate. In fact, it can tolerate a 74% random loss rate for the first 223 rounds. With regard to the potential errors in the measurements, the authors mitigate them using Tolerant ASCA (TASCA). Similarly, CASE 1 cannot be compromised even in error-free situations, while the authors can still successfully recover the internal state of CASEs 2 to 4 from a single power trace, even with a high error rate, including 100% incorrect measurements. Surprisingly, for CASEs 2 to 4, the authors can recover the internal state with a 100% success rate, regardless of the error rate. As a result, the security of Trivium will not be enhanced when transitioning from a smaller 8-bit platform to a larger 32-bit platform. In the end, the authors will consider some more abstract attack models. The results can provide us with additional insights into the security of Trivium from a different perspective. In this paper, the authors show that the first Algebraic Side-Channel Attacks on Trivium are implemented both in ASIC under Hamming distance leakage model and in microcontrollers of different buses under Hamming weight leakage model. image