net: implement CBC processing in constant-time in libssl.

net/third_party/nss/ssl/ssl3con.c

Index: net/third_party/nss/ssl/ssl3con.c
diff --git a/net/third_party/nss/ssl/ssl3con.c b/net/third_party/nss/ssl/ssl3con.c
index 506044750c6306ecef59d8bc217f2c048011f68f..e38a624a1a940fe1b0f87e644c42d28723e8f9b5 100644
--- a/net/third_party/nss/ssl/ssl3con.c
+++ b/net/third_party/nss/ssl/ssl3con.c
@@ -1846,7 +1846,6 @@ static const unsigned char mac_pad_2 [60] = {
 };
 
 /* Called from: ssl3_SendRecord()
-**		ssl3_HandleRecord()
 ** Caller must already hold the SpecReadLock. (wish we could assert that!)
 */
 static SECStatus
@@ -2028,6 +2027,136 @@ ssl3_ComputeRecordMAC(
     return rv;
 }
 
+/* This is a bodge to allow this code to be compiled against older NSS headers
+ * that don't contain the CBC constant-time changes. */
+#ifndef CKM_NSS_HMAC_CONSTANT_TIME
+#define CKM_NSS_HMAC_CONSTANT_TIME (CKM_NSS + 19)
+#define CKM_NSS_SSL3_MAC_CONSTANT_TIME (CKM_NSS + 20)
+
+typedef struct CK_NSS_MAC_CONSTANT_TIME_PARAMS {
+    CK_MECHANISM_TYPE hashAlg;  /* in */
+    CK_ULONG ulBodyTotalLen;    /* in */
+    CK_BYTE * pHeader;          /* in */
+    CK_ULONG ulHeaderLen;    /* in */
+} CK_NSS_MAC_CONSTANT_TIME_PARAMS;
+#endif
+
+/* Called from: ssl3_HandleRecord()
+ * Caller must already hold the SpecReadLock. (wish we could assert that!)
+ *
+ * On entry:
+ *   originalLen >= inputLen >= MAC size
+*/
+static SECStatus
+ssl3_ComputeRecordMACConstantTime(
+    ssl3CipherSpec *   spec,
+    PRBool             useServerMacKey,
+    PRBool             isDTLS,
+    SSL3ContentType    type,
+    SSL3ProtocolVersion version,
+    SSL3SequenceNumber seq_num,
+    const SSL3Opaque * input,
+    int                inputLen,
+    int                originalLen,
+    unsigned char *    outbuf,
+    unsigned int *     outLen)
+{
+    CK_MECHANISM_TYPE            macType;
+    CK_NSS_MAC_CONSTANT_TIME_PARAMS params;
+    PK11Context *                mac_context;
+    SECItem                      param;
+    SECStatus                    rv;
+    unsigned char                header[13];
+    PK11SymKey *                 key;
+    int                          recordLength;
+
+    PORT_Assert(inputLen >= spec->mac_size);
+    PORT_Assert(originalLen >= inputLen);
+
+    if (spec->bypassCiphers) {
+	/* This function doesn't support PKCS#11 bypass. We fallback on the
+	 * non-constant time version. */
+	goto fallback;
+    }
+
+    if (spec->mac_def->mac == mac_null) {
+	*outLen = 0;
+	return SECSuccess;
+    }
+
+    header[0] = (unsigned char)(seq_num.high >> 24);
+    header[1] = (unsigned char)(seq_num.high >> 16);
+    header[2] = (unsigned char)(seq_num.high >>  8);
+    header[3] = (unsigned char)(seq_num.high >>  0);
+    header[4] = (unsigned char)(seq_num.low  >> 24);
+    header[5] = (unsigned char)(seq_num.low  >> 16);
+    header[6] = (unsigned char)(seq_num.low  >>  8);
+    header[7] = (unsigned char)(seq_num.low  >>  0);
+    header[8] = type;
+
+    macType = CKM_NSS_HMAC_CONSTANT_TIME;
+    recordLength = inputLen - spec->mac_size;
+    if (spec->version <= SSL_LIBRARY_VERSION_3_0) {
+	macType = CKM_NSS_SSL3_MAC_CONSTANT_TIME;
+	header[9] = recordLength >> 8;
+	header[10] = recordLength;
+	params.ulHeaderLen = 11;
+    } else {
+	if (isDTLS) {
+	    SSL3ProtocolVersion dtls_version;
+
+	    dtls_version = dtls_TLSVersionToDTLSVersion(version);
+	    header[9] = dtls_version >> 8;
+	    header[10] = dtls_version;
+	} else {
+	    header[9] = version >> 8;
+	    header[10] = version;
+	}
+	header[11] = recordLength >> 8;
+	header[12] = recordLength;
+	params.ulHeaderLen = 13;
+    }
+
+    params.hashAlg = spec->mac_def->mmech;
+    params.ulBodyTotalLen = originalLen;
+    params.pHeader = header;
+
+    param.data = (unsigned char*) &params;
+    param.len = sizeof(params);
+    param.type = 0;
+
+    key = spec->server.write_mac_key;
+    if (!useServerMacKey) {
+	key = spec->client.write_mac_key;
+    }
+    mac_context = PK11_CreateContextBySymKey(macType, CKA_SIGN, key, &param);
+    if (mac_context == NULL) {
+	/* Older versions of NSS may not support constant-time MAC. */
+	goto fallback;
+    }
+
+    rv  = PK11_DigestBegin(mac_context);
+    rv |= PK11_DigestOp(mac_context, input, inputLen);
+    rv |= PK11_DigestFinal(mac_context, outbuf, outLen, spec->mac_size);
+    PK11_DestroyContext(mac_context, PR_TRUE);
+
+    PORT_Assert(rv != SECSuccess || *outLen == (unsigned)spec->mac_size);
+
+    if (rv != SECSuccess) {
+	rv = SECFailure;
+	ssl_MapLowLevelError(SSL_ERROR_MAC_COMPUTATION_FAILURE);
+    }
+    return rv;
+
+fallback:
+    /* ssl3_ComputeRecordMAC expects the MAC to have been removed from the
+     * length already. */
+    inputLen -= spec->mac_size;
+    return ssl3_ComputeRecordMAC(spec, useServerMacKey, isDTLS, type,
+				 version, seq_num, input, inputLen,
+				 outbuf, outLen);
+}
+
 static PRBool
 ssl3_ClientAuthTokenPresent(sslSessionID *sid) {
     PK11SlotInfo *slot = NULL;
@@ -10045,6 +10174,177 @@ ssl3_HandleHandshake(sslSocket *ss, sslBuffer *origBuf)
     return SECSuccess;
 }
 
+/* These macros return the given value with the MSB copied to all the other
+ * bits. They use the fact that arithmetic shift shifts-in the sign bit.
+ * However, this is not ensured by the C standard so you may need to replace
+ * them with something else for odd compilers. */
+#define DUPLICATE_MSB_TO_ALL(x) ( (unsigned)( (int)(x) >> (sizeof(int)*8-1) ) )
+#define DUPLICATE_MSB_TO_ALL_8(x) ((unsigned char)(DUPLICATE_MSB_TO_ALL(x)))
+
+/* SECStatusToMask returns, in constant time, a mask value of all ones if rv ==
+ * SECSuccess.  Otherwise it returns zero. */
+static unsigned SECStatusToMask(SECStatus rv)
+{
+    unsigned int good;
+    /* rv ^ SECSuccess is zero iff rv == SECSuccess. Subtracting one results in
+     * the MSB being set to one iff it was zero before. */
+    good = rv ^ SECSuccess;
+    good--;
+    return DUPLICATE_MSB_TO_ALL(good);
+}
+
+/* ssl_ConstantTimeGE returns 0xff if a>=b and 0x00 otherwise. */
+static unsigned char ssl_ConstantTimeGE(unsigned a, unsigned b)
+{
+    a -= b;
+    return DUPLICATE_MSB_TO_ALL(~a);
+}
+
+/* ssl_ConstantTimeEQ8 returns 0xff if a==b and 0x00 otherwise. */
+static unsigned char ssl_ConstantTimeEQ8(unsigned char a, unsigned char b)
+{
+    unsigned c = a ^ b;
+    c--;
+    return DUPLICATE_MSB_TO_ALL_8(c);
+}
+
+static SECStatus ssl_RemoveSSLv3CBCPadding(sslBuffer *plaintext,
+					   unsigned blockSize,
+					   unsigned macSize) {
+    unsigned int paddingLength, good, t;
+    const unsigned int overhead = 1 /* padding length byte */ + macSize;
+
+    /* These lengths are all public so we can test them in non-constant
+     * time. */
+    if (overhead > plaintext->len) {
+	return SECFailure;
+    }
+
+    paddingLength = plaintext->buf[plaintext->len-1];
+    /* SSLv3 padding bytes are random and cannot be checked. */
+    t = plaintext->len;
+    t -= paddingLength+overhead;
+    /* If len >= padding_length+overhead then the MSB of t is zero. */
+    good = DUPLICATE_MSB_TO_ALL(~t);
+    /* SSLv3 requires that the padding is minimal. */
+    t = blockSize - (paddingLength+1);
+    good &= DUPLICATE_MSB_TO_ALL(~t);
+    plaintext->len -= good & (paddingLength+1);
+    return (good & SECSuccess) | (~good & SECFailure);
+}
+
+
+static SECStatus ssl_RemoveTLSCBCPadding(sslBuffer *plaintext,
+					 unsigned macSize) {
+    unsigned int paddingLength, good, t, toCheck, i;
+    const unsigned int overhead = 1 /* padding length byte */ + macSize;
+
+    /* These lengths are all public so we can test them in non-constant
+     * time. */
+    if (overhead > plaintext->len) {
+	return SECFailure;
+    }
+
+    paddingLength = plaintext->buf[plaintext->len-1];
+    t = plaintext->len;
+    t -= paddingLength+overhead;
+    /* If len >= paddingLength+overhead then the MSB of t is zero. */
+    good = DUPLICATE_MSB_TO_ALL(~t);
+
+    /* The padding consists of a length byte at the end of the record and then
+     * that many bytes of padding, all with the same value as the length byte.
+     * Thus, with the length byte included, there are paddingLength+1 bytes of
+     * padding.
+     *
+     * We can't check just |paddingLength+1| bytes because that leaks
+     * decrypted information. Therefore we always have to check the maximum
+     * amount of padding possible. (Again, the length of the record is
+     * public information so we can use it.) */
+    toCheck = 255; /* maximum amount of padding. */
+    if (toCheck > plaintext->len-1) {
+	toCheck = plaintext->len-1;
+    }
+
+    for (i = 0; i < toCheck; i++) {
+	unsigned int t = paddingLength - i;
+	/* If i <= paddingLength then the MSB of t is zero and mask is
+	 * 0xff.  Otherwise, mask is 0. */
+	unsigned char mask = DUPLICATE_MSB_TO_ALL(~t);
+	unsigned char b = plaintext->buf[plaintext->len-1-i];
+	/* The final |paddingLength+1| bytes should all have the value
+	 * |paddingLength|. Therefore the XOR should be zero. */
+	good &= ~(mask&(paddingLength ^ b));
+    }
+
+    /* If any of the final |paddingLength+1| bytes had the wrong value,
+     * one or more of the lower eight bits of |good| will be cleared. We
+     * AND the bottom 8 bits together and duplicate the result to all the
+     * bits. */
+    good &= good >> 4;
+    good &= good >> 2;
+    good &= good >> 1;
+    good <<= sizeof(good)*8-1;
+    good = DUPLICATE_MSB_TO_ALL(good);
+
+    plaintext->len -= good & (paddingLength+1);
+    return (good & SECSuccess) | (~good & SECFailure);
+}
+
+/* On entry:
+ *   originalLength >= macSize
+ *   macSize <= MAX_MAC_LENGTH
+ *   plaintext->len >= macSize
+ */
+static void ssl_CBCExtractMAC(sslBuffer *plaintext,
+			      unsigned int originalLength,
+			      SSL3Opaque* out,
+			      unsigned int macSize) {
+    unsigned char rotatedMac[MAX_MAC_LENGTH];
+    /* macEnd is the index of |plaintext->buf| just after the end of the MAC. */
+    unsigned macEnd = plaintext->len;
+    unsigned macStart = macEnd - macSize;
+    /* scanStart contains the number of bytes that we can ignore because
+     * the MAC's position can only vary by 255 bytes. */
+    unsigned scanStart = 0;
+    unsigned i, j, divSpoiler;
+    unsigned char rotateOffset;
+
+    if (originalLength > macSize + 255 + 1)
+	scanStart = originalLength - (macSize + 255 + 1);
+
+    /* divSpoiler contains a multiple of macSize that is used to cause the
+     * modulo operation to be constant time. Without this, the time varies
+     * based on the amount of padding when running on Intel chips at least.
+     *
+     * The aim of right-shifting macSize is so that the compiler doesn't
+     * figure out that it can remove divSpoiler as that would require it
+     * to prove that macSize is always even, which I hope is beyond it. */
+    divSpoiler = macSize >> 1;
+    divSpoiler <<= (sizeof(divSpoiler)-1)*8;
+    rotateOffset = (divSpoiler + macStart - scanStart) % macSize;
+
+    memset(rotatedMac, 0, macSize);
+    for (i = scanStart; i < originalLength;) {
+	for (j = 0; j < macSize && i < originalLength; i++, j++) {
+	    unsigned char macStarted = ssl_ConstantTimeGE(i, macStart);
+	    unsigned char macEnded = ssl_ConstantTimeGE(i, macEnd);
+	    unsigned char b = 0;
+	    b = plaintext->buf[i];
+	    rotatedMac[j] |= b & macStarted & ~macEnded;
+	}
+    }
+
+    /* Now rotate the MAC. If we knew that the MAC fit into a CPU cache line we
+     * could line-align |rotatedMac| and rotate in place. */
+    memset(out, 0, macSize);
+    for (i = 0; i < macSize; i++) {
+	unsigned char offset = (divSpoiler + macSize - rotateOffset + i) % macSize;
+	for (j = 0; j < macSize; j++) {
+	    out[j] |= rotatedMac[i] & ssl_ConstantTimeEQ8(j, offset);
+	}
+    }
+}
+
 /* if cText is non-null, then decipher, check MAC, and decompress the
  * SSL record from cText->buf (typically gs->inbuf)
  * into databuf (typically gs->buf), and any previous contents of databuf
@@ -10074,15 +10374,18 @@ ssl3_HandleRecord(sslSocket *ss, SSL3Ciphertext *cText, sslBuffer *databuf)
     ssl3CipherSpec *     crSpec;
     SECStatus            rv;
     unsigned int         hashBytes = MAX_MAC_LENGTH + 1;
-    unsigned int         padding_length;
     PRBool               isTLS;
-    PRBool               padIsBad = PR_FALSE;
     SSL3ContentType      rType;
     SSL3Opaque           hash[MAX_MAC_LENGTH];
+    SSL3Opaque           givenHashBuf[MAX_MAC_LENGTH];
+    SSL3Opaque          *givenHash;
     sslBuffer           *plaintext;
     sslBuffer            temp_buf;
     PRUint64             dtls_seq_num;
     unsigned int         ivLen = 0;
+    unsigned int         originalLen = 0;
+    unsigned int         good;
+    unsigned int         minLength;
 
     PORT_Assert( ss->opt.noLocks || ssl_HaveRecvBufLock(ss) );
 
@@ -10150,6 +10453,30 @@ ssl3_HandleRecord(sslSocket *ss, SSL3Ciphertext *cText, sslBuffer *databuf)
 	}
     }
 
+    good = (unsigned)-1;
+    minLength = crSpec->mac_size;
+    if (cipher_def->type == type_block) {
+	/* CBC records have a padding length byte at the end. */
+	minLength++;
+	if (crSpec->version >= SSL_LIBRARY_VERSION_TLS_1_1) {
+	    /* With >= TLS 1.1, CBC records have an explicit IV. */
+	    minLength += cipher_def->iv_size;
+	}
+    }
+
+    /* We can perform this test in variable time because the record's total
+     * length and the ciphersuite are both public knowledge. */
+    if (cText->buf->len < minLength) {
+	SSL_DBG(("%d: SSL3[%d]: HandleRecord, record too small.",
+		 SSL_GETPID(), ss->fd));
+	/* must not hold spec lock when calling SSL3_SendAlert. */
+	ssl_ReleaseSpecReadLock(ss);
+	SSL3_SendAlert(ss, alert_fatal, bad_record_mac);
+	/* always log mac error, in case attacker can read server logs. */
+	PORT_SetError(SSL_ERROR_BAD_MAC_READ);
+	return SECFailure;
+    }
+
     if (cipher_def->type == type_block &&
 	crSpec->version >= SSL_LIBRARY_VERSION_TLS_1_1) {
 	/* Consume the per-record explicit IV. RFC 4346 Section 6.2.3.2 states
@@ -10167,16 +10494,6 @@ ssl3_HandleRecord(sslSocket *ss, SSL3Ciphertext *cText, sslBuffer *databuf)
 	    PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
 	    return SECFailure;
 	}
-	if (ivLen > cText->buf->len) {
-	    SSL_DBG(("%d: SSL3[%d]: HandleRecord, IV length check failed",
-		     SSL_GETPID(), ss->fd));
-	    /* must not hold spec lock when calling SSL3_SendAlert. */
-	    ssl_ReleaseSpecReadLock(ss);
-	    SSL3_SendAlert(ss, alert_fatal, bad_record_mac);
-	    /* always log mac error, in case attacker can read server logs. */
-	    PORT_SetError(SSL_ERROR_BAD_MAC_READ);
-	    return SECFailure;
-	}
 
 	PRINT_BUF(80, (ss, "IV (ciphertext):", cText->buf->buf, ivLen));
 
@@ -10187,12 +10504,7 @@ ssl3_HandleRecord(sslSocket *ss, SSL3Ciphertext *cText, sslBuffer *databuf)
 	rv = crSpec->decode(crSpec->decodeContext, iv, &decoded,
 			    sizeof(iv), cText->buf->buf, ivLen);
 
-	if (rv != SECSuccess) {
-	    /* All decryption failures must be treated like a bad record
-	     * MAC; see RFC 5246 (TLS 1.2). 
-	     */
-	    padIsBad = PR_TRUE;
-	}
+	good &= SECStatusToMask(rv);
     }
 
     /* If we will be decompressing the buffer we need to decrypt somewhere
@@ -10234,54 +10546,70 @@ ssl3_HandleRecord(sslSocket *ss, SSL3Ciphertext *cText, sslBuffer *databuf)
     rv = crSpec->decode(
 	crSpec->decodeContext, plaintext->buf, (int *)&plaintext->len,
 	plaintext->space, cText->buf->buf + ivLen, cText->buf->len - ivLen);
+    good &= SECStatusToMask(rv);
 
     PRINT_BUF(80, (ss, "cleartext:", plaintext->buf, plaintext->len));
-    if (rv != SECSuccess) {
-        /* All decryption failures must be treated like a bad record
-         * MAC; see RFC 5246 (TLS 1.2). 
-         */
-        padIsBad = PR_TRUE;
-    }
+
+    originalLen = plaintext->len;
 
     /* If it's a block cipher, check and strip the padding. */
-    if (cipher_def->type == type_block && !padIsBad) {
-        PRUint8 * pPaddingLen = plaintext->buf + plaintext->len - 1;
-	padding_length = *pPaddingLen;
-	/* TLS permits padding to exceed the block size, up to 255 bytes. */
-	if (padding_length + 1 + crSpec->mac_size > plaintext->len)
-	    padIsBad = PR_TRUE;
-	else {
-            plaintext->len -= padding_length + 1;
-            /* In TLS all padding bytes must be equal to the padding length. */
-            if (isTLS) {
-                PRUint8 *p;
-                for (p = pPaddingLen - padding_length; p < pPaddingLen; ++p) {
-                    padIsBad |= *p ^ padding_length;
-                }
-            }
-        }
-    }
+    if (cipher_def->type == type_block) {
+	const unsigned int blockSize = cipher_def->iv_size;
+	const unsigned int macSize = crSpec->mac_size;
 
-    /* Remove the MAC. */
-    if (plaintext->len >= crSpec->mac_size)
-	plaintext->len -= crSpec->mac_size;
-    else
-    	padIsBad = PR_TRUE;	/* really macIsBad */
+	if (crSpec->version <= SSL_LIBRARY_VERSION_3_0) {
+	    good &= SECStatusToMask(ssl_RemoveSSLv3CBCPadding(
+			plaintext, blockSize, macSize));
+	} else {
+	    good &= SECStatusToMask(ssl_RemoveTLSCBCPadding(
+			plaintext, macSize));
+	}
+    }
 
     /* compute the MAC */
     rType = cText->type;
-    rv = ssl3_ComputeRecordMAC( crSpec, (PRBool)(!ss->sec.isServer),
-        IS_DTLS(ss), rType, cText->version,
-        IS_DTLS(ss) ? cText->seq_num : crSpec->read_seq_num,
-	plaintext->buf, plaintext->len, hash, &hashBytes);
-    if (rv != SECSuccess) {
-        padIsBad = PR_TRUE;     /* really macIsBad */
+    if (cipher_def->type == type_block) {
+	rv = ssl3_ComputeRecordMACConstantTime(
+	    crSpec, (PRBool)(!ss->sec.isServer),
+	    IS_DTLS(ss), rType, cText->version,
+	    IS_DTLS(ss) ? cText->seq_num : crSpec->read_seq_num,
+	    plaintext->buf, plaintext->len, originalLen,
+	    hash, &hashBytes);
+
+	ssl_CBCExtractMAC(plaintext, originalLen, givenHashBuf,
+			  crSpec->mac_size);
+	givenHash = givenHashBuf;
+
+	/* plaintext->len will always have enough space to remove the MAC
+	 * because in ssl_Remove{SSLv3|TLS}CBCPadding we only adjust
+	 * plaintext->len if the result has enough space for the MAC and we
+	 * tested the unadjusted size against minLength, above. */
+	plaintext->len -= crSpec->mac_size;
+    } else {
+	/* This is safe because we checked the minLength above. */
+	plaintext->len -= crSpec->mac_size;
+
+	rv = ssl3_ComputeRecordMAC(
+	    crSpec, (PRBool)(!ss->sec.isServer),
+	    IS_DTLS(ss), rType, cText->version,
+	    IS_DTLS(ss) ? cText->seq_num : crSpec->read_seq_num,
+	    plaintext->buf, plaintext->len,
+	    hash, &hashBytes);
+
+	/* We can read the MAC directly from the record because its location is
+	 * public when a stream cipher is used. */
+	givenHash = plaintext->buf + plaintext->len;
+    }
+
+    good &= SECStatusToMask(rv);
+
+    if (hashBytes != (unsigned)crSpec->mac_size ||
+	NSS_SecureMemcmp(givenHash, hash, crSpec->mac_size) != 0) {
+	/* We're allowed to leak whether or not the MAC check was correct */
+	good = 0;
     }
 
-    /* Check the MAC */
-    if (hashBytes != (unsigned)crSpec->mac_size || padIsBad || 
-	NSS_SecureMemcmp(plaintext->buf + plaintext->len, hash,
-	                 crSpec->mac_size) != 0) {
+    if (good == 0) {
 	/* must not hold spec lock when calling SSL3_SendAlert. */
 	ssl_ReleaseSpecReadLock(ss);