Category: cryptography

How Will China’s Quantum Advances Change Internet Security?

How Will China’s Quantum Advances Change Internet Security?

Image Generated with Dalle 3

Introduction:

Chinese scientists have recently announced that they have successfully cracked military-grade encryption using a quantum computer with 372 qubits, a significant achievement that underscores the rapid evolution of quantum technology. This breakthrough has sparked concerns across global cybersecurity communities as RSA-2048 encryption—a widely regarded standard—was reportedly compromised. However, while this development signifies an important leap forward in quantum capabilities, its immediate implications are nuanced, particularly for everyday encryption protocols.

Drawing on technical insights from recent papers and analyses, this article delves deeper into the technological aspects of the breakthrough and explores why, despite this milestone, quantum computing still has limitations that prevent it from immediately threatening personal and business-level encryption.

The Quantum Breakthrough: Factoring RSA-2048

As reported by The Quantum Insider and South China Morning Post, the Chinese research team employed a 372-qubit quantum computer to crack RSA-2048 encryption, a cryptographic standard widely used to protect sensitive military information. RSA encryption relies on the difficulty of factoring large numbers, a task that classical computers would take thousands of years to solve. However, using quantum algorithms—specifically an enhanced version of Shor’s algorithm—the team demonstrated that quantum computers could break RSA-2048 in a much shorter time frame.

The breakthrough optimised Shor’s algorithm to function efficiently within the constraints of a 372-qubit machine. This marks a critical turning point in quantum computing, as it demonstrates the potential for quantum systems to tackle problems previously considered infeasible for classical systems. However, the paper from the Chinese Journal of Computers (2024) offers deeper insights into the quantum architecture and algorithmic refinements that made this breakthrough possible, highlighting both the computational power and limitations of the system.

Quantum Hardware and Algorithmic Optimisation

The technical aspects of the Chinese breakthrough, as detailed in the 2024 paper published in the Chinese Journal of Computers (CJC), emphasise the improvements in quantum hardware and algorithmic approaches that were key to this success. The paper outlines how the researchers enhanced Shor’s algorithm to mitigate the high error rates commonly associated with quantum computing, allowing for more stable computations over longer periods. This required optimising quantum gate operations, reducing quantum noise, and employing error-correction codes to preserve the integrity of qubit states.

Despite these improvements, the paper makes it clear that current quantum computers, including the 372-qubit machine used in this experiment, still suffer from several limitations. The system required an extremely controlled environment to maintain qubit coherence, and any deviation from ideal conditions would have introduced significant errors. Furthermore, the researchers faced challenges related to the scalability of the system, as error rates increase exponentially with the number of qubits involved. These limitations are consistent with the broader consensus in the field, as noted by Bill Buchanan and other experts, that practical quantum decryption on a global scale is not yet feasible.

The CJC paper also points out that while the breakthrough is impressive, it does not represent a complete realisation of quantum supremacy—the point at which quantum computers outperform classical computers across a wide range of tasks. The paper discusses the need for further advancements in quantum gate fidelity, qubit interconnectivity, and error correction to make quantum decryption scalable and applicable to broader, real-world encryption protocols.

Technical Analysis based on Li et al. (2024):

The paper explores two approaches for attacking RSA public key cryptography using quantum annealing:

1. Quantum Annealing for Combinatorial Optimization:

  • Method: This approach translates the mathematical attack method into a combinatorial optimization problem suited for the Ising model or QUBO model [1]. The Ising model represents a system of interacting spins, which can be mapped to the problem of factoring large integers used in RSA encryption.
  • Key Contribution: The paper proposes a high-level optimization model for multiplication tables and establishes a new dimensionality reduction formula. This formula reduces the number of qubits needed, thus saving resources and improving the stability of the Ising model [1]. The authors demonstrate this by successfully decomposing a two-million-level integer using a D-Wave Advantage system.
  • Comparison: This approach outperforms previous methods by universities and corporations like Purdue, Lockheed Martin, and Fujitsu [1]. This is achieved by significantly reducing the range of coefficients required in the Ising model, leading to a higher success rate in decomposition.
  • Focus: This technique represents a class of attack algorithms specifically designed for D-Wave quantum computers, known for their use of quantum annealing [1].

2. Quantum Annealing with Classical Methods:

  • Method: This approach combines the quantum annealing algorithm with established mathematical methods for cryptographic attacks, aiming to optimize attacks on specific cryptographic components [1]. It integrates the classical lattice reduction algorithm with the Schnorr algorithm.
  • Key Contribution: The authors leverage the quantum tunneling effect to adjust the rounding direction within the Babai algorithm, allowing for precise vector determination, a crucial step in the attack [1]. Quantum computing’s exponential acceleration capabilities address the challenge of calculating numerous rounded directions, essential for solving lattice problems [1]. Additionally, the paper proposes methods to improve search efficiency for close vectors, considering both qubit resources and time costs [1]. Notably, it demonstrates the first 50-bit integer decomposition on a D-Wave Advantage system, showcasing the algorithm’s versatility [1].
  • Comparison: The paper argues that D-Wave quantum annealing offers a more practical approach for smaller-scale attacks compared to Variational Quantum Algorithms (VQAs) on NISQ (Noisy Intermediate-Scale Quantum) computers. VQAs suffer from the “barren plateaus” problem, which can hinder algorithm convergence and limit effectiveness [1]. Quantum annealing is less susceptible to this limitation and offers an advantage when dealing with smaller-scale attacks.

Citations:

  1. Li, Gao, et al. “A Novel Quantum Annealing Attack on RSA Public Key Cryptosystems.” WC 2024 (2024).

Implications for Civilian Encryption: Limited Immediate Impact

While the Chinese breakthrough is undeniably significant, it is essential to recognise that the decryption of military-grade encryption does not immediately translate to vulnerabilities in civilian encryption protocols. Most personal and business communications rely on RSA-1024, elliptic-curve cryptography (ECC), or other lower-bit encryption systems. These systems remain secure against the capabilities of today’s quantum computers.

Moreover, as highlighted in the paper by Buchanan and echoed in the CJC analysis, many organisations are already transitioning towards post-quantum cryptography (PQC). PQC algorithms are specifically designed to withstand quantum attacks, ensuring that even as quantum computers advance, encryption systems will evolve to meet new threats.

Another key point raised by the CJC paper is that quantum decryption requires an immense amount of resources and computational power. The system used to break RSA-2048 involved highly specialised hardware and extensive computational time. Scaling such an operation to break everyday encryption protocols, such as those used in internet banking or personal communications, would require quantum computers with far more qubits and error-correction capabilities than are currently available.

Preparing for a Quantum Future: Post-Quantum Cryptography

As quantum computing technology evolves, it is imperative that governments, companies, and cybersecurity professionals continue preparing for the eventual reality of quantum decryption. This preparation includes developing and implementing post-quantum cryptographic solutions that are immune to quantum attacks. The National Institute of Standards and Technology (NIST) has already initiated efforts to standardise post-quantum cryptographic algorithms, which are designed to be secure against both classical and quantum attacks. The CJC paper underlines the importance of this transition and suggests that PQC will likely become the new standard in encryption over the next decade.

In addition to PQC, the CJC paper highlights the need for ongoing research into hybrid encryption systems, which combine classical cryptographic techniques with quantum-resistant methods. These hybrid systems could provide a transitional solution, allowing existing infrastructure to remain secure while fully quantum-resistant algorithms are developed and implemented.

Conclusion: A Scientific Milestone with Limited Immediate Consequences

The Chinese research team’s quantum decryption of military-grade encryption is a groundbreaking scientific achievement, signalling that quantum computing is rapidly advancing towards practical applications. However, as emphasised in the technical analyses from the Chinese Journal of Computers and other sources, this breakthrough is not yet a direct threat to civilian encryption systems. Current quantum computers remain limited by their error rates, scalability challenges, and the need for controlled environments, preventing widespread decryption capabilities.

As organisations and governments prepare for a post-quantum future, the adoption of post-quantum cryptography and hybrid systems will be crucial in ensuring that encryption protocols remain robust against both classical and quantum threats. While the breakthrough highlights the potential power of quantum computing, its impact on everyday encryption is still years, if not decades, away.

References and Further Reading

  1. Bill Buchanan, “A Major Advancement on Quantum Cracking,” Medium, 2024.
  2. The Quantum Insider, “Chinese Scientists Report Using Quantum Computer to Hack Military-Grade Encryption,” October 11, 2024.
  3. South China Morning Post, “Chinese Scientists Hack Military-Grade Encryption Using Quantum Computer,” October 2024.
  4. Interesting Engineering, “China’s Scientists Successfully Hack Military-Grade Encryption with Quantum Computer,” October 2024.
  5. Shor, P.W., “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
  6. National Institute of Standards and Technology (NIST), “Post-Quantum Cryptography: Current Status,” 2024.
  7. Chinese Journal of Computers, “Quantum Algorithmic Enhancements in Breaking RSA-2048 Encryption,” 2024.
What Makes SM2 Encryption Special? China’s Recommended Algorithm

What Makes SM2 Encryption Special? China’s Recommended Algorithm

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.

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:

  1. 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.
  2. Private key:
    • Randomly chosen integer d (1 < d < n).
  3. 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

  1. SM2 relies on Elliptic Curve Cryptography (ECC): This advanced mathematical method provides superior security compared to traditional RSA algorithms.
  2. 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.
  3. 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).
  4. Troubleshooting tools: ASN.1 issues can be tackled with asn1js, while Java problems can be identified using jdb and jd-gui.
  5. Cryptography requires expertise: Understanding and implementing cryptographic algorithms like SM2 demands specialized knowledge and careful attention.

References & Further Reading:

  1. Elliptic Curve Cryptography (ECC) 
  2. What is the math behind elliptic curve cryptography? | HackerNoon 
  3. Releases · guanzhi/GmSSL
Bitnami