encode_qp runs slowly on space characters at the end of a line

[jbalazerpfpt]

When the input to MIME::Base64::encode_qp has a line that ends in a long run of space characters, more of those characters get encoded than necessary, and the processing runs extremely slowly. The bug is a denial of service attack vulnerability.

In Base64.xs, the while-loop of lines 360-361 backtracks from the end of an input line to the beginning of a run of consecutive horizontal white space characters at the end of the input line. The result is that those white space characters all get encoded with an equals sign. Under RFC 2045’s quoted-printable definition, that is allowed but unnecessary, as only the single last horizontal white space character of an input line needs to be encoded.

But more importantly, the backtracking causes a huge slowdown when an input line ends in a long run of white space characters. The forward scanning of lines 355-356 and the backtracking of lines 360-361 run repeatedly within the loop of line 351, starting at each successive character position in the run of white space characters that ends the input line. The time complexity of this operation is O(n^2) when it should be O(n). An input line that ends in several hundred thousand white space characters can take minutes to process.

Changing the while-loop to an 'if' statement fixes both issues, causing just the single last white space character of a line to get encoded and avoiding the backtracking that caused the slowdown:

+++ Base64.xs
@@ -357,7 +357,7 @@
            }
            if (p == end || *p == '\n') {
                /* whitespace at end of line must be encoded */
-               while (p > p_beg && (*(p - 1) == '\t' || *(p - 1) == ' '))
+               if (p > p_beg && (*(p - 1) == '\t' || *(p - 1) == ' '))
                    p--;
            }