287654 - NSC_Encrypt with RSA mechanism crashes if len is greater than modulus len

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Julien Pierre]

I tried to encrypt 140 bytes of data with PK11_PubEncryptRaw . The public key
was 1024 bits. The input and output buffers were both more than large enough
(1024 bytes). This resulted in a crash in the softoken, in rsawrapr.c, in
rsa_FormatBlock .

I used the access checking feature of dbx to identify the problem. See log
below. The issue is that the lower lovel code apparently uses an intermediate
buffer for the encryption, which is only 128 bytes. Then it does a memcpy of the
size of the entire input buffer, which is bigger .

RTC: Enabling Error Checking...
RTC: Running program...
Write to unallocated (wua) on thread 1:
Attempting to write 1 byte at address 0x4aa81c
    which is 12 bytes past end of heap block of size 128 bytes at 0x4aa790
This block was allocated from:
        [1] PR_Malloc() at line 436 in "prmem.c"
        [2] PORT_Alloc() at line 113 in "secport.c"
        [3] SECITEM_ArenaDupItem() at line 210 in "secitem.c"
        [4] SECITEM_DupItem() at line 186 in "secitem.c"
        [5] pk11_addTokenKeyByHandle() at line 2052 in "pkcs11u.c"
        [6] pk11_mkHandle() at line 2930 in "pkcs11u.c"
        [7] pk11_key_collect() at line 4093 in "pkcs11.c"
        [8] nsslowkey_TraverseKeys() at line 439 in "keydb.c"

t@1 (l@1) stopped in rsa_FormatBlock at line 421 in file "rsawrapr.c"
  421          
PORT_Memcpy(result->data+(modulusLen-data->len),data->data,data->len);
(dbx) p data->len
data->len = 140U
(dbx) where     
current thread: t@1
=>[1] rsa_FormatBlock(result = 0xffbfe0f8, modulusLen = 128U, blockType =
RSA_BlockRaw, data = 0xffbfe0ec), line 421 in "rsawrapr.c"
  [2] RSA_EncryptRaw(key = 0x4b2728, output = 0xffbfe3a8 "\xff\xbf\xe4",
output_len = 0xffbfe198, max_output_len = 128U, input = 0xffbfe7a8
"^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A"
..., input_len = 140U), line 827 in "rsawrapr.c"
  [3] NSC_Encrypt(hSession = 4U, pData = 0xffbfe7a8
"^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A"
..., ulDataLen = 140U, pEncryptedData = 0xffbfe3a8 "\xff\xbf\xe4",
pulEncryptedDataLen = 0xffbfe218), line 889 in "pkcs11c.c"
  [4] pk11_PubEncryptRaw(key = 0x4b1ef8, enc = 0xffbfe3a8 "\xff\xbf\xe4", data =
0xffbfe7a8
"^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A"
..., dataLen = 140U, mech = 0xffbfe290, wincx = (nil)), line 824 in "pk11obj.c"
  [5] PK11_PubEncryptRaw(key = 0x4b1ef8, enc = 0xffbfe3a8 "\xff\xbf\xe4", data =
0xffbfe7a8
"^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A"
..., dataLen = 140U, wincx = (nil)), line 840 in "pk11obj.c"
  [6] PK11_PublicKeyOp(key = 0x4b1ef8, output = 0xffbfe3a8 "\xff\xbf\xe4", input
= 0xffbfe7a8
"^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A^A"
...), line 240 in "rsaperf.c"
  [7] main(argc = 8, argv = 0xffbfec64), line 427 in "rsaperf.c"
(dbx)

Comment 1

[Julien Pierre]

Attachment: don't try to copy data outside output buffer boundaries

Comment 2

[Julien Pierre]

Comment on attachment 178545 [details] [diff] [review]
don't try to copy data outside output buffer boundaries

This patch fixes the crash (buffer overflow).

However, I'm not sure if it is correct thing to do.

In this case, the caller of PK11_PubEncryptRaw isn't notified that not all the
data was encrypted. That function only returns a SECStatus, and I feel it
should return SECFailure in this case. How that should actually accomplished in
the various layers in between, I'm not certain. Bob ?

Comment 3

[Robert Relyea]

PK11_PubEncryptRaw should fail if we try to encrypt more then modulus bytes.
The failure should come from NSC_Encrypt, which should get it from blapi.

This behavior for NSC_Encrypt is defined by PKCS #11. Encrypt PKCS should also
fail if the block is greater than the modulus - the minimum header (there's an
assert in the RSA code for this). It's OK to put the check in RSA OP since
NSC_Decrypt, NSC_Sign, NSC_Verify, and NSC_VerifyRecover should all fail the
same way for RSA operations.

bob

Comment 4

[Julien Pierre]

Comment on attachment 178545 [details] [diff] [review]
don't try to copy data outside output buffer boundaries

Marking patch obsolete

Comment 5

[Julien Pierre]

Attachment: check modulus length for RSA raw encrypt case

Comment 6

[Julien Pierre]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

Bob, Nelson, please review this very short patch. Thanks !

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

>+	if (data->len > modulusLen ) {
>+	    return SECFailure;
>+	}

This test suffices to prevent a crash, but still allows SOME invalid data
to be processed.  Specifically, the input data must be numerically less
than the modulus.  This is always true when the input data is shorter 
than the modulus.  When the input data and modulus are of equal length,
memcmp can be used to compare them, and determine if the input is less
than the modulus.  

I guess we have to decide whether the purpose of the test is only to 
avoid crashes, or is to ensure correctness of the operation.  If it is only
to avoid crashes, then this patch is OK.

Comment 8

[Wan-Teh Chang]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

I was going to say we should set an error code before
returning SECFailure, then I found that none of the
functions in this file sets error code...

Comment 9

[Wan-Teh Chang]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

Re: Nelson's question in comment 7, I think we should
ensure correctness of the operation.

Comment 10

[Julien Pierre]

I agree that we should ensure the correctness of the operation. I believe there
is a subsequent check in freebl for the test that Nelson talked about in comment
7 . I tripped over this in my testing of rsaperf also when I fed an
uninitialized buffer of the correct size, and the operation failed .
I can't remember if it was for encrypt or decrypt.

Looking at the code in freebl/rsa.c, I see the following code in rsa_PrivateKeyOp :

    /* check input out of range (needs to be in range [0..n-1]) */
    modLen = rsa_modulusLen(&key->modulus);
    offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
    if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
	PORT_SetError(SEC_ERROR_INVALID_ARGS);
	return SECFailure;
    }

However, I see no equivalent check in rsa_publicKeyOp, which is the encrypt
case. So, perhaps we have to do the check at the higher PKCS#11 level. But I
think that's inconsistent. Thoughts ?

Comment 11

[Julien Pierre]

Attachment: also check input value against modulus

Comment 12

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

Marking r+=nelson
I believe this patch is correct and necessary but not sufficient, as noted
above.

Comment 13

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 179314 [details] [diff] [review]
also check input value against modulus

Several problems with this patch.

In the private key code, the value comparison was done before the 
numbers were converted from canonical byte strings to mp_ints.
In this case, the numbers have already been converted to mp_ints
so the code cannot simply return here or it will leak the mp_ints.
It needs to "go to cleanup".  Also, since they are already mp_ints,
it is easier and better (and probably faster) to use the mpi 
comparison function to compare their numeric values.  

Also, if the input value is numerically too big, SEC_ERROR_INPUT_LEN 
is probably the right error code.  That goes for the previous 
patch that checked buffer length, too.

Suggested (but untested) alternative patch:

>     /* 2.  Represent message as integer in range [0..n-1] */
>     CHECK_MPI_OK( mp_read_unsigned_octets(&m, input, modLen) );
>+    /* 2 bis. check input out of range (needs to be in range [0..n-1]) */
>+    if (mp_cmp(&m, &n) >= 0)
>+        PORT_SetError(SEC_ERROR_INPUT_LEN);
>+        rv = SECFailure;
>+        goto cleanup;
>+    }

Comment 14

[Nelson Bolyard (seldom reads bugmail)]

That "alternative patch" is missing a {.  

Comment 15

[Julien Pierre]

Nelson,

Thanks for catching the leak. I looked at the code for mp_cmp, and I don't think
way it will execute faster than memcmp in most cases. I would be OK with either
check.

Comment 16

[Julien Pierre]

Attachment: correct patch

I think the attached patch will be most efficient. It checks the input value
before converting the message to mp_ints .

Comment 17

[Julien Pierre]

Comment on attachment 178872 [details] [diff] [review]
check modulus length for RSA raw encrypt case

I checked in this patch for the softoken.

Checking in rsawrapr.c;
/cvsroot/mozilla/security/nss/lib/softoken/rsawrapr.c,v  <--  rsawrapr.c
new revision: 1.8; previous revision: 1.7
done

Comment 18

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 179555 [details] [diff] [review]
correct patch

I agree this patch is correct.	I believe it is less efficient because memcmp
will load and compare each byte of each string, byte-by-byte, whereas mp_cmp
will load and compare the values word-by-word.	But this patch is correct, so I
leave it to you to decide whether to go with memcmp or mp_cmp.

Comment 19

[Julien Pierre]

Nelson,

I checked in the patch attached to the tip.

I believe the mp_cmp will be significantly more complex code due to the use of
mp_int structures and pointer indirection, whereas memcmp could be done with
just a couple instruction s(using eg. "rep cmpsb" on x86).

I actually just benchmarked the two methods briefly. I can't tell them apart,
even after running for 30 seconds. The results are within 0.5 % of each other,
one way or the other. I'm not going to spend more time on it because we aren't
concerned about RSA encrypt performance, which is on the client side.

Checking in rsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/rsa.c,v  <--  rsa.c
new revision: 1.35; previous revision: 1.34