Power Analysis and Countermeasures on the MiMC Block Cipher

Abstract

Modern zero-knowledge (ZK), fully homomorphic encryption (FHE) and Multi-party Computation (MPC) protocols have motivated research interest in Arithmetization-Oriented (AO) cryptographic primitives. The use of these protocols on embedded platforms requires consideration for protection against side-channel analysis (SCA), including timing and power attacks. Compared to traditional bitoriented block ciphers, the design of side-channel countermeasures for AO-based ciphers poses unique challenges due to their different mathematical properties and computation requirements.In this work, we perform side-channel analysis of MiMC, a well-known AO block cipher. We first consider its constant-time implementation over the BN254 prime field for both x86 and ARM-v7 targets. Next, we demonstrate both profiled (SASCA) and unprofiled (linear regression) power analysis of our implementation on the ARM Cortex-M4 microcontroller, showing that a DPA adversary can reduce the key-guessing space to just 231 candidates using only ≈ 32 000 power measurements, and the profiling adversary can perform full key recovery in as few as 100measurements.Hence, we consider and compare two side-channel countermeasures: a classical ISW masking approach, and the redundant number representation (RNR) adapted for large prime fields. For the RNR countermeasure, we show that ≈ 64 bits of redundancy are sufficient to reduce the information leakage enough to make DPA attacks impractical. Our claim is supported both by a standard fixed-vs-random leakage assessment with 10 million collected traces and by quantitative analysis via SASCA attacks. Finally, we compare the performance of the RNR countermeasure with first-order masking. While masking incurs in a ≈ 8.3x overhead on a Cortex-M4 MCU and in an ≈ 81x overhead on an x86-64 CPU, the RNR approach only introduces a ≈ 50% overhead on both targets.