Affected: ruby net-imap

Net::IMAP implements Internet Message Access Protocol (IMAP) client functionality in Ruby. Prior to versions 0.4.24, 0.5.14, and 0.6.4, Net::IMAP::ResponseReader has quadratic time complexity when reading large responses containing many string literals. A hostile server can send responses which are crafted to exhaust the client's CPU for a denial of service attack. This issue has been patched in versions 0.4.24, 0.5.14, and 0.6.4.

Affected: RubyGems: net-imap

### Summary

`Net::IMAP::ResponseReader` has quadratic time complexity when reading large responses containing many string literals. A hostile server can send responses which are crafted to exhaust the client's CPU for a denial of service attack.

### Details

For each literal in a response, `ResponseReader` rescans the entire growing response buffer. The regular expression that is used to scan the response buffer runs in linear time. With many literals, this becomes O(n²) total work. The regular expression should run in constant time: it is anchored to the end and only the last 23 bytes of the buffer are relevant.

Because the algorithmic complexity is super-linear, this bypasses protection from `max_response_size`: a response can stay well below the default size limit while still causing very large CPU cost.

`Net::IMAP::ResponseReader` runs continuously in the receiver thread until the connection closes.

### Impact

This consumes disproportionate CPU time in the client's receiver thread. A hostile server could use this to exhaust the client's CPU for a denial of service attack.

For a response near the default `max_response_size`, each individual regexp scan could take between 100 to 200ms on common modern hardware, and this may be repeated 200k times per megabyte of response. While the regexp is scanning, it retains the Global VM lock, preventing other threads from running.

Although other threads should not be _completely_ blocked, their run time will be signific…