ecc: add API's to support EAP-PWD
PATCH v3 1/4 ecc: add API's to support EAP-PWD
EAP-PWD requires the following ECC functionality
- Point multiplication
- Point addition
- Point inverse
- Scalar addition
--- ell/ecc.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ ell/ecc.h | 14 ++++++++++++++ 2 files changed, 67 insertions(+)
ell/ecc.c +53 -0
@@ -435,3 +435,56 @@ LIB_EXPORT void l_ecc_scalar_free(struct l_ecc_scalar *c)memset (c->c,0 , c->curve->ndigits *8 );l_free (c); } + +LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_order( +const struct l_ecc_curve *curve) +{ +return _ecc_constant_new (curve, (void *) curve->n, curve->ndigits *8 ); +} + +LIB_EXPORT bool l_ecc_scalar_add(struct l_ecc_scalar *ret, +const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b, +const struct l_ecc_scalar *mod) +{ +if (unlikely (!ret || !a || !b || !mod)) +return false; + +_vli_mod_add (ret->c, a->c, b->c, mod->c, a->curve->ndigits); + +return true; +} + +LIB_EXPORT bool l_ecc_point_multiply(struct l_ecc_point *ret, +const struct l_ecc_scalar *scalar, +const struct l_ecc_point *point) +{ +if (unlikely (!ret || !scalar || !point)) +return false; + +_ecc_point_mult (ret, point, scalar->c,NULL , scalar->curve->p); + +return true; +} + +LIB_EXPORT bool l_ecc_point_add(struct l_ecc_point *ret, +const struct l_ecc_point *a, +const struct l_ecc_point *b) +{ +if (unlikely (!ret || !a || !b)) +return false; + +_ecc_point_add (ret, a, b, a->curve->p); + +return true; +} + +LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p) +{ +if (unlikely (!p)) +return false; + +_vli_mod_sub (p->y, p->curve->p, p->y, p->curve->p, p->curve->ndigits); + +return true; +}
ell/ecc.h +14 -0
@@ -61,6 +61,20 @@ ssize_t l_ecc_scalar_get_data(const struct l_ecc_scalar *c, void *buf, size_t len);void l_ecc_scalar_free (struct l_ecc_scalar *c); +/* Constant operations */ +struct l_ecc_scalar *l_ecc_curve_get_order (const struct l_ecc_curve *curve); +bool l_ecc_scalar_add (struct l_ecc_scalar *ret,const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b, +const struct l_ecc_scalar *mod); + +/* Point operations */ +bool l_ecc_point_multiply (struct l_ecc_point *ret, +const struct l_ecc_scalar *scalar, +const struct l_ecc_point *point); +bool l_ecc_point_add (struct l_ecc_point *ret,const struct l_ecc_point *a, +const struct l_ecc_point *b); +bool l_ecc_point_inverse (struct l_ecc_point *p); + #ifdef __cplusplus }#endif
Signature · 1 line
2.17.1
Hi James,
Quoted 10 lines · James Prestwood
EAP-PWD requires the following ECC functionality
- Point multiplication
- Point addition
- Point inverse
- Scalar addition--- ell/ecc.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ ell/ecc.h | 14 ++++++++++++++ 2 files changed, 67 insertions(+)
<snip>
ell/ecc.c LIB_EXPORT void l_ecc_scalar_free(struct l_ecc_scalar *c) · line 442
Quoted 5 lines
ell/ecc.c +5
-0+ +LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_order( +const struct l_ecc_curve *curve) +{ +return _ecc_constant_new (curve, (void *) curve->n, curve->ndigits *8 );
I took out this cast.
Review
Quoted 2 lines
(quoted diff) +2
-0+} +
Regards,
-Denis
PATCH v3 2/4 ecc: added API's to support SAE
In reply to James PrestwoodThe functionality require was:
- Scalar multiplication
- Find a scalars legendre symbol
- Sum the curve equations X side
- Get prime from curve (needed for input to SAE KDF)
- Check if scalars/points are equal
--- ell/ecc.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- ell/ecc.h | 15 ++++++++++++++ 2 files changed, 75 insertions(+), 1 deletion(-)
ell/ecc.c +60 -1
@@ -160,7 +160,7 @@ void _ecc_native2be(uint64_t *dest, const uint64_t *native, }static void ecc_compute_y_sqr (const struct l_ecc_curve *curve, -uint64_t *y_sqr,uint64_t *x) +uint64_t *y_sqr,const uint64_t *x) {uint64_t sum[L_ECC_MAX_DIGITS ] = {0 };uint64_t tmp[L_ECC_MAX_DIGITS ] = {0 };
@@ -488,3 +488,62 @@ LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p)return true; } + +LIB_EXPORT bool l_ecc_scalar_multiply(struct l_ecc_scalar *ret, +const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b) +{ +if (unlikely (!ret || !a || !b)) +return false; + +_vli_mod_mult_fast (ret->c, a->c, b->c, a->curve->p, a->curve->ndigits); + +return true; +} + +LIB_EXPORT int l_ecc_scalar_legendre(struct l_ecc_scalar *value) +{ +if (unlikely (!value)) +return -1 ; + +return _vli_legendre (value->c, value->curve->p, value->curve->ndigits); +} + +LIB_EXPORT bool l_ecc_scalar_sum_x(struct l_ecc_scalar *ret, +const struct l_ecc_scalar *x) +{ +if (unlikely (!ret || !x)) +return false; + +ecc_compute_y_sqr (x->curve, ret->c, x->c); + +return true; +} + +LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_prime( +const struct l_ecc_curve *curve) +{ +if (unlikely (!curve)) +return NULL ; + +return _ecc_constant_new (curve, (void *) curve->p, curve->ndigits *8 ); +} + +LIB_EXPORT bool l_ecc_scalars_are_equal(const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b) +{ +if (unlikely (!a || !b)) +return false; + +return (memcmp (a->c, b->c, a->curve->ndigits *8 ) ==0 ); +} + +LIB_EXPORT bool l_ecc_points_are_equal(const struct l_ecc_point *a, +const struct l_ecc_point *b) +{ +if (unlikely (!a || !b)) +return false; + +return ((memcmp (a->x, b->x, a->curve->ndigits *8 ) ==0 ) && + (memcmp (a->y, b->y, a->curve->ndigits *8 ) ==0 )); +}
ell/ecc.h +15 -0
@@ -75,6 +75,21 @@ bool l_ecc_point_add(struct l_ecc_point *ret, const struct l_ecc_point *a, const struct l_ecc_point *b);bool l_ecc_point_inverse (struct l_ecc_point *p); +/* extra operations needed for SAE */ +bool l_ecc_scalar_multiply (struct l_ecc_scalar *ret, +const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b); +int l_ecc_scalar_legendre (struct l_ecc_scalar *value); +bool l_ecc_scalar_sum_x (struct l_ecc_scalar *ret,const struct l_ecc_scalar *x); + +struct l_ecc_scalar *l_ecc_curve_get_prime (const struct l_ecc_curve *curve); + +bool l_ecc_scalars_are_equal (const struct l_ecc_scalar *a, +const struct l_ecc_scalar *b); + +bool l_ecc_points_are_equal (const struct l_ecc_point *a, +const struct l_ecc_point *b); + #ifdef __cplusplus }#endif
Signature · 1 line
2.17.1
Re: [PATCH v3 2/4] ecc: added API's to support SAE
Hi James,
Quoted 11 lines · James Prestwood
The functionality require was:
- Scalar multiplication
- Find a scalars legendre symbol
- Sum the curve equations X side
- Get prime from curve (needed for input to SAE KDF)
- Check if scalars/points are equal--- ell/ecc.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- ell/ecc.h | 15 ++++++++++++++ 2 files changed, 75 insertions(+), 1 deletion(-)
<snip>
ell/ecc.c LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p) · line 529
Quoted 7 lines
ell/ecc.c +7
-0+LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_prime( +const struct l_ecc_curve *curve) +{ +if (unlikely (!curve)) +return NULL ; + +return _ecc_constant_new (curve, (void *) curve->p, curve->ndigits *8 );
I took out this cast and applied this patch.
Review
Quoted 2 lines
(quoted diff) +2
-0+} +
Regards,
-Denis
PATCH v3 3/4 ecc: moved point add, exp, and legendre into ecc.c
In reply to James Prestwood_ecc_point_add, _vli_mod_exp, and _vli_legendre were all written in house, in addition to the ecc code taken from the kernel. Inside IWD it was much more convenient to just bundle these into the same file. Now (in ELL), since we have ecc-private.h, its much easier to keep these separate and out of ecc-external.c.
--- ell/ecc-external.c | 123 +++++++-------------------------------------- ell/ecc-private.h | 4 ++ ell/ecc.c | 90 +++++++++++++++++++++++++++++++++ 3 files changed, 111 insertions(+), 106 deletions(-)
ell/ecc-external.c +17 -106
@@ -180,7 +180,7 @@ static uint64_t vli_add(uint64_t *result, const uint64_t *left, }/* Computes result = left - right, returning borrow. Can modify in place. */ -static uint64_t vli_sub (uint64_t *result,const uint64_t *left, +uint64_t _vli_sub (uint64_t *result,const uint64_t *left,const uint64_t *right,unsigned int ndigits) {
@@ -327,7 +327,7 @@ void _vli_mod_add(uint64_t *result, const uint64_t *left,* get remainder. */ if (carry ||_vli_cmp (result, mod, ndigits) >=0 ) -vli_sub (result, result, mod, ndigits); +_vli_sub (result, result, mod, ndigits); }/* Computes result = (left - right) % mod.
@@ -337,7 +337,7 @@ void _vli_mod_sub(uint64_t *result, const uint64_t *left, const uint64_t *right, const uint64_t *mod, unsigned int ndigits) { - uint64_t borrow = vli_sub(result, left, right, ndigits); + uint64_t borrow = _vli_sub(result, left, right, ndigits);/* In this case, p_result == -diff == (max int) - diff. * Since -x % d == d - x, we can get the correct result from
@@ -372,7 +372,7 @@ static void vli_mmod_fast_192(uint64_t *result, const uint64_t *product, carry +=vli_add (result, result, tmp, ndigits);while (carry ||_vli_cmp (curve_prime, result, ndigits) !=1 ) - carry -=vli_sub (result, result, curve_prime, ndigits); + carry -=_vli_sub (result, result, curve_prime, ndigits); }/* Computes result = product % curve_prime
@@ -421,28 +421,28 @@ static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product, tmp[1 ] = (product[6 ] >>32 ); tmp[2 ] =0 ; tmp[3 ] = (product[4 ] &0xffffffff ) | (product[5 ] <<32 ); - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);/* d2 */ tmp[0 ] = product[6 ]; tmp[1 ] = product[7 ]; tmp[2 ] =0 ; tmp[3 ] = (product[4 ] >>32 ) | (product[5 ] &0xffffffff00000000ull ); - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);/* d3 */ tmp[0 ] = (product[6 ] >>32 ) | (product[7 ] <<32 ); tmp[1 ] = (product[7 ] >>32 ) | (product[4 ] <<32 ); tmp[2 ] = (product[4 ] >>32 ) | (product[5 ] <<32 ); tmp[3 ] = (product[6 ] <<32 ); - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);/* d4 */ tmp[0 ] = product[7 ]; tmp[1 ] = product[4 ] &0xffffffff00000000ull ; tmp[2 ] = product[5 ]; tmp[3 ] = product[6 ] &0xffffffff00000000ull ; - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);if (carry <0 ) { do {
@@ -450,7 +450,7 @@ static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product, }while (carry <0 ); }else {while (carry ||_vli_cmp (curve_prime, result, ndigits) !=1 ) - carry -=vli_sub (result, result, curve_prime, ndigits); + carry -=_vli_sub (result, result, curve_prime, ndigits); } }
@@ -550,7 +550,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product, tmp[3 ] =ECC_SET_S (product,18 ,17 ); tmp[4 ] =ECC_SET_S (product,20 ,19 ); tmp[5 ] =ECC_SET_S (product,22 ,21 ); - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);/* s8 */ tmp[0 ] =ECC_SET_S (product,20 ,-1 );
@@ -559,7 +559,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product, tmp[3 ] =0 ; tmp[4 ] =0 ; tmp[5 ] =0 ; - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);/* s9 */ tmp[0 ] =0 ;
@@ -568,7 +568,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product, tmp[3 ] =0 ; tmp[4 ] =0 ; tmp[5 ] =0 ; - carry -=vli_sub (result, result, tmp, ndigits); + carry -=_vli_sub (result, result, tmp, ndigits);if (carry <0 ) { do {
@@ -576,7 +576,7 @@ static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product, }while (carry <0 ); }else {while (carry ||_vli_cmp (curve_prime, result, ndigits) !=1 ) - carry -=vli_sub (result, result, curve_prime, ndigits); + carry -=_vli_sub (result, result, curve_prime, ndigits); } }
@@ -675,13 +675,13 @@ void _vli_mod_inv(uint64_t *result, const uint64_t *input,if (carry) v[ndigits -1 ] |=0x8000000000000000ull ; }else if (cmp_result >0 ) { -vli_sub (a, a, b, ndigits); +_vli_sub (a, a, b, ndigits);_vli_rshift1 (a, ndigits);if (_vli_cmp (u, v, ndigits) <0 )vli_add (u, u, mod, ndigits); -vli_sub (u, u, v, ndigits); +_vli_sub (u, u, v, ndigits);if (!EVEN (u)) carry =vli_add (u, u, mod, ndigits);
@@ -689,13 +689,13 @@ void _vli_mod_inv(uint64_t *result, const uint64_t *input,if (carry) u[ndigits -1 ] |=0x8000000000000000ull ; }else { -vli_sub (b, b, a, ndigits); +_vli_sub (b, b, a, ndigits);_vli_rshift1 (b, ndigits);if (_vli_cmp (v, u, ndigits) <0 )vli_add (v, v, mod, ndigits); -vli_sub (v, v, u, ndigits); +_vli_sub (v, v, u, ndigits);if (!EVEN (v)) carry =vli_add (v, v, mod, ndigits);
@@ -972,92 +972,3 @@ bool _ecc_point_is_zero(const struct l_ecc_point *point)return (vli_is_zero (point->x, point->curve->ndigits) &&vli_is_zero (point->y, point->curve->ndigits)); } - -/* (rx, ry) = (px, py) + (qx, qy) */ -void _ecc_point_add (struct l_ecc_point *ret,const struct l_ecc_point *p, -const struct l_ecc_point *q, -const uint64_t *curve_prime) -{ -/* -* s = (py - qy)/(px - qx) -* -* rx = s^2 - px - qx -* ry = s(px - rx) - py -*/ -uint64_t s[L_ECC_MAX_DIGITS ]; -uint64_t kp1[L_ECC_MAX_DIGITS ]; -uint64_t kp2[L_ECC_MAX_DIGITS ]; -uint64_t resx[L_ECC_MAX_DIGITS ]; -uint64_t resy[L_ECC_MAX_DIGITS ]; -unsigned int ndigits = p->curve->ndigits; - -vli_clear (s, ndigits); - -/* kp1 = py - qy */ -_vli_mod_sub (kp1, q->y, p->y, curve_prime, ndigits); -/* kp2 = px - qx */ -_vli_mod_sub (kp2, q->x, p->x, curve_prime, ndigits); -/* s = kp1/kp2 */ -_vli_mod_inv (kp2, kp2, curve_prime, ndigits); -_vli_mod_mult_fast (s, kp1, kp2, curve_prime, ndigits); -/* rx = s^2 - px - qx */ -_vli_mod_mult_fast (kp1, s, s, curve_prime, ndigits); -_vli_mod_sub (kp1, kp1, p->x, curve_prime, ndigits); -_vli_mod_sub (resx, kp1, q->x, curve_prime, ndigits); -/* ry = s(px - rx) - py */ -_vli_mod_sub (kp1, p->x, resx, curve_prime, ndigits); -_vli_mod_mult_fast (kp1, s, kp1, curve_prime, ndigits); -_vli_mod_sub (resy, kp1, p->y, curve_prime, ndigits); - -vli_set (ret->x, resx, ndigits); -vli_set (ret->y, resy, ndigits); -} - -/* result = (base ^ exp) % p */ -void _vli_mod_exp (uint64_t *result,uint64_t *base,uint64_t *exp, -const uint64_t *mod,unsigned int ndigits) -{ -unsigned int i; -int bit; -uint64_t n[L_ECC_MAX_DIGITS ]; -uint64_t r[L_ECC_MAX_DIGITS ] = {1 }; - -vli_set (n, base, ndigits); - -for (i =0 ; i < ndigits; i++) { -for (bit =0 ; bit <64 ; bit++) { -uint64_t tmp[L_ECC_MAX_DIGITS ]; - -if (exp[i] & (1ull << bit)) { -_vli_mod_mult_fast (tmp, r, n, mod, ndigits); -vli_set (r, tmp, ndigits); - } - -_vli_mod_mult_fast (tmp, n, n, mod, ndigits); -vli_set (n, tmp, ndigits); - } - } - -vli_set (result, r, ndigits); -} - -int _vli_legendre (uint64_t *val,const uint64_t *p,unsigned int ndigits) -{ -uint64_t tmp[L_ECC_MAX_DIGITS ]; -uint64_t exp[L_ECC_MAX_DIGITS ]; -uint64_t _1[L_ECC_MAX_DIGITS ] = {1ull }; -uint64_t _0[L_ECC_MAX_DIGITS ] = {0 }; - -/* check that val ^ ((p - 1) / 2) == [1, 0 or -1] */ - -vli_sub (exp, p, _1, ndigits); -_vli_rshift1 (exp, ndigits); -_vli_mod_exp (tmp, val, exp, p, ndigits); - -if (_vli_cmp (tmp, _1, ndigits) ==0 ) -return 1 ; -else if (_vli_cmp (tmp, _0, ndigits) ==0 ) -return 0 ; -else -return -1 ; -}
ell/ecc-private.h +4 -0
@@ -75,6 +75,10 @@ void _vli_mod_exp(uint64_t *result, uint64_t *base, uint64_t *exp,int _vli_cmp (const uint64_t *left,const uint64_t *right,unsigned int ndigits); +uint64_t _vli_sub (uint64_t *result,const uint64_t *left, +const uint64_t *right, +unsigned int ndigits); +int _vli_legendre (uint64_t *val,const uint64_t *p,unsigned int ndigits);bool _ecc_point_is_zero (const struct l_ecc_point *point);
ell/ecc.c +90 -0
96 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH v3 3/4] ecc: moved point add, exp, and legendre into ecc.c
Hi James,
Quoted 11 lines · James Prestwood
_ecc_point_add,_vli_mod_exp, and_vli_legendrewere all written in house, in addition to the ecc code taken from the kernel. Inside IWD it was much more convenient to just bundle these into the same file. Now (in ELL), since we haveecc-private.h, its much easier to keep these separate and out ofecc-external.c.--- ell/ecc-external.c | 123 +++++++-------------------------------------- ell/ecc-private.h | 4 ++ ell/ecc.c | 90 +++++++++++++++++++++++++++++++++ 3 files changed, 111 insertions(+), 106 deletions(-)
Patch 3 & 4 applied, thanks.
Regards,
-Denis
PATCH v3 4/4 ecc: Updated _ecc_point_mult to match kernel
In reply to James PrestwoodCommit 3da2c1dfdb802b184eea0653d1e589515b52d74b was added to the kernel which addressed potential timing attacks. This updates our ecc code with the same fix. It was slightly modified to not change the internal API parameters (we can get the curve from the point, rather than passing in the curve structure).
--- ell/ecc-external.c | 43 ++++++++++--------------------------------- 1 file changed, 10 insertions(+), 33 deletions(-)
ell/ecc-external.c +10 -33
@@ -68,37 +68,6 @@ static uint64_t vli_test_bit(const uint64_t *vli, unsigned int bit)return (vli[bit /64 ] & ((uint64_t )1 << (bit %64 ))); } -/* Counts the number of 64-bit "digits" in vli. */ -static unsigned int vli_num_digits (const uint64_t *vli,unsigned int ndigits) -{ -int i; - -/* Search from the end until we find a non-zero digit. -* We do it in reverse because we expect that most digits will -* be nonzero. -*/ -for (i = ndigits -1 ; i >=0 && vli[i] ==0 ; i--); - -return (i +1 ); -} - -/* Counts the number of bits required for vli. */ -static unsigned int vli_num_bits (const uint64_t *vli,unsigned int ndigits) -{ -unsigned int i, num_digits; -uint64_t digit; - - num_digits =vli_num_digits (vli, ndigits); -if (num_digits ==0 ) -return 0 ; - - digit = vli[num_digits -1 ]; -for (i =0 ; digit; i++) - digit >>=1 ; - -return ((num_digits -1 ) *64 + i); -} -/* Sets dest = src. */ static void vli_set (uint64_t *dest,const uint64_t *src,unsigned int ndigits) {
@@ -916,12 +885,20 @@ void _ecc_point_mult(struct l_ecc_point *result, uint64_t *initial_z, const uint64_t *curve_prime) {/* R0 and R1 */ +const struct l_ecc_curve *curve = point->curve;uint64_t rx[2 ][L_ECC_MAX_DIGITS ];uint64_t ry[2 ][L_ECC_MAX_DIGITS ];uint64_t z[L_ECC_MAX_DIGITS ]; +uint64_t sk[2 ][L_ECC_MAX_DIGITS ];int i, nb; -unsigned int ndigits = point->curve->ndigits; -int num_bits =vli_num_bits (scalar, ndigits); +unsigned int ndigits = curve->ndigits; +int num_bits; +int carry; + + carry =vli_add (sk[0 ], scalar, curve->n, ndigits); +vli_add (sk[1 ], sk[0 ], curve->n, ndigits); + scalar = sk[!carry]; + num_bits =sizeof (uint64_t ) * ndigits *8 +1 ;vli_set (rx[1 ], point->x, ndigits);vli_set (ry[1 ], point->y, ndigits);
Signature · 1 line
2.17.1