Let’s introduce a couple of Lattice-based cryptanalyses

In both DSA and ECDSA (the elliptic-curve DSA) procedures, the signature output is a pair (r,s) of integer numbers such that

s × k ≡ ( h + α × r ) mod q,

where α, h, and k are the private key, the hash of the message to be signed, and the ephemeral key ¹, respectively. In particular, r is either the output of the exponentiation (DSA case: g^k) or the scalar point multiplication (ECDSA case: [k]P) procedure.

The following lattice descriptions are based on the results presented in [4], which is more focused on the practical Side-Channel Analysis. However, for a deep read, I suggest the paper by Gabrielle De Micheli and Nadia Heninger.

Timing attacks

Lattice-based cryptanalysis using timing attacks are commonly focused on determining a few bits from the ephemeral key, which can be easily correlated with the private key by using the above equation. For instance, if the exponentiation or scalar point multiplication procedures have been implemented in non-constant-time, then by a simple timing analysis it is possible to find a sample of d signatures (r_i, s_i) with shorter-than-average ephemeral key k_i < q / 2^ℓ_i for some positive integer ℓ_i. Moreover, the dimensional-(d+1) lattice

B =	[ 2W1 × q [ 0 [ ⋮ [ 0	0 2W2 × q ⋱ ⋯	⋯ ⋱ ⋱ 0	⋯ ⋯ 0 2Wd × q	0 ] ⋮ ] ⋮ ] 0 ]
	[ 2W1 × t1	2W2 × t2	⋯	2Wd × td	1 ]

and the integer vectors u = ( 2W₁ × û₁ + q, …, 2W₁ × û₁ + q, 0 ), z = ( λ₁, …, λ_d, α ), and y = ( 2W₁ × ν₁, …, 2W_d × ν_d, α ) satisfy zB - u = y with W_i = 2^ℓ_i, λ_i ∊ { -q, …, q }, and ν_i ∊ { -(q - 1)/2, …, (q - 1)/2 } the signed modular reduction of û_i + q/(2W_i) mod q.

wNAF trace approach

Let’s focus on scalar point multiplications using wNAF scalar codifications. Assuming a window width equals w, two kwnon consecutive non-zero coefficients κ_j and κ_{j + ℓ} leads to an equation with δ α-correlated bits. Each column of the lattice B (with same shape as given above), is determined by the pair (κ_j, κ_{j + ℓ}) along with the public values h and (r,s).

In particular, the entries of the integer vector t coincide with r × s^-1 × 2^{m - j - ℓ - 1} mod q, W = 2^δ where δ is equal to (ℓ - w) and (ℓ - w + 1) for the unsigned and signed approaches ^{2 3}, respectively. In both cases, the integer vector has the same shape like in the timing attack but without the term q, and the entries of u are equal to

• 2^{m + w - ℓ - 1} - (r × s^-1 + 2^{j + w} - 2^{j + ℓ}) × 2^{m - j - ℓ - 1} mod q for the unsigned case (for more details [5]); or
• (2b + 1) × 2^{m + w - ℓ - 2} - (r × s^-1 × 2^{m - j - ℓ - 1}) mod q, where b denotes the sign of κ_{j + ℓ} (for more details [1]).

Solving the lattice

In summary, the private key recovery can be reduced to a Closest Vector Problem (CVP) instance of a given lattice. However, any CVP instance with input lattice B and vector u can be mapped into a Shortest Vector Problem (SVP) instance by looking for a short lattice basis vector in the dimensional-(d + 2) lattice B’

[ B	0 ]
[ u	q ]

In both SVP and CVP instances, one proceeds by reducing the lattice with the LLL or BKZ procedures. But in practice, one proceeds by applying the method by Gama et al. [3], which can be summarized as follows:

• To reduce (using BKZ) another dimensional-(d + 2) lattice β which is computed by shuffling the columns of B’ and multiplying it by a unimodular matrix with low density approximately;
• To look for a short lattice basis vector in the reduced lattice of β: if private key recovery is unsuccessful, update β as the reduced matrix of β and repeat the procedure.

---

References

[1] T. Allan, B. B. Brumley, K. Falkner, J. van de Pol, Y. Yarom, Amplifying side channels through performance degradation, Annual Computer Security Applications Conference - ACSAC 2016, ACM (2016), 422-435 🔗;

[2] G. De Micheli and N. Heninger, Recovering cryptographic keys from partial information, by example, IACR Cryptol. ePrint Arch. 2020: 1506 (2020) 🔗;

[3] N. Gama, P. Q. Nguyen, O. Regev, Lattice Enumeration Using Extreme Pruning, Advances in Cryptology - EUROCRYPT 2010, LNCS 6110, 257-278, 2010 🔗;

[4] S. ul Hassan, I. Gridin, I. M. Delgado-Lozano, C. Pereida-García, J.-J. Chi-Domínguez, A. Cabrera Aldaya, B. B. Brumley, Déjà Vu: Side-Channel Analysis of Mozilla’s NSS, Conference on Computer and Communications Security - CCS 2020, ACM (2020), 1887-1902 🔗;

[5] J. van de Pol, N. P. Smart, Y. Yarom, Just a Little Bit More, Topics in Cryptology - CT-RSA 2015, LNCS 9048, 3-21, 2015 🔗.

---