signing alogrithm in eosjs-ecc yields different signature from that in eos!

[arc0035]

Hi,

I'm working on signature related development and I find that signing alogrithm in eosjs-ecc yields different signature from that in eos!!!! Both tag is dawn-v4.0.0.

Reproduce steps:

Firstly let's generate a signature from eos networks.

1 ) Let's have a transaction, for example:

{"expiration":"2018-05-23T07:29:11","ref_block_num":1,"ref_block_prefix":2,"max_net_usage_words":3,"max_cpu_usage_ms":4,"delay_sec":5,"context_free_actions":[],"actions":[{"account":"eosio.token","name":"issue","authorization":[{"actor":"eosio.token","permission":"active"}],"data":"0000000000ea305580969800000000000455445400000000056973737565"}],"transaction_extensions":[],"signatures":[],"context_free_data":[]}

And we use the default private key 5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3

2 ) I add some printing statements in private_key.cpp:

3 ) I send this transaction to v1/wallet/sign_transaction interface via rpc. Then in eos side, we know the digest of the transaction is 9d8815193d76ee236ef08e8b9fb675e6def3af8d8209d7665540ab9e17944e19 (in hex)

4 ) The sign_transaction yields result:

{"expiration":"2018-05-22T23:29:11.000+0000","refBlockNum":1,"refBlockPrefix":2,"maxNetUsageWords":3,"maxKcpuUsageMs":4,"delaySec":5,"contextFreeActions":[],"actions":[{"account":"eosio.token","name":"issue","authorization":[{"actor":"eosio.token","permission":"active"}],"data":"0000000000ea305580969800000000000455445400000000056973737565"}],"transactionExtensions":[],"signatures":["SIG_K1_K3dztmFctY8QPgD6BEnxaV4s1gxyfHPZYTqHx8gH9Hiq2MLvn8Uc4ki6w7C89GVXAQ5JFM37BERe5qJSVHAqSkD8AabtKR"],"contextFreeData":[]}

You can see the signature is :

SIG_K1_K3dztmFctY8QPgD6BEnxaV4s1gxyfHPZYTqHx8gH9Hiq2MLvn8Uc4ki6w7C89GVXAQ5JFM37BERe5qJSVHAqSkD8AabtKR

Now let's try it from eosjs-ecc. Steps:

1 ) I write some simple code. The input:

Digest: 9d8815193d76ee236ef08e8b9fb675e6def3af8d8209d7665540ab9e17944e19

private key: 5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3

2 ) Execute the code, the signature is:

SIG_K1_KgMrn3yteiHtoUnqBjBcVhjuJRkeXAfwaYFQaCDmMC6sD7mGU5qQRaz3GHWe96Mfvq5Ei56EHBiwjh7sg6GYjBGzcRv81Y

Background:

I'm writing a java based eos library and I've finished the java version fc-library. For the same transaction the java version fc-library yields same digest with eos side, however the final signatures are different(although I use the same private key). The signature in eos code refers to secp256k1.c in bitcoin and it is too hard for me to investigate so I have to refer to the eosjs-ecc for the ecc signing algorithm however by which I found that even for same digest and same private key the eosjs-ecc yields different signatures with this eos repository!!!

Any solution or advice on this please?

Regards

[jcalfee]

Thanks for all the helpful commands .. I'll work up a unit test and review implementations as soon as possible ..

Related: EOSIO/eosjs#121

[arc0035]

Hi jcalfee,

Thanks for the reply:)

[jcalfee]

Related #17

[jcalfee]

How did you get v1/wallet/sign_transaction to work? My test key is in keosd but this API is directly on nodeosd..

[arc0035]

Before my program call this signing interface, it will call wallet related rpc on 8888 to make sure that the wallet is unlocked and already imported the keys to sign :)

And we can force cleos to operate wallet through 8888 by setting this option: --wallet-url

[arc0035]

Hi ,

Any good news? :)

[jcalfee]

I'm working on this today .. A few simple things to get out of the way first.. Fortunately DPoS affords us some protection. Deterministic is better though.

[XuNeal]

Hey @jcalfee And @masonhunk, I have read the eos code, and compared the different between the eos and eosjs-ecc carefully. Now I can modify the eosjs-ecc to produce the same result with eos.

follow the @masonhunk testcase:

And the result is：

Pls check the PR:
#22

[arc0035]

@XuNeal Thanks and it looks good for me.

感谢大神

[jcalfee]

An update..

The canonical1 unit test I just checked in is the example above and includes @XuNeal's PR #22. It passes if I use the original method of checking for a canonical signature:

// toDer
const canonical = lenR === 32 && lenS === 32

This happens to be the most efficient when compared to the one below.

I have some confusion though, the other related ticket EOSIO/eosjs#121 references a Go implementation using a different (is)canonical condition. When I looked at how EOSIO/eos is being built, I found it is not simply checking the length of R and S anymore. It is using EOSIO/eos public_key::is_canonical. I implemented this (commit above) and found it is much slower and even causing one of the unit test to timeout. This other check does causes the second unit test (canonical2) to pass but the first to fail (canonical1).

So, only one unit test with pass at a time depending on the (is)canonical test being used.

The question remains: double check which is_canonical test is being used and find out why the discrepancy. After this is resolved we can have a valid unit test. It may be necessary to test with an alternative library such as secp256k1 (at npmjs) or perhaps just replacing bigi with bn.js. The BN.js library is probably a 2x speed improvement in some operations.

[XuNeal]

@jcalfee I wonder where the canonical2 come from, maybe that case is wrong. I test sign 32 bytes zero in the cpp version of eos, and I get the same result with eosjs-ecc.

The test code:

int main(int argc, const char * argv[]) {
    // using sha256 = fc::sha256;
    // char b[32];
    // memset(b, 0, sizeof(b));
    // auto sb = fc::sha256::hash(b, sizeof(b));
    auto sb =  fc::sha256("0000000000000000000000000000000000000000000000000000000000000000");
    auto strpkey = std::string("5HxQKWDznancXZXm7Gr2guadK7BhK9Zs8ejDhfA9oEBM89ZaAru");
    auto pkey = eosio::chain::private_key_type(strpkey);
    auto sig2 = pkey.sign(sb);
    auto strsig2 = (std::string)sig2;
    printf("%s\n", strsig2.c_str());
    return 0;
}

The output:

SIG_K1_KjLTq9WozaHp2fNNfSZmTzcqiu82gPcVU3ZyaEZJgH3WykSANvun9t3Pw6Z2xvbAcz24rcKBADWG7nvzq9wAobpq62CYVC

[arc0035]

another test case:

the digest is "6cb75bc5a46a7fdb64b92efefca01ed7b060ab5e0d625226e8efbc0980c3ddc1"
the private key: 5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3

the eos v4.1.0 yields: SIG_K1_Kk1yUXAG2Cfo2qvWuJiyvaGdwZBQ1HzSf4EZ9arUTWBL4kTngLM1GSUU59bJUVAqwJ886CNQMcR7mmx323gjQGvhEU8WpX

using the code by the above pr(and call "signHash"), it yields:
SIG_K1_K7ZppaTdB9w8RKCLRC9kVwMhjGgCGRmBsfTVVYuVNKoFRgh6DNHuSEyKEsQjChNG5ZuqfWcpF
MbEuL3rQKxsVmMKiZM3da

Hi @XuNeal

Could you provide the cpp signature code thus I can study furthur into the ecdsa logic?

[arc0035]

Any good news?

[XuNeal]

@masonhunk
Sorry, I had a weekend, and thanks, you find a bug. In eos the initial value of nonce is 1. I have fixed that with commit: 0141963

If you want to check the sign method in eos, here it is:

// ref: https://github.com/EOSIO/fc/blob/master/src/crypto/elliptic_impl_priv.cpp#L88
static int extended_nonce_function( unsigned char *nonce32, const unsigned char *msg32,
                                        const unsigned char *key32, unsigned int attempt,
                                        const void *data ) {
        unsigned int* extra = (unsigned int*) data;
        (*extra)++;
        return secp256k1_nonce_function_default( nonce32, msg32, key32, *extra, nullptr );
    }

    compact_signature private_key::sign_compact( const fc::sha256& digest, bool require_canonical )const
    {
        FC_ASSERT( my->_key != empty_priv );
        compact_signature result;
        int recid;
        unsigned int counter = 0;
        do
        {
            FC_ASSERT( secp256k1_ecdsa_sign_compact( detail::_get_context(), (unsigned char*) digest.data(), (unsigned char*) result.begin() + 1, (unsigned char*) my->_key.data(), extended_nonce_function, &counter, &recid ));
        } while( require_canonical && !public_key::is_canonical( result ) );
        result.begin()[0] = 27 + 4 + recid;
        return result;
    }

And the implement of secp256k1_nonce_function_default is:

// ref: https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/secp256k1.c#L335
static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
   unsigned char keydata[112];
   unsigned int offset = 0;
   secp256k1_rfc6979_hmac_sha256 rng;
   unsigned int i;
   /* We feed a byte array to the PRNG as input, consisting of:
    * - the private key (32 bytes) and message (32 bytes), see RFC 6979 3.2d.
    * - optionally 32 extra bytes of data, see RFC 6979 3.6 Additional Data.
    * - optionally 16 extra bytes with the algorithm name.
    * Because the arguments have distinct fixed lengths it is not possible for
    *  different argument mixtures to emulate each other and result in the same
    *  nonces.
    */
   buffer_append(keydata, &offset, key32, 32);
   buffer_append(keydata, &offset, msg32, 32);
   if (data != NULL) {
       buffer_append(keydata, &offset, data, 32);
   }
   if (algo16 != NULL) {
       buffer_append(keydata, &offset, algo16, 16);
   }
   secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, offset);
   memset(keydata, 0, sizeof(keydata));
   for (i = 0; i <= counter; i++) {
       secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
   }
   secp256k1_rfc6979_hmac_sha256_finalize(&rng);
   return 1;
}

[arc0035]

@XuNeal
Thanks very much. I read the RFC6979 carefully and it looks like eosjs-ecc does not implement this specification strictly. But even I adjust the code to match RFC6979, it still yields a different result other than EOS..So for now I have to dig furthur into EOS code. Thanks for the help!

[arc0035]

Hi ,

I think I've got the point.

After I read the source c code that EOS use(https://github.com/cryptonomex/secp256k1-zkp.git), I got some insights about signing logic. The core idea is simple: the algorithm generates a sequence of k by rfc6979(which ensures that the k sequence is determinestic) until it find a proper k that provides valid signature.

For the implementation , there is a "retrycounter"(called nonce in eosjs-ecc) to control the max length of the sequence. For example, for digest "9d8815193d76ee236ef08e8b9fb675e6def3af8d8209d7665540ab9e17944e19 ", firstly the counter is 1, then gets k value 78937978489545279348689506485008167242570381689764260783950945000648534
931899 which does not provide canoncialised signatures; then the algorithm set counter to 2, so it generates the first k value 78937978489545279348689506485008167242570381689764260783950945000648534 and ignores it(because it is already tested when counter == 1) then it generates the second k 50962684009203208823070746277808909963094551076887427562061002517767735
273186 that is valid and the process returns.

The eosjs-ecc strictly match above algorithm after @XuNeal make the PR . However for eos itself, it ignores the first k and it searches the k from second k!!!! So if the very first k provides valid signature, the eos will ignore it and continues the search while the eosjss will take the very first k as valid results. This is the case of digest "6cb75bc5a46a7fdb64b92efefca01ed7b060ab5e0d625226e8efbc0980c3ddc1" with private key 5KQwrPbwdL6PhXujxW37FSSQZ1JiwsST4cqQzDeyXtP79zkvFD3 as I stated in above comments.

Here is the c code and you can see that the counter passed is 1 and the k loop exectues two times:

//https://github.com/EOSIO/fc/blob/master/src/crypto/elliptic_impl_priv.cpp#L88
static int extended_nonce_function( unsigned char *nonce32, const unsigned char *msg32,
const unsigned char key32, unsigned int attempt,
const void data ) {
unsigned int extra = (unsigned int) data;
(*extra)++;//THIS IS THE INITIAL COUNTER VALUE, NOW IT IS 1 INSTEAD OF 0
return secp256k1_nonce_function_default( nonce32, msg32, key32, *extra, nullptr );
}

//secp256k1.c in https://github.com/cryptonomex/secp256k1-zkp.git
static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void data) {
secp256k1_rfc6979_hmac_sha256_t rng;
unsigned int i;
secp256k1_rfc6979_hmac_sha256_initialize(&rng, key32, 32, msg32, 32, (const unsigned char)data, data != NULL ? 32 : 0);
for (i = 0; i <= counter; i++) {//SINCE THIS COUNTER IS PASSED AS 1 IN THE FIRST TIME, SO THE LOOP WILL EXECUTE DOUBLE TIMES AND THE FIRST K IS IGNORED!!!!!!!!!!
secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
}
secp256k1_rfc6979_hmac_sha256_finalize(&rng);
return 1;
}

What I want to say is:
1 after @XuNeal 's pr, the eosjs-ecc is already good, it provides a valid signature(One hash can have MANY valid signatures, not just one). The only difference is that eos starts search from the second k while eosjs-ecc starts from the first k so sometimes they produce different results(but these results are both legal results).

2 we can adjust the eosjs-ecc loop code to ignore the very first k to make it strictly works the way eos does. It is up to @jcalfee to determine whether to do this. Here is how:

1. in signHash method in signature.js, change the initial nonce value to 1:
   

2. in deterministicGenerateK method of ecdsa.js , slightly change the loop structure:

Now, it produces the exactly same signatures with eos now.

@XuNeal @jcalfee

[XuNeal]

Hi @masonhunk
If you read my comment carefully, you will find I have a commit to skip first K.

Whatever, you have described the problem cleanly. Great Job

[venediktov]

Hi @jcalfee is this issue related to a snag I am hitting with ETH/EOS signature incompatibility in 4 out of 10 times in my tests ?
Please see my ETH/EOS recovery tests here
https://github.com/venediktov/cplusplus/blob/master/eth_eos.js
If you run it few times you will see signatures from ETH stop matching signatures from EOS for the same private key. Is it something to do with 4 attempts checking for non-canonical signature explained below ?

https://bitcoin.stackexchange.com/questions/68254/how-can-i-fix-this-non-canonical-signature-s-value-is-unnecessarily-high

I just need a clue where things break in order to fix my code , perhaps this is not EOS issue ?

The second pass what makes the signature different between EOS and ETH when canonical edge case is solved . ETH does not do second pass it just checks s > n/2 and then s -= n , but EOSJS-ECC has a while loop in the place and generates different signature for those canonical edge cases .

Changing code as shown in the picture will produce identical signature to ETH in all cases .
This is maybe the case when EOS node library code produces different signature too.

[jcalfee]

I had several developers check on this. Signatures on this chain for a given hash and private key do not need to match, they need only be canonical and valid. All the variations discussed are valid canonical signatures. So, I removed the bug label.

There is still some testing to do for variations of deployment size and performance:

• Adjust the k value per the RFC6979 sepc (k=0)
• Test with secp256k1 library (instead of ecurve)
• Test with a modified version of ecurve using bnjs

[jcalfee]

Signatures are not unique. Always recover a public key..

[venediktov]

@masonhunk , @jcalfee , @XuNeal , why do we even need this loop ? ETH only adjusts s period . I removed the loop and eos/eth/eosjs-ecc/eth-crypto all in sync now. With this loop I had problems with some private keys it was not recovering public key correctly.

[jcalfee]

The loop is necessary to find a signature that will pass canonical in nodeos. If a public key can't be recovered a valid transaction would fail; this is not an issue with eosjs + nodeos...

[abourget]

I'd really like to get to the bottom of this. Here's my analysis (we've had similar requests in eos-go):

eoscanada/eos-go#36 (comment)

We've create a small repo to compare the different implementation (see in my comment therein). There's a lot of versions and PRs to compare.. if some want to help out.

(not sure why this comment "unassigned jcalfee" !)

[foonsun]

I had several developers check on this. Signatures on this chain for a given hash and private key do not need to match, they need only be canonical and valid. All the variations discussed are valid canonical signatures. So, I removed the bug label.

There is still some testing to do for variations of deployment size and performance:

• Adjust the k value per the RFC6979 sepc (k=0)
• Test with secp256k1 library (instead of ecurve)
• Test with a modified version of ecurve using bnjs

Hi,Do you mean that the signatures used by eosjs-ecc and nodeos are both valid? If I use nodeos recover function:

public void assert_recover_key(const checksum256 * digest,const char * sig,size_t siglen,const char * pub,size_t publen) 

@jcalfee
Can the function recover the public key from signatures of eosjs-ecc ?thanks