xorl %eax, %eax

CVE-2009-4212: MIT Kerberos Multiple Integer Underflows

leave a comment »

On 12 January 2010 the MIT Kerberos Team released a new security advisory. This is about some integer underflow issues in some code of RC4 and AES encryption algorithms that can be triggered remotely. From their advisories we can read the following:

The greatest risk is from AES decryption of invalid ciphertexts, 
which can theoretically lead to arbitrary code execution under
extraordinarily unlikely conditions.  Other scenarios are more 
likely to lead to denial of service.

Here is the buggy code as seen in 1.7 release of the popular authentication software and specifically under src/lib/crypto/arcfour/arcfour.c source code file…

/* This is the arcfour-hmac decryption routine */
krb5_error_code
krb5_arcfour_decrypt(const struct krb5_enc_provider *enc,
		     const struct krb5_hash_provider *hash,
		     const krb5_keyblock *key, krb5_keyusage usage,
		     const krb5_data *ivec, const krb5_data *input,
		     krb5_data *output)
{
  krb5_keyblock k1,k2,k3;
  krb5_data d1,d2,d3,salt,ciphertext,plaintext,checksum;
  krb5_keyusage ms_usage;
  size_t keybytes, keylength, hashsize, blocksize;
  krb5_error_code ret;

  blocksize = enc->block_size;
  keybytes = enc->keybytes;
  keylength = enc->keylength;
  hashsize = hash->hashsize;

  d1.length=keybytes;
  d1.data=malloc(d1.length);
      ...
  ciphertext.length=input->length-hashsize;
  ciphertext.data=input->data+hashsize;
  plaintext.length=ciphertext.length;
  plaintext.data=malloc(plaintext.length);
  if (plaintext.data == NULL) {
      ...
  memcpy(output->data, plaintext.data+CONFOUNDERLENGTH,
	 (plaintext.length-CONFOUNDERLENGTH));
  output->length=plaintext.length-CONFOUNDERLENGTH;
      ...
  return (ret);
}

This is the function responsible for the RC4 decryption. In the above code snippet you can see that ‘ciphertext’ which is of type ‘krb5_data’ that is defined at src/include/krb5/krb5.hin like this:

typedef krb5_int32      krb5_error_code;
typedef krb5_int32      krb5_deltat;

typedef krb5_error_code krb5_magic;

typedef struct _krb5_data {
        krb5_magic magic;
        unsigned int length;
        char *data;
} krb5_data;

is initialized through the user controlled ‘input->length-hashsize’ where ‘hashsize’ is also derived from the user input as you can see a few lines above and it contains the size of the hash which is taken from the ‘krb5_hash_provider’ structure that you can see below (as seen in src/include/k5-int.h):

struct krb5_hash_provider {
    size_t hashsize, blocksize;

    /* this takes multiple inputs to avoid lots of copying. */
    krb5_error_code (*hash) (unsigned int icount, const krb5_data *input,
                             krb5_data *output);
};

Now, these user controlled values are subtracted and used to initialize the ‘ciphertext.length’ which should normally be the length of the input minus the hash. This is then assigned to ‘plaintext.length’ which is then used as a size argument to malloc(3) library routine. If the subtraction of those integers resulted in an integer underflow the result could be a small integer that would be allocated using malloc(3) but the subsequent memcpy(3) will attempt to copy ‘plaintext.length-CONFOUNDERLENGTH’ which could result in a second underflow since ‘CONFOUNDERLENGTH’ is defined like:

#define CONFOUNDERLENGTH 8

as we can find at src/lib/crypto/arcfour/arcfour-int.h and this would result in read out of bounds situation.
To fix this, the following patch was applied:

   hashsize = hash->hashsize;
 
+  /* Verify input and output lengths. */
+  if (input->length < hashsize + CONFOUNDERLENGTH)
+    return KRB5_BAD_MSIZE;
+  if (output->length < input->length - hashsize - CONFOUNDERLENGTH)
+    return KRB5_BAD_MSIZE;
+
   d1.length=keybytes;
   d1.data=malloc(d1.length);

Which checks the provided lengths before proceeding with further processing and in case of an error it will immediately return with ‘KRB5_BAD_MSIZE’ which stands for “Message size is incompatible with encryption type”.
The next issue can be found under src/lib/crypto/enc_provider/aes.c:

krb5_error_code
krb5int_aes_encrypt(const krb5_keyblock *key, const krb5_data *ivec,
		    const krb5_data *input, krb5_data *output)
{
    aes_ctx ctx;
    char tmp[BLOCK_SIZE], tmp2[BLOCK_SIZE], tmp3[BLOCK_SIZE];
    int nblocks = 0, blockno;

/*    CHECK_SIZES; */
      ...
    nblocks = (input->length + BLOCK_SIZE - 1) / BLOCK_SIZE;

    if (nblocks == 1) {
	/* XXX Used for DK function.  */
	enc(output->data, input->data, &ctx);
    } else {
	unsigned int nleft;

	for (blockno = 0; blockno < nblocks - 2; blockno++) {
      ...
	}
	/* Do final CTS step for last two blocks (the second of which
	   may or may not be incomplete).  */
	xorblock(tmp, input->data + (nblocks - 2) * BLOCK_SIZE);
      ...
	nleft = input->length - (nblocks - 1) * BLOCK_SIZE;
	memcpy(output->data + (nblocks - 1) * BLOCK_SIZE, tmp2, nleft);
      ...
	memcpy(tmp3, input->data + (nblocks - 1) * BLOCK_SIZE, nleft);
      ...
	memcpy(output->data + (nblocks - 2) * BLOCK_SIZE, tmp2, BLOCK_SIZE);
      ...
    return 0;
}

In this code, the user controlled ‘input->length’ is calculated in blocks and stored in ‘nblocks’ signed integer. This constant value is defined at lib/crypto/aes/aes.h like this:

/*  BLOCK_SIZE is in BYTES: 16, 24, 32 or undefined for aes.c and 16, 20, 
    24, 28, 32 or undefined for aespp.c.  When left undefined a slower 
    version that provides variable block length is compiled.    
*/

#define BLOCK_SIZE  16

And obviously, this could result in an integer underflow if the ‘input->length’ is less than BLOCK_SIZE. If this is the case, the subsequent operations that are shown in the code snippet will result in memory corruption. This one was fixed using the following patch:

     if (nblocks == 1) {
-	/* XXX Used for DK function.  */
+	/* Used when deriving keys. */
+	if (input->length < BLOCK_SIZE)
+	    return KRB5_BAD_MSIZE;
 	enc(output->data, input->data, &ctx);
-    } else {
+    } else if (nblocks > 1) {
 	unsigned int nleft;

That checks the provided length and it also checks its value in the ‘else’ clause.
The next vulnerability is in the same source code file, in the routine you see here:

krb5_error_code
krb5int_aes_decrypt(const krb5_keyblock *key, const krb5_data *ivec,
		    const krb5_data *input, krb5_data *output)
{
    aes_ctx ctx;
    char tmp[BLOCK_SIZE], tmp2[BLOCK_SIZE], tmp3[BLOCK_SIZE];
    int nblocks = 0, blockno;

    CHECK_SIZES;
       ...
    nblocks = (input->length + BLOCK_SIZE - 1) / BLOCK_SIZE;

    if (nblocks == 1) {
	if (input->length < BLOCK_SIZE)
	    abort();
	dec(output->data, input->data, &ctx);
    } else {
       ...
    return 0;
}

Even though this code checks the length’s size, it will invoke abort(3) that could result in a simple remote DoS situation. Also, there is no check in the ‘else’ clause regarding the ‘nblocks’ value. To fix this, this patch was used:

     if (nblocks == 1) {
 	if (input->length < BLOCK_SIZE)
-	    abort();
+	    return KRB5_BAD_MSIZE;
 	dec(output->data, input->data, &ctx);
-    } else {
+    } else if (nblocks > 1) {
 
 	for (blockno = 0; blockno < nblocks - 2; blockno++) {

Moving on to krb5int_aes_encrypt_iov() we have the following code:

static krb5_error_code
krb5int_aes_encrypt_iov(const krb5_keyblock *key,
		        const krb5_data *ivec,
		        krb5_crypto_iov *data,
		        size_t num_data)
{
    aes_ctx ctx;
    char tmp[BLOCK_SIZE], tmp2[BLOCK_SIZE];
    int nblocks = 0, blockno;
    size_t input_length, i;
         ...
    nblocks = (input_length + BLOCK_SIZE - 1) / BLOCK_SIZE;

    assert(nblocks > 1);
         ...

Here the bug is the easily triggerable assert(3) that could be used for remote DoS and it was patched like this:

     }
 
+    IOV_BLOCK_STATE_INIT(&input_pos);
+    IOV_BLOCK_STATE_INIT(&output_pos);
+
     nblocks = (input_length + BLOCK_SIZE - 1) / BLOCK_SIZE;
-
-    assert(nblocks > 1);
-
-    {
+    if (nblocks == 1) {
+	krb5int_c_iov_get_block((unsigned char *)tmp, BLOCK_SIZE,
+				data, num_data, &input_pos);
+	enc(tmp2, tmp, &ctx);
+	krb5int_c_iov_put_block(data, num_data, (unsigned char *)tmp2,
+				BLOCK_SIZE, &output_pos);
+    } else if (nblocks > 1) {
 	char blockN2[BLOCK_SIZE];   /* second last */
 	char blockN1[BLOCK_SIZE];   /* last block */
-	struct iov_block_state input_pos, output_pos;
 
-	IOV_BLOCK_STATE_INIT(&input_pos);
-	IOV_BLOCK_STATE_INIT(&output_pos);
-
 	for (blockno = 0; blockno < nblocks - 2; blockno++) {

And the exact same assert(3) bug was also present in krb5int_aes_decrypt_iov() which is the equivalent decryption function. Another similar issue was fixed in src/lib/crypto/dk/dk_decrypt.c and specifically in the following function:

static krb5_error_code
krb5_dk_decrypt_maybe_trunc_hmac(const struct krb5_enc_provider *enc,
				 const struct krb5_hash_provider *hash,
				 const krb5_keyblock *key, krb5_keyusage usage,
				 const krb5_data *ivec, const krb5_data *input,
				 krb5_data *output, size_t hmacsize,
				 int ivec_mode)
{
          ...
    /* allocate and set up ciphertext and to-be-derived keys */

    hashsize = hash->hashsize;
    blocksize = enc->block_size;
    keybytes = enc->keybytes;
    keylength = enc->keylength;

    if (hmacsize == 0)
	hmacsize = hashsize;
    else if (hmacsize > hashsize)
	return KRB5KRB_AP_ERR_BAD_INTEGRITY;

    enclen = input->length - hmacsize;
          ...
    if ((plaindata = (unsigned char *) malloc(enclen)) == NULL) {
          ...
    /* decrypt the ciphertext */

    d1.length = enclen;
    d1.data = input->data;

    d2.length = enclen;
    d2.data = (char *) plaindata
          ...
    output->length = plainlen;

    memcpy(output->data, d2.data+blocksize, output->length);
          ...
    return(ret);
}

The underflow could happen during the ‘enclen’ calculation and it could then result in a heap based overflow since the allocated space using malloc(3) might be less than the ‘output->length’ that memcpy(3) will attempt to copy. The fix was of course…

 	return KRB5KRB_AP_ERR_BAD_INTEGRITY;
 
+    /* Verify input and output lengths. */
+    if (input->length < blocksize + hmacsize)
+	return KRB5_BAD_MSIZE;
+    if (output->length < input->length - blocksize - hmacsize)
+	return KRB5_BAD_MSIZE;
+
     enclen = input->length - hmacsize;

Next, the bug fix was performed in src/lib/crypto/raw/raw_decrypt.c in the routine shown below…

krb5_error_code
krb5_raw_decrypt(const struct krb5_enc_provider *enc,
		 const struct krb5_hash_provider *hash,
		 const krb5_keyblock *key, krb5_keyusage usage,
		 const krb5_data *ivec, const krb5_data *input,
		 krb5_data *output)
{
    return((*(enc->decrypt))(key, ivec, input, output));
}

This is a simple wrapper around the callback decryption routine which is more of an abstraction layer. However, to ensure that the check will be performed regardless of the decryption routine that will be executed, the developers added the check in this layer too. So, here is the patch:

 {
+    if (output->length < input->length)
+	return KRB5_BAD_MSIZE;
     return((*(enc->decrypt))(key, ivec, input, output));
 }

Finally, src/lib/crypto/old/old_decrypt.c was also updated like this:

     hashsize = hash->hashsize;
 
+    /* Verify input and output lengths. */
+    if (input->length < blocksize + hashsize || input->length % blocksize != 0)
+	return(KRB5_BAD_MSIZE);
     plainsize = input->length - blocksize - hashsize;
-
     if (arg_output->length < plainsize)

Kerberos’ developers also wrote a new test case code which is available at src/lib/crypto/crypto_tests/t_short.c and here is a brief explanation of it…

#include "k5-int.h"

krb5_enctype interesting_enctypes[] = {
    ENCTYPE_DES_CBC_CRC,
    ENCTYPE_DES_CBC_MD4,
    ENCTYPE_DES_CBC_MD5,
    ENCTYPE_DES3_CBC_SHA1,
    ENCTYPE_ARCFOUR_HMAC,
    ENCTYPE_ARCFOUR_HMAC_EXP,
    ENCTYPE_AES256_CTS_HMAC_SHA1_96,
    ENCTYPE_AES128_CTS_HMAC_SHA1_96,
    0
};

/* Abort if an operation unexpectedly fails. */
static void
x(krb5_error_code code)
{
    if (code != 0)
        abort();
}

This array includes some encryption algorithms supported by the MIT Kerberos and a very simple function that will simply abort(3) in case of an error code. The next function in the test case code is:

/* Abort if a decrypt operation doesn't have the expected result. */
static void
check_decrypt_result(krb5_error_code code, size_t len, size_t min_len)
{
    if (len < min_len) {
        /* Undersized tokens should always result in BAD_MSIZE. */
        if (code != KRB5_BAD_MSIZE)
            abort();
    } else {
        /* Min-size tokens should succeed or fail the integrity check. */
        if (code != 0 && code != KRB5KRB_AP_ERR_BAD_INTEGRITY)
            abort();
    }
}

In case of an undersized token it will abort(3) if the return value wasn’t ‘KRB5_BAD_MSIZE’ since this will mean that the code reached a bug similar to the ones that got fixed above. The next check will be performed to ensure that small sized tokens fail in the key integrity check, if this isn’t the case it will abort(3) too.
Now the code that performs the check is:

static void
test_enctype(krb5_enctype enctype)
{
    krb5_error_code ret;
    krb5_keyblock keyblock;
    krb5_enc_data input;
    krb5_data output;
    krb5_crypto_iov iov[2];
    unsigned int dummy;
    size_t min_len, len;

    printf("Testing enctype %d\n", (int) enctype);
    x(krb5_c_encrypt_length(NULL, enctype, 0, &min_len));
    x(krb5_c_make_random_key(NULL, enctype, &keyblock));
    input.enctype = enctype;

As you can read, it will use the passed ‘enctype’ to krb5_c_encrypt_length() to get the minimum length of the encrypted data and store it in ‘min_len’ and then invoke krb5_c_make_random_key() to generate a random key that will be stored in ‘keyblock’. The routine will then execute this:

    /* Try each length up to the minimum length. */
    for (len = 0; len <= min_len; len++) {
        input.ciphertext.data = calloc(len, 1);
        input.ciphertext.length = len;
        output.data = calloc(len, 1);
        output.length = len;

The loop will be executed up to the ‘min_len’ which was earlier retrieved and it’s the minimum length value. Next it will simply initialize the ciphertext structure based on the iterator’s value and it will continue like…

        /* Attempt a normal decryption. */
        ret = krb5_c_decrypt(NULL, &keyblock, 0, NULL, &input, &output);
        check_decrypt_result(ret, len, min_len);

        if (krb5_c_crypto_length(NULL, enctype, KRB5_CRYPTO_TYPE_HEADER,
                                 &dummy) == 0) {
            /* Attempt an IOV stream decryption. */
            iov[0].flags = KRB5_CRYPTO_TYPE_STREAM;
            iov[0].data = input.ciphertext;
            iov[1].flags = KRB5_CRYPTO_TYPE_DATA;
            iov[1].data.data = NULL;
            iov[1].data.length = 0;
            ret = krb5_c_decrypt_iov(NULL, &keyblock, 0, NULL, iov, 2);
            check_decrypt_result(ret, len, min_len);
        }

        free(input.ciphertext.data);
        free(output.data);
    }
}

It will attempt to decrypt this random key using krb5_c_decrypt() and then call check_decrypt_result() which was discussed earlier and it will check that the return values are correct. A similar operation will be performed on IOV stream decryption too and when the ‘for’ loop exits, it will free the allocated space.
Finally, the main() routine is:

int
main(int argc, char **argv)
{
    int i;
    krb5_data notrandom;

    notrandom.data = "notrandom";
    notrandom.length = 9;
    krb5_c_random_seed(NULL, &notrandom);
    for (i = 0; interesting_enctypes[i]; i++)
        test_enctype(interesting_enctypes[i]);
    return 0;
}

Which will pass all of the encryption algorithms of the ‘interesting_enctypes’ array to the previously explained testing function. So, this test case program will check that there are no bugs even when minimum tokens are used for the provided cryptographic algorithms.

Written by xorl

January 13, 2010 at 21:26

Posted in bugs

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s