[eosio] eos/wax signature error is_ Canonical (c): signature is not canonical

review

《【 Blockchain 】 Publish a pure Python Realized EOSIO WAX SDK》
In the previous post , We re implemented a lightweight EOSIO SDK, But it took a while , It is found that sometimes transactions are submitted to EOS/WAX Online RPC Node time , The following error will be returned ：

{“code”:500,“message”:“Internal Service Error”,“error”:{“code”:10,“name”:“assert_exception”,“what”:“Assert Exception”,“details”:[{“message”:“is_canonical( c ): signature is not canonical”,“file”:“elliptic_secp256k1.cpp”,“line_number”:164,“method”:“public_key”}]}}

Probably because the signature is not standard ,R or S Overvalued

Specification signature

The canonical signature is actually in BTC It is stipulated in :

【Low S values in signatures】:https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#Low_S_values_in_signatures

BTC in bip62 Specifies the in the signature S The value cannot be greater than N/2, Because for a standard R Values and S value ,(R, S)、(N-R, S)、(R, N-S)、(N-R, N-S) Are legal signature values , If it is not constrained , It can lead to a problem , For the same transaction , There are four legal signature results , When your transaction is submitted to the Internet , A malicious attacker can use your signature (R, S), Generate an identical transaction , With signature (N-R, S), Replay attack (Replay Attacks).

The result was that your deal was for B Jun transfer 500 Coins , After being replayed by a malicious person , It will turn into two transactions , Repeat to B Jun transfer 500 Two coins , And suffer losses .

actually , Just specification R or S Less than N/2 To avoid the problem , But in the EOSIO in , This specification is more stringent ：

https://steemit.com/steem/@dantheman/steem-and-bitshares-cryptographic-security-update

EOSIO requirement R and S Both must be less than at the same time N/2 Talent

Troubleshoot problems

our 【eosapi】 The code of the signature part , The reference is 【ueosio】, Let's see is_canonical() The implementation of the ：

def is_canonical(r, s):
	C = int((2 ** 256 - 1) / 2)
    return r <= C and s <= C

No problem , Signature is 256 Bit ,N by 256 The maximum number of digits 2 ** 256 - 1, The code checks R and S All less than N/2
What is it for? EOS RPC The server still reports an error ？

The best way to solve the problem is to look at the source code

The returned error message has told us ：

{“message”:“is_canonical( c ): signature is not canonical”,“file”:“elliptic_secp256k1.cpp”,“line_number”:164,“method”:“public_key”}

The mistake comes from 【elliptic_secp256k1.cpp】 Of the 164 That's ok , So we were EOSIO official github Find this line of code in , And find 【is_canonical】 The implementation of this function ：
https://github.com/EOSIO/fc/blob/master/src/crypto/elliptic_common.cpp

bool public_key::is_canonical( const compact_signature& c ) {
    
        return !(c.data[1] & 0x80)
               && !(c.data[1] == 0 && !(c.data[2] & 0x80))
               && !(c.data[33] & 0x80)
               && !(c.data[33] == 0 && !(c.data[34] & 0x80));
    }

Then the case was solved , It turns out that it not only requires R and S All less than N/2, Also require R and S Are greater than or equal to (2 ** (256-8) - 1) / 2

Understand the principles

First, explain how to understand this algorithm , First compact_signature& c What is it? ,compact_signature& c Signature data , Let's see 【ueosio】 How to generate this signature ：

def sign_hash(h, pk):
    nonce = 0
    while True:
        v, r, s = ecdsa_raw_sign_nonce(h, pk, nonce)
        if is_canonical(r, s):
            signature = '00%02x%064x%064x' % (v, r, s)
            break
        nonce += 1
    sig = DataStream(bytes.fromhex(signature)).unpack_signature()
    return sig

This 【signature】 It's actually V / R / S It's stitched together , altogether 66 Bytes , At the beginning ‘\x00’ Indicates the signature type , Omit to remove , Finally, the server resolves compact_signature& c The actual is V / R / S Put it together 65 Bytes , among V Occupy 1 Bytes ,R and S Accounting for 32 byte , Because the signature is 256 Bit .

So in 【is_canonical】 in ,c.data[1] Refers to R The highest byte of the value （ high 8 position ）,c.data[33] Refers to S The highest byte of the value （ high 8 position ）

that

 c.data[1] & 0x80

What does that mean ？

First c.data[1] yes 1 Bytes ,0x80 What is the binary of , yes 10000000

c.data[1] Place and place 0x80, When the result is True ？ Of course it's a request c.data[1] The highest bit of binary is also 1 When , The expression is True, When c.data[1] The highest binary bit of is 0 When , Expression return False

c.data[1] The highest binary bit of is 1 Words , that c.data[1] At the very least >= 0x80, c.data[1] The highest binary bit of is 0 Words , that c.data[1] must < 0x80

So this bitwise and expression is actually equivalent to

 c.data[1] >= 128

therefore

!(c.data[1] & 0x80)

Is actually equivalent to

c.data[1] < 128

And one 32 Bytes of 256 The highest byte of bits （ high 8 position ） Less than 128 What does that mean ？

First , The maximum value of a byte is 255, Less than 128 Is less than half of the maximum value represented by this byte

And one 32 The highest byte of the number of bytes is less than 128, It means this 32 Byte number , Less than 32 Half the maximum value that a byte can represent , That is less than N/2 Well

So go around , The meaning of this code is still to ask R and S All less than N/2

But beyond that , It also adds two conditions ：

&& !(c.data[1] == 0 && !(c.data[2] & 0x80))

&& !(c.data[33] == 0 && !(c.data[34] & 0x80));

Does that mean , R If the highest byte of is equal to 0 Words ,R The next highest byte of cannot be less than 128 Well ,S It's worth the same

and R The next highest byte of cannot be less than 128, Doesn't that mean asking R Greater than or equal to (2 ** (256-8) - 1) / 2

solve

therefore ,【ueosio】 Of 【is_canonical】 In theory, the function can be changed in this way ：

def is_canonical(r, s):
    C1 = int((2 ** 256 - 1) / 2)
    C2 = int((2 ** (256-8) - 1) / 2)
    return C2 <= r < C1 and C2 <= s < C1

Of course , The most rigorous change is to be completely consistent with EOSIO The official code is consistent , Finally, we changed it like this ：

def is_canonical(c):
    return not (c[1] & 0x80) \
           and not (c[1] == 0 and not (c[2] & 0x80)) \
           and not (c[33] & 0x80) \
           and not (c[33] == 0 and not (c[34] & 0x80))

And the code has been submitted for update ：
https://github.com/encoderlee/eosapi/commit/5ffd1235dd938cc8836be58f9f12622e7f3d08ae

Please update in time , To avoid this problem ：

pip install --upgrade eosapi

Digression

I want to refer to our signature code 【ueosio】, Without reference to 【eospy】？

In fact, the main problem is performance , The same deal ,【eospy】 Signing takes time 20ms, and 【ueosio】 Time consuming only 2ms, Difference between 10 Twice as many ！！！

20ms What is the concept ？ My computer room from here to Shanghai Telecom is delayed 20ms Not even , If you submit a transaction more slowly than others 20ms, How can you rob others when you are a Trading Robot .

【eospy】 The signature library used internally is 【ecdsa】
and
【ueosio】 The signature library used internally is 【cryptos】

Logically speaking 【ecdsa】 Than 【cryptos】 More popular , It is also more perfect , and 【ecdsa】 The claimed test data is not so straying , So it's probably 【eospy】 The use of posture problems caused by the slow

【cryptos】 stay github Upper star Although not so much , however ！

【cryptos】 stay github The project name on is 【pybitcointools】, Its original version was the founder of Ethereum V God himself wrote , later V God has no time and energy to maintain , It is left to the open source community , See here for details ：
https://github.com/vbuterin/pybitcointools

I really don’t have time to maintain this library further. If you want to fork it or use it despite lack of maintenance, feel free to clone locally and revert one commit.
This externally-maintained fork looks good though I did not personally
write it so can’t vouch for security:
https://github.com/primal100/pybitcointools

Apart from efficiency , Once again proved our 【eosapi】 choice V Divine 【cryptos】 Implementing the underlying signature algorithm is the right choice ！

Exchange and discussion