china - Nocturnalknight's Lair

What Makes SM2 Encryption Special? China’s Recommended Algorithm

By [email protected] | December 9, 2023 | Comments 0 Comment

This article is intended for security enthusiasts or otherwise for people with an advanced understanding of Cryptography and some Programming. I have tried to give in some background theory a very basic implementation.

Are there backdoors in AES and what is China’s response to it?

The US NIST has been pushing AES as the standard for symmetric key encryption. However, many luminaries in cryptographic research and industry observers suspect that as possibly pushing a cipher with an NSA/ GCHQ backdoor. For Chinese entities (Government or commercial), the ShāngMì (SM) series of ciphers provide alternatives. The SM9 standards provide a family of algorithms which will perform the entire gamut of things that RSA or AES is expected to do. They include the following.

SM2 provides signature and verification based on Elliptic Curve Cryptography (ECC)
SM3 is a hashing algorithm (Alternative to AES Hash)
SM4 is a set of encryption/decryption block-cipher algorithms

SM4 was developed by Lü Shuwang in 2007 and became a national standard (GB/T 32907–2016) in 2016 [RFC 8998].

Elliptic Curve Cryptography (ECC)

ECC is one of the most prevalent approaches to public-key cryptography, along with Diffie–Hellman, RSA & YAK

Public-key Cryptography

Public-key cryptography relies on the generation of two keys:

one private key which must remain private
one public key which can be shared with the world

It is impossible to know a private key from a public key (it takes more than centuries to compute – assuming a workable quantum computer is infeasible using existing material science). It is possible to prove the possession of a private key without disclosing it. This proof can be verified by using its corresponding public key. This proof is called a digital signature.

High-level Functions

ECC can perform signature and verification of messages (authenticity). ECC can also perform encryption and decryption (confidentiality), however, not directly. For encryption/decryption, it needs the help of a shared secret aka Key.

It achieves the same level of security as RSA (Rivest-Shamir-Adleman), the traditional public-key algorithm, using substantially shorter key sizes. This reduction translates into lower processing requirements and reduced storage demands. For instance, an ECC 256-bit key provides comparable security to an RSA 3072-bit key.

For brevity’s sake, I’d refer you to Hans Knutson’s very well-explained article on Hacker Noon

Theory Summary: A Look Inside SM2 Key Generation

This section aims to offer a simplified understanding of different parameters found in SM2 libraries and their corresponding meanings, drawing inspiration from the insightful guides by Hans Knutson on Hacker Noon and Svetlin Nakov’s CryptoBook. (links in the reference section)

Comparing RSA and ECC Key Generation:

RSA: Based on prime number factorization.
- Private key: Composed of two large prime numbers (p and q).
- Public key: Modulus (m) obtained by multiplying p and q (m = p * q).
- Key size: Determined by the number of bits in modulus (m).
- Difficulty: Decomposing m back into p and q is computationally intensive.
ECC: Leverages the discrete logarithm of elliptic curve elements.
- Elliptic curve: Defined as the set of points (x, y) satisfying the equation y^2 = x^3 + ax + b.
- Example: Bitcoin uses the curve secp256k1 with the equation y^2 = x^3 + 7.
- Point addition: Defined operation on points of the curve.

Key Generation in SM2:

Domain parameters:
- A prime field p of 256 bits.
- An elliptic curve E defined within the field p.
- A base point G on the curve E.
- Order n of G, representing the number of points in the subgroup generated by G.
Private key:
- Randomly chosen integer d (1 < d < n).
Public key:
- Point Q = d * G.

Understanding Parameters:

Prime field p: Defines the mathematical space where the curve operates.
Elliptic curve E: Provides a structure for performing cryptographic operations.
Base point G: Serves as a starting point for generating other points on the curve.
Order n: Represents the number of points in the subgroup generated by G, which dictates the security level of the scheme.
Private key d: Secret integer randomly chosen within a specific range.
Public key Q: Point obtained by multiplying the private key d with the base point G.

Visualization:

Imagine a garden with flowers planted on specific points (x, y) satisfying a unique equation. This garden represents the elliptic curve E. You have a special key (d) that allows you to move around the garden and reach a specific flower (Q) using a defined path. Each step on this path is determined by the base point G. While anyone can see the flower (Q), only you have the knowledge of the path (d) leading to it, thus maintaining confidentiality.

This analogy provides a simplified picture of key generation in SM2, illustrating the interplay between different parameters and their cryptographic significance.

Diving Deeper into SM2/SM3/SM4 Integration with Golang

This section focuses on the integration of the Chinese cryptographic standards SM2, SM3, and SM4 into Golang applications. It details the process of porting Java code to Golang and the specific challenges encountered.

Open-Source Implementations:

GmSSL: Main open-source implementation of SM2/SM3/SM4, stands for “Guomi.”
Other implementations: gmsm (Golang), gmssl (Python), CFCA SADK (Java).

Porting Java Code to Golang:

Goal: Reverse-engineer the usage of CFCA SADK in Java code and adapt the corresponding functionality in Golang using gmsm.
Approach:
- Hashing (SM3) and encryption (SM4) algorithms were directly ported using equivalent functions across languages.
- Security operations added to a classic REST API POST required specific attention.
- Step 1:
  - Original parameters are concatenated in alphabetical order.
  - API key is appended.
  - The combined string is hashed using SM3.
  - The resulting hash is added as an additional POST parameter.
- Step 2:
  - Original parameters are concatenated in alphabetical order.
  - The signature is generated using SM2.
  - Challenge: Golang library lacked PKCS7 formatting support for signatures, only supporting American standards.
  - Solution: Modification of the Golang library to support PKCS7 formatting for SM2 signatures.

Response Processing:

Response body is encrypted using SM4 with a key derived from the API key.
Response body includes both an SM3 hash and SM2 signature for verification.

Key Takeaways:

Porting cryptographic algorithms across languages requires careful consideration of specific functionalities.
Lack of standard support for specific formats (PKCS7 in this case) might necessitate library modification.
Integrating SM2/SM3/SM4 in Golang requires utilizing libraries like gmsm and potentially adapting them for specific needs.

Getting your Hands Dirty

Go to https://github.com/guanzhi/GmSSL/releases download the version for your OS and move to your working directory.

1 - $ unzip or tar -xvf GmSSL-master.zip/tar
2 - $ mkdir build
    $ cd build
    $ cmake ..
    $ make
    $ make test
    $ sudo make install
3 - $ gmssl version
    $ GmSSL 3.1.0 Dev
4 -
$ KEY=11223344556677881122334455667788
$ IV=11223344556677881122334455667788

$ echo hello | gmssl sm4 -cbc -encrypt -key $KEY -iv $IV -out sm4.cbc
$ gmssl sm4 -cbc -decrypt -key $KEY -iv $IV -in sm4.cbc

$ echo hello | gmssl sm4 -ctr -encrypt -key $KEY -iv $IV -out sm4.ctr
$ gmssl sm4 -ctr -decrypt -key $KEY -iv $IV -in sm4.ctr

$ echo -n abc | gmssl sm3
$ gmssl sm2keygen -pass 1234 -out sm2.pem -pubout sm2pub.pem
$ echo -n abc | gmssl sm3 -pubkey sm2pub.pem -id 1234567812345678
$ echo -n abc | gmssl sm3hmac -key 11223344556677881122334455667788

$ gmssl sm2keygen -pass 1234 -out sm2.pem -pubout sm2pub.pem

$ echo hello | gmssl sm2sign -key sm2.pem -pass 1234 -out sm2.sig #-id 1234567812345678
$ echo hello | gmssl sm2verify -pubkey sm2pub.pem -sig sm2.sig -id 1234567812345678

$ echo hello | gmssl sm2encrypt -pubkey sm2pub.pem -out sm2.der
$ gmssl sm2decrypt -key sm2.pem -pass 1234 -in sm2.der

$ gmssl sm2keygen -pass 1234 -out sm2.pem -pubout sm2pub.pem

$ echo hello | gmssl sm2encrypt -pubkey sm2pub.pem -out sm2.der
$ gmssl sm2decrypt -key sm2.pem -pass 1234 -in sm2.der

$ gmssl sm2keygen -pass 1234 -out rootcakey.pem
$ gmssl certgen -C CN -ST Beijing -L Haidian -O PKU -OU CS -CN ROOTCA -days 3650 -key rootcakey.pem -pass 1234 -out rootcacert.pem -key_usage keyCertSign -key_usage cRLSign
$ gmssl certparse -in rootcacert.pem

How to Get Keys

The private key used for SM2 signing was provided to us, along with a passphrase for testing purposes. Of course, in production systems, the private key is generated and kept private. The file extension is .sm2; the first step was to make use of it.

It can be parsed with:

$ openssl asn1parse -in file.sm2

    0:d=0  hl=4 l= 802 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim: INTEGER           :01
    7:d=1  hl=2 l=  71 cons: SEQUENCE
    9:d=2  hl=2 l=  10 prim: OBJECT            :1.2.156.10197.6.1.4.2.1
   21:d=2  hl=2 l=   7 prim: OBJECT            :1.2.156.10197.1.104
   30:d=2  hl=2 l=  48 prim: OCTET STRING      [HEX DUMP]:8[redacted]7
   80:d=1  hl=4 l= 722 cons: SEQUENCE
   84:d=2  hl=2 l=  10 prim: OBJECT            :1.2.156.10197.6.1.4.2.1
   96:d=2  hl=4 l= 706 prim: OCTET STRING      [HEX DUMP]:308[redacted]249

The OID 1.2.156.10197.1.104 means SM4 Block Cipher. The OID 1.2.156.10197.6.1.4.2.1 simply means data.

.sm2 files are an ASN.1 structure encoded in DER and base64-ed. The ASN.1 structure contains (int, seq1, seq2). Seq1 contains the SM4-encrypted SM2 private key x. Seq2 contains the x509 cert of the corresponding SM2 public key (ECC coordinates (x,y) of the point X). From the private key x, it is also possible to get X=x•P.

The x509 certificate is signed by CFCA, and the signature algorithm 1.2.156.10197.1.501 means SM2 Signing with SM3.

How to Sign with SM2

Now that the private key x is known, it is possible to use it to sign the concatenation of parameters and return the PKCS7 format expected.

As a reminder, ECC Digital Signature Algorithm takes a random number k. This is why it is important to add a random generator to the signing function. It is also difficult to troubleshoot: signing the same message twice will provide different outputs.

The signature will return two integers, r and s, as defined previously.

The format returned is PKCS7, which is structured with ASN.1. The asn1js tool is perfect for reading and comparing ASN.1 structures. For maximum privacy, it should be cloned and used locally.

The ASN.1 structure of the signature will follow:

The algorithm used as hash, namely 1.2.156.10197.1.401 (sm3Hash)
The data that is signed, with OID 1.2.156.10197.6.1.4.2.1 (data)
A sequence of the x509 certificates corresponding to the private keys used to sign (we can sign with multiple keys)
A set of the digital signatures for all the keys/certificates signing. Each signature is a sequence of the corresponding certificate information (countryName, organizationName, commonName) and finally the two integer r and s, in hexadecimal representation

To generate such signature, the Golang equivalent is:

import (
	"math/big"
	"encoding/hex"
	"encoding/base64"
	"crypto/rand"
	"github.com/tjfoc/gmsm/sm2"
	"github.com/pgaulon/gmsm/x509" // modified PKCS7
)

[...]

	PRIVATE, _ := hex.DecodeString("somehexhere")
	PUBLICX, _ := hex.DecodeString("6de24a97f67c0c8424d993f42854f9003bde6997ed8726335f8d300c34be8321")
	PUBLICY, _ := hex.DecodeString("b177aeb12930141f02aed9f97b70b5a7c82a63d294787a15a6944b591ae74469")

	priv := new(sm2.PrivateKey)
	priv.D = new(big.Int).SetBytes(PRIVATE)
	priv.PublicKey.X = new(big.Int).SetBytes(PUBLICX)
	priv.PublicKey.Y = new(big.Int).SetBytes(PUBLICY)
	priv.PublicKey.Curve = sm2.P256Sm2()

	cert := getCertFromSM2(sm2CertPath) // utility to provision a x509 object from the .sm2 file data
	sign, _ := priv.Sign(rand.Reader, []byte(toSign), nil)
	signedData, _ := x509.NewSignedData([]byte(toSign))
	signerInfoConf := x509.SignerInfoConfig{}
	signedData.AddSigner(cert, priv, signerInfoConf, sign)
	pkcs7SignedBytes, _ := signedData.Finish()
	return base64.StdEncoding.EncodeToString(pkcs7SignedBytes)

Key Takeaways: Demystifying SM2 Cryptography

SM2 relies on Elliptic Curve Cryptography (ECC): This advanced mathematical method provides superior security compared to traditional RSA algorithms.
ECC keys are unique: The public key is a point reached by repeatedly adding the base point to itself a specific number of times. This number acts as the private key and remains secret.
ECC signatures are dynamic: Unlike static signatures, ECC signatures use a random element, ensuring they vary even for the same message. Each signature consists of two unique values (r and s).
Troubleshooting tools: ASN.1 issues can be tackled with asn1js, while Java problems can be identified using jdb and jd-gui.
Cryptography requires expertise: Understanding and implementing cryptographic algorithms like SM2 demands specialized knowledge and careful attention.

References & Further Reading: