ECC public key validation stucks in ltc_ecc_map

[KimSangpil]

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]

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

Does this issue still apply there?

[KimSangpil]

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]

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]

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

[karel-m]

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]

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

[karel-m]

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).