1636771 - (CVE-2020-12403) CHACHA20-POLY1305 decryption with undersized tag leads to out-of-bounds read

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Guido Vranken]

Attachment: chacha20_oob_read.cpp

User Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:76.0) Gecko/20100101 Firefox/76.0

Steps to reproduce:

Recent NSS checkout compiled on 64 bit Linux using:

./build.sh --clang --enable-fips --static --asan --disable-tests --fuzz=oss

Then compile and run the attached C++ file.

Actual results:

out-of-bounds read

=================================================================
==20341==ERROR: AddressSanitizer: global-buffer-overflow on address 0x00000085a697 at pc 0x00000063ca9c bp 0x7ffdb7d48510 sp 0x7ffdb7d48508
READ of size 1 at 0x00000085a697 thread T0
#0 0x63ca9b in Hacl_Chacha20Poly1305_256_aead_decrypt /mnt/2tb/cf-nss/sandbox/nss/out/Debug/../../lib/freebl/verified/Hacl_Chacha20Poly1305_256.c:1167:64
#1 0x58fedf in ChaCha20Poly1305_Open /mnt/2tb/cf-nss/sandbox/nss/out/Debug/../../lib/freebl/chacha20poly1305.c:267:19
#2 0x7ef031 in sftk_ChaCha20Poly1305_Decrypt /mnt/2tb/cf-nss/sandbox/nss/out/Debug/../../lib/softoken/pkcs11c.c:705:12
#3 0x7f1383 in NSC_Decrypt /mnt/2tb/cf-nss/sandbox/nss/out/Debug/../../lib/softoken/pkcs11c.c:1813:10
#4 0x6eadfd in PK11_Decrypt /mnt/2tb/cf-nss/sandbox/nss/out/Debug/../../lib/pk11wrap/pk11obj.c:933:11
#5 0x5192a8 in main /mnt/2tb/cf-nss/cryptofuzz/modules/nss/poc.cpp:46:5
#6 0x7f503c413b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310
#7 0x41c6e9 in _start (/mnt/2tb/cf-nss/cryptofuzz/modules/nss/poc+0x41c6e9)

I have not yet checked if Firefox via TLS or WebCrypt might be affected.

Expected results:

no memory violations

Comment 1

[Guido Vranken]

More CHACHA20-POLY1305 bugs:

Incorrect encryption/decryption

These input parameters to the encrypt operation:

cleartext: {0x0c, 0x00, 0x00, 0xe9, 0xff, 0x11, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0xf1, 0x00, 0x00, 0x00,
0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0xff, 0xf7, 0xf7} (44 bytes)
aad: nullopt
cipher iv: {0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0x04, 0x00, 0x00, 0x00, 0x80, 0x00, 0x20, 0x00, 0x00, 0x00} (16 bytes)
cipher key: {0x00, 0x00, 0x00, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, 0xfe, 0x91, 0x3b, 0x43, 0x98, 0xea, 0x25,
0x19, 0x79, 0x00, 0x02, 0x01, 0x00, 0x16, 0x00, 0xc7, 0xea, 0x00, 0x00, 0x80, 0x00, 0x08, 0x1c} (32 bytes)
cipher: CHACHA20

lead to this ciphertext:

Ciphertext: {0xb8, 0x26, 0x20, 0xec, 0x5d, 0xbb, 0x82, 0xa0, 0xc2, 0x69, 0xa1, 0xa4, 0x2f, 0x87, 0x8c, 0xb1,
0x59, 0x17, 0x15, 0xa3, 0x96, 0xf9, 0x94, 0x26, 0x20, 0x05, 0xa2, 0xaa, 0x82, 0xa0, 0xc2, 0x69,
0xa1, 0x9e, 0xde, 0x78, 0x73, 0x4e, 0xa6, 0x17, 0x35, 0x5c, 0x61, 0x0e} (44 bytes)

and after decryption:

Purported cleartext: {0x0c, 0x00, 0x00, 0xe9, 0xff, 0x11, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3a, 0xf1, 0x00, 0x00, 0x00,
0x00, 0x00, 0x20, 0x00, 0x00, 0x00, 0x51, 0x10, 0xda, 0xe0, 0xf9, 0xe5, 0x87, 0x0e, 0x06, 0xdd,
0x83, 0x1c, 0x35, 0xbb, 0x8f, 0x22, 0x0c, 0x7b, 0xfb, 0x4c, 0xe1, 0xbd} (44 bytes)

Unexpected output size

Input parameters:

cleartext: {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x04, 0x00, 0x00, 0x00, 0x87, 0x2a, 0x00, 0x9b,
0x9b, 0x00, 0x04, 0x00, 0xf0, 0x19, 0x8b, 0xf4, 0xd7, 0x59, 0x01, 0x1f, 0x01, 0xa8, 0x11, 0x65,
0x72, 0x22, 0xd9, 0x83, 0xcf, 0x61, 0x7f, 0xe1, 0x1b, 0xe9, 0x72, 0x20, 0x1f, 0xc6, 0x6b, 0xd8,
0x70, 0xf9, 0xb4, 0xaf, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x00, 0x00, 0xe0, 0xfa, 0xf7, 0xd1, 0xb2,
0xff, 0x00, 0x20, 0x33, 0x00, 0x23, 0x04, 0x20, 0xf3, 0xfb, 0xf5, 0xeb, 0x5a, 0x2b, 0x4a, 0x50,
0xfd, 0x26, 0xb2, 0x00, 0xe7, 0x00, 0x00, 0x64, 0x3a, 0x57, 0xb8, 0x03, 0x00, 0x2b, 0x00, 0x00,
0xce, 0x00, 0x40, 0x71, 0x04, 0x64, 0xa3, 0x49, 0xa7, 0x57, 0x01, 0x1f, 0x01, 0xa8, 0x11, 0x65,
0x72, 0x22, 0xb1, 0xe2, 0xc6, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20} (125 bytes)
aad: nullopt
cipher iv: {0x00, 0x2b, 0x08, 0x2e, 0x74, 0x00, 0xfd, 0x57, 0x30, 0x20, 0x23, 0x04} (12 bytes)
cipher key: {0x00, 0x20, 0xe5, 0x3f, 0xbd, 0x3a, 0x00, 0x03, 0xb8, 0x00, 0x2b, 0x98, 0x00, 0x30, 0x00, 0x00,
0x00, 0x00, 0x01, 0xff, 0xff, 0xb4, 0x00, 0x5f, 0x32, 0x34, 0x00, 0xc3, 0x00, 0x00, 0x00, 0x00} (32 bytes)
cipher: CHACHA20_POLY1305
tagSize: 1

This should produce an output of 125 (cleartext size) + 1 (desired tag size), but the output is 133 bytes.

This is OSS-Fuzz/Cryptofuzz bug https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=22146

Comment 2

[Guido Vranken]

Apologies, the first bug in my previous message is CHACHA20, not CHACHA20_POLY1305.

Comment 3

[Guido Vranken]

Attachment: poc oob write

```

Comment 4

[Guido Vranken]

Previous message is an OOB write with chacha20-poly1305.

Comment 5

[J.C. Jones [:jcj] (he/him)]

This is very interesting, this appears to be within the verified code.

Comment 6

[Emma Humphries ☕️🎸🧞‍♀️✨ (she/they) [:emceeaich] (Pacific Time) use needinfo]

This bug is part of a group of bugs in a security or private group which have the old default Severity of normal which has not been changed, and the default priority of --. This indicates that this bugs Severity should be set to -- so it will show up in triage lists.

Comment 7

[Emma Humphries ☕️🎸🧞‍♀️✨ (she/they) [:emceeaich] (Pacific Time) use needinfo]

Trying to set that severity again.

Comment 8

[Benjamin Beurdouche [:beurdouche]]

Attachment: Bug 1636771 - Fix incorrect call to Chacha20Poly1305 by PKCS11. r=jcj,kjacobs

Comment 9

[Benjamin Beurdouche [:beurdouche]]

(In reply to J.C. Jones [:jcj] (he/him) [increased latency due to COVID-19] from comment #5)

This is very interesting, this appears to be within the verified code.

Nope, it is in the caller. At first glance, Chacha20Poly1305 has 16 bytes tags and for some reason the caller
was allowed to ask for a variable length tag !(tagLen == 0 || tagLen > 16) following the PK11 interface.

It seems that freebl is affected but TLS should not have called that code with tagLen =! 16
My first look seem to indicate that it is not the case but this needs to be confirmed.

For softoken, sftk_CryptInit is setting tagLen to 16...
https://searchfox.org/mozilla-central/source/security/nss/lib/softoken/pkcs11c.c#1229
https://searchfox.org/mozilla-central/source/security/nss/lib/softoken/pkcs11c.c#1244
WebCrypto seem unaffected as it doesn't provide Chacha20Poly1305.

Comment 10

[Benjamin Beurdouche [:beurdouche]]

Hi Guido !
Thanks for the report, I believe I can confirm the second one, but I couldn't reproduce the first one.

Chacha20 from HACL* specification, code, and OpenSSL compute a close but different ciphertext than what you
reported above, namely: b82620ec5dbb82a0c269a1a42f878cb1591715a396f9e536fae55b4f05aec4b42282eb3c0393556cceef7744
they also can perform decrypt(encrypt(x)) = x successfully with the above key, nonce, plaintext.

Could you confirm the inputs/outputs above, the code path, and from which implementation the
expected ciphertext was generated?
Also could you add bbeurdouche, kjacobs, tvandermerwe, and jcj to the OSS report if possible ? : )

Thanks a lot !

Comment 11

[Guido Vranken]

Attachment: chacha20_streaming_discrepancy.cpp

Comment 12

[Guido Vranken]

The problem appears to be in the streaming/multi-part API. Compile the file I just uploaded with and without -DMULTIPART to see the difference in output.

Kevin is already receiving reports from OSS-Fuzz. I can add the others if I you give me e-mail addresses linked to a Google account. Because my fuzzer is a differential fuzzer (comparing outputs across libraries with the same inputs), and OSS-Fuzz cannot determine itself which library has a bug, you will also receive occasional reports on bugs in other libraries.

Comment 13

[J.C. Jones [:jcj] (he/him)]

There are a couple of bugs here, but we'll probably want to land their fixes in a single commit.

With the information I have at-hand, I believe this is a sec-moderate for NSS, as control of the cipherstreams for ChaCha can provide a useful memory widget. However, since this is difficult to get to from Firefox, I think it is sec-low for Firefox's purposes.

Dan, please allocate a CVE.

I've assigned this to Ben. Ben, please file a follow-on security bug linked to this one for the tests. We'll treat this as a sec-moderate and land the tests around the disclosure date.

Comment 14

[Daniel Veditz [:dveditz]]

Assigned CVE-2020-12403 to this issue.

I've set the in-testsuite? flag which you can use as a reminder to land the tests later or file a follow-up bug.

Comment 15

[BugBot [:suhaib / :marco/ :calixte]]

The severity field is not set for this bug.
:jcj, could you have a look please?

For more information, please visit auto_nag documentation.

Comment 16

[J.C. Jones [:jcj] (he/him)]

Also raised at OSS-Fuzz:
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=23934

Detailed Report: https://oss-fuzz.com/testcase?key=5091247321251840

Comment 17

[Benjamin Beurdouche [:beurdouche]]

The submitted patch is supposed to take care of the AEAD part and the OOB read/write.

Kevin and I discussed about the issue regarding the correctness of the incremental API for Chacha20 (the "incorrect encryption/decryption" bug here) and while doing so we discovered another issue for the incremental Chacha20+Poly1305 in AEAD mode.

We think it might be ok to land the current patch now and open a separate public bug for the PK11 incremental mode issues,
would that work for you?

Comment 18

[Kevin Jacobs [:kjacobs]]

Just to clarify on the above, the issue is that the PKCS #11 spec doesn't seem to clearly define how multi-part encryption/decryption operations should work: should they buffer until they have enough input to produce an output (e.g. >= one block), or should operations be rejected when the inputs are too short (CKR_BUFFER_TOO_SMALL is hinted at)? NSS currently does neither, at least in the ChaCha20/+Poly1305 case.

Comment 19

[Robert Relyea]

So NSS doesn't implement Multipart/incremental AEAD. Each call to C_EncryptMessage() shouldl be a complete block, so an error should return if it's not big enough. C_EncryptMessageBegin() and C_EncryptMessageNext() are the multipart operations.

In AEAD each 'chunk' must have the tag. C_EncryptMessage() deals with a single chunk. Each call returns the tag and iv (in AES_GCM) in the parameters. The others deal with the chunk piecemeal. So if there is any message limit for AEAD, then C_EncryptMessage() should enforce the limit and fail.

I think the question, though is what to do if the target buffer is too small. We should return CKR_BUFFER_TOO_SMALL and have the caller retry the full operation. NOTE: the tag isn't part of the target buffer, so the buffer length should be equal to or greater than the length of the input buffer. The tag is returned in a separate buffer for AEAD.

Is there a real usecase for incremental/multipart AEAD? S/MIME was brought up as potentially needing it, which is why it's in the spec, but in practice it's pretty much of a stretch to use AEAD for such an operation. AEAD is better for streaming than block operations.

bob

Comment 20

[Kevin Jacobs [:kjacobs]]

For the code in question (attached in chacha20_streaming_discrepancy.cpp), the function that gets called is C_EncryptUpdate, but this applies equally to C_DecryptUpdate. This is ChaCha20 without Poly1305, so when calling with less than one block of input we can truncate the ciphertext, but then the results obviously won't match the single-shot encryption if called more than once as part of a larger message (because the key stream changes where otherwise it wouldn't). I imagine AES-CTR would have the same issue.

Your response is helpful, thanks. Is it safe to assume that each C_Encrypt/DecryptUpdate call is also a single chunk, i.e. it's the application responsibility to know whether to call the operation with an input shorter than the underlying block size?

Comment 21

[Robert Relyea]

OK, I'm a little confused. ChaCha20 (and AES-CTR for that matter) are stream ciphers. How does 'blocks' com into play? Is the ChaCha20 stream generator not buffering the intermediate stream results?

For straight block ciphers, pkcs #11 does require that the results be buffered but that the full data length must be a multiple of the blocksize by the time finalize is called (finalize with a partial unencrypted/undecrypted block in the buffer will return an error). Softoken, however requires each operation to be a multiple of block size. That's been a long standing issue, If we want to fix that it should be done in the pkcs11c.c layer so all block functions benefit.

Upshot: ChaCha20 (not the AEAD ChaCha20/Poly) is a stream cipher, and multipart is supported, and should work with any size input returning the same number of bytes in return. If it uses a block cipher under the covers to create the stream, that stream should be buffered for the next input, so we probably should fix that issue. (I think that's why you aren't seeing much about the underlying block size... because the cipher isn't supposed to have an underlying block size).

bob

Comment 22

[Robert Relyea]

If you look at the code in ctr.c (which is a generic counter implementation that can be used by any base cipher, and is used by AES), in CTR_Update, you'll see we have a buffer callled buffer (next but to use is buffer[bufPtr]). This holds the stream blocks from the previous call. They are applied to the input first before we generate any new stream values. Then we generate the full block of the stream for the next batch until we reach the last partial block. At that point we generate one last stream, put it in the buffer, encrypt the partial block and then mark where we are in the buffer for the next call to update.

I looks like we got our chacha20 implementation from somewhere else, so it's not using our ctr.c code. We can fix this either by fixing the chacha20 implementation directly, or having it use our ctr.c code (assuming it uses the same endianness for the counter as our current ctr.c code. We don't need to mess with the version that chacha20/poly uses currently becase we don't support multipart in AEAD.

Comment 23

[Benjamin Beurdouche [:beurdouche]]

Ok, since the incremental chacha20 part is only a correctness issue and not really a security issue, would you be ok if we open a separate public bug about it? That would allow Kevin to land the patch which is currently attached and fixes the OOBs and the size of the Poly tag.

Comment 24

[Robert Relyea]

So I just checked and our chacha20 implementation doesn't support multipart at all. It only support single shot. We only specify the counter at init time. If we want to support multipart, we need to keep the counter internally and advance it as needed. For now we should set context->multi = PR_FALSE in the CKM_CHACHA20 section. Once we fix the code we can turn it back on.

Right now each call to EncryptUpdate() will produce a second block with the same key and counter. This is not secure at all (It's trival to recover the stream when you do this). So let's at least set context->multi = PR_FALSE so we don't have any code that is generating insecure output. We can then fix multipart later (Note: that means chacah20_streaming_discrepency.cpp will fail because XXXUpdate will now return an error, but that is better than returning data that could compromise your previously encrypted data).

Comment 25

[Benjamin Beurdouche [:beurdouche]]

Attachment: Bug 1636771 - Disable PKCS11 incremental mode for ChaCha20. r=kjacobs,rrelyea

Depends on D74801

Comment 26

[Benjamin Beurdouche [:beurdouche]]

I agree that it is a good idea to disable the mechanism until we decide to fix it, so I attached a second patch to do this.

Comment 27

[Kevin Jacobs [:kjacobs]]

https://hg.mozilla.org/projects/nss/rev/a5e82e40f03e24941e5890fbb0056ee90c0a4026
https://hg.mozilla.org/projects/nss/rev/615362dff5adcec579cc769e3ad0dbfe29d2a86f

Comment 28

[J.C. Jones [:jcj] (he/him)]

I'm planning to uplift this bug's patches to the 3.53 branch for whenever we make our next build of NSS destined for ESR 78.

Comment 29

[Guido Vranken]

A bounty for this would be nice.. Not a lot of people are actively testing this stuff.

Comment 30

[J.C. Jones [:jcj] (he/him)]

NSS_3_53_BRANCH
https://hg.mozilla.org/projects/nss/rev/f282556e6cc7715f5754aeaadda6f902590e7e38
https://hg.mozilla.org/projects/nss/rev/c25adfdfab34ddb08d3262aac3242e3399de1095

Comment 31

[Tom Ritter [:tjr] (OOTO until 4/30 at least)]

Attachment: advisory.txt

Advisory attached. Unclear to me how the OOB read data was disclosed (was it directly in the plaintext? passed through decryption so you could reverse it if the key was known?) so I left it ambiguous.