40
T. Oder et al.
2.4 Implementation
To evaluate the performance of the CCA2-conversion and our masking scheme, we
implemented the constructions on an ARM Cortex-M4F. Our evaluation platform
is an STM32F4 DISCOVERY board with 1 Mbyte of flash memory, 192 kbyte of
RAM, a floating-point unit (FPU), and a true random number generator (TRNG). In
order to keep the running time constant and independent, we implemented critical
components in assembly language. Furthermore, to prevent cache timing attacks we
disabled the cache of the on-board flash memory by setting the DCEN bit of the
FLASH_ACR register to zero.
We use SHAKE-128 as instantiation for all random oracles H , G, H , and
H and use a different initialization vector for each of them. As the hashing
plays a minor role in terms of performance, we selected the readable KECCAK
implementation by Saarinen [48] as basis for our implementation as it allowed us
to easily implement side-channel countermeasures. To achieve a constant running
time we decided to implement the binomial sampler from [3] with k = 8. To sample
the necessary randomness, we implemented a PRNG that is initialized with a 256bit seed. For encryption, we generate this secret seed from the on-board TRNG and
then use a PRNG to generate Gaussian noise. As we have to perform a re-encryption
during the decryption that must sample the exact same values, we cannot use the
TRNG for this purpose but have to initialize the PRNG with the same seed. We also
use SHAKE-128 as PRNG.
For the implementation of polynomial arithmetic we need a high-performance
and constant-time modular reduction to prevent remote timing attacks [40]. As a
consequence, the implementation of the NTT and especially the three-instruction
modular reduction from [20] is not suitable. It uses the DIV instruction, which has
a data-dependent variable execution time that can reach from 2 to 12 clock cycles.
Therefore, we implemented a Barrett reduction [6] using the FPU of the CortexM4F that takes 6 clock cycles and is timing-independent. De Clercq et al. [20]
also present an optimized implementation of the NTT. They implement the NTT in
assembly and also proposed an optimized memory access scheme. Their idea is to
store two coefficients in one data word and being able to load/store both coefficients
with the same instruction. Alkim et al. implemented the NTT as well as reported
in [2]. By combining a Montgomery reduction with Barrett reduction, their NTT is
considerably faster than the one from [20] and most importantly also has a constant
execution time. We therefore embedded the NTT from [2] into our implementation.
A theoretically secure masking scheme can still show leakage in an actual
implementation due to unconsidered effects inside the microarchitecture of the
microcontroller. For instance, overriding a register that holds one share with the
content of another register storing the other share will inevitably leak information.
Similarly, one must avoid to load or store both shares from or to memory in
consecutive instructions (or even the same instruction, e.g., load multiple LDM).
Furthermore, carry bits can be a source of leakage. We carefully designed our
implementation to not suffer from these problems. For operations that can be
T. Oder et al.
2.4 Implementation
To evaluate the performance of the CCA2-conversion and our masking scheme, we
implemented the constructions on an ARM Cortex-M4F. Our evaluation platform
is an STM32F4 DISCOVERY board with 1 Mbyte of flash memory, 192 kbyte of
RAM, a floating-point unit (FPU), and a true random number generator (TRNG). In
order to keep the running time constant and independent, we implemented critical
components in assembly language. Furthermore, to prevent cache timing attacks we
disabled the cache of the on-board flash memory by setting the DCEN bit of the
FLASH_ACR register to zero.
We use SHAKE-128 as instantiation for all random oracles H , G, H , and
H and use a different initialization vector for each of them. As the hashing
plays a minor role in terms of performance, we selected the readable KECCAK
implementation by Saarinen [48] as basis for our implementation as it allowed us
to easily implement side-channel countermeasures. To achieve a constant running
time we decided to implement the binomial sampler from [3] with k = 8. To sample
the necessary randomness, we implemented a PRNG that is initialized with a 256bit seed. For encryption, we generate this secret seed from the on-board TRNG and
then use a PRNG to generate Gaussian noise. As we have to perform a re-encryption
during the decryption that must sample the exact same values, we cannot use the
TRNG for this purpose but have to initialize the PRNG with the same seed. We also
use SHAKE-128 as PRNG.
For the implementation of polynomial arithmetic we need a high-performance
and constant-time modular reduction to prevent remote timing attacks [40]. As a
consequence, the implementation of the NTT and especially the three-instruction
modular reduction from [20] is not suitable. It uses the DIV instruction, which has
a data-dependent variable execution time that can reach from 2 to 12 clock cycles.
Therefore, we implemented a Barrett reduction [6] using the FPU of the CortexM4F that takes 6 clock cycles and is timing-independent. De Clercq et al. [20]
also present an optimized implementation of the NTT. They implement the NTT in
assembly and also proposed an optimized memory access scheme. Their idea is to
store two coefficients in one data word and being able to load/store both coefficients
with the same instruction. Alkim et al. implemented the NTT as well as reported
in [2]. By combining a Montgomery reduction with Barrett reduction, their NTT is
considerably faster than the one from [20] and most importantly also has a constant
execution time. We therefore embedded the NTT from [2] into our implementation.
A theoretically secure masking scheme can still show leakage in an actual
implementation due to unconsidered effects inside the microarchitecture of the
microcontroller. For instance, overriding a register that holds one share with the
content of another register storing the other share will inevitably leak information.
Similarly, one must avoid to load or store both shares from or to memory in
consecutive instructions (or even the same instruction, e.g., load multiple LDM).
Furthermore, carry bits can be a source of leakage. We carefully designed our
implementation to not suffer from these problems. For operations that can be