Secure Binary Field Multiplication

Hwajeong Seo, Chien-Ning Chen, Zhe Liu, Yasuyuki Nogami, Taehwan Park, Jongseok Choi, Howon Kim

TL;DR

This paper tackles the security of binary field multiplication, a crucial operation in cryptography. The authors demonstrate a side-channel attack on a common Look-Up Table (LUT) based implementation and propose a novel masked binary field multiplication method that is more resistant to such attacks.

What Problem Does This Paper Address?

Binary field multiplication is a fundamental building block for many cryptographic algorithms, most notably Elliptic Curve Cryptography (ECC) and Galois/Counter Mode (GCM). Efficient implementations are critical for performance, especially on resource-constrained embedded systems. Two common approaches are bit-wise scanning and Look-Up Table (LUT) based methods. While LUT-based methods are generally considered more secure due to their regular and constant-time nature, this paper investigates their vulnerability to Side Channel Attacks (SCA). Specifically, the authors aim to show that even seemingly secure LUT-based implementations can leak information through power consumption, and they propose a more robust alternative.

Methods

The paper's core contributions lie in both attack and defense:

  • Side-Channel Attack (SCA) on LUT-based Multiplication: The authors employ Horizontal Correlation Power Analysis (CPA) to attack LUT-based binary field multiplication. This attack exploits the fact that LUT construction involves memory access patterns that are correlated with the weights of the operands. By analyzing power traces, they demonstrate the ability to identify operands used in the multiplication process. They specifically target the Lopez et al. method, which involves online LUT construction and subsequent LUT accesses.
  • Masked Binary Field Multiplication: To counter the identified vulnerabilities, the authors propose a new "masked binary field multiplication" method. This approach aims to achieve a regular and constant-time execution without relying on branch operations or LUT accesses. The core idea is to use operand masking to ensure that operations are performed in a predictable manner, thus obscuring information leakage through timing and power consumption. They present both a 32-bit and a 64-bit version of this masked method, incorporating Karatsuba multiplication for performance optimization in the latter.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and experimental demonstration of attacks and a new method, rather than training on large datasets.

Key Insights and Ideas

  • LUTs are not inherently immune to side-channel attacks: Despite their regular structure, the memory access patterns during LUT construction and usage can still leak sensitive information, particularly when analyzed with advanced techniques like Horizontal CPA.
  • Operand masking is a viable defense: The proposed masked binary field multiplication effectively hides information leakage by ensuring predictable operations, even when dealing with varying operand values.
  • Trade-off between security and performance: While the proposed masked method offers enhanced security, it comes at a performance cost compared to some existing, less secure methods. However, the authors argue that for many applications, the security benefits outweigh the performance penalty.
  • Scalability of the masked approach: The integration of Karatsuba multiplication into the masked method demonstrates its potential for efficient implementation on larger operands, which is crucial for modern cryptographic standards.

Key Results

  • The authors successfully demonstrate a Horizontal CPA attack that can identify operands used in LUT-based binary field multiplication by analyzing power traces.
  • They propose a masked binary field multiplication method that is resistant to both timing and power analysis attacks by avoiding branch operations and regular LUT accesses.
  • The proposed masked Karatsuba Block-Comb method shows improved scalability for larger operands compared to previous approaches.
  • Table 4 provides a comparison of clock cycles for various binary field multiplication methods, showing that the proposed method has higher clock cycles but is more secure. For 163-bit multiplication, the proposed method takes 14,445 cycles, while other methods range from 3,274 to 5,057 cycles. For 233-bit multiplication, it takes 20,537 cycles, compared to 8,314 for another method.

Limitations and Future Work

  • Performance overhead: The proposed masked binary field multiplication method incurs a performance penalty compared to some existing, less secure implementations. The authors acknowledge this trade-off and suggest further optimization techniques.
  • Future Work: The authors plan to extend their research by attacking other LUT-based algorithms, such as those used for exponentiation and scalar multiplication. They also intend to investigate the applicability of their attack to binary field squaring and to further optimize the performance of their proposed secure implementation for practical applications. Finally, they aim to evaluate the performance of GCM and other ECC primitives using their secure binary field multiplication method.

Summary updated

Abstract

Binary field multiplication is the most fundamental building block of binary field Elliptic Curve Cryptography (ECC) and Galois/Counter Mode (GCM). Both bit-wise scanning and Look-Up Table (LUT) based methods are commonly used for binary field multiplication. In terms of Side Channel Attack (SCA), bit-wise scanning exploits insecure branch operations which leaks information in a form of timing and power consumption. On the other hands, LUT based method is regarded as a relatively secure approach because LUT access can be conducted in a regular and atomic form. This ensures a constant time solution as well. In this paper, we conduct the SCA on the LUT based binary field multiplication. The attack exploits the horizontal Correlation Power Analysis (CPA) on weights of LUT. We identify the operand with only a power trace of binary field multiplication. In order to prevent SCA, we also suggest a mask based binary field multiplication which ensures a regular and constant time solution without LUT and branch statements.
BibTeX
@article{seo2015secure,
  author = {Hwajeong Seo and Chien-Ning Chen and Zhe Liu and Yasuyuki Nogami and Taehwan Park and Jongseok Choi and Howon Kim},
  title = {{Secure Binary Field Multiplication}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
}
Figure