Public Key Extraction in Implicit Certificates (ECQV)

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Public Key Extraction in Implicit Certificates (ECQV)

biscas
Hi All,

I am currently using BouncyCastle 1.61 to create an application to generate
Implicit Certificates  (see
https://en.wikipedia.org/wiki/Implicit_certificate) and sign messages as
well as an application to extract the ECDSA Public Key, and verify the ECDSA
signature.

The goal is to use the application to generate Implicit Certificates AND
Signatures (it is a strange use case) so that devices in the field are able
to verify the ECDSA signature.
The applications so far developed are working correctly against each other
that is:
1. The Verifier Application is able to extract the ECDSA Public Key from an
implicit certificate computed by the Signer Application.
2. The Verifier Application is then able to verify the ECDSA Signature.

Moreover:
3. the Verifier Application is able to extract ECDSA Public Keys and verify
signatures from third-parties.

However the devices themselves when receiving an implicit certificate
generated by the Signer Application are not able to extract the correct
ECDSA Public Key. We are absolutely sure that this is not due to the Hash
computations, as the implicit certificate hashes are correctly computed.
Given 1. 2. and 3. we are also quite sure that from the algorithmic point of
view the Verifier application is mathematically correct.
In particular Public Key extraction is done in BouncyCastle 1.61, where
CURVE = new SecT163K1Curve() by:

ECPoint certPublicKey = CURVE.decodePoint(publicReconstKey);

//CryptoClassUtils.matyasMeyersOseasHashing is the chosen hashing function
that returns a 16 byte //array, so well within floor(Log_2(CURVE.getN())))
byte[] hash = CryptoClassUtils.matyasMeyersOseasHashing(implicitCert));        
BigInteger ECDSA_SIGNING_CERTIFICATE_HASH = new BigInteger(1,hash);

ECPoint ecdsaPublicKey = certPublicKey
                .multiply(ECDSA_SIGNING_CERTIFICATE_HASH)
                .add(CURVE.decodePoint(caPublicKey));

Now, given this I wonder whether there is some encoding/decoding regarding
compressed points. For instance:

With:

implicitCert = {0x02, 0x03, 0x7f, 0xf5, 0x63, 0x64, 0x52, 0x15, 0x78, 0xf3,
0x09, 0xf4, 0x70, 0x39, 0x24, 0x1a, 0xa4, 0xf2, 0xac, 0x30, 0x72, 0x66,
0x00, 0x0f, 0x93, 0xff, 0xfd, 0x03, 0x06, 0x9e, 0x54, 0x45, 0x53, 0x54,
0x53, 0x45, 0x43, 0x41, 0x01, 0x09, 0x00, 0x00, 0x10, 0x63, 0x00, 0x00,
0x00, 0x00};

caPublicKey = {0x03, 0x00, 0x86, 0x0b, 0xda, 0x66, 0xb4, 0xf0, 0xb9, 0x2c,
0x7c, 0xac, 0x1c, 0xaa, 0xb5, 0x15, 0xac, 0x78, 0xda, 0x80, 0xa0, 0x89};

publicReconstrKey = {0x02, 0x03, 0x7f, 0xf5, 0x63, 0x64, 0x52, 0x15, 0x78,
0xf3, 0x09, 0xf4, 0x70, 0x39, 0x24, 0x1a, 0xa4, 0xf2, 0xac, 0x30, 0x72,
0x66};

hash = {0x4b, 0x1a, 0x9c, 0xb5, 0xfa, 0x64, 0x8a, 0x6a, 0x75, 0x20, 0xff,
0x19, 0x6c, 0x68, 0x08, 0x5d};

ECDSA_SIGNING_CERTIFICATE_HASH = 99830277875878979416225826737509369949;

The developed Verifier will output ECDSA Public Key:

ecdsaPublicKey = {0x02, 0x07, 0xb2, 0xcb, 0xfd, 0x35, 0xa2, 0x38, 0x01,
0xdc, 0x65, 0x3e, 0x54, 0x0d, 0x75, 0x89, 0x4e, 0xec, 0x23, 0x74, 0xa3,
0x1c}

Certicom's Public Key Extraction algorithms will output instead:

ecdsaPublicKeyByCerticom = {0x02,0x00,0x2F,0x4A,0x8C,0xE8,0xAB,
0xCA,0xAE,0x3A,0x56,0xAC, 0x5E, 0xD1, 0x54, 0xE9, 0x5E, 0xE8, 0x5D, 0xDF,
0x77, 0xE4};

This behaviour is completely deterministic.

At this moment all I suspect is some kind of issue on encoding/decoding
elliptic curve points on these curves against Certicom's implementation. Do
you guys have any past experience integrating elliptic curve crypto against
Certicom's libs, specially those used in ZigBee?

Kindly,

Manuel













--
Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

Peter Dettman-3
Hi Manuel,
I think issues with the compressed point encoding is very unlikely.
Based on what you say, it's probably not a math issue either.

When you say "Certicom's Public Key Extraction algorithms" (CPKEA), what
specifically do you mean here? Is there a spec for it somewhere?

- Is this a hardware device, or some sort of testing library or what?
- Do you pass it the CA public key, or is it pre-configured? Does it
have a configured (alternate) CA public key for testing?
- Do you pass it your calculated hash and reconstruction data, or does
it work from the certificate itself?

There are a few points of failure I can see here (more than one might
apply!):

1. Domain parameters: you (via BC) are using the recommended basepoint
for sect163k1 (SEC 2, 3.2.1); do you know for sure that CPKEA hasn't
specified a different one?

2. CA public key mismatch (if it is pre-configured somehow, can you
print it out?).

3. Hash disagreement. If you pass it the hash, try passing 0 so that it
should just return you the CA public key. If it calculates its own hash:
have you configured the hash algorithm correctly, are you able to see
the hash outputs, have you tried other hash algorithms e.g. SHA-256?

Regards,
Pete Dettman

On 16/7/19 7:29 pm, biscas wrote:

> Hi All,
>
> I am currently using BouncyCastle 1.61 to create an application to generate
> Implicit Certificates  (see
> https://en.wikipedia.org/wiki/Implicit_certificate) and sign messages as
> well as an application to extract the ECDSA Public Key, and verify the ECDSA
> signature.
>
> The goal is to use the application to generate Implicit Certificates AND
> Signatures (it is a strange use case) so that devices in the field are able
> to verify the ECDSA signature.
> The applications so far developed are working correctly against each other
> that is:
> 1. The Verifier Application is able to extract the ECDSA Public Key from an
> implicit certificate computed by the Signer Application.
> 2. The Verifier Application is then able to verify the ECDSA Signature.
>
> Moreover:
> 3. the Verifier Application is able to extract ECDSA Public Keys and verify
> signatures from third-parties.
>
> However the devices themselves when receiving an implicit certificate
> generated by the Signer Application are not able to extract the correct
> ECDSA Public Key. We are absolutely sure that this is not due to the Hash
> computations, as the implicit certificate hashes are correctly computed.
> Given 1. 2. and 3. we are also quite sure that from the algorithmic point of
> view the Verifier application is mathematically correct.
> In particular Public Key extraction is done in BouncyCastle 1.61, where
> CURVE = new SecT163K1Curve() by:
>
> ECPoint certPublicKey = CURVE.decodePoint(publicReconstKey);
>
> //CryptoClassUtils.matyasMeyersOseasHashing is the chosen hashing function
> that returns a 16 byte //array, so well within floor(Log_2(CURVE.getN())))
> byte[] hash = CryptoClassUtils.matyasMeyersOseasHashing(implicitCert));        
> BigInteger ECDSA_SIGNING_CERTIFICATE_HASH = new BigInteger(1,hash);
>
> ECPoint ecdsaPublicKey = certPublicKey
>                 .multiply(ECDSA_SIGNING_CERTIFICATE_HASH)
>                 .add(CURVE.decodePoint(caPublicKey));
>
> Now, given this I wonder whether there is some encoding/decoding regarding
> compressed points. For instance:
>
> With:
>
> implicitCert = {0x02, 0x03, 0x7f, 0xf5, 0x63, 0x64, 0x52, 0x15, 0x78, 0xf3,
> 0x09, 0xf4, 0x70, 0x39, 0x24, 0x1a, 0xa4, 0xf2, 0xac, 0x30, 0x72, 0x66,
> 0x00, 0x0f, 0x93, 0xff, 0xfd, 0x03, 0x06, 0x9e, 0x54, 0x45, 0x53, 0x54,
> 0x53, 0x45, 0x43, 0x41, 0x01, 0x09, 0x00, 0x00, 0x10, 0x63, 0x00, 0x00,
> 0x00, 0x00};
>
> caPublicKey = {0x03, 0x00, 0x86, 0x0b, 0xda, 0x66, 0xb4, 0xf0, 0xb9, 0x2c,
> 0x7c, 0xac, 0x1c, 0xaa, 0xb5, 0x15, 0xac, 0x78, 0xda, 0x80, 0xa0, 0x89};
>
> publicReconstrKey = {0x02, 0x03, 0x7f, 0xf5, 0x63, 0x64, 0x52, 0x15, 0x78,
> 0xf3, 0x09, 0xf4, 0x70, 0x39, 0x24, 0x1a, 0xa4, 0xf2, 0xac, 0x30, 0x72,
> 0x66};
>
> hash = {0x4b, 0x1a, 0x9c, 0xb5, 0xfa, 0x64, 0x8a, 0x6a, 0x75, 0x20, 0xff,
> 0x19, 0x6c, 0x68, 0x08, 0x5d};
>
> ECDSA_SIGNING_CERTIFICATE_HASH = 99830277875878979416225826737509369949;
>
> The developed Verifier will output ECDSA Public Key:
>
> ecdsaPublicKey = {0x02, 0x07, 0xb2, 0xcb, 0xfd, 0x35, 0xa2, 0x38, 0x01,
> 0xdc, 0x65, 0x3e, 0x54, 0x0d, 0x75, 0x89, 0x4e, 0xec, 0x23, 0x74, 0xa3,
> 0x1c}
>
> Certicom's Public Key Extraction algorithms will output instead:
>
> ecdsaPublicKeyByCerticom = {0x02,0x00,0x2F,0x4A,0x8C,0xE8,0xAB,
> 0xCA,0xAE,0x3A,0x56,0xAC, 0x5E, 0xD1, 0x54, 0xE9, 0x5E, 0xE8, 0x5D, 0xDF,
> 0x77, 0xE4};
>
> This behaviour is completely deterministic.
>
> At this moment all I suspect is some kind of issue on encoding/decoding
> elliptic curve points on these curves against Certicom's implementation. Do
> you guys have any past experience integrating elliptic curve crypto against
> Certicom's libs, specially those used in ZigBee?
>
> Kindly,
>
> Manuel

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

biscas
Hi Peter,

Thank you very much for your insightful comments. I hadn't thought of point
3, though our impression is that hash mismatch is impossible, that is: the
Hash function (in this case Matyas Meyers Oseas hashing function (128 bits))
on our side outputs exactly the same as the Hash function in Certicom's
case. Either way, I find very worthwhile to investigate whether Public Key
Extraction having as 0 the Hash still outputs the same CA Public Key.

A little more context on the problem at hand:

Every ZigBee device in the market contains Certicom issued implicit
certificates, not only for initial ZigBee  communications, but for firmware
verification as well. Certicom also gives every ZigBee chip manufacturer
their own elliptic curve lib, eccapi.h, which covers all the use cases where
the devices need to use Elliptic Point crypto.

Namely the function that reconstruct Public Keys given the inputs is:


Reconstructs the remote party's public key using its implicit certificate
and the CA public key.

int ZSE_ECQVReconstructPublicKey(unsigned char* certificate,
                                 unsigned char* caPublicKey,
                                 unsigned char* publicKey,
                                 HashFunc *Hash,
                                 YieldFunc *yield,
                                 unsigned long yieldLevel);

where:
certificate/input is a 48 byte array containing the certificate.
caPublicKey/input is the 22 byte array containing the CA Public Key
publicKey/output is the output, that is, the ECDSA Public Key
HashFunc is a function point to an Hash Function, in this use case, it will
always be MMOHash based on AES-128
YieldFunc/YieldLevel are functions for device watchdogs, to interrupt
computations on the device, so not really relevant here. Certicom's spec for
the function is unknown, as well as test-vectors. What is known is how it
/should/ operate, see Wikipedia or Certicom's own explanation of the ECQV
https://www.certicom.com/content/certicom/en/code-and-cipher/explaining-implicit-certificates-part-2.html

Kind Regards,

Manuel




--
Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

biscas
Hi Peter,

Regarding Point 3, we have made the suggested test, that is:

int dummy_hash(unsigned char *digest, unsigned long int sz, unsigned char
*dat){
    memset(digest,0,16);
    return 0;
}

ZSE_ECQVReconstructPublicKey(u_certificate,ca_PublicKey,u_recoveredPublicKey1,dummy_hash,
yield, YIELD_LEVEL);

If CA_Public_Key is a Public Key generated via BouncyCastle, for instance:

BC_CA_PUBLIC_KEY:
03:03:8B:06:D2:86:55:52:31:3C:0A:13:E6:2B:22:F4:48:DE:CB:D1:E1:77
RECOVERED_KEY:
03:06:79:D1:85:B2:E5:9F:F1:94:1C:07:FA:DE:E1:80:4A:32:9D:A4:97:11
RECOVERED KEY is different from the BC_CA_PUBLIC_KEY AND BouncyCastle deems
it to be invalid.

CERTICOM_CA_PUBLIC_KEY:
02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
RECOVERED_KEY:
02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8

If on the other side, CERTICOM_CA_PUBLIC_KEY is used as input, output
matches input. Moreover the CERTICOM_CA_PUBLIC_KEY is a valid one according
to BouncyCastle. This at least explains why the developed BC Verifier is
able to verify signatures from certificates emitted by Certicom.




--
Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

Peter Dettman-3
Hi Manuel,
That is a very strange result!

As far as I can see, BC_CA_PUBLIC_KEY is a valid public key, do you have
any other sect163k1 implementations to hand to confirm/contradict that?

The RECOVERED_KEY from BC_CA_PUBLIC_KEY is invalid because its order is
2N instead of N (this curve has cofactor 2). The point of order 2 is
(0,1) on this curve, but RECOVERED_KEY is not that, nor is it
(BC_CA_PUBLIC_KEY + (0,1)).

Which means the "public key reconstruction data" would have to be
invalid; not just with incorrect order, but actually not even a point on
the curve - but did you use the same certificate in each test or
generate separate ones? (Using different procedures?)

Could you provide the certificate(s) for these cases please.

If you are able to do more tests, could you please try this hash==0 test
with the basepoint (G) as the CA:
    0302FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8

Also, if you try it for many (100s) newly-generated BC CA keys, does it
always fail i.e. RECOVERED_KEY is different?

Regards,
Pete Dettman

On 17/7/19 5:51 pm, biscas wrote:

> Hi Peter,
>
> Regarding Point 3, we have made the suggested test, that is:
>
> int dummy_hash(unsigned char *digest, unsigned long int sz, unsigned char
> *dat){
>     memset(digest,0,16);
>     return 0;
> }
>
> ZSE_ECQVReconstructPublicKey(u_certificate,ca_PublicKey,u_recoveredPublicKey1,dummy_hash,
> yield, YIELD_LEVEL);
>
> If CA_Public_Key is a Public Key generated via BouncyCastle, for instance:
>
> BC_CA_PUBLIC_KEY:
> 03:03:8B:06:D2:86:55:52:31:3C:0A:13:E6:2B:22:F4:48:DE:CB:D1:E1:77
> RECOVERED_KEY:
> 03:06:79:D1:85:B2:E5:9F:F1:94:1C:07:FA:DE:E1:80:4A:32:9D:A4:97:11
> RECOVERED KEY is different from the BC_CA_PUBLIC_KEY AND BouncyCastle deems
> it to be invalid.
>
> CERTICOM_CA_PUBLIC_KEY:
> 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
> RECOVERED_KEY:
> 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
>
> If on the other side, CERTICOM_CA_PUBLIC_KEY is used as input, output
> matches input. Moreover the CERTICOM_CA_PUBLIC_KEY is a valid one according
> to BouncyCastle. This at least explains why the developed BC Verifier is
> able to verify signatures from certificates emitted by Certicom.
>
>
>
>
> --
> Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html
>


Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

biscas
This post was updated on .
Hi Peter,

The results of the tests with dummy_hash function == 0:

CA Public Key BouncyCastle
input: 03:03:8B:06:D2:86:55:52:31:3C:0A:13:E6:2B:22:F4:48:DE:CB:D1:E1:77
output: 03:06:79:D1:85:B2:E5:9F:F1:94:1C:07:FA:DE:E1:80:4A:32:9D:A4:97:11
CA Public Key Certicom
input: 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
output: 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
CA Public Key Base Point G
03:02:FE:13:C0:53:7B:BC:11:AC:AA:07:D7:93:DE:4E:6D:5E:5C:94:EE:E8
02:06:93:E6:EF:A3:28:03:9E:5B:1C:33:B7:B3:9D:02:E3:57:36:77:9D:98


I'll try running battery tests, tomorrow; I have done different tests in
the past, though with not a dummy hash function ==0, and the results always caused failures if using BC Public Keys. I don't have access to any other EC lib right now; I'll have a look at openssl...

The strange thing is that Certicom supposedly states that implements exactly
their SECG articles; and now it seems that somehow they restrict the usage
of their libs to Certicom issued points, in some strange way...

Kindly,

Manuel



--
Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

Peter Dettman-3
Hi Manuel, a question below.

On 18/7/19 7:56 pm, biscas wrote:
> CA Public Key Certicom
> input: 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
> output: 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8
> CA Public Key Base Point G
> input: 03:02:FE:13:C0:53:7B:BC:11:AC:AA:07:D7:93:DE:4E:6D:5E:5C:94:EE:E8
> output: 02:00:FD:E8:A7:F3:D1:08:42:24:96:2A:4E:7C:54:E6:9A:C3:F0:4D:A6:B8

Is this ^^^ a typo? It returns "CA Public Key Certicom" when the input
is G??

Regards,
Pete Dettman

Reply | Threaded
Open this post in threaded view
|

Re: Public Key Extraction in Implicit Certificates (ECQV)

biscas
Hi Peter,

It was a typo indeed but on the test reporting :p

Please see the edited post :)

Kindly,

Manuel





--
Sent from: http://bouncy-castle.1462172.n4.nabble.com/Bouncy-Castle-Dev-f1462173.html