Fix RC4 reads/writes outside array bounds.

mozilla/security/nss/lib/freebl/arcfour.c

 /* arcfour.c - the arc four algorithm.
  *
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-/* See NOTES ON UMRs, Unititialized Memory Reads, below. */
-
 #ifdef FREEBL_NO_DEPEND
 #include "stubs.h"
 #endif
 
 #include "prerr.h"
 #include "secerr.h"
 
 #include "prtypes.h"
 #include "blapi.h"
 
@@ skipping 93 matching lines @@
 RC4_AllocateContext(void)
 {
     return PORT_ZNew(RC4Context);
 }
 
 SECStatus   
 RC4_InitContext(RC4Context *cx, const unsigned char *key, unsigned int len,
                 const unsigned char * unused1, int unused2, 
                 unsigned int unused3, unsigned int unused4)
 {
-        int i;
+        unsigned int i;
         PRUint8 j, tmp;
         PRUint8 K[256];
         PRUint8 *L;
 
         /* verify the key length. */
         PORT_Assert(len > 0 && len < ARCFOUR_STATE_SIZE);
         if (len == 0 || len >= ARCFOUR_STATE_SIZE) {
                 PORT_SetError(SEC_ERROR_INVALID_ARGS);
                 return SECFailure;
         }
@@ skipping 210 matching lines @@
 
 #ifdef IS_LITTLE_ENDIAN
 #define RSH <<
 #define LSH >>
 #else
 #define RSH >>
 #define LSH <<
 #endif
 
 #ifdef CONVERT_TO_WORDS
-/* NOTE about UMRs, Uninitialized Memory Reads.
- *
- * This code reads all input data a WORD at a time, rather than byte at 
- * a time, and writes all output data a WORD at a time.  Shifting and 
- * masking is used to remove unwanted data and realign bytes when 
- * needed.  The first and last words of output are read, modified, and
- * written when needed to preserve any unchanged bytes.  This is a huge
- * win on machines with high memory latency.  
- *
- * However, when the input and output buffers do not begin and end on WORD 
- * boundaries, and the WORDS in memory that contain the first and last 
- * bytes of those buffers contain uninitialized data, then this code will 
- * read those uninitialized bytes, causing a UMR error to be reported by 
- * some tools.  
- *
- * These UMRs are NOT a problem, NOT errors, and do NOT need to be "fixed".
- * 
- * All the words read and written contain at least one byte that is 
- * part of the input data or output data.  No words are read or written
- * that do not contain data that is part of the buffer.  Therefore, 
- * these UMRs cannot cause page faults or other problems unless the 
- * buffers have been assigned to improper addresses that would cause
- * page faults with or without UMRs.  
- */
 static SECStatus 
 rc4_wordconv(RC4Context *cx, unsigned char *output,
              unsigned int *outputLen, unsigned int maxOutputLen,
              const unsigned char *input, unsigned int inputLen)
 {
         ptrdiff_t inOffset = (ptrdiff_t)input % WORDSIZE;
         ptrdiff_t outOffset = (ptrdiff_t)output % WORDSIZE;
-        register WORD streamWord, mask;

[wtc, 2013/02/08 17:15:55]

|mask| is used to mask off the unwanted bytes in the
initial or final partial word. So it is gone now.

-        register WORD *pInWord, *pOutWord;

[wtc, 2013/02/08 17:15:55]

Here I want to make |pInWord| a const pointer.

+        register WORD streamWord;
+        const register WORD *pInWord;
+        register WORD *pOutWord;
         register WORD inWord, nextInWord;

[wtc, 2013/02/08 17:46:43]

Visual C++ does not allow me to take the address of inWord
(which I do in the memcpy calls) because inWord is a register
variable. I fixed this by removing 'register', but it does
show it may be worthwhile to use a different solution, which
will need to deal with byte order.

         PRUint8 t;
         register Stype tmpSi, tmpSj;
         register PRUint8 tmpi = cx->i;
         register PRUint8 tmpj = cx->j;
         unsigned int byteCount;
         unsigned int bufShift, invBufShift;
         int i;
+        const unsigned char *finalIn;
+        unsigned char *finalOut;
 
         PORT_Assert(maxOutputLen >= inputLen);
         if (maxOutputLen < inputLen) {
                 PORT_SetError(SEC_ERROR_INVALID_ARGS);
                 return SECFailure;
         }
         if (inputLen < 2*WORDSIZE) {
                 /* Ignore word conversion, do byte-at-a-time */
                 return rc4_no_opt(cx, output, outputLen, maxOutputLen, input, inputLen);
         }
         *outputLen = inputLen;
-        pInWord = (WORD *)(input - inOffset);
+        pInWord = (const WORD *)(input - inOffset);
+        pOutWord = (WORD *)(output - outOffset);
         if (inOffset < outOffset) {
                 bufShift = 8*(outOffset - inOffset);
                 invBufShift = 8*WORDSIZE - bufShift;
         } else {
                 invBufShift = 8*(inOffset - outOffset);
                 bufShift = 8*WORDSIZE - invBufShift;
         }
         /*****************************************************************/
         /* Step 1:                                                       */

[wtc, 2013/02/08 17:15:55]

Step 1 is a complete rewrite. Therefore, do not review the
diffs. Instead, understand what the original code is trying
to do at a high-level, and then just read the new code.

In Step 1 I use memcpy() in two locations to make the code
look simpler. It can be replaced by a for loop that copies
one byte at a time, if necessary.

NOTE: Step 1 consists of nested if-else statements. I
believe it is possible to untangle them so they are not
nested, something like this:

    if (outOffset) {
        // Consume the first partial output word one byte
        // at a time. inputLen and pOutWord will be updated.
    }

    // Set up pInWord and inWord for Step 2. This requires
    // an if-else statement, possibly an if-else-if.

         /* If the first output word is partial, consume the bytes in the */
         /* first partial output word by loading one or two words of      */
         /* input and shifting them accordingly.  Otherwise, just load    */
         /* in the first word of input.  At the end of this block, at     */
         /* least one partial word of input should ALWAYS be loaded.      */
         /*****************************************************************/
         if (outOffset) {
-                /* Generate input and stream words aligned relative to the
-                 * partial output buffer.
-                 */
                 byteCount = WORDSIZE - outOffset; 
-                pOutWord = (WORD *)(output - outOffset);
-                mask = streamWord = 0;
-#ifdef IS_LITTLE_ENDIAN
-                for (i = WORDSIZE - byteCount; i < WORDSIZE; i++) {
-#else
-                for (i = byteCount - 1; i >= 0; --i) {
-#endif
+                for (i = 0; i < byteCount; i++) {
                         ARCFOUR_NEXT_BYTE();
-                        streamWord |= (WORD)(cx->S[t]) << 8*i;
-                        mask |= MASK1BYTE << 8*i;
-                } /* } */
-                inWord = *pInWord++; /* UMR? see comments above. */
+                        output[i] = cx->S[t] ^ input[i];
+                }
+                /* Consumed byteCount bytes of input */
+                inputLen -= byteCount;
+                pInWord++;
+
+                /* move to next word of output */
+                pOutWord++;
+
                 /* If buffers are relatively misaligned, shift the bytes in inWord
                  * to be aligned to the output buffer.
                  */
-                nextInWord = 0;
                 if (inOffset < outOffset) {
-                        /* Have more bytes than needed, shift remainder into nextInWord */
-                        nextInWord = inWord LSH 8*(inOffset + byteCount);
-                        inWord = inWord RSH bufShift;
+                        /* The first input word (which may be partial) has more bytes
+                         * than needed.  Copy the remainder to inWord.
+                         */
+                        inWord = 0;
+                        memcpy(&inWord, &input[byteCount], outOffset - inOffset);
                 } else if (inOffset > outOffset) {
-                        /* Didn't get enough bytes from current input word, load another
-                         * word and then shift remainder into nextInWord.
+                        /* Consumed some bytes in the second input word.  Copy the
+                         * remainder to inWord.
                          */
-                        nextInWord = *pInWord++;
-                        inWord = (inWord LSH invBufShift) | 
-                                 (nextInWord RSH bufShift);
-                        nextInWord = nextInWord LSH invBufShift;
+                        inWord = *pInWord++;
+                        inWord = inWord LSH invBufShift;
                 }
-                /* Store output of first partial word */
-                *pOutWord = (*pOutWord & ~mask) | ((inWord ^ streamWord) & mask);
-                /* UMR?  See comments above. */
-
-                /* Consumed byteCount bytes of input */
-                inputLen -= byteCount;
-                /* move to next word of output */
-                pOutWord++;
-                /* inWord has been consumed, but there may be bytes in nextInWord */
-                inWord = nextInWord;
         } else {
                 /* output is word-aligned */
-                pOutWord = (WORD *)output;
                 if (inOffset) {
                         /* Input is not word-aligned.  The first word load of input 
                          * will not produce a full word of input bytes, so one word
                          * must be pre-loaded.  The main loop below will load in the
                          * next input word and shift some of its bytes into inWord
                          * in order to create a full input word.  Note that the main
                          * loop must execute at least once because the input must
                          * be at least two words.
                          */
-                        inWord = *pInWord++; /* UMR? see comments above. */
-                        inWord = inWord LSH invBufShift;
+                        inWord = 0;
+                        memcpy(&inWord, &input[0], WORDSIZE - inOffset);
+                        pInWord++;
                 } else {
                         /* Input is word-aligned.  The first word load of input 
                          * will produce a full word of input bytes, so nothing
                          * needs to be loaded here.
                          */
                         inWord = 0;
                 }
         }
         /* Output buffer is aligned, inOffset is now measured relative to
          * outOffset (and not a word boundary).
          */
         inOffset = (inOffset + WORDSIZE - outOffset) % WORDSIZE;
         /*****************************************************************/
         /* Step 2: main loop                                             */

[wtc, 2013/02/08 17:15:55]

Step 2 is unchanged, except that at the end we need to figure
out where the remaining input starts. That address is stored
in |finalIn|.

         /* At this point the output buffer is word-aligned.  Any unused  */
         /* bytes from above will be in inWord (shifted correctly).  If   */
         /* the input buffer is unaligned relative to the output buffer,  */
         /* shifting has to be done.                                      */
         /*****************************************************************/
         if (inOffset) {
                 for (; inputLen >= WORDSIZE; inputLen -= WORDSIZE) {
                         nextInWord = *pInWord++;
                         inWord |= nextInWord RSH bufShift;
                         nextInWord = nextInWord LSH invBufShift;
                         ARCFOUR_NEXT_WORD();
                         *pOutWord++ = inWord ^ streamWord;
                         inWord = nextInWord;
                 }
                 if (inputLen == 0) {
                         /* Nothing left to do. */
                         cx->i = tmpi;
                         cx->j = tmpj;
                         return SECSuccess;
                 }
-                /* If the amount of remaining input is greater than the amount
-                 * bytes pulled from the current input word, need to do another
-                 * word load.  What's left in inWord will be consumed in step 3.
-                 */
-                if (inputLen > WORDSIZE - inOffset)
-                        inWord |= *pInWord RSH bufShift; /* UMR?  See above. */
+                finalIn = (const unsigned char *)pInWord - WORDSIZE + inOffset;
         } else {
                 for (; inputLen >= WORDSIZE; inputLen -= WORDSIZE) {
                         inWord = *pInWord++;
                         ARCFOUR_NEXT_WORD();
                         *pOutWord++ = inWord ^ streamWord;
                 }
                 if (inputLen == 0) {
                         /* Nothing left to do. */
                         cx->i = tmpi;
                         cx->j = tmpj;
                         return SECSuccess;
-                } else {
-                        /* A partial input word remains at the tail.  Load it. 
-                         * The relevant bytes will be consumed in step 3.
-                         */
-                        inWord = *pInWord; /* UMR?  See comments above */
                 }
+                finalIn = (const unsigned char *)pInWord;
         }
         /*****************************************************************/
         /* Step 3:                                                       */

[wtc, 2013/02/08 17:15:55]

Step 3 is a complete rewrite, but is simple.

-        /* A partial word of input remains, and it is already loaded     */
-        /* into nextInWord.  Shift appropriately and consume the bytes   */
-        /* used in the partial word.                                     */
+        /* Do the remaining partial word of input one byte at a time.    */
         /*****************************************************************/
-        mask = streamWord = 0;
-#ifdef IS_LITTLE_ENDIAN
-        for (i = 0; i < inputLen; ++i) {
-#else
-        for (i = WORDSIZE - 1; i >= WORDSIZE - inputLen; --i) {
-#endif
+        finalOut = (unsigned char *)pOutWord;
+        for (i = 0; i < inputLen; i++) {
                 ARCFOUR_NEXT_BYTE();
-                streamWord |= (WORD)(cx->S[t]) << 8*i;
-                mask |= MASK1BYTE << 8*i;
-        } /* } */
-        /* UMR?  See comments above. */
-        *pOutWord = (*pOutWord & ~mask) | ((inWord ^ streamWord) & mask);
+                finalout[i] = cx->S[t] ^ finalIn[i];
+        }
         cx->i = tmpi;
         cx->j = tmpj;
         return SECSuccess;
 }
 #endif
 #endif /* NSS_BEVAND_ARCFOUR */
 
 SECStatus 
 RC4_Encrypt(RC4Context *cx, unsigned char *output,
             unsigned int *outputLen, unsigned int maxOutputLen,
@@ skipping 35 matching lines @@
         /* Convert the byte-stream to a word-stream */
         return rc4_wordconv(cx, output, outputLen, maxOutputLen, input, inputLen);
 #else
         /* Operate on bytes, but unroll the main loop */
         return rc4_unrolled(cx, output, outputLen, maxOutputLen, input, inputLen);
 #endif
 }
 
 #undef CONVERT_TO_WORDS
 #undef USE_WORD