Unbounded recursion when decrypting messages leading to unbounded allocation

[teythoon]

Description

Looking at https://tests.sequoia-pgp.org/#Maximum_recursion_depth suggested that RNP does not constrain the recursion when processing messages (or it has a very high limit). And indeed, processing a PGP compression quine leads to unbounded memory allocation.

Steps to Reproduce

1. Download https://gitlab.com/sequoia-pgp/sequoia/-/raw/master/openpgp/tests/data/messages/compression-quine.gpg?inline=false
2. Set limits to protect your system: ulimit -d 1048576
3. rnp --decrypt compression-quine.gpg

Expected Behavior

Recursion depth must be limited and processing aborted.

Actual Behavior

Unbounded memory allocation.

[ni4]

@teythoon Thanks for reporting, we'll provide a fix. While nested compressed messages are not denied by the RFC 4880, logically it doesn't have any sense. So probably it would be more correct to throw an error after the first nested compressed packet.

[teythoon]

The same problem applies to nested encryption containers, which do make sense. The underlying problem is recursion depth.

[teythoon]

I'd like to raise the severity of this issue. This is a trivially exploitable DOS with nasty consequences (the system starts trashing and gets unresponsive as a result). Yet, #1217 which was reported later got a higher priority.

[teythoon]

I have a follow-up question, if I may. I have inspected your test vector ("message.zlib-quine"), and it is different from our quine and the quine that Taylor offers for download:

% sha256sum quine*pgp
d1ea93dbb39b8c3098ac5d7f23fd39644e15e839fb31f9be1ba506104a4f17de  quine.old-taylor.pgp
1eed41e4b93b23797a8b46a7ef9e34f330c905fd082bfddf9fcb918a76d08b66  quine.rnp.pgp
78cb0cafcfa463f559de50eff6fa68898967e421a6fdb904b780602d864209ba  quine.sequoia.pgp
% ls -l quine*pgp
-rw-r--r-- 1 teythoon teythoon 182 Oct  1  2013 quine.old-taylor.pgp
-rw-r--r-- 1 teythoon teythoon 180 Aug  6 10:23 quine.rnp.pgp
-rw-r--r-- 1 teythoon teythoon 182 Aug  6 11:56 quine.sequoia.pgp

While working on our parser, I noticed that Taylor's original quine had a bug: The framing information was off. This is the patch I sent him, which he applied to the quine generator's source, but he didn't regenerate the quine:

diff --git a/quine.c b/quine.c
index 41431f3..bb2bd41 100644
--- a/quine.c
+++ b/quine.c
@@ -300,7 +300,7 @@ main(const int argc, char **const argv)
 {
    const uint8_t head[] = {
        0xa0,           /* pkt hdr, old fmt, compressed, 1-octet len */
-           0xb0,           /* length: 176 octets */
+         0xb4,               /* length: 180 octets */
        0x01,           /* compression alg: raw DEFLATE */
    };
    const size_t n_head = sizeof(head);

This is what happens if I inspect all three quines using Sequoia (disregarding any actual output, I'm only interested in errors (if any)):

% sq packet dump quine.old-taylor.pgp >/dev/null ; echo $?
Error: corrupt deflate stream
1
% sq packet dump quine.sequoia.pgp >/dev/null ; echo $?
0
% sq packet dump quine.rnp.pgp >/dev/null ; echo $?
Error: Malformed packet: Truncated packet
1

You can see the framing error in the original quine, our fixed version, and your version seems to have some issue too. Now, I haven't investigated further, but I wanted to share this with you.

The reason that Taylor didn't notice the bug in his quine is that GnuPG, for example, doesn't correctly enforce the packet boundaries. So if RNP is happy with his quine, this may indicate a similar problem in RNP. Similarly, the fact that your quine is rejected by Sequoia and accepted by RNP could hint at a problem, but I haven't looked at this closely.

Taylor's quine: https://mumble.net/~campbell/misc/pgp-quine/ Our version: https://gitlab.com/sequoia-pgp/sequoia/-/raw/master/openpgp/tests/data/messages/compression-quine.gpg

[ni4]

@teythoon Yeah, I slightly modified the sample to not include the trailer. Actually, the main idea of this test is to make sure that RNP stops processing at some point on such quine.

In Sequoia - do you first process the outer compressed packet, decompressing the whole, and then process it's contents?

[teythoon]

Yeah, I slightly modified the sample to not include the trailer.

What do you mean by trailer? Also, what motivated the change?

In Sequoia - do you first process the outer compressed packet, decompressing the whole, and then process it's contents?

We do it in a streaming fashion, but logically that is exactly what we do.

[ni4]

What do you mean by trailer? Also, what motivated the change?

This one: const uint8_t tail[] = { 0 };. It was causing warning that there is data beyond the zlib stream.

We do it in a streaming fashion, but logically that is exactly what we do.

In RNP we do not read the whole zlib stream before creating the next layer object (so we have constant memory footprint, independent from the input size), this could be the reason of different behavior.