diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/IMPLEMENTATIONS.md | 562 | ||||
| -rw-r--r-- | docs/LIBS.md | 111 | ||||
| -rw-r--r-- | docs/VULNS.md | 22 |
3 files changed, 12 insertions, 683 deletions
diff --git a/docs/IMPLEMENTATIONS.md b/docs/IMPLEMENTATIONS.md deleted file mode 100644 index d333ed5..0000000 --- a/docs/IMPLEMENTATIONS.md +++ /dev/null @@ -1,562 +0,0 @@ -# Implementations - -This document contains information about possible implementation choices and algorithms when implementing elliptic curve cryptography. It is mainly concerned with curve models, coordinate systems, addition formulas and scalar multiplication algorithms. Also, only curves over \( \mathbb{F}_p \) are analyzed. - ---- - -## Curve models - -### Weierstrass (full) - -#### Affine -$$ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 $$ - -#### Projective -$$ Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3 $$ - - -### Weierstrass (short) - -[EFD entry](https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html) - - toweierstrass weierx = x - toweierstrass weiery = y - a0 = 1 - a1 = 0 - a2 = 0 - a3 = 0 - a4 = a - a6 = b - fromweierstrass x = weierx - fromweierstrass y = weiery - -#### Affine -$$ y^2 = x^3 + a x + b $$ - -#### Projective -$$ Y^2Z = X^3 + aXZ^2 + bZ^3 $$ - -#### Jacobian -$$ Y^2 = X^3 + aXZ^4 + bZ^6 $$ - - -### Montgomery - -[EFD entry](https://www.hyperelliptic.org/EFD/g1p/auto-montgom.html) - - toweierstrass weierx = x - toweierstrass weiery = y - a0 = b - a1 = 0 - a2 = a - a3 = 0 - a4 = 1 - a6 = 0 - fromweierstrass x = weierx - fromweierstrass y = weiery - -#### Affine -$$ By^2 = x^3 + Ax^2 + x $$ - - -### Edwards - -[EFD entry](https://www.hyperelliptic.org/EFD/g1p/auto-edwards.html) - - toweierstrass u = (c+y)/(c-y) - toweierstrass v = 2 c (c+y)/(x(c-y)) - a0 = 1/(1-d c^4) - a1 = 0 - a2 = 4/(1-d c^4)-2 - a3 = 0 - a4 = 1 - a6 = 0 - fromweierstrass x = 2 c u/v - fromweierstrass y = c(u-1)/(u+1) - -#### Affine -$$ x^2 + y^2 = c^2 (1 + dx^2y^2) $$ - - -### Twisted Edwards - -[EFD entry](https://www.hyperelliptic.org/EFD/g1p/auto-twisted.html) - - toweierstrass u = (1+y)/(1-y) - toweierstrass v = 2 (1+y)/(x(1-y)) - a0 = 1/(a-d) - a1 = 0 - a2 = 4 a/(a-d)-2 - a3 = 0 - a4 = 1 - a6 = 0 - fromweierstrass x = 2 u/v - fromweierstrass y = (u-1)/(u+1) - -#### Affine -$$ ax^2 + y^2=1 + dx^2y^2 $$ - - -### Hessian - -[EFD entry](https://www.hyperelliptic.org/EFD/g1p/auto-hessian.html) - - toweierstrass u = 12(d^3-1)/(d+x+y)-9 d^2 - toweierstrass v = 36(y-x)(d^3-1)/(d+x+y) - a0 = 1 - a1 = 0 - a2 = 0 - a3 = 0 - a4 = -27 d(d^3+8) - a6 = 54(d^6-20 d^3-8) - fromweierstrass x = (36(d^3-1)-v)/(6(u+9 d^2))-d/2 - fromweierstrass y = (v+36(d^3-1))/(6(u+9 d^2))-d/2 - -#### Affine -$$ x^3+y^3+1=3dxy $$ - -#### Projective -$$ X^3 + Y^3 + Z^3 = 3dXYZ $$ - - ---- - -## Coordinates - -### Affine - -$$ [x, y] \in \mathbb{K}^2 $$ - -*(Weierstrass)* infinity is special cased, sometimes represented as \( [0] \). - -*(Weierstrass)* negation: \(-[x, y] = [x, -y] \) - - - To Projective: \( [x, y] \rightarrow (x : y : 1) \) - - To Jacobian: \( [x, y] \rightarrow (x : y : 1) \) - - To Chudnovsky: \( [x, y] \rightarrow (x : y : 1 : 1 : 1) \) - -### Projective -\begin{align*} -[X, Y, Z] &\in \mathbb{K}^3 \\ -[X_1, Y_1, Z_1] &\sim [X_2, Y_2, Z_2] \\ -\text{if}\ X_1 &= λ X_2, \\ - Y_1 &= λ Y_2, \\ - Z_1 &= λ Z_2 \\ -\text{for some}\ λ &\in \mathbb{K}^* \\ -(X : Y : Z) &= \{(λ X, λ Y, λ Z) | λ \in \mathbb{K}^* \} -\end{align*} - -*(Weierstrass)* infinity is \((0 : 1 : 0)\). - -*(Weierstrass)* negation: \( -(X : Y : Z) = (X : -Y : Z) \) - - - To Affine: \( (X : Y : Z) \rightarrow [X/Z, Y/Z] \) - - To Jacobian: \( (X : Y : Z) \rightarrow (X/Z : Y/Z : 1) \) ? - - To Chudnovsky: \( (X : Y : Z) \rightarrow (X/Z : Y/Z : 1 : 1 : 1) \) ? - -### Jacobian -\begin{align*} -[X, Y, Z] &\in \mathbb{K}^3 \\ -[X_1, Y_1, Z_1] &\sim [X_2, Y_2, Z_2] \\ -\text{if}\ X_1 &= λ^2 X_2, \\ - Y_1 &= λ^3 Y_2, \\ - Z_1 &= λ Z_2 \\ -\text{for some}\ λ &\in \mathbb{K}^* \\ -(X : Y : Z) &= \{(λ^2 X, λ^3 Y, λ Z) | λ \in \mathbb{K}^* \} -\end{align*} - -*(Weierstrass)* infinity is \( (1 : 1 : 0) \). - -*(Weierstrass)* negation: \( -(X : Y : Z) = (X : -Y : Z) \) - - - To Affine: \( (X : Y : Z) \rightarrow [X/Z^2, Y/Z^3] \) - - To Projective: \( (X : Y : Z) \rightarrow (X/Z^2 : Y/Z^3 : 1) \) ? - - To Chudnovsky: \( (X : Y : Z) \rightarrow (X : Y : Z : Z^2 : Z^3) \) - -### Chudnovsky -\begin{align*} -[X, Y, Z, Z^2, Z^3] &\in \mathbb{K}^5 \\ -(X : Y : Z : Z^2 : Z^3 ) &= \{(λ^2 X, λ^3 Y, λ Z, λ^2 Z^2, λ^3 Z^3) | λ \in \mathbb{K}^* \} -\end{align*} - -*(Weierstrass)* infinity is \( (1 : 1 : 0 : 0 : 0) \). ? - -*(Weierstrass)* negation: \( -(X : Y : Z : Z^2 : Z^3) = (X : -Y : Z : Z^2 : Z^3) \) - - - To Affine: \( (X : Y : Z : Z^2 : Z^3) \rightarrow [X/Z^2, Y/Z^3] \) - - To Projective: \( (X : Y : Z : Z^2 : Z^3) \rightarrow (X/Z^2 : Y/Z^3 : 1) \) ? - - To Jacobian: \( (X : Y : Z : Z^2 : Z^3) \rightarrow (X : Y : Z) \) - - ---- - -## Formulas - - - Addition - - Doubling - - Tripling - - Differential addition - - Differential addition and doubling - - Scaling - -See EFD[^3]. - ---- - -## Scalar multiplication - -See TAOCP volume 2, section 4.6.3 for introduction to multiplication/exponentiation and addition/multiplication chains.[^5] - -Scalar multiplication on elliptic curves is very similar to usual multiplication/exponentiation in general additive/multiplicative groups, respectively, with some additional structure: - - - \(A + B\) when \(A \ne B\) might be a different operation from \(A + A = [2]A\), and also sometimes takes different time. - - negation \(-A\) is easy/fast. - - \(0\) sometimes has a special representation and thus requires special casing. - - sometimes, there exists a fast operation of \(\phi: E(\mathbb{F}_p) \rightarrow E(\mathbb{F}_p) \) with \( \phi(P) = [k]P \) for some \(k \in \mathbb{K}\) computable using some endomorphism on the curve. - -Some links: - - - [wiki/Addition_chain](https://en.wikipedia.org/wiki/Addition_chain) - - [wiki/Addition-subtraction_chain](https://en.wikipedia.org/wiki/Addition-subtraction_chain) - - [wiki/Exponentiation_by_squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) - - [wiki/Addition-chain_exponentiation](https://en.wikipedia.org/wiki/Addition-chain_exponentiation) - -We define: - - - \( \lambda(k) = \lfloor \log_2 k \rfloor \) , the size of k - - \( k_i \) , the *i*-th bit of *k* - - \( \nu(k) = \vert \{ i \vert 0 \le i \le \lambda(k), k_i = 1\} \vert \) , the number of nonzero bits in *k* - - \( l(k) \) , the length of NAF of *k* - - \( \sigma(k) = \vert \{ i \vert 0 \le i \le l(k), NAF(k)_i \ne 0 \} \vert \) , the number of nonzero values in the NAF of *k* - - \( C_2 \) , the cost of doubling a point - - \( C_+ \) , the cost of point addition - - \( C_{algo}(k) \) , the cost of scalar multiplication by *k* of the algorithm *algo* - - *Addition chain* of *n*, is a sequence of integers: -\( 1 = a_0, a_1, \ldots, a_r = n\), -where \(a_i = a_j + a_k\) for some \( k \le j < i, \forall i \in \{ 1, 2, \ldots, r \} \) - - *Addition-subtraction chain* of *n*, is a sequence of integers: -\( 1 = a_0, a_1, \ldots, a_r = n\), -where \(a_i = \pm a_j \pm a_k\) for some \( k \le j < i, \forall i \in \{ 1, 2, \ldots, r \} \) - - *Addition sequence* for \( r_1, r_2, \ldots, r_t \) is an addition chain: \( 1 = a_1, a_2, \ldots, a_l \) which contains \( r_1, r_2, \ldots, r_t \). Useful when operating with one element and many powers \( g^{r_1}, g^{r_2}, \ldots \) - - *Vector addition chain* for \(r \in \mathbb{N}^t \) is a sequence of elements \( v_i \) of \( \mathbb{N}^t \) such that \( v_i = e_i \) for \( 1 \le i \le t \) and \( v_i = v_j + v_k \) for \(j \le k < i \). Useful when powering many elements to many powers \( g_1^{r_1}, g_2^{r_2}, \ldots \) - -### Double and Add (binary exponentiation) - -Uses binary addition chain. - -<u>Algorithm 3.26</u> (right-to-left) in GECC[^1] - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Q ← ∞. - 2. For i from 0 to t-1 do - 2.1 If k_i = 1 then Q ← Q + P. - 2.2 P ← 2P. - 3. Return(Q). - -<u>Algorithm 3.27</u> (left-to-right) in GECC[^1] - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Q ← ∞. - 2. For i from t - 1 downto 0 do - 2.1 Q ← 2Q. - 2.2 If k_i = 1 then Q ← Q + P. - 3. Return(Q). - -Cost: \( C_{binexp}(k) = \lambda(k)C_2 + (\nu(k) - k_0)C_+\)[^7] - -### Double and Add Always (binary exponentiation - constant time) - -Uses binary addition chain, but does all the additions/multiplications. - -(right-to-left) - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Q ← ∞. - 2. For i from t - 1 downto 0 do - 2.1 If k_i = 1 then Q ← Q + P else Dummy ← Q + P. - 2.2 P ← 2P. - 3. Return(Q). - -(left-to-right) - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Q ← ∞. - 2. For i from t - 1 downto 0 do - 2.1 Q ← 2Q. - 2.2 If k_i = 1 then Q ← Q + P else Dummy ← Q + P. - 3. Return(Q). - -Cost: \( C_{const\_binexp}(k) = \lambda(k) (C_2 + C_+) \) ? - - -### Binary NAF multiplication (signed binary exponentiation) - -**Definition 3.28**[^1] A *non-adjacent form (NAF)* of a positive integer *k* is an expression \( k = \Sigma_{i=0}^{l - 1} k_i 2^i \) where \(k_i \in \{0, ±1\}, k_{l−1} \ne 0\), and no two consecutive digits \( k_i \) are nonzero. The length of the NAF is *l*. - -<u>Algorithm 3.30</u> Computing the NAF of a positive integer[^1] - - INPUT: A positive integer k. - OUTPUT: NAF(k). - 1. i ← 0. - 2. While k ≥ 1 do - 2.1 If k is odd then: - k_i ← 2 − (k mod 4), k ← k − k_i ; - 2.2 Else: - k_i ← 0. - 2.3 k ← k/2, i ← i + 1. - 3. Return(k_{i−1}, k_{i−2}, ..., k_1, k_0). - -<u>Algorithm 3.31</u> Binary NAF multiplication (left-to-right)[^1] - - INPUT: Positive integer k, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Use Algorithm 3.30 to compute NAF(k). - 2. Q ← ∞. - 3. For i from l - 1 downto 0 do - 3.1 Q ← 2Q. - 3.2 If k_i = 1 then Q ← Q + P. - 3.3 If k_i = -1 then Q ← Q - P. - 4. Return(Q). - -Can be made constant time. - -Cost: \( C_{bin\_NAF} = l(k)C_2 + \sigma(k)C_+ + \text{NAF computation cost}\) ? - -### \(m\)-ary method - -Like binary double-and-add but uses a different base *m*.[^6] - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_m, P ∈ E(F_q). - OUTPUT: [k]P - 1. Compute P_i = [i]P for i ∈ {1, 2, ..., m - 1}. - 2. Q ← ∞. - 3. For i from l downto 0 do - 3.1 Q ← [m]Q. - 3.2 Q ← Q + P_{k_i}. - 4. Return(Q). - -### \( 2^r \) method - -Like \(m\)-ary method, with \( m = 2^r \), means that `[m]Q` is doable with only doubling.[^6] - -### Sliding window - -<u>Algorithm 13.6</u> Sliding window in HEHCC[^2] - - INPUT: Window width w, k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P - 1. Compute P_i = [i]P for i ∈ {3, 5, ..., 2^w - 1}. //precomputation for fixed P - 2. Q ← ∞, i ← t - 1. - 3. While i ≥ 0 do - 3.1 If k_i = 0 then: - Q ← [2]Q, i ← i - 1. - 3.2 Else: - 3.2.1 s ← max(i - k + 1, 0). - 3.2.2 While k_s = 0 do - s ← s + 1. - 3.2.3 For h from 1 to i - s + 1 do - Q ← [2]Q. - 3.2.4 u ← (k_i, ..., k_s)_2. - 3.2.5 Q ← P_u. // u is odd. - 3.2.6 i ← s - 1. - 4. Return(Q). - -<u>Algorithm 3.38</u> Sliding window with NAF(signed sliding window) in GECC[^1] - - INPUT: Window width w, positive integer k, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Use Algorithm 3.30 to compute NAF(k). - 2. Compute P_i = [i]P for i ∈ {1, 3, ..., 2(2^w - (-1)^w)/3 - 1}. //precomputation for fixed P - 3. Q ← ∞, i ← l - 1. - 4. While i ≥ 0 do - 4.1 If k_i = 0 then: - t ← 1, u ← 0. - 4.2 Else: - find the largest t ≤ w such that u ← (k_i , ..., k_{i-t+1}) is odd. - 4.3 Q ← [2^t]Q. - 4.4 If u > 0 then: - Q ← Q + P_u. - 4.5 Else: - if u < 0 then Q ← Q - P_{-u}. - 4.6 i ← i - t. - 5. Return(Q). - -### Window NAF multiplication - -**Definition 3.32**[^1] Let \( w \ge 2 \) be a positive integer. A *width-w NAF* of a positive integer *k* is an expression \( k = \Sigma_{i=0}^{l - 1} k_i 2^i \) where each nonzero coefficient \( k_i \) is odd, \( \vert k_i \vert < 2^{w - 1}, k_{l-1} \ne 0 \), and at most one of any *w* consecutive digits is nonzero. The length of the width-w NAF is *l*. - - -<u>Algorithm 3.35</u> Computing the width-w NAF of a positive integer[^1] - - INPUT : Window width w, positive integer k. - OUTPUT : NAF-w(k). - 1. i ← 0. - 2. While k ≥ 1 do - 2.1 If k is odd then: - k_i ← k mods 2^w , k ← k − k_i; // k mods 2^w is an integer u, -2^{w-1} ≤ u < 2^{w-1}, u ≡ k mod 2^w - 2.2 Else: - k_i ← 0. - 2.3 k ← k/2, i ← i + 1. - 3. Return(k_{i−1}, k_{i−2}, ..., k_1, k_0). - -<u>Algorithm 3.36</u> in GECC[^1] - - INPUT: Window width w, positive integer k, P ∈ E(F_q). - OUTPUT: [k]P. - 1. Use Algorithm 3.35 to compute NAF-w(k). - 2. Compute P_i = [i]P for i ∈ {1, 3, 5, ..., 2^{w-1} - 1}. //precomputation for fixed P - 3. Q ← ∞. - 4. For i from l - 1 downto 0 do - 4.1 Q ← 2Q. - 4.2 If k_i != 0 then: - If k_i > 0 then: - Q ← Q + P_{k_i} ; - Else: - Q ← Q - P_{-k_i} . - 5. Return(Q). - -### Fractional window - -[^10] and [^11] - -### Montgomery ladder - -The same name, Montgomery ladder, is used both for the general ladder idea of exponentiation/scalar-multiplication and the concrete *x*-coordinate only addition formulas and scalar multiplication algorithm on Montgomery curves. - -<u>Algorithm 13.35</u> in [^2] (general Montgomery ladder) - - INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q). - OUTPUT: [k]P . - 1. P_1 ← P and P_2 ← [2]P - 2. For i = t − 1 downto 0 do - 2.1 If k_i = 0 then - P_1 ← [2]P_1; P_2 ← P_1 + P_2. - Else - P_1 ← P_1 + P_2; P_2 ← [2]P_2. - 3. Return(P_1). - -<u>Algorithm 3.</u> in [^8] (general Montgomery ladder) - - INPUT: G ∈ E(F_q), k = (1, k_{t−2}, ..., k_0)2 - OUTPUT: Y = kG - 1. R0 ← G; R1 ← [2]G - 2. for j = t − 2 downto 0 do - 2.1 if (k_j = 0) then - R1 ← R0 + R1; R0 ← [2]R0 - else [if (kj = 1)] - R0 ← R0 + R1; R1 ← [2]R1 - 3. return R0 - -Montgomery addition formulas (Projective coordinates/XZ coordinates):[^2] - - - Addition (\( n \ne m \)): -\begin{align*} -X_{m+n} &= Z_{m-n}((X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n))^2 \\ -Z_{m+n} &= X_{m-n}((X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n))^2 -\end{align*} - - - Doubling: -\begin{align*} -4X_nZ_n &= (X_n + Z_n)^2 - (X_n - Z_n)^2 \\ -X_{2n} &= (X_n + Z_n)^2 (X_n - Z_n)^2 \\ -Z_{2n} &= 4X_nZ_n((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n)) -\end{align*} - - - \( Y \) recovery: -\begin{align*} -x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1} \\ -y_n &= \frac{(x_1x_n + 1) (x_1 + x_n + 2A) - 2A - (x_1 - x_n)^2x_{n+1}}{2By_1} -\end{align*} - -### Brier-Joye (+ Lopez-Dahab) ladder - -Not really a scalar-multiplication algorithm. Generalization of the stricter Montgomery ladder(the *x*-coordinate only scalar-mult algo and addition formulas on Montgomery curves) to short Weierstrass elliptic curves over fields of \( \text{char}\ \mathbb{K} \ne 2, 3 \) by Brier & Joye. Furthermore the *x*-coordinate only addition formulas were generalized to curves over \( \mathbb{F}_{2^m} \) by Lopez & Dahab. - -Brier-Joye addition formulas (Projective coordinates/XZ coordinates):[^2] - - - Addition (\( n \ne m \)): -\begin{align*} -X_{m+n} &= Z_{m-n}(-4a_6Z_mZ_n(X_mZ_n + X_nZ_m) + (X_mX_n - a_4 Z_mZ_n)^2) \\ -Z_{m+n} &= X_{m-n}(X_mZ_n - X_nZ_m)^2 -\end{align*} - - - Doubling: -\begin{align*} -X_{2n} &= (X_n^2 - a_4Z_n^2)^2 - 8 a_6X_nZ_n^3 \\ -Z_{2n} &= 4Z_n(X_n(X_n^2 + a_4 Z_n^2) + a_6Z_n^3) -\end{align*} - - - \( Y \) recovery: -\begin{align*} -x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1} \\ -y_n &= \frac{2a_6 +(x_1x_n + a_4) (x_1 + x_n) - (x_1 - x_n)^2x_{n+1}}{2y_1} -\end{align*} - -Lopez-Dahab addition formulas on \( E(\mathbb{F}_{2^m}) \)(Projective coordinates/XZ coordinates):[^2] - - - Addition (\( n \ne m \)): -\begin{align*} -Z_{m+n} &= (X_mZ_n)^2 + (X_nZ_m)^2 \\ -X_{m+n} &= Z_{m+n}X_{m-n} + X_mZ_nX_nZ_m -\end{align*} - - - Doubling: -\begin{align*} -X_{2n} &= X_n^4 + a_6Z_n^4 = (X_n^2 + \sqrt{a_6}Z_n^2)^2 \\ -Z_{2n} &= X_n^2Z_n^2 -\end{align*} - - - \( Y \) recovery: -\begin{align*} -x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1} \\ -y_n &= \frac{(x_n + x_1)((x_n + x_1)(x_{n+1} + x_1) + x_1^2 + y_1)}{x_1} + y_1 -\end{align*} - -### GLV scalar multiplication - -[^13] - -### Fixed-base windowing (BGMW) - -<u>Algorithm 3.41</u> and <u>Algorithm 3.42</u> in GECC[^1] - - -### Fixed-base comb - -<u>Algorithm 3.44</u> and <u>Algorithm 3.45</u> in GECC[^1] - -### Möller-1 - -> The method may fail in some cases in that an addition step may turn out to be a point doubling or may involve the point at infinity (which both requires special treatment and is potentially clearly visible through side channels). However, we will show that the probability of this happening is negligible if multipliers are appropriately selected: Randomly chosen e is safe.[^9] - -## References - -[^1]: HANKERSON, Darrel; MENEZES, Alfred J.; VANSTONE, Scott. Guide to Elliptic Curve Cryptography. New York, USA: Springer, 2004. ISBN 9780387218465. Available from DOI: [10.1007/b97644](https://dx.doi.org/10.1007/b97644). - -[^2]: COHEN, Henri; FREY, Gerhard; AVANZI, Roberto M.; DOCHE, Christophe; LANGE, Tanja; NGUYEN, Kim; VERCAUTEREN, Frederik. Handbook of Elliptic and Hyper-elliptic Curve Cryptography. CRC Press, 2005-07-19. Discrete Mathematics and It’s Applications, no. 34. ISBN 9781584885184. - -[^3]: BERNSTEIN, Daniel J.; LANGE, Tanja. Explicit Formulas Database, <https://www.hyperelliptic.org/EFD/> - -[^4]: <http://point-at-infinity.org/ecc/> - -[^5]: KNUTH, Donald: The Art of Computer Programming, Volume 2: Seminumerical algorithms - -[^6]: GORDON, Daniel M.: A survey of fast exponentiation methods. - -[^7]: MORAIN, Francois; OLIVOS, Jorge: Speeding up the computations on an elliptic curve using addition-subtraction chains. - -[^8]: JOYE, Marc; YEN, Sung-Ming: The Montgomery Powering Ladder. - -[^9]: MOLLER, Bodo: Securing Elliptic Curve Point Multiplication against Side-Channel Attacks. - -[^10]: MOLLER, Bodo: Improved Techniques for Fast Exponentiation. - -[^11]: MOLLER, Bodo: Fractional Windows Revisited: Improved Signed-Digit Representations for Efficient Exponentiation. - -[^12]: KOYAMA, Kenji; TSURUOKA, Yukio: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method. - -[^13]: GALLANT, Robert P.; LAMBERT, Robert J.; VANSTONE, Scott A.: Faster point multiplication on elliptic curves with efficient endomorphisms.
\ No newline at end of file diff --git a/docs/LIBS.md b/docs/LIBS.md index 4f10dfe..a71b792 100644 --- a/docs/LIBS.md +++ b/docs/LIBS.md @@ -1,130 +1,21 @@ # Supported libraries -Libraries that ECTester can test. +Libraries that ECTester can test: - [BouncyCastle](https://bouncycastle.org/java.html) - - Java - - Works with the short Weierstrass curve model for ECDSA and ECDH. - - Works with coordinates: - - Affine - - Projective(Homogenous) - - Jacobian - - Jacobian-Chudnovsky - - Jacobian-Modified - - Lambda-Affine? - - Lambda-Projective? - - Skewed? - - Multiple scalar multiplication algorithms implemented and used: - - Double-and-add always (DoubleAddMultiplier) - - Fixed point comb (FixedPointCombMultiplier) - - GLV (Gallant-Lambert-Vanstone) using endomorphisms (GLVMultiplier): Faster point multiplication on elliptic curves with efficient endomorphisms. <-- default, if available - - Binary NAF right-to-left multiplication(mixed coordinates) (MixedNafR2LMultiplier) - - Montgomery ladder (MontgomeryLadderMultiplier) - - Binary NAF right-to-left multiplication (NafR2LMultiplier) - - Binary NAF left-to-right multiplication (NafL2RMultiplier) - - Double-and-add reference implementation (ReferenceMultiplier) - - Window NAF left-to-right multiplication (WNafL2RMultiplier) <-- default - - Window Tau-NAF multiplication (WTauNafMultiplier): Improved Algorithms for Arithmetic on Anomalous Binary Curves - - Zeroless signed digit binary right-to-left multiplication (ZSignedDigitR2LMultiplier) - - Zeroless signed digit binary left-to-right multiplication (ZSignedDigitL2RMultiplier) - - Has custom field and point arithmetic for: - - Curve25519 (transformed into short Weierstrass model) - - SMP2 curves - - SECG curves - [Sun EC](https://docs.oracle.com/javase/7/docs/technotes/guides/security/SunProviders.html#SunEC) - - Java + C - - Uses the short Weierstrass curve model. - - For prime field curves: - - Uses 5-bit window NAF, Uses mixed Modified-Jacobian coordinates - for doubling and Chudnovsky Jacobian coordinates for additions (ecp_jm.c). From: - Brown, Hankerson, Lopez, Menezes: Software Implementation of the NIST Elliptic Curves Over Prime Fields. - - Contains an implementation of scalar multiplication with 4-bit sliding window, using Jacobian coordinates (ecp_jac.c) - - Contains an implementation of IEEE P1363 algorithm A.10.3 using affine coordinates (ecp_aff.c) - - For binary field curves: - - Uses Lopez-Dahab (Montgomery) ladder, XZ coordinates (ec2_mont.c): Fast multiplication on elliptic curves over GF(2^m) without precomputation (Algorithm 2P) - - Contains an implementation of IEEE P1363 algorithm A.10.3 using affine coordinates (ec2_aff.c) - - Has some custom arithmetic for some of the NIST primes. - [WolfCrypt(WolfSSL)](https://www.wolfssl.com) - - C + Java - - Prime field curves only. - - Jacobian coordinates: - - Uses sliding window scalar multiplication, (discards `b` parameter of curve), but validates points. - [OpenSSL](https://www.openssl.org/) - - C - - For prime field curves: - - Uses Jacobian coordinates, and Montgomery ladder, also uses wNAF-based interleaving multi-exponentiation method(ec_mult.c): http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf - - Also uses multiplication with precomputation by wNAF splitting(ec_mult.c) - - For binary field curves: - - Uses Jacobian coordinates, and Lopez-Dahab ladder, also uses wNAF-based interleaving multi-exponentiation method(ec2_smpl.c) - [BoringSSL](https://boringssl.googlesource.com/boringssl) - - C - - Supports prime field curves only: - - Use Jacobian coordinates, and Montgomery ladder, also uses optimized arithmetic on NIST P-224, P-256. - - Bundled as a git submodule in `ext/boringssl`. To build and use run: -```bash -cd ext/boringssl -mkdir build && cd build -cmake -DBUILD_SHARED_LIBS=1 -GNinja .. -ninja -``` - [Crypto++](https://cryptopp.com/) - - C++ - - For prime field curves: - - Uses projective coordinates and sliding window scalar multiplication algorithm. - - For binary field curves: - - Uses affine coordinates and sliding window scalar multiplication algorithm. - [libtomcrypt](http://www.libtom.net/LibTomCrypt/) - - C - - Uses Jacobian coordinates. - - Sliding window scalar multiplication algorithm. - [libgcrypt](https://www.gnupg.org/related_software/libgcrypt/) - - C - - Only supports prime field curves. - - Uses short Weierstrass, Montgomery and Twisted Edwards models. - - Uses left-to-right double-and-add always scalar multiplication and Jacobian coordinates in short Weierstrass form. - - Uses Montgomery ladder and X-only in Montgomery form. - - Uses left-to-right double-and-add always scalar multiplication in Twisted Edwards form. - [Botan](https://botan.randombit.net/) - - C++ - - Uses blinded(randomized) Montgomery ladder. - - <https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2> - - <https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc> - - <https://eprint.iacr.org/2015/657> - - ECTester supports v2.4.0 and up. - [Microsoft CNG](https://msdn.microsoft.com/en-us/library/windows/desktop/aa376210(v=vs.85).aspx) - - C API. - - <del>Closed source.</del> Not any more: <https://github.com/Microsoft/SymCrypt>. - - For prime field curves(only supports): - - Uses Short Weierstrass model. - - Uses Twisted Edwards model. - - Uses Montgomery model. - - Uses fixed window scalar multiplication. - - Uses Wnaf multi-scalar multiplication with interleaving. - - Uses Montgomery ladder. - [mbedTLS](https://tls.mbed.org/) - - C - - Only supports prime field curves. - - Uses short Weierstrass and Montgomery models. - - Uses comb method for short Weierstrass curves, using (randomized) Jacobian coordinates. - - <http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2> - - Uses Montgomery ladder with xz coordinates for Montgomery curves. - [Intel Performance Primitives](https://software.intel.com/en-us/ipp-crypto-reference-2019) - - C - - Only supports prime field curves. - - Uses 5-bit window NAF. - - Uses Jacobian coordinates. - - <https://github.com/intel/ipp-crypto> - [Nettle](http://www.lysator.liu.se/~nisse/nettle/) - - C - - No support for explicit parameters, only SECG named curves. - - Uses Jacobian coordinates. - - <https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b> - - <https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl> - - <https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-madd-2007-bl> - - Uses double-and-add always or windowing algorithm. - - Uses Pippenger scalar mult for Twisted Edwards curves. - [LibreSSL](https://www.libressl.org/) - - C # Libraries with ECC support diff --git a/docs/VULNS.md b/docs/VULNS.md index d7117b5..3db4f81 100644 --- a/docs/VULNS.md +++ b/docs/VULNS.md @@ -2,17 +2,17 @@ ## Cards -| CVE | Card | CVSS v3 | Description | Discoverer | -|:-------------------------------------------------------------------------------:|:------------------------:|:---------:| ----------- |:----------:| -| [CVE-2019-15809](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-15809) | Athena IDProtect | 4.7 MEDIUM| Smart cards from the Athena SCS manufacturer, based on the Atmel Toolbox 00.03.11.05 and the AT90SC chip, contain a timing side channel in ECDSA signature generation. This allows a local attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because the Atmel Toolbox 00.03.11.05 contains two versions of ECDSA signature functions, described as fast and secure, but the affected cards chose to use the fast version, which leaks the bit length of the random nonce via timing. This affects: <ul> <li>Athena IDProtect 010b.0352.0005</li> <li>Athena IDProtect 010e.1245.0002</li> <li>Athena IDProtect 0106.0130.0401</li> <li>Athena IDProtect 010e.1245.0002</li> <li>Valid S/A IDflex V 010b.0352.0005</li> <li>SafeNet eToken 4300 010e.1245.0002</li> <li>TecSec Armored Card 010e.0264.0001</li> <li>TecSec Armored Card 0108.0264.0001</li> </ul> | [Jan Jancar](https://github.com/J08nY) | +| CVE | Card | CVSS v3 | Description | Discoverer | +|:-------------------------------------------------------------------------------:|:----------------:|:----------:|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|:--------------------------------------:| +| [CVE-2019-15809](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-15809) | Athena IDProtect | 4.7 MEDIUM | Smart cards from the Athena SCS manufacturer, based on the Atmel Toolbox 00.03.11.05 and the AT90SC chip, contain a timing side channel in ECDSA signature generation. This allows a local attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because the Atmel Toolbox 00.03.11.05 contains two versions of ECDSA signature functions, described as fast and secure, but the affected cards chose to use the fast version, which leaks the bit length of the random nonce via timing. This affects: <ul> <li>Athena IDProtect 010b.0352.0005</li> <li>Athena IDProtect 010e.1245.0002</li> <li>Athena IDProtect 0106.0130.0401</li> <li>Athena IDProtect 010e.1245.0002</li> <li>Valid S/A IDflex V 010b.0352.0005</li> <li>SafeNet eToken 4300 010e.1245.0002</li> <li>TecSec Armored Card 010e.0264.0001</li> <li>TecSec Armored Card 0108.0264.0001</li> </ul> | [Jan Jancar](https://github.com/J08nY) | ## Libraries -| CVE | Library | CVSS v3 | Description | Discoverer | -|:-------------------------------------------------------------------------------:|:------------------------:|:---------:| ----------- |:----------:| -| [CVE-2018-20187](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-20187) | Botan 2 | 5.9 MEDIUM| A side-channel issue was discovered in Botan before 2.9.0. An attacker capable of precisely measuring the time taken for ECC key generation may be able to derive information about the high bits of the secret key, as the function to derive the public point from the secret scalar uses an unblinded Montgomery ladder whose loop iteration count depends on the bitlength of the secret. This issue affects only key generation, not ECDSA signatures or ECDH key agreement.| [Jan Jancar](https://github.com/J08nY)| -| [CVE-2019-13627](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13627) | libgcrypt | 5.9 MEDIUM| Libgcrypt 1.3.0 through 1.8.4 (ECDSA) and 1.6.0 through 1.8.4 (EdDSA) contains a timing side channel in ECDSA/EdDSA signature generation. This allows a local or a remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because mpi/ec.c scalar multiplication leaks the bit length of the scalar.| [Jan Jancar](https://github.com/J08nY)| -| [CVE-2019-13628](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13628) | wolfCrypt, wolfSSL | 5.9 MEDIUM| wolfSSL and wolfCrypt 4.0.0 and earlier (when configured without --enable-fpecc, --enable-sp, or --enable-sp-math) contain a timing side channel in ECDSA signature generation. This allows a local attacker, able to precisely measure the duration of signature operations, to infer information about the nonces used and potentially mount a lattice attack to recover the private key used. The issue occurs because ecc.c scalar multiplication might leak the bit length.| [Jan Jancar](https://github.com/J08nY)| -| [CVE-2019-13629](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13629) | MatrixSSL | 5.9 MEDIUM| MatrixSSL 4.2.1 and earlier contains a timing side channel in ECDSA signature generation. This allows a local or a remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because crypto/pubkey/ecc_math.c scalar multiplication leaks the bit length of the scalar.| [Jan Jancar](https://github.com/J08nY) | -| [CVE-2019-14317](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-14317) | wolfCrypt, wolfSSL | 5.3 MEDIUM| wolfSSL and wolfCrypt 4.1.0 and earlier (formerly known as CyaSSL) generate biased DSA nonces. This allows a remote attacker to compute the long term private key from several hundred DSA signatures via a lattice attack. The issue occurs because dsa.c fixes two bits of the generated nonces.| [Jan Jancar](https://github.com/J08nY)| -| [CVE-2019-14318](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-14318) | Crypto++ | 5.9 MEDIUM| Crypto++ 8.3.0 and earlier contains a timing side channel in ECDSA signature generation. This allows a local or remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because scalar multiplication in ecp.cpp (prime field curves, small leakage) and algebra.cpp (binary field curves, large leakage) is not constant time and leaks the bit length of the scalar among other information.| [Jan Jancar](https://github.com/J08nY)| +| CVE | Library | CVSS v3 | Description | Discoverer | +|:-------------------------------------------------------------------------------:|:------------------:|:----------:|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|:--------------------------------------:| +| [CVE-2018-20187](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-20187) | Botan 2 | 5.9 MEDIUM | A side-channel issue was discovered in Botan before 2.9.0. An attacker capable of precisely measuring the time taken for ECC key generation may be able to derive information about the high bits of the secret key, as the function to derive the public point from the secret scalar uses an unblinded Montgomery ladder whose loop iteration count depends on the bitlength of the secret. This issue affects only key generation, not ECDSA signatures or ECDH key agreement. | [Jan Jancar](https://github.com/J08nY) | +| [CVE-2019-13627](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13627) | libgcrypt | 5.9 MEDIUM | Libgcrypt 1.3.0 through 1.8.4 (ECDSA) and 1.6.0 through 1.8.4 (EdDSA) contains a timing side channel in ECDSA/EdDSA signature generation. This allows a local or a remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because mpi/ec.c scalar multiplication leaks the bit length of the scalar. | [Jan Jancar](https://github.com/J08nY) | +| [CVE-2019-13628](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13628) | wolfCrypt, wolfSSL | 5.9 MEDIUM | wolfSSL and wolfCrypt 4.0.0 and earlier (when configured without --enable-fpecc, --enable-sp, or --enable-sp-math) contain a timing side channel in ECDSA signature generation. This allows a local attacker, able to precisely measure the duration of signature operations, to infer information about the nonces used and potentially mount a lattice attack to recover the private key used. The issue occurs because ecc.c scalar multiplication might leak the bit length. | [Jan Jancar](https://github.com/J08nY) | +| [CVE-2019-13629](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-13629) | MatrixSSL | 5.9 MEDIUM | MatrixSSL 4.2.1 and earlier contains a timing side channel in ECDSA signature generation. This allows a local or a remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because crypto/pubkey/ecc_math.c scalar multiplication leaks the bit length of the scalar. | [Jan Jancar](https://github.com/J08nY) | +| [CVE-2019-14317](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-14317) | wolfCrypt, wolfSSL | 5.3 MEDIUM | wolfSSL and wolfCrypt 4.1.0 and earlier (formerly known as CyaSSL) generate biased DSA nonces. This allows a remote attacker to compute the long term private key from several hundred DSA signatures via a lattice attack. The issue occurs because dsa.c fixes two bits of the generated nonces. | [Jan Jancar](https://github.com/J08nY) | +| [CVE-2019-14318](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-14318) | Crypto++ | 5.9 MEDIUM | Crypto++ 8.3.0 and earlier contains a timing side channel in ECDSA signature generation. This allows a local or remote attacker, able to measure the duration of hundreds to thousands of signing operations, to compute the private key used. The issue occurs because scalar multiplication in ecp.cpp (prime field curves, small leakage) and algebra.cpp (binary field curves, large leakage) is not constant time and leaks the bit length of the scalar among other information. | [Jan Jancar](https://github.com/J08nY) | |