A Tale of Two Shares: Why Two-Share Threshold Implementation Seems Worthwhile-and Why it is Not

Cong Chen, Mohammad Farmani, Thomas Eisenbarth

TL;DR

This paper explores the feasibility of using only two shares for Threshold Implementations (TI) of lightweight ciphers, aiming to reduce hardware overhead and randomness requirements. While it achieves perfect first-order side-channel resistance and some area reduction, it suffers from a significant second-order leakage, making it less practical than the standard three-share approach.

What Problem Does This Paper Address?

Modern cryptographic hardware is vulnerable to side-channel attacks, which exploit physical leakage (like power consumption or electromagnetic emissions) to extract secret keys. Masking is a common countermeasure, aiming to obscure the secret by splitting it into multiple "shares" and processing them independently. Threshold Implementation (TI) is a popular masking technique that offers provable resistance against first-order attacks and is relatively easy to implement. However, traditional TI schemes, especially those providing higher-order security, incur substantial area and time overheads, and require significant amounts of randomness for re-masking. This makes them too expensive for many resource-constrained embedded applications. The paper investigates whether reducing the number of shares from the typical three to just two could offer a more cost-effective solution while retaining security benefits.

Methods

The core of the paper is the application of a two-share Threshold Implementation (2-TI) to two lightweight block ciphers: Simon and Present. The authors adapt the standard TI methodology, which requires functions to be correct, uniform, and non-complete, to a two-share setting.

  • Non-completeness Adaptation: The key challenge in 2-TI is maintaining non-completeness, a property crucial for glitch resistance. This is achieved by serializing the computation of nonlinear functions into multiple pipeline stages. This means a function's output is computed in steps, with intermediate results stored in registers before being used in the next stage. This serialization ensures that no single subfunction has access to all shares of a secret value, thus preventing leakage even if glitches occur.
  • Cipher Decomposition: For Present, the authors follow a prior work's approach of decomposing its non-linear S-box into simpler quadratic functions, which are then implemented using 2-TI.
  • Leakage Analysis: The paper employs the Test Vector Leakage Assessment (TVLA) methodology, specifically a non-specific paired t-test, to evaluate the side-channel resistance of the implemented ciphers. This statistical test is used to detect deviations from a leakage-free hypothesis. Both first-order and second-order leakages are analyzed.

Datasets

Not discussed in the paper. The evaluation uses simulated and implemented cryptographic circuits rather than external datasets.

Key Insights and Ideas

  • Two-Share TI is Possible, But Compromised: The paper demonstrates that it's technically feasible to implement lightweight ciphers using only two shares for TI, achieving perfect first-order resistance.
  • Second-Order Leakage is the Achilles' Heel: The most significant finding is that 2-TI, while effective against first-order attacks, exhibits a pronounced second-order leakage. This is attributed to the inherent properties of sharing a value into only two parts, where the variance of the shares can still depend on the secret value, unlike in three-share schemes.
  • Serialization Trade-offs: To achieve non-completeness in 2-TI, nonlinear functions must be serialized, leading to increased latency (more clock cycles per round) and potentially larger area overhead for the logic compared to a non-serialized implementation.
  • Practical Implications: Despite the theoretical possibility, the strong second-order leakage makes 2-TI less "worthwhile" for practical security compared to 3-TI, which, while having higher overhead, fails more gracefully against higher-order attacks.

Key Results

  • Simon: The 2-TI implementation of Simon showed resistance to first-order DPA with 10 million traces. However, second-order leakage was detectable with approximately 500 traces.
  • Present: Similarly, the 2-TI Present implementation was resistant to first-order DPA. Second-order leakage was detected with around 6000 traces.
  • Area/Performance:
    • For Simon, 2-TI used more slice registers and LUTs than an unprotected version but less than a 3-TI version. Throughput was significantly reduced due to the doubled clock cycles per round.
  • For Present, 2-TI required more resources than an unprotected version, partly due to extra registers needed for non-completeness.

Limitations and Future Work

  • Second-Order Leakage: The primary limitation is the inherent strong second-order leakage in 2-TI, which undermines its practical security for applications requiring higher-order protection.
  • Throughput Penalty: The serialization required for non-completeness in 2-TI leads to a significant reduction in throughput.
  • Future Work: The authors suggest that the "graceful failure" of three-share TI against higher-order attacks, which was previously considered a drawback, might be an undervalued feature. Further analysis of this aspect could be beneficial. They also note that while their round-based designs are not fully optimized, the principles of 2-TI could be applied to bit-serialized designs to potentially further reduce overhead.

Summary updated

Abstract

This work explores the possibilities for practical Threshold Implementation (TI) with only two shares in order for a smaller design that needs less randomness but is still first-order leakage resistant. We present the first two-share Threshold Implementations of two lightweight block ciphers—Simon and Present. The implementation results show that two-share TI improves the compactness but usually further reduces the throughput when compared with first-order resistant three-share schemes. Our leakage analysis shows that two-share TI can retain perfect first-order resistance. However, the analysis also exposes a strong second-order leakage. All results are backed up by simulation as well as analysis of actual implementations.
BibTeX
@article{chen2016tale,
  author = {Cong Chen and Mohammad Farmani and Thomas Eisenbarth},
  title = {{A Tale of Two Shares: Why Two-Share Threshold Implementation Seems Worthwhile-and Why it is Not}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}
Figure