Code Branch Avoidance Techniques in SM2 Elliptic Curve Cryptographic Implementations

This article discusses the security risks associated with code branches based on sensitive data in cryptographic implementations, particularly for the SM2 elliptic curve public key cryptography algorithm used in China's national commercial cryptography standards.

The Problem of Code Branches: When code branches are made based on sensitive values (such as bits of a private key), external observers can infer the secret data through various observable side effects including voltage fluctuations, electromagnetic radiation changes, and memory access patterns. This can lead to complete compromise of secret values.

Point Addition vs Point Doubling: The article explains the computational differences between point addition and point doubling operations in elliptic curve cryptography. For the SM2 curve (y² = x³ - 3x + b), the slope calculations differ: point addition uses λ = (yq - yp)/(xq - xp) while point doubling uses λ = (3xp² - 3)/2yp. The doubling operation requires an additional square computation, creating measurable differences in power consumption and electromagnetic emissions that attackers can exploit.

Montgomery Ladder Approach: The Montgomery Ladder algorithm attempts to equalize computation between branches by always performing both point addition and doubling operations regardless of the branch condition. However, this approach still creates code branches that can be exploited through cache timing attacks (Flush+Reload method), where instruction cache access patterns reveal which branch was taken.

Defense Techniques: The article presents a select-based method to avoid code branches entirely. Instead of branching on sensitive bits, a selection function chooses between a point and the point at infinity (zero point), then always performs point addition:

func selectPoint(out *SM2Point, mask int, a, b *SM2Point) {
// If mask is 0, out = a; if mask is 1, out = b
}
func scalarMultSelect(q *SM2Point, x scalar) (*SM2Point, error) {
out := NewSM2Point()
zero := NewSM2Point()
selected := NewSM2Point()
for _, bit := range x.bits {
out.Double(out)
selectPoint(&selected, bit, zero, q)
out.Add(out, selected)
}
return out, nil
}

This approach ensures constant execution time regardless of secret values, though at the cost of performance. The article emphasizes that code branch avoidance is a fundamental security requirement rather than just masking specific attack vectors.