Provably-Secure (Chinese Government) SM2 and Simplified SM2 Key Exchange Protocols

Ang Yang, Junghyun Nam, Moonseong Kim, Kim‐Kwang Raymond ChooThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper provides the first formal security proof for the widely adopted SM2 key exchange protocol, a critical component of Chinese commercial and government digital infrastructure. Additionally, it introduces a more efficient, simplified version of SM2, also accompanied by a rigorous security proof, offering enhanced performance without compromising security.

What Problem Does This Paper Address?

The SM2 protocol is a key exchange mechanism based on elliptic curve cryptography (ECC) that has been mandated for use by Chinese government agencies and is prevalent in commercial applications. While ECC offers strong security with smaller key sizes compared to traditional methods like RSA, the security of cryptographic protocols relies heavily on formal proofs within established security models. Despite SM2's widespread adoption, it lacked a formal security proof, leaving its security properties open to debate and potentially vulnerable to attacks that might exploit unproven assumptions. This paper addresses this critical gap by providing a rigorous mathematical proof of SM2's security and proposing an optimized alternative.

Methods

The authors employ the Bellare-Rogaway model, a standard and widely accepted framework for proving the security of key exchange protocols. This model uses a game-based approach where an adversary interacts with simulated protocol participants (oracles) to try and break the protocol's security. The core of their proof relies on the indistinguishability-based security notion, meaning an adversary cannot distinguish between a real session key and a randomly generated one.

The security of both the original SM2 and their simplified version is proven under the Elliptic Curve Discrete Logarithm Problem (ECDLP) assumption. ECDLP is a computationally hard problem in mathematics, and its difficulty is the foundation for the security of many ECC-based cryptosystems. If an adversary can solve ECDLP, they can break the protocol. The proofs are conducted within the random oracle model, a common abstraction in cryptography where hash functions are treated as ideal random oracles.

The paper also introduces a simplified SM2 protocol. This simplification aims to improve efficiency by reducing the number of operations and message exchanges, while maintaining the core cryptographic principles and security guarantees.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The SM2 Protocol Lacked Formal Security Guarantees: Despite its widespread use and government mandate, SM2 had no formal security proof, which is a significant concern for any cryptographic protocol.
  • Formal Proofs are Crucial for Trust: The paper highlights that even widely deployed protocols need rigorous mathematical backing to assure implementers and users of their security properties.
  • ECDLP is the Security Foundation: The security of both SM2 and its simplified version is firmly rooted in the difficulty of the Elliptic Curve Discrete Logarithm Problem, a well-established cryptographic assumption.
  • Efficiency Gains are Possible: The proposed simplified SM2 protocol demonstrates that performance improvements can be achieved without sacrificing security, making it more suitable for resource-constrained environments.
  • Implicit and Explicit Key Confirmation: Both the original and simplified SM2 protocols offer both implicit (assurance that the other party can compute the key) and explicit (assurance that the other party has computed the key) key confirmation, which enhances overall security.

Key Results

The paper successfully provides a provable security guarantee for the SM2 key exchange protocol in the Bellare-Rogaway model under the ECDLP assumption. They also present a simplified SM2 protocol that is more efficient than the original, with a comparable security proof. A comparison table (Table 3) shows that their simplified protocol has a lower computational cost (fewer additions, multiplications, exponentiations, and hash operations) than several other existing pairing-free key exchange protocols, including the original SM2.

Limitations and Future Work

The proofs are conducted within the random oracle model, which is a theoretical construct. While standard, it's worth noting that real-world hash functions are not perfect random oracles. The authors acknowledge that their proofs rely on the ECDLP assumption, meaning the security is as strong as the difficulty of solving ECDLP. Future work could explore the security of these protocols against more advanced or specific types of attacks, or investigate their performance in real-world network conditions. The paper also implicitly suggests that other widely used protocols lacking formal proofs could benefit from similar rigorous analysis.

Summary updated

Abstract

We revisit the SM2 protocol, which is widely used in Chinese commercial applications and by Chinese government agencies. Although it is by now standard practice for protocol designers to provide security proofs in widely accepted security models in order to assure protocol implementers of their security properties, the SM2 protocol does not have a proof of security. In this paper, we prove the security of the SM2 protocol in the widely accepted indistinguishability-based Bellare-Rogaway model under the elliptic curve discrete logarithm problem (ECDLP) assumption. We also present a simplified and more efficient version of the SM2 protocol with an accompanying security proof.
BibTeX
@article{yang2014provably,
  author = {Ang Yang and Junghyun Nam and Moonseong Kim and Kim‐Kwang Raymond Choo},
  title = {{Provably-Secure (Chinese Government) SM2 and Simplified SM2 Key Exchange Protocols}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/825984},
}
Figure