Ruby (aka CRuby) before 1.8.7-p357 computes hash values without restricting the ability to trigger hash collisions predictably, which allows context-dependent attackers to cause a denial of service (CPU consumption) via crafted input to an application that maintains a hash table.
Ruby applications using versions prior to 1.8.7-p357 are vulnerable to a denial-of-service (DoS) attack. By providing specially crafted input, attackers can trigger hash collisions, leading to excessive CPU consumption and application unavailability, effectively rendering the application unresponsive.
Step 1: Payload Generation: The attacker crafts a set of input strings designed to collide within the Ruby hash table. These strings are carefully constructed to produce the same hash value when processed by the vulnerable hash function.
Step 2: Input Delivery: The attacker submits the crafted input to the Ruby application. This could be through a web form, API call, or any other input mechanism that the application uses.
Step 3: Hash Table Population: The Ruby application receives the input and attempts to store it in a hash table (e.g., a hash or a dictionary). Due to the predictable hash function, the crafted input strings all map to the same bucket within the hash table.
Step 4: Collision Trigger: When the application attempts to access or process any of the colliding keys, it must iterate through the entire bucket containing all the colliding entries. This linear search consumes significant CPU resources.
Step 5: Denial of Service: The CPU consumption caused by the linear search leads to a denial-of-service. The application becomes unresponsive, unable to process legitimate requests, and potentially crashes or becomes unavailable.
The vulnerability stems from the lack of randomization in Ruby's hash function implementation. Specifically, the hash function used in older versions of Ruby (CRuby) does not adequately prevent predictable hash collisions. An attacker can craft input that forces multiple keys to hash to the same bucket within a hash table. When the application attempts to retrieve or process these colliding keys, it results in a linear search through the bucket, leading to a significant performance degradation. This is because the hash table's performance degrades from O(1) to O(n) for lookups and insertions in the worst-case scenario, where n is the number of colliding keys. The root cause is the predictable nature of the hash function, which allows attackers to control the hash values of their input.