| 説明 | ## Denial of Service via Non-Cryptographic Hashing in InfiniStore KV Map
### Summary
An attacker with the ability to submit cache keys to an InfiniStore service can craft many distinct keys that collide under the process's default `std::hash<std::string>` implementation, causing bucket reuse in the global `kv_map`, which leads to algorithmic complexity denial of service and negatively impacts all clients sharing the InfiniStore instance.
### Affected Versions
- **Affected:** All versions containing the global `std::unordered_map<std::string, boost::intrusive_ptr<PTR>> kv_map` implementation through commit `502490382125803f785c80bf0345e9038df31f88`
- **Confirmed affected:** InfiniStore source version `0.0.0`, commit `502490382125803f785c80bf0345e9038df31f88`
- **Fixed:** Not available at the time of reporting
- **Introduced in:** Not verified
The vulnerable state is in memory. Colliding entries already inserted into `kv_map` remain unsafe until they are evicted, `purge_kv_map()` is called, or the server process is restarted. A fix that changes the hash scheme should rebuild or clear the existing map state.
### Details
The vulnerability occurs because InfiniStore stores attacker-influenced cache keys in a process-wide `std::unordered_map` and relies on the implementation's default `std::hash<std::string>` for bucket placement. In common libstdc++ builds this hash is deterministic and not designed to resist adversarial collision generation. Distinct cache keys remain distinct at the equality layer, but a large set of keys that share the same hash bucket makes operations on the shared map degrade from expected O(1) behavior to O(n), blocking the single-threaded libuv server path.
**Where the Hash is Computed**
The following code is from version `0.0.0`, commit `502490382125803f785c80bf0345e9038df31f88`.
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.h#L40-L41
extern std::unordered_map<std::string, boost::intrusive_ptr<PTR>> kv_map;
extern std::unordered_map<uintptr_t, boost::intrusive_ptr<PTR>> inflight_rdma_writes;
```
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L38-L41
// evict memory from head to tail, the PTR is shared by lru_queue and kv_map
// so we have to pop from both to evict the memory
std::list<boost::intrusive_ptr<PTR>> lru_queue;
std::unordered_map<std::string, boost::intrusive_ptr<PTR>> kv_map;
```
The hash is selected implicitly by `std::unordered_map<std::string, ...>` as `std::hash<std::string>`. The input is the full cache key string. The effective hash width is implementation-dependent `size_t`; the application does not add a keyed secret, per-process randomization, tenant domain separation, or a digest schema version.
**What Fields Are Included or Excluded**
The hash input includes:
- The cache key string bytes supplied through TCP or RDMA metadata paths
The hash input excludes:
- A per-process random secret or keyed hash seed
- Client identity or authentication context
- Tenant, user, or trust-domain namespace
- Operation type, cache schema version, or key schema version
- Rate-limit or per-client accounting state
These excluded values do not cause incorrect key equality because `std::unordered_map` still compares strings for equality. They matter because bucket placement is availability-sensitive. With a deterministic non-cryptographic hash, an attacker can precompute many distinct keys that collide in the target bucket namespace and force linear work in shared server operations.
**How the Hash is Used for a Security-Relevant Decision**
The following code is from version `0.0.0`, commit `502490382125803f785c80bf0345e9038df31f88`.
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L236-L266
int Client::tcp_payload_request(const TCPPayloadRequest *req) {
DEBUG("do tcp_payload_request... {}", op_name(req->op()));
switch (req->op()) {
case OP_TCP_PUT: {
evict_cache(ON_DEMAND_MIN_THRESHOLD, ON_DEMAND_MAX_THRESHOLD);
bool allocated =
mm->allocate(req->value_length(), 1,
[&](void *addr, uint32_t lkey, uint32_t rkey, int pool_idx) {
current_tcp_task_ = boost::intrusive_ptr<PTR>(new PTR(
addr, req->value_length(), pool_idx, req->key()->str()));
});
if (!allocated) {
ERROR("Failed to allocate memory");
return OUT_OF_MEMORY;
}
DEBUG("allocated memory: addr: {}, lkey: {}, rkey: {}", current_tcp_task_->ptr,
mm->get_lkey(current_tcp_task_->pool_idx),
mm->get_rkey(current_tcp_task_->pool_idx));
kv_map[req->key()->str()] = current_tcp_task_;
// set state machine
state_ = READ_VALUE_THROUGH_TCP;
bytes_read_ = 0;
expected_bytes_ = req->value_length();
break;
}
case OP_TCP_GET: {
auto it = kv_map.find(req->key()->str());
```
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L771-L791
int Client::check_key(const std::string &key_to_check) {
int ret;
// check if the key exists and committed
if (kv_map.count(key_to_check) > 0) {
ret = 0;
}
else {
ret = 1;
}
send_resp(FINISH, &ret, sizeof(ret));
reset_client_read_state();
return 0;
}
int Client::get_match_last_index(const GetMatchLastIndexRequest *request) {
int left = 0, right = request->keys()->size();
while (left < right) {
int mid = left + (right - left) / 2;
request->keys()->Get(mid);
if (kv_map.count(request->keys()->Get(mid)->str())) {
```
The hash output controls the bucket chosen for insertions, lookups, and deletions. That bucket choice is a security-relevant availability decision because every request path runs in the same server process and colliding buckets convert expected constant-time map operations into linear scans.
The service accepts unauthenticated protocol messages that only need the fixed magic value:
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/protocol.h#L35-L43
#define MAGIC 0xdeadbeef
#define MAGIC_SIZE 4
#define OP_RDMA_EXCHANGE 'E'
#define OP_RDMA_READ 'A'
#define OP_RDMA_WRITE 'W'
#define OP_CHECK_EXIST 'C'
#define OP_GET_MATCH_LAST_IDX 'M'
#define OP_DELETE_KEYS 'X'
```
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L656-L659
int verify_header(header_t *header) {
if (header->magic != MAGIC) {
return INVALID_REQ;
}
```
The server also binds the service listener to all interfaces by default:
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L1002-L1011
loop = uv_default_loop();
loop = (uv_loop_t *)loop_ptr;
assert(loop != NULL);
uv_tcp_init(loop, &server);
struct sockaddr_in addr;
uv_ip4_addr("x.x.x.x", config.service_port, &addr);
uv_tcp_bind(&server, (const struct sockaddr *)&addr, 0);
int r = uv_listen((uv_stream_t *)&server, 128, on_new_connection);
```
**Why Hash Equality Does Not Imply Security Equivalence**
The issue is not a wrong-object lookup or a raw cryptographic break of a secure digest. The issue is application-level hash flooding: InfiniStore treats the default unordered-map hash distribution as an availability invariant, but the hash function is deterministic and non-cryptographic. Distinct keys that are not equal can still share the same bucket hash. Once many attacker-controlled keys share a bucket, `count()`, `find()`, `operator[]`, and `erase()` require linear work across the colliding chain.
Because `src/infinistore.cpp` notes that the server is single-threaded, slow map operations can block unrelated clients:
```cpp
// https://github.com/bytedance/InfiniStore/blob/502490382125803f785c80bf0345e9038df31f88/src/infinistore.cpp#L1-L1
// single thread right now.
```
**How the Attacker Constructs a Conflicting Object**
The attacker constructs a collision set for the target C++ standard library implementation. Each object is a different cache operation with a different key, but the chosen keys share the same unordered-map bucket hash on the target host.
```json
{
"operation": "OP_TCP_PUT",
"key": "libstdcxx-colliding-key-000001",
"value": "attacker-controlled-block-a"
}
```
```json
{
"operation": "OP_TCP_PUT",
"key": "libstdcxx-colliding-key-000002",
"value": "attacker-controlled-block-b"
}
```
The two keys are not security-equivalent: they are distinct cache entries and should be independent. They become availability-equivalent at the hash-table bucket layer because the default hash places them in the same collision chain. Scaling this from two keys to thousands of precomputed colliding keys causes subsequent reads, writes, existence checks, prefix-match checks, and deletions to spend linear time in that chain.
**Version-Specific Behavior**
The vulnerable behavior was confirmed in commit `502490382125803f785c80bf0345e9038df31f88`, where `src/meson.build` declares project version `0.0.0` and the global `kv_map` uses the default `std::unordered_map` hasher. Exploitability depends on the C++ standard library implementation and target architecture because `std::hash<std::string>` is implementation-defined. The advisory is confirmed for libstdc++-style deterministic, non-randomized string hashing. Other standard library imple |
|---|