Security issue (DoS) in Crypto++ ASN1 decoder

[noloader]

We sent a copy to the mailing list at Security issue (DoS) in Crypto++ ASN1 decoder.

We asked for a CVE to be assigned on oss-security. CVE-2016-9939 was assigned to the issue.

On Mon, Dec 12, 2016 at 8:45 AM, Gergely Nagy ngg@tresorit.com wrote:

Hi!

I have found a bug in several BERDecode* functions which could be used for a
DoS attack.

The issue is similar to CVE-2016-2109 in OpenSSL which was disclosed in
https://www.openssl.org/news/secadv/20160503.txt

Basically after the ASN1 decoder reads the length, it allocates a
SecByteBlock of that size before checking that there is enough data
available.

This can cause memory exhaustion on most platforms, but it has (in my
opinion) the worst effect on 64-bit Linux systems where the allocation
will succeed for huge sizes and then a BERDecodeError exception will be
thrown that causes the destructor of the SecByteBlock to be called,
which can hang the CPU for a really long time zeroing out memory.

I have attached a patch (for the current master branch) that fixes this
behavior in both versions of BERDecodeOctetString, BERDecodeTextString,
BERDecodeBitString and BERDecodeUnsigned. I am not 100% sure that there are
no other places in the code with the same issue.

I don't know how you want to disclose this issue, but if you want to assign
a CVE number and release a new version before publicly disclosing it
then we won't deploy our fix until then.

We will binary patch our software which includes a statically linked
Crypto++ after 30 days if we don't get a proper response.

When you disclose the issue please refer to me as "Gergely Nagy (Tresorit)",
and say that the bug was found using "honggfuzz".

Thanks,

Gergely Nagy (Tresorit)

---

Here is the patch that was attached to the email.

diff --git a/asn.cpp b/asn.cpp
index 5708a2c..3e3ae81 100644
--- a/asn.cpp
+++ b/asn.cpp
@@ -124,6 +124,9 @@ size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
 
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
+
 	str.New(bc);
 	if (bc != bt.Get(str, bc))
 		BERDecodeError();
@@ -140,6 +143,9 @@ size_t BERDecodeOctetString(BufferedTransformation &bt, BufferedTransformation &
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
 
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
+
 	bt.TransferTo(str, bc);
 	return bc;
 }
@@ -162,10 +168,12 @@ size_t BERDecodeTextString(BufferedTransformation &bt, std::string &str, byte as
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
 
-	SecByteBlock temp(bc);
-	if (bc != bt.Get(temp, bc))
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
+
+	str.resize(bc);
+	if (bc != bt.Get((byte *)str.data(), bc))
 		BERDecodeError();
-	str.assign((char *)temp.begin(), bc);
 	return bc;
 }
 
@@ -189,6 +197,9 @@ size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigne
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
 
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
+
 	byte unused;
 	if (!bt.Get(unused))
 		BERDecodeError();
diff --git a/asn.h b/asn.h
index e8283f7..aff1c31 100644
--- a/asn.h
+++ b/asn.h
@@ -499,6 +499,9 @@ void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag = INTEGER,
 	if (!definite)
 		BERDecodeError();
 
+	if (bc > in.MaxRetrievable())
+		BERDecodeError();
+
 	SecByteBlock buf(bc);
 
 	if (bc != in.Get(buf, bc))

[denisbider]

This is a necessary fix. Thank you to Gergely for the submission.

Note that, in the proposed patch to BERDecodeTextString, there is not only a fix for this issue, but also a new optimization where bt.Get() is called directly on memory managed by std::string, instead of retrieving data first into SecByteBlock, and then moving it to the string.

This optimization opens a door to another possible issue. bt.Get() may fail halfway, which would result in data being partly written into memory managed by std::string before throwing a decode exception. In this occurrence, the partly written data might not get cleared, which it would have been if it was written to SecByteBlock instead.

I suggest avoiding the optimization implemented by this patch in this particular function, but otherwise adopting the fix.

[denisbider]

In addition, I believe the proposed fix to BERDecodeBitString can be improved. If bc == 0, BERDecodeBitString will call str.resize(bc-1), which will be str.resize(SIZE_MAX). This seems unlikely to succeed on any platform, but if the allocation request is passed to the OS, it could result in the program being aborted. I suggest also adding an explicit check here to prevent bc == 0.

[ngg]

Hi! I am Gergely Nagy who reported this bug.

BERDecodeTextString is called when it is requested explicitly to put the decoded data in a std::string,
I would think that someone who calls this understands that std::string does not clear memory like SecByteBlock does. However I agree that modification does not belong to this security issue.

This is my new revised suggested patch based on the comments above:

diff --git a/asn.cpp b/asn.cpp
index 5708a2c..2bd4af6 100644
--- a/asn.cpp
+++ b/asn.cpp
@@ -123,6 +123,8 @@ size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
 	size_t bc;
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
 
 	str.New(bc);
 	if (bc != bt.Get(str, bc))
@@ -139,6 +141,8 @@ size_t BERDecodeOctetString(BufferedTransformation &bt, BufferedTransformation &
 	size_t bc;
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
 
 	bt.TransferTo(str, bc);
 	return bc;
@@ -161,6 +165,8 @@ size_t BERDecodeTextString(BufferedTransformation &bt, std::string &str, byte as
 	size_t bc;
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
 
 	SecByteBlock temp(bc);
 	if (bc != bt.Get(temp, bc))
@@ -188,6 +194,10 @@ size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigne
 	size_t bc;
 	if (!BERLengthDecode(bt, bc))
 		BERDecodeError();
+	if (bc == 0)
+		BERDecodeError();
+	if (bc > bt.MaxRetrievable())
+		BERDecodeError();
 
 	byte unused;
 	if (!bt.Get(unused))
diff --git a/asn.h b/asn.h
index e8283f7..95b08bc 100644
--- a/asn.h
+++ b/asn.h
@@ -498,6 +498,8 @@ void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag = INTEGER,
 	bool definite = BERLengthDecode(in, bc);
 	if (!definite)
 		BERDecodeError();
+	if (bc > in.MaxRetrievable())
+		BERDecodeError();
 
 	SecByteBlock buf(bc);

[ngg]

I have created a pull request #347 with the revised patch.

[noloader]

I've got some of the TestASN1Parse() function written. Two observations are surfacing if I am parsing ITU X.690 properly. (1) it looks like the issues are a little wider than the patch covers. (2) it looks like some of this is valid ASN.1 BER even though its causing a hang.

[ngg]

This simple code reproduces the issue, the maximum failing length really depends on the platform.
I tried this on x64 Linux, this will allocate and then zero out a 1GB buffer (this can be increased on my machine up to 64GB) before throwing BERDecodeErr

#include "asn.h"

using namespace CryptoPP;

int main(void)
{
    std::string data;
    StringSink sink(data);
    sink.Put(OCTET_STRING);
    DERLengthEncode(sink, 1024ULL * 1024 * 1024 * 1);
    sink.MessageEnd();

    StringSource source(data, true);
    std::string out;
    BERDecodeTextString(*source.AttachedTransformation(), out, OCTET_STRING);

    return 0;
}

[noloader]

Thanks @ngg, @denisbider.

I think I am seeing better results with the patch below. It rejects malformed BOOLEAN, OBJECT_IDENTIFIER and other types. For example "\x01\x02\xff" is a malformed BOOLEAN because it specifies a length of two octets, but only provides one content octet. The library currently accepts "\x01\x02\xff" when using a BERGeneralDecoder.

The throw is a tad bit worrisome because some of this can be valid ASN.1 BER when streaming and using indefinite length encoding. But the best I can tell, streaming is not fully supported in Crypto++'s implementation, so I think its mostly an academic concern.

Ironically, I think we reject some inputs we should accept. I need to look into it in more detail, but we don't seem to be handling constructed values properly in all cases.

Here's what the cut-in for TestASN1Parse() looks like at the moment: Crypto++ TestASN1Parse() test cases. It needs to be filled-out with more tests.

---

$ git diff asn.cpp > asn.diff
riemann:cryptopp$ cat asn.diff 
diff --git a/asn.cpp b/asn.cpp
index 297ff01..aabccfb 100644
--- a/asn.cpp
+++ b/asn.cpp
@@ -70,6 +70,10 @@ bool BERLengthDecode(BufferedTransformation &bt, lword &length, bool &definiteLe
 			length = (length << 8) | b;
 		}
 	}
+
+	if (length > bt.MaxRetrievable())
+		return false;
+
 	return true;
 }
 
@@ -81,6 +85,8 @@ bool BERLengthDecode(BufferedTransformation &bt, size_t &length)
 		BERDecodeError();
 	if (!SafeConvert(lw, length))
 		BERDecodeError();
+	if (length > bt.MaxRetrievable())
+		BERDecodeError();
 	return definiteLength;
 }

[denisbider]

@noloader: Note that the proposed fix, to check MaxRetrievable() in BERLengthDecode itself, changes the interface in a way that's potentially breaking. Currently, this is legal:

1. BERDecodeLength
2. Pump number of bytes required
3. BERDecodeWhatever

After the change to BERDecodeLength, the above will no longer work. In fact, there will be no way for the user to check what number of bytes they might need to pump, without implementing their own version of BERDecodeLength.

Gergely's proposal fixes this in a way that does not change the contract in this corner case. However, it has the slight disadvantage that the check has to be performed when decoding each structure type.

In my opinion, the time of decoding the structure is the more appropriate place to check this.

[noloader]

Thanks @denisbider.

"...After the change to BERDecodeLength, the above will no longer work. In fact, there will be no way for the user to check what number of bytes they might need to pump..."

I think this is what I am struggling with. There's a not-so-readily-apparent intersection with streaming ASN.1 objects. Stepping back, when do we support the filter interface with Pump? What do we do with BERGeneralDecoder?

[ngg]

I don't think that BERDecodeLength should check the remaining length. It can break currently working totally valid codes like the one @denisbider mentioned.

[denisbider]

@noloader - what is the problem with BERGeneralDecoder?

It means that places that use it have to check the length. Integer::BERDecode is an example consumer that seems to perform this check properly.

If you would like to avoid this, so as to reduce the number of places where this check needs to occur and can go wrong, I think it would make sense to add the length check into BERGeneralDecoder::Init.

However, I would not put this check into BERDecodeLength, simply because the act of decoding a length does not imply intent to decode everything that follows it.

[denisbider]

... However, Integer::BERDecode is not always called. For example, DL_PrivateKey_EC<EC>::BERDecodePrivateKey does this:

BERGeneralDecoder dec(seq, OCTET_STRING);
if (!dec.IsDefiniteLength())
    BERDecodeError();
Integer x;
x.Decode(dec, (size_t)dec.RemainingLength());

Then in Integer::Decode, we only have this:

assert(bt.MaxRetrievable() >= inputLen);

That's an assert, but that will be omitted in production, which means an unchecked allocation will occur in Release modes:

const size_t size = RoundupSize(BytesToWords(inputLen));
reg.CleanNew(size);

So yeah, I think it may definitely be worth it to add this check to BERGeneralDecoder::Init.

[noloader]

@denisbider, @ngg, @gcsideal,

Sorry about falling of the radar. I was a bit under the weather for about a week. Sorry about that.

We have had more time to think about things, and I think we have two different problems. The first problem is @ngg's initial finding, and I think the analysis and revised patch is correct. I'm going to get it checked in with some test cases shortly.

I think the BERGeneralDecoder case is different than @ngg's initial finding. Where's @ngg's finding handled the imperative "fully parse it now" case, BERGeneralDecoder appears to be a more general case. In the BERGeneralDecoder case, we won't know there's a problem until MessageEnd is called.

The BERGeneralDecoder case appears to beg for something along the lines of reserve/resize from the SecBlock. It will allow the SecBlock to measure the high water mark, and only zeroize what has been used.

I need to write some test code to see what feels right or works best for BERGeneralDecoder. Wei provided us with a ByteQueue that can add storage/nodes on the fly. Or maybe a new type of SecBlock with specialized behavior to track size and capacity is a better fit.

[noloader]

Here's a small test program that streams data into the decoder. Its a bit contrived because of the INTEGER. In practice the library uses the outer decoder to remove BIT_STRING and OCTET_STRING.

#include "asn.h"
#include "queue.h"
#include <iostream>
using namespace CryptoPP;

int main(int argc, char* argv[])
{
	ByteQueue queue;
	queue.Put((const byte*)"\x02\x0f" "CC", 4);
	std::cout << "MaxRetrievable: " << queue.MaxRetrievable() << std::endl;
	
	BERGeneralDecoder decoder(queue, INTEGER);
	std::cout << "MaxRetrievable: " << queue.MaxRetrievable() << std::endl;
	
	queue.Put((const byte*)"CCCCCCCCCCCCC", 13);
	std::cout << "MaxRetrievable: " << queue.MaxRetrievable() << std::endl;
	decoder.Skip(15);  // pretend the value is consumed
	
	std::cout << "MaxRetrievable: " << queue.MaxRetrievable() << std::endl;
	decoder.MessageEnd();

	return 0;
}

And:

$  ./test.exe
MaxRetrievable: 4
MaxRetrievable: 2
MaxRetrievable: 15
MaxRetrievable: 0

[noloader]

Cleared at Crypto++ 6.0 release.