Topic: Bogus locator in getheaders (test data wanted) - page 2. (Read 637 times)
Bumping with hope that more people will check and either confirm or disprove.
Maybe also notably, Altcoins that forked out of bitcoin long time ago, may still have maximum size of the network message set to 32 MB, which makes the problem for them eight times worse.
Thanks for the review, I think I will wait for more people to check it out and confirm if this is valid before pushing it further. I'm also unaware of the absolute cost of a single hash table look up in C++. Still gut feeling is that hundred thousand of those can take some time and it seems completely unnecessary to allow locators to have more than a hundred of items.
Well, after taking a second look into this, I guess you are completely right. Sorry for my confusing answer earlier.
I see it just as you do: you could probably hang a node for quite a while with this.
Maybe you should reach out to gmaxwell about this?
I see it just as you do: you could probably hang a node for quite a while with this.
Maybe you should reach out to gmaxwell about this?
Small correction.
The limit of what a node replies to a GETHEADERS message can be found here - in net_processing.cpp:
You can request as much as you want, you will not get back more than MAX_HEADERS_RESULTS nor will the node process more than that.
The limit of what a node replies to a GETHEADERS message can be found here - in net_processing.cpp:
Code:
// we must use CBlocks, as CBlockHeaders won't include the 0x00 nTx count at the end
std::vectorvHeaders;
int nLimit = MAX_HEADERS_RESULTS;
LogPrint(BCLog::NET, "getheaders %d to %s from peer=%d\n", (pindex ? pindex->nHeight : -1), hashStop.IsNull() ? "end" : hashStop.ToString(), pfrom->GetId());
for (; pindex; pindex = chainActive.Next(pindex))
{
vHeaders.push_back(pindex->GetBlockHeader());
if (--nLimit <= 0 || pindex->GetBlockHash() == hashStop)
break;
}
You can request as much as you want, you will not get back more than MAX_HEADERS_RESULTS nor will the node process more than that.
But this code is executed AFTER FindForkInGlobalIndex is called. I'm talking about FindForkInGlobalIndex itself.
Small correction.
The limit of what a node replies to a GETHEADERS message can be found here - in net_processing.cpp:
You can request as much as you want, you will not get back more than MAX_HEADERS_RESULTS nor will the node process more than that.
The limit of what a node replies to a GETHEADERS message can be found here - in net_processing.cpp:
Code:
// we must use CBlocks, as CBlockHeaders won't include the 0x00 nTx count at the end
std::vectorvHeaders;
int nLimit = MAX_HEADERS_RESULTS;
LogPrint(BCLog::NET, "getheaders %d to %s from peer=%d\n", (pindex ? pindex->nHeight : -1), hashStop.IsNull() ? "end" : hashStop.ToString(), pfrom->GetId());
for (; pindex; pindex = chainActive.Next(pindex))
{
vHeaders.push_back(pindex->GetBlockHeader());
if (--nLimit <= 0 || pindex->GetBlockHash() == hashStop)
break;
}
You can request as much as you want, you will not get back more than MAX_HEADERS_RESULTS nor will the node process more than that.
I'm trying to understand the getheaders protocol message and how bitcoin core operates when it receives one. FindForkInGlobalIndex is being called when the locator is present the message. This message seems to go through all hashes inside of the locator and make a hash table look up to see if we know the hash.
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
Not possible,
you can only request 10 unconnecting headers announcements before a DOS limiter kicks in.
The variable (static const int MAX_UNCONNECTING_HEADERS = 10) limiting this is hard coded in validation.h.
Just do a "grep MAX_UNCONNECTING_HEADERS * -r" to see where the it's actually getting limited ... hint: in net_processing.cpp
Sorry, I fail to see that. The constant is used in ProcessHeadersMessage, which seems to have nothing to do with processing of getheaders protocol message (which starts on line 2029).
Thanks for reply. I admit that my C++ is not very good, so I could be missing something or misreading something. However, I can't see what you say in the code.
In primitives\block.h we have
So it seems there is no filtering on serialization - i.e. it looks like "what comes from network is going directly to the object instance". So if I read it correctly - if I send 100k hashes in locator, this object will be initialized with all of them.
Then in validation.cpp we have
so that looks to me like we go through all of them and we do lookups and we only have further processing when it is found.
What I don't see then is where this is implemented:
In primitives\block.h we have
Code:
struct CBlockLocator
{
std::vectorvHave;
CBlockLocator() {}
explicit CBlockLocator(const std::vector& vHaveIn) : vHave(vHaveIn) {}
ADD_SERIALIZE_METHODS;
template
inline void SerializationOp(Stream& s, Operation ser_action) {
int nVersion = s.GetVersion();
if (!(s.GetType() & SER_GETHASH))
READWRITE(nVersion);
READWRITE(vHave);
}
So it seems there is no filtering on serialization - i.e. it looks like "what comes from network is going directly to the object instance". So if I read it correctly - if I send 100k hashes in locator, this object will be initialized with all of them.
Then in validation.cpp we have
Code:
CBlockIndex* FindForkInGlobalIndex(const CChain& chain, const CBlockLocator& locator)
{
AssertLockHeld(cs_main);
// Find the latest block common to locator and chain - we expect that
// locator.vHave is sorted descending by height.
for (const uint256& hash : locator.vHave) {
CBlockIndex* pindex = LookupBlockIndex(hash);
if (pindex) {
if (chain.Contains(pindex))
return pindex;
if (pindex->GetAncestor(chain.Height()) == chain.Tip()) {
return chain.Tip();
}
}
}
return chain.Genesis();
}
so that looks to me like we go through all of them and we do lookups and we only have further processing when it is found.
What I don't see then is where this is implemented:
Quote
because the client software doesn't check all the hashes exhaustively
I was discussing getblockheader instead of your inquiry about getheaders. My mistake.
Now your problem is about a spv node who might send a huge block locator with bogus hashes, causing the client software to go through nonsense exhaustive searches.
Block locator is a special stack supposed to have around 10*log2maxblockheigt items with genesis block's hash on top. The structure is designed to help the situation with (specially) temporary short range forks. Abusing this structure for attacking the node by keeping it busy locating hashes is not possible, because the client software doesn't check all the hashes exhaustively, it tries to locate the fork point (approximately) by performing a (special version) of binary search on the list.
A more safe implementation should check the number of locators (block locator size) as well to be acceptable (not too large), I admit.
Now your problem is about a spv node who might send a huge block locator with bogus hashes, causing the client software to go through nonsense exhaustive searches.
Block locator is a special stack supposed to have around 10*log2maxblockheigt items with genesis block's hash on top. The structure is designed to help the situation with (specially) temporary short range forks. Abusing this structure for attacking the node by keeping it busy locating hashes is not possible, because the client software doesn't check all the hashes exhaustively, it tries to locate the fork point (approximately) by performing a (special version) of binary search on the list.
A more safe implementation should check the number of locators (block locator size) as well to be acceptable (not too large), I admit.
https://en.bitcoin.it/wiki/Protocol_documentation#getheaders - talking about block locator hashes.
I suppose getblockheader doesn't accept multiple inputs, you send one hash you get one result either in json or raw hex serialized format. I don't see any support for multiple hashes of multiple blocks to be requested. Am I missing something?
I'm trying to understand the getheaders protocol message and how bitcoin core operates when it receives one. FindForkInGlobalIndex is being called when the locator is present the message. This message seems to go through all hashes inside of the locator and make a hash table look up to see if we know the hash.
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
In the seem to me that an attacker can send us this protocol message with bogus hashes and the only limit I can see is the peer to peer network protocol message size limit of 4,000,000 bytes. This translates to roughly 125,000 hashes inside of the locator.
Therefore it seems that it is possible for the attacker to make us perform that many hash table look up operations while holding cs_main lock.
Is this really possible or am I missing something? If it is possible, is it not a denial service vector?
Jump to: