Paper 2024/1187
STORM — Small Table Oriented Redundancy-based SCA Mitigation for AES
Abstract
Side-channel-analysis (SCA) resistance with cost optimization in AES hardware implementations remains a significant challenge. While traditional masking-based schemes offer provable security, they often incur substantial resource overheads (latency, area, randomness, performance, power consumption). Alternatively, the RAMBAM scheme introduced a redundancy-based approach to control the signal-to-noise ratio, and achieves exponential leakage reduction as redundancy increases. This method results in only a slight increase in area and in power consumption, and a significant decrease in the amount of randomness needed, without any increase in latency. However, it lacks a formal security proof. In this study, we introduce a scheme, denoted STORM, that synergizes RAMBAM's methodology with the utilization of look-up-tables (LUTs) in memory (ROM/RAM) in a redundant domain. STORM, like RAMBAM, is as fast as a typical unprotected implementation and has the same latency, but has a significantly higher maximal clock frequency than RAMBAM, and consumes less than half the power. RAMBAM and STORM are code-based schemes in the sense that their set of representations is a code in the vector space $GF(2)^{8 d}$. RAMBAM requires a richer structure of a ring on $GF(2)^{8 d}$ and a ring homomorphism whereas STORM utilizes a simple vector space. In code-based-masking (CBM), as in all masking schemes, non-interference based notions (t-S/NI) are fundamental for establishing provable security. RAMBAM and STORM diverge from this approach. While CBM employs codes in vector spaces over $GF(2^8)$ for AES protection, RAMBAM and STORM use codes over $GF(2)$ without the need for t-S/NI-gadgets, leaving them both smaller and more efficient. Independence in security proofs typically means that in each individual computation (in a clock-cycle), at least one share does not participate. This approach does not work for RAMBAM where several field multiplications are executed sequentially in a cycle. However, in STORM no multiplications are performed due to its memory based tables, leaving only (independent) bitwise-XORs. Therefore, the reasoning necessary for proving security is different and STORM, unlike RAMBAM, enjoys provable security. We consider two distinct scenarios, \emph{both with provable security}: (1) STORM1 --- ``leakage-free’’ memory reads, demonstrating (1,1,0)-robustness for LUTs with redundancy 2 in the 1-probe model and for LUTs with redundancy 6 in the 2-probe model, and (2) STORM2 --- leaky memory reads, where additional protection mechanisms and a notion of memory-read robustness are introduced. STORM can be implemented not only in HW, but in SW as well. However, this paper and the proofs in it relate to STORM's HW implementations.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- AESDPAHomomorphismLeakageMaskingMemoryRandomizationRAMBAMRedundancyRingsSide-channelSCASTORMSIFA-1LUT
- Contact author(s)
-
belenky @ fortifyiq com
chernyshchyk @ fortifyiq com
karavaev @ fortifyiq com
maksymenko @ fortifyiq com
teper @ fortifyiq com
ryzhkova @ fortifyiq com
itamar levi @ biu ac il
osnat keren @ biu ac il
kreimer @ fortifyiq com - History
- 2024-07-25: approved
- 2024-07-23: received
- See all versions
- Short URL
- https://ia.cr/2024/1187
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1187, author = {Yaacov Belenky and Hennadii Chernyshchyk and Oleg Karavaev and Oleh Maksymenko and Valery Teper and Daria Ryzhkova and Itamar Levi and Osnat Keren and Yury Kreimer}, title = {{STORM} — Small Table Oriented Redundancy-based {SCA} Mitigation for {AES}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1187}, year = {2024}, url = {https://eprint.iacr.org/2024/1187} }