BUFFER OVERFLOW IN RSAREF2

Advisory ID: CORE-120199

CVE Name: CVE-1999-0834

Bugtraq ID: 843

While researching the exploitability of a buffer overflow in SSH up to version 1.2.27, we discovered a second buffer overflow in the implmementation of the RSA algorithm in RSAREF2 from RSA Data Security.

This advisory addresses the details of the bug discovered, the details are somewhat focused on the ability to exploit the bug in SSH compiled with RSAREF2, but its extensible to any software product that uses RSAREF2

**Problem description**RSAREF2 API exports 4 functions in rsa.c:

int RSAPublicEncrypt()

int RSAPrivateEncrypt()

int RSAPublicDecrypt()

int RSAPrivateDecrypt()

The 4 functions define a local variable pkcsBlock of fixed length

MAX_RSA_MODULUS_LEN (128 bytes)

In order to perform the RSA operations, the functions call the internal functions RSAPrivateBlock() and RSAPublicBlock(). RSAPrivateDecrypt() and RSAPublicDecrypt() pass a pointer to the local variable pkcsBlock to be used as the output buffer for RSAPublicBlock() and RSAPrivateBlock() respectively. The two functions then perform the RSA operations and copy the results to the output buffer using the NN_Encode() and NN_Decode() functions.

Lack of strict bounds checking and proper validation of input parameters in all these functions allows an attacker to overflow the pkcsBLock variable and overwrite the stack, making it possible to execute arbitrary commands on the vulnerable system.

**Technical details**As an axample we will describe the vulnerability focusing on the decrypt operations performed in RSAREF2 based on the private key. Such operations are done with the function RSAPrivateDecrypt() defined as follows in rsa.c:

/* RSA private-key decryption, according to PKCS #1.

*/

int RSAPrivateDecrypt (output, outputLen, input, inputLen, privateKey)

unsigned char *output; /* output

block */

unsigned int *outputLen; /* length of output

block */

unsigned char *input; /* input

block */

unsigned int inputLen; /* length of input

block */

R_RSA_PRIVATE_KEY *privateKey; /* RSA private

key */

{

int status;

unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];

unsigned int i, modulusLen, pkcsBlockLen;

modulusLen = (privateKey->bits + 7) / 8;

if (inputLen > modulusLen)

return (RE_LEN);

if (status = RSAPrivateBlock

(pkcsBlock, &pkcsBlockLen, input, inputLen, privateKey))

return (status);

...

return (0);

}

Note that inputLen is checked against a transformation of privateKey's bits field, to satisfy this constrain an attacker must alter this field in privateKey, but this, almost by miracle doesn't affect the final result.

As we can see, RSAPrivateDecrypt() calls RSAPrivateBlock() passing pkcsBlock as the output buffer, no length checking is performed to ensure that pkcsBlock will not be overrun. RSAPrivateBLock() performs the RSA private key operations ans is define as follows:

/* Raw RSA private-key operation. Output has same length as modulus.

Assumes inputLen < length of modulus.

Requires input < modulus.

*/

static int RSAPrivateBlock (output, outputLen, input, inputLen,

privateKey)

unsigned char *output; /* output

block */

unsigned int *outputLen; /* length of output

block */

unsigned char *input; /* input

block */

unsigned int inputLen; /* length of input

block */

R_RSA_PRIVATE_KEY *privateKey; /* RSA private

key */

{

NN_DIGIT c[MAX_NN_DIGITS], cP[MAX_NN_DIGITS], cQ[MAX_NN_DIGITS],

dP[MAX_NN_DIGITS], dQ[MAX_NN_DIGITS], mP[MAX_NN_DIGITS],

mQ[MAX_NN_DIGITS], n[MAX_NN_DIGITS], p[MAX_NN_DIGITS],

q[MAX_NN_DIGITS],

qInv[MAX_NN_DIGITS], t[MAX_NN_DIGITS];

unsigned int cDigits, nDigits, pDigits;

NN_Decode (c, MAX_NN_DIGITS, input, inputLen);

...

cDigits = NN_Digits (c, MAX_NN_DIGITS);

nDigits = NN_Digits (n, MAX_NN_DIGITS);

pDigits = NN_Digits (p, MAX_NN_DIGITS);

/* Compute mP = cP^dP mod p and mQ = cQ^dQ mod q. (Assumes q has

length at most pDigits, i.e., p > q.)

*/

...

/* Chinese Remainder Theorem:

m = ((((mP - mQ) mod p) * qInv) mod p) * q + mQ.

*/

if (NN_Cmp (mP, mQ, pDigits) >= 0)

NN_Sub (t, mP, mQ, pDigits);

else {

NN_Sub (t, mQ, mP, pDigits);

NN_Sub (t, p, t, pDigits);

}

NN_ModMult (t, t, qInv, p, pDigits);

NN_Mult (t, t, q, pDigits);

NN_Add (t, t, mQ, nDigits);

*outputLen = (privateKey->bits + 7) / 8;

NN_Encode (output, *outputLen, t, nDigits);

...

return (0);

}

RSAPrivateBlock() calls NN_Encode() to encode and copy the results into the output buffer (a pointer to the pkcsBlock variable in RSAPublicDecrypt() function), the length of the output buffer is calculated based on the bits field of the pivateKey structure, passed originally to RSAPublicDecrypt() and does not take into account the fixed length characteristics of the output buffer.

The NN_Encode() function is defined as follows:

/* Encodes b into character string a, where character string is ordered from most to least significant.

Lengths: a[len], b[digits].

Assumes NN_Bits (b, digits) <= 8 * len.

(Otherwise most significant digits are truncated.)

*/

void NN_Encode (a, len, b, digits)

NN_DIGIT *b;

unsigned char *a;

unsigned int digits, len;

{

NN_DIGIT t;

int j;

unsigned int i, u;

for (i = 0, j = len - 1; i < digits && j >= 0; i++) {

t = b[i];

for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)

a[j] = (unsigned char)(t >> u);

}

for (; j >= 0; j--)

a[j] = 0;

}

NN_Encode() encodes and copies to 'a' (the output buffer, pkcsBLock) 'digits' bytes of 'b' (the results of the RSA private key operation) from the end to the start of the buffer, starting at position 'len', the modulus length of the private key passed to RSAPrivateDecrypt().

Providing a suitable modulus length to RSAPrivateDecrypt() it is possible to force NN_Encode() to copy data beyond the bounds of pkcsBLock and overwrite the return address of RSAPRivateDecrypt(), gaining control of the processor and being able to execute code located elsewhere in the vulnerable program.

The exploitability of this bug in SSH comes from the fact that a bug in SSH itself <http://www.securityfocus.com/vdb/bottom.html?vid=797> discussed and published in the vuln-dev and bugtraq mailing lists, allows a remote client to provide a suitable private key to the RSAREF functions.

The same problem is present in the RSAPublicDecrypt() function, and its exploitability might be even easier, since its much easier to provide a malicious public key to any software package that supports RSA and uses the RSAREF2 implementation.

**Impact**It is possible to execute arbitrary commands as the user that runs the RSAREF2 code.

For SSH up to 1.2.27 compiled with RSAREF2 this implies the remote execution of arbitrary commands as root.

**Fix information**RSA Security was contacted and replied that they don't support RSAREF2 anymore.

For futher details you may contact John Linn

A patch is provided below, please read carefully the file license.txt from the RSAREF2 distribution before applying it.

**Vulnerable systems**- - SSH up to 1.2.27 compiled with RSAREF2 (RSAREF is not compiled in by default but it's required in some cases in USA)

- - Possibly any other software packages that uses RSAREF2

Additional information

This vulnerability was discovered by Alberto Soliño and Gerardo Richarte at Core SDI S.A.

**Copyright Notice:**The contents of this advisory are copyright (c) 1999 CORE SDI S.A. and may be distributed freely provided that no fee is charged for this distribution and proper credit is given.

**Fix**Copy de remining of this message to a file named rsaref.patch in rsaref2/source, and apply with 'patch <rsaref.patch'

*** rsa.original.c Fri Mar 25 14:01:48 1994

--- rsa.c Fri Dec 10 12:56:34 1999

***************

*** 33,38 ****

--- 33,41 ----

unsigned char byte, pkcsBlock[MAX_RSA_MODULUS_LEN];

unsigned int i, modulusLen;

+ if (publicKey->bits > MAX_RSA_MODULUS_BITS)

+ return (RE_LEN);

+

modulusLen = (publicKey->bits + 7) / 8;

if (inputLen + 11 > modulusLen)

return (RE_LEN);

***************

*** 78,83 ****

--- 81,89 ----

unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];

unsigned int i, modulusLen, pkcsBlockLen;

+ if (publicKey->bits > MAX_RSA_MODULUS_BITS)

+ return (RE_LEN);

+

modulusLen = (publicKey->bits + 7) / 8;

if (inputLen > modulusLen)

return (RE_LEN);

***************

*** 128,133 ****

--- 134,142 ----

int status;

unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];

unsigned int i, modulusLen;

+

+ if (privateKey->bits > MAX_RSA_MODULUS_BITS)

+ return (RE_LEN);

modulusLen = (privateKey->bits + 7) / 8;

if (inputLen + 11 > modulusLen)

***************

*** 168,173 ****

--- 177,185 ----

unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];

unsigned int i, modulusLen, pkcsBlockLen;

+ if (privateKey->bits > MAX_RSA_MODULUS_BITS)

+ return (RE_LEN);

+

modulusLen = (privateKey->bits + 7) / 8;

if (inputLen > modulusLen)

return (RE_LEN);