ECC public key validation stucks in ltc_ecc_map

KimSangpil commented

2016-02-23 19:57:01 -06:00

(Migrated from github.com)

ECDSA ceriticom[http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf] reference
says ECDSA public key (or private key) has to be validated by checking list below

Q : public key to validate
n: order of domain parameter
O: point at infinity

Check that Q ≠ O
..
..
Check that nQ = O

so I was calculate nQ using ltc_ecc_mulmod(n, Q, result, modulus, 1)
but it hangs.
here is the code(looked up ecc_test() codes)

   void     *modulus, *order;
   ecc_point  *Q, *Result;
   int i, err, primality;    
       /* ECC-224 */
 i=4;
       /* read modulus */
if ((err = mp_read_radix(modulus, (char *)ltc_ecc_sets[i].prime, 16)) != CRYPT_OK)   { goto done; }
       /* read order */
if ((err = mp_read_radix(order, (char *)ltc_ecc_sets[i].order, 16)) != CRYPT_OK)     { goto done; }

       /* read Q */
       if ((err = mp_read_radix(Q->x, (char *)"EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60", 16)) != C
RYPT_OK)         { goto done; }       
       if ((err = mp_read_radix(Q->y, (char *)"6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC", 16)) != C
RYPT_OK)         { goto done; }       
       mp_set(Q->z, 1);

       /* calculate nQ */
       if ((err = ltc_mp.ecc_ptmul(order, Q, Result, modulus, 1)) != CRYPT_OK)                  { goto done; }

used curve is(from src/pk/ecc/ecc.c)
LTC_ECC224
P="FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"
B="B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4"
n="FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D"
Gx="B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21"
Gy="BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34"

used public key parameter is (It is correct key !! has to be validate)
Qx = EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60
Qy = 6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC

I compiled libtomcrypt using libtommath library(both are static compiled).
build flags was
CFLAGS="-DLTM_DESC -I ../libtommath/" EXTRALIBS="-L. -ltommath" make
CFLAGS="-DLTM_DESC -I ../libtommath/" EXTRALIBS="-L. -ltommath" make test

Module seems to be stuck at ltc_ecc_map. but I don't know why.
Help me if you got anything clue.

and I got another question
Is there anything method that ECC point is at infinity?

my thinking was if Qz==0 then point is at infinity (look at the openssl is_point_at_infinity).
I want to know whether it corrects.

thanks.

ECDSA ceriticom[http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf] reference says ECDSA public key (or private key) has to be validated by checking list below Q : public key to validate n: order of domain parameter O: point at infinity 1. Check that Q ≠ O 2. .. 3. .. 4. Check that nQ = O so I was calculate nQ using ltc_ecc_mulmod(n, Q, result, modulus, 1) but it hangs. here is the code(looked up ecc_test() codes) ``` void *modulus, *order; ecc_point *Q, *Result; int i, err, primality; /* ECC-224 */ i=4; /* read modulus */ if ((err = mp_read_radix(modulus, (char *)ltc_ecc_sets[i].prime, 16)) != CRYPT_OK) { goto done; } /* read order */ if ((err = mp_read_radix(order, (char *)ltc_ecc_sets[i].order, 16)) != CRYPT_OK) { goto done; } /* read Q */ if ((err = mp_read_radix(Q->x, (char *)"EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60", 16)) != C RYPT_OK) { goto done; } if ((err = mp_read_radix(Q->y, (char *)"6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC", 16)) != C RYPT_OK) { goto done; } mp_set(Q->z, 1); /* calculate nQ */ if ((err = ltc_mp.ecc_ptmul(order, Q, Result, modulus, 1)) != CRYPT_OK) { goto done; } ``` used curve is(from src/pk/ecc/ecc.c) LTC_ECC224 P="FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001" B="B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4" n="FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D" Gx="B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21" Gy="BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34" used public key parameter is (It is correct key !! has to be validate) Qx = EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60 Qy = 6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC I compiled libtomcrypt using libtommath library(both are static compiled). build flags was CFLAGS="-DLTM_DESC -I ../libtommath/" EXTRALIBS="-L. -ltommath" make CFLAGS="-DLTM_DESC -I ../libtommath/" EXTRALIBS="-L. -ltommath" make test Module seems to be stuck at ltc_ecc_map. but I don't know why. Help me if you got anything clue. and I got another question Is there anything method that ECC point is at infinity? my thinking was if Qz==0 then point is at infinity (look at the openssl is_point_at_infinity). I want to know whether it corrects. thanks.

sjaeckel commented

2016-02-29 06:03:05 -06:00

(Migrated from github.com)

@karel-m has an updated version of ecc in the miko-ecc-enhancements branch.

Does this issue still apply there?

@karel-m has an updated version of ecc in the [miko-ecc-enhancements](https://github.com/libtom/libtomcrypt/tree/miko-ecc-enhancements) branch. Does this issue still apply there?

KimSangpil commented

2016-03-01 19:38:37 -06:00

(Migrated from github.com)

yes.
I checked out miko-ecc-enhancements
and doing same test.
It has same problem, too.
I changed somes parameters in above test code.

   void     *a, *modulus, *order;
   ecc_point  *Q, *Result;
   int i, err, primality;    
       /* ECC-224 */
 i=13;
       /* read A */
if ((err = mp_read_radix(a, (char *)ltc_ecc_sets[i].A,  16)) != CRYPT_OK)            { goto done; }   
       /* read modulus */
if ((err = mp_read_radix(modulus, (char *)ltc_ecc_sets[i].prime, 16)) != CRYPT_OK)   { goto done; }
       /* read order */
if ((err = mp_read_radix(order, (char *)ltc_ecc_sets[i].order, 16)) != CRYPT_OK)     { goto done; }

       /* read Q */
       if ((err = mp_read_radix(Q->x, (char *)"EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60", 16)) != C
RYPT_OK)         { goto done; }       
       if ((err = mp_read_radix(Q->y, (char *)"6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC", 16)) != C
RYPT_OK)         { goto done; }       
       mp_set(Q->z, 1);

       /* calculate nQ */
       if ((err = ltc_mp.ecc_ptmul(order, Q, Result, a, modulus, 1)) != CRYPT_OK)                  { goto done; }

And I find out it stucks at ltc_ecc_map()
I think module does not have checking whether the point is at infinity
when doing calculating ecc math.

Shouldn't we add this logic in module doing math?
Could you describe the math logic to me in libtomcrypt module when doing ecc?
I think I can help it.

yes. I checked out miko-ecc-enhancements and doing same test. It has same problem, too. I changed somes parameters in above test code. ``` void *a, *modulus, *order; ecc_point *Q, *Result; int i, err, primality; /* ECC-224 */ i=13; /* read A */ if ((err = mp_read_radix(a, (char *)ltc_ecc_sets[i].A, 16)) != CRYPT_OK) { goto done; } /* read modulus */ if ((err = mp_read_radix(modulus, (char *)ltc_ecc_sets[i].prime, 16)) != CRYPT_OK) { goto done; } /* read order */ if ((err = mp_read_radix(order, (char *)ltc_ecc_sets[i].order, 16)) != CRYPT_OK) { goto done; } /* read Q */ if ((err = mp_read_radix(Q->x, (char *)"EA3745501BBC6A70BBFDD8AEEDB18CF5073C6DC9AA7CBB5915170D60", 16)) != C RYPT_OK) { goto done; } if ((err = mp_read_radix(Q->y, (char *)"6C9CB8E68AABFEC989CAC5E2326E0448B7E69C3E56039BA21A44FDAC", 16)) != C RYPT_OK) { goto done; } mp_set(Q->z, 1); /* calculate nQ */ if ((err = ltc_mp.ecc_ptmul(order, Q, Result, a, modulus, 1)) != CRYPT_OK) { goto done; } ``` And I find out it stucks at ltc_ecc_map() I think module does not have checking whether the point is at infinity when doing calculating ecc math. Shouldn't we add this logic in module doing math? Could you describe the math logic to me in libtomcrypt module when doing ecc? I think I can help it.

KimSangpil commented

2016-03-02 03:49:24 -06:00

(Migrated from github.com)

I think this would be an answer

When doing ltc_mp.ecc_ptmul()

Add checks the point whether the point is at infinity before ltc_ecc_map()

// point at inifinity check function
int ltc_is_point_at_infinity(ecc_point *in)                                                                           
{ 
  if(mp_cmp_d(&in->z, 0)==LTC_MP_EQ)                                                                                           
  {                                                                                           
    return 1;                                                                                                         
  }
  else                                                                                                                
  {      
    return 0;                                                                                                         
  }                                                                                                                   
}      

// modified ltc_ecc_mulmod function
int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *a, void *modulus, int map)
{
   ecc_point *tG, *M[8];
   int        i, j, err;
   void       *mu, *mp;
   ltc_mp_digit buf;
   int        first, bitbuf, bitcpy, bitcnt, mode, digidx;

   LTC_ARGCHK(k       != NULL);
   LTC_ARGCHK(G       != NULL);
   LTC_ARGCHK(R       != NULL);
   LTC_ARGCHK(a       != NULL);
   LTC_ARGCHK(modulus != NULL);

  // ..... mulmod operation

   /* map R back from projective space */
   if (map) {
      err = ltc_is_point_at_infinity(R);
      if(err)
      {
      err = ltc_ecc_map(R, modulus, mp);
      }
      else
      {
        fprintf(stderr, "point at infinity!!\n");
      }
   } else {
      err = CRYPT_OK;
   }
done:
   if (mu != NULL) {
      mp_clear(mu);
   }
   mp_montgomery_free(mp);
   ltc_ecc_del_point(tG);
   for (i = 0; i < 8; i++) {
       ltc_ecc_del_point(M[i]);
   }
   return err;
}

but, ltc_is_point_at_infinity(R) returns LTC_MP_GT
because of R->z has used of 4

What was wrong ?
I think logic is quite simple and will be working.

It would be very appreciated If you give me a comment.

I think this would be an answer When doing ltc_mp.ecc_ptmul() Add checks the point whether the point is at infinity before ltc_ecc_map() ``` // point at inifinity check function int ltc_is_point_at_infinity(ecc_point *in) { if(mp_cmp_d(&in->z, 0)==LTC_MP_EQ) { return 1; } else { return 0; } } // modified ltc_ecc_mulmod function int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *a, void *modulus, int map) { ecc_point *tG, *M[8]; int i, j, err; void *mu, *mp; ltc_mp_digit buf; int first, bitbuf, bitcpy, bitcnt, mode, digidx; LTC_ARGCHK(k != NULL); LTC_ARGCHK(G != NULL); LTC_ARGCHK(R != NULL); LTC_ARGCHK(a != NULL); LTC_ARGCHK(modulus != NULL); // ..... mulmod operation /* map R back from projective space */ if (map) { err = ltc_is_point_at_infinity(R); if(err) { err = ltc_ecc_map(R, modulus, mp); } else { fprintf(stderr, "point at infinity!!\n"); } } else { err = CRYPT_OK; } done: if (mu != NULL) { mp_clear(mu); } mp_montgomery_free(mp); ltc_ecc_del_point(tG); for (i = 0; i < 8; i++) { ltc_ecc_del_point(M[i]); } return err; } ``` but, ltc_is_point_at_infinity(R) returns LTC_MP_GT because of R->z has used of 4 What was wrong ? I think logic is quite simple and will be working. It would be very appreciated If you give me a comment.

sjaeckel commented

2016-03-10 13:09:32 -06:00

(Migrated from github.com)

@karel-m can you please have a look and integrate that case in your ecc branch and fix it?

karel-m commented

2017-03-28 02:59:41 -05:00

(Migrated from github.com)

Could you please test the latest branch miko-ecc-enhancements - the fix is: b744d26 (although we should perhaps review handling of points at infinity also at other places).

Any improvements to _ecc_issue108 test (based on your example) are welcome:
https://github.com/libtom/libtomcrypt/blob/miko-ecc-enhancements/testprof/ecc_test.c#L109

Could you please test the latest branch `miko-ecc-enhancements` - the fix is: b744d26 (although we should perhaps review handling of points at infinity also at other places). Any improvements to `_ecc_issue108` test (based on your example) are welcome: https://github.com/libtom/libtomcrypt/blob/miko-ecc-enhancements/testprof/ecc_test.c#L109

sjaeckel commented

2017-06-12 16:17:38 -05:00

(Migrated from github.com)

@karel-m should I open a PR with the backported fix and testcase?

karel-m commented

2017-06-12 16:32:08 -05:00

(Migrated from github.com)

should I open a PR with the backported fix and testcase?

No, handling "point at infinity" is not a simple patch.

It is fixed in miko-ecc-enhancements (just checkout and grep for "infinity" to see all places that need fixing).

> should I open a PR with the backported fix and testcase? No, handling "point at infinity" is not a simple patch. It is fixed in `miko-ecc-enhancements` (just checkout and grep for "infinity" to see all places that need fixing).

karel-m commented

2017-06-12 16:44:42 -05:00

(Migrated from github.com)

Unfortunately rebasing miko-ecc-enhancements on current develop fails very badly and I am currently short of time to investigate more.

Unfortunately rebasing `miko-ecc-enhancements` on current `develop` fails very badly and I am currently short of time to investigate more.

sjaeckel commented

2017-06-13 05:36:12 -05:00

(Migrated from github.com)

No, handling "point at infinity" is not a simple patch.

Damn, but that patch at least fixes this issue ;-)

Unfortunately rebasing miko-ecc-enhancements on current develop fails very badly and I am currently short of time to investigate more.

~~That's also out of discussion for now, I'd prefer to have the remaining issues solved that we accepted to go into 1.18~~
Ah damn, this one is in 1.18... either we push it to next or we have to backport the "point at infinity" checks...

> No, handling "point at infinity" is not a simple patch. Damn, but that patch at least fixes this issue ;-) > Unfortunately rebasing miko-ecc-enhancements on current develop fails very badly and I am currently short of time to investigate more. ~~That's also out of discussion for now, I'd prefer to have the remaining issues solved that we accepted to go into 1.18~~ Ah damn, this one is in 1.18... either we push it to next or we have to backport the "point at infinity" checks...

sjaeckel commented

2017-06-27 07:16:17 -05:00

(Migrated from github.com)

@karel-m how should we proceed with this issue?

karel-m commented

2018-05-28 15:34:11 -05:00

(Migrated from github.com)

This should be fixed in develop. I'll close this issue in 2 weeks unless there is a feedback that it is still a problem.

Rows
Columns

ECC public key validation stucks in ltc_ecc_map #108