jq Hash Collision Vulnerability Leading to Denial-of-Service

A denial-of-service vulnerability has been identified in jq, a command-line JSON processor, affecting all versions prior to the latest commit. The issue arises from the use of MurmurHash3 with a hardcoded seed, which allows attackers to precompute hash collisions. By sending a crafted JSON object of approximately 100 KB, keys can be manipulated to hash into the same bucket, causing hash table lookups to degrade from constant time to linear time. This exploitation transforms jq operations into quadratic time complexity, leading to significant CPU exhaustion. Common use cases such as CI/CD pipelines, web services, and data processing scripts are particularly impacted.

Impact

Exploitation of this vulnerability causes severe CPU exhaustion, turning efficient jq operations into resource-intensive processes. This denial-of-service effect can disrupt CI/CD pipelines, web services, and data processing tasks.

Reproduction

The vulnerability can be reproduced by creating a JSON object where all keys are crafted to hash into the same bucket, using the known seed value of 0x432A9843. This can be done by a script that generates keys designed to collide when hashed with MurmurHash3, then using jq to process the resulting JSON object. The performance degradation can be observed by timing the jq operation, which will take significantly longer with the crafted payload than with a normal one.

Remediation

The vulnerability has been patched by randomizing the hash seed, preventing the precomputation of collisions. Users should update to the latest version of jq where this fix is applied.