Add GCM, CTR, and CTS modes to AES.

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

+/* 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/. */
+/* $Id: cts.c,v 1.27 2012/04/25 14:49:43 gerv%gerv.net Exp $ */
+
+#ifdef FREEBL_NO_DEPEND
+#include "stubs.h"
+#endif
+#include "blapit.h"
+#include "blapii.h"
+#include "cts.h"
+#include "secerr.h"
+
+struct CTSContextStr {
+    freeblCipherFunc cipher;
+    void *context;
+    unsigned char iv[MAX_BLOCK_SIZE];
+};
+
+CTSContext *
+CTS_CreateContext(void *context, freeblCipherFunc cipher, 
+                  const unsigned char *iv, unsigned int blocksize)
+{
+    CTSContext  *cts;
+
+    cts = PORT_ZNew(CTSContext);
+    if (cts == NULL) {
+        return NULL;
+    }
+    PORT_Memcpy(cts->iv, iv, blocksize);
+    cts->cipher = cipher;
+    cts->context = context;
+    return cts;
+}
+
+void
+CTS_DestroyContext(CTSContext *cts, PRBool freeit)
+{
+    if (freeit) {
+        PORT_Free(cts);
+    }
+}
+        
+/*
+ * See addemdum to NIST SP 800-38A
+ * Generically handle cipher text stealing. Basically this is doing CBC
+ * operations except someone can pass us a partial block. 
+ *
+ *  Output Order:
+ *  CS-1:  C1||C2||C3..Cn-1(could be partial)||Cn   (NIST)
+ *  CS-2: pad == 0 C1||C2||C3...Cn-1(is full)||Cn   (Schneier)
+ *  CS-2: pad != 0 C1||C2||C3...Cn||Cn-1(is partial)(Schneier)
+ *  CS-3: C1||C2||C3...Cn||Cn-1(could be partial)   (Kerberos)
+ *
+ * The characteristics of these three options:
+ *  - NIST & Schneier (CS-1 & CS-2) are identical to CBC if there are no
+ * partial blocks on input.
+ *  - Scheier and Kerberos (CS-2 and CS-3) have no embedded partial blocks,
+ * which make decoding easier.
+ *  - NIST & Kerberos (CS-1 and CS-3) have consistant block order independent
+ * of padding.
+ *
+ * PKCS #11 did not specify which version to implement, but points to the NIST
+ * spec, so this code implements CTS-CS-1 from NIST. 
+ *
+ * To convert the returned buffer to:
+ *   CS-2 (Schneier): do
+ *       unsigned char tmp[MAX_BLOCK_SIZE];
+ *       pad = *outlen % blocksize;
+ *       if (pad) {
+ *          memcpy(tmp, outbuf+*outlen-blocksize, blocksize);
+ *          memcpy(outbuf+*outlen-pad,outbuf+*outlen-blocksize-pad, pad);
+ *          memcpy(outbuf+*outlen-blocksize-pad, tmp, blocksize);
+ *       }
+ *   CS-3 (Kerberos): do
+ *       unsigned char tmp[MAX_BLOCK_SIZE];
+ *       pad = *outlen % blocksize;
+ *       if (pad == 0) {
+ *           pad = blocksize;
+ *       }
+ *       memcpy(tmp, outbuf+*outlen-blocksize, blocksize);
+ *       memcpy(outbuf+*outlen-pad,outbuf+*outlen-blocksize-pad, pad);
+ *       memcpy(outbuf+*outlen-blocksize-pad, tmp, blocksize);
+ */
+SECStatus
+CTS_EncryptUpdate(CTSContext *cts, unsigned char *outbuf, 
+                unsigned int *outlen, unsigned int maxout, 
+                const unsigned char *inbuf, unsigned int inlen,
+                unsigned int blocksize)
+{
+    unsigned char lastBlock[MAX_BLOCK_SIZE];
+    unsigned int tmp;
+    int fullblocks;
+    int written;
+    SECStatus rv;
+
+    if (inlen < blocksize) {
+        PORT_SetError(SEC_ERROR_INPUT_LEN);
+        return SECFailure;
+    }
+
+    if (maxout < inlen) {
+        *outlen = inlen;
+        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
+        return SECFailure;
+    }
+    fullblocks = (inlen/blocksize)*blocksize;

[Ryan Sleevi, 2012/09/11 19:34:30]

nit: The rest of the file uses spaces between operators, it seems, so this
should be

fullblocks = (inlen / blocksize) * blocksize;

Also on line 193.

+    rv = (*cts->cipher)(cts->context, outbuf, outlen, maxout, inbuf, 
+         fullblocks, blocksize);
+    if (rv != SECSuccess) {
+        return SECFailure;
+    }
+    inbuf += fullblocks;
+    inlen -= fullblocks;
+    if (inlen == 0) {
+        return SECSuccess;
+    }
+    written = *outlen - (blocksize - inlen);
+    outbuf += written;
+    maxout -= written;
+
+    /*
+     * here's the CTS magic, we pad our final block with zeros,

[Ryan Sleevi, 2012/09/11 19:34:30]

From merely inspecting the code (I've not yet fired into a debugger to trace),
this surprises me that it does the right thing when a caller is using
C_EncryptInit + C_EncryptUpdate( * 2 or more) + C_EncryptFinal.

My concern is that it would perform the CTS for every EncryptUpdate, rather than
deferring the CTS to the final call to C_EncryptFinal.

With CKM_AES_GCM, context->doPad is not set to true (at least, not on line
773/774 of
https://bugzilla.mozilla.org/page.cgi?id=splinter.html&bug=373108&attachment=...
). context->update = AES_Encrypt (
http://mxr.mozilla.org/security/source/security/nss/lib/softoken/pkcs11c.c#772
), context->blocksize = 0 (
http://mxr.mozilla.org/security/source/security/nss/lib/softoken/pkcs11c.c#433 )

When NSC_EncryptUpdate is called, if doPad = 0, it will call context->update
with the (entire) data passed to C_EncryptUpdate. This will call AES_Encrypt,
which will forward to cx->worker with the entire buffer from C_EncryptUpdate.
cx->worker in this case is CTS_EncryptUpdate.

If the buffer supplied to C_EncryptUpdate/NSC_EncryptUpdate is not a full AES
blocksize, then it seems it might be prematurely doing the CTS before
C_EncryptFinal has been called.

Again, I haven't stepped through a debugger yet with this, but I didn't see any
tests for the case, which is why I wanted to check how it was expected to behave
here.

[rjrejyea, 2012/09/19 21:56:02]

So your current understanding any my initial understanding of the PKCS #11 spec
for CTS was the same, and incorrect. The definition of CTS is on a call-for call
basis. That is each call to EncryptUpdate must have at least 1 block, and will
return a CTS encoded result of exactly the same size as the input.

This is consistent with the Kerberos usage. I initially implemented something
that kept back blocks and returned the CTS result at the end of the final, but
then I looked at how PKCS #11 defined CTS and realized my understanding and
implementation were incorrect.

bob

[Ryan Sleevi, 2012/09/19 22:21:35]

I'm not convinced that's the case.

Calls to C_Encrypt are documented (in Table 44, in Section 6.10, of PKCS#11 2.30
Draft 7) as taking "Input Length: Any, >= block size"

So a single call to C_Encrypt() should, as appropriate, finalize the block and
do the stealing.

However, for C_EncryptUpdate, which works in data parts, I did not think it was
necessary that pPart/ulPartLen be the same length as pData/ulDataLen of
C_Encrypt. That is, I haven't seen where (and I may have missed it) it's
required the ulPartLen be a multiple of block size (instead of, say, 3 calls
with lengths of 7 + 1 + 8)

C_Encrypt explicitly mentions the CKR_DATA_LEN_RANGE error when the
preconditions for the mechanism are not met, but C_EncryptUpdate does not place
those requirements. However, C_EncryptFinal *does* explicitly call out
CKR_DATA_LEN_RANGE, which is why I think the call sequence:

C_EncryptInit
C_EncryptUpdate(7)
C_EncryptUpdate(1)
C_EncryptUpdate(8)
C_EncryptFinal()

was/is a valid sequence (and which would break here)

[rjrejyea, 2012/09/19 22:52:48]

You are misreading the table. If you see the AES code:

C_Encrypt is 'multiple of block size'. This is the valid input for each call to
C_EncryptUpdate. (It's illegal to do C_EncryptUpdate(7) C_EncryptUpdate(1) and
then finalize).

Note the comment: no final part.

If you do 'cashing' of the partial blocks and then complete the stealing bits at
the end, you have to return some data at final. The only way not to have to
return data at final is to return CTS on each call to Update, which is what is
implemented.

bob

Your sequence is not valid according to the PKCS #11 spec.

bob

[Ryan Sleevi, 2012/09/19 23:04:53]

See linked bug - looks like Nelson read the spec the same way I did.

As far as the caching, returning data at C_Final, which in the case of CTS would
be the final two blocks (swapped and stolen, as appropriately), seems like a
correct read under Section 11.2.

"Cryptographic functions which return output in a variable-length buffer should
always return as much output *as can be computed from what has been passed in to
them thus far*.

As an example, consider a session which is performing a multiple-part decryption
operation with DES in cipher-block chaining mode with PKCS padding. Suppose
that, initially, 8 bytes of ciphertext are passed to the C_DecryptUpdate
function. The blocksize of DES is 8 bytes, but PKCS padding makes it unclear at
this stage whether the ciphertext was produced from encrypting a 0-byte string,
or from encrypting some string of length at least 8 bytes. Hence the call to
C_DecryptUpdate should return 0 bytes of plaintext. If a single additional byte
of ciphertext is supplied by a subsequent call to C_DecryptUpdate, then that
call should return 8 bytes of plaintext (one full DES block)."

While that focuses on Decrypt, and on CBC, it does seem to support the semantics
I described. Note the last sentence "If a single additional byte of ciphertext
is supplied" - which suggests that it is valid to call C_DecryptUpdate with one
byte of input.

When you look at Table 28 (Section 6.6.12), which describes general block cipher
CBC with PKCS padding, it makes it clear that C_Decrypt inputs should be
"multiple of blocksize". Combining the two sections, it seems that
C_DecryptUpdate is not bound by the convention established in C_Decrypt.

Thus, for streaming (_Init, _Update, Final), it *does* seem like the application
does need to keep some degree of caching - as best it can. In the case of CTS,
any time you have cached_input_len > 2*blocksize, it seems like you can return
at least 1 blocksize of ciphertext.

+     * then do a CBC encrypt. CBC will xor our plain text with
+     * the previous block (Cn-1), capturing part of that block (Cn-1**) as it
+     * xors with the zero pad. We then write this full block, overwritting
+     * (Cn-1**) in our buffer. This allows us to have input data == output
+     * data since Cn contains enough information to reconver Cn-1** when
+     * we decrypt (at the cost of some complexity as you can see in decrypt
+     * below */
+    PORT_Memset(lastBlock, 0, blocksize);

[Ryan Sleevi, 2012/09/11 19:34:30]

In the "premature optimization" department, it's worth noting that you may be
zeroizing memory you're just going to end up copying over.

Perhaps:
if (blocksize - len)
  PORT_Memset(lastBlock + inlen, 0, blocksize - inlen)

+    PORT_Memcpy(lastBlock, inbuf, inlen);
+    rv = (*cts->cipher)(cts->context, outbuf, &tmp, maxout, lastBlock, 
+                        blocksize, blocksize);
+    PORT_Memset(lastBlock, 0, blocksize);
+    return rv;
+}
+
+
+#define XOR_BLOCK(x,y,count) for(i=0; i < count; i++) x[i] = x[i] ^ y[i]

[Ryan Sleevi, 2012/09/11 19:34:30]

In CTR and GCM, you defined this as a function (ctr_xor/gcm_xor), but in CTS,
you define it as a macro.

Is there a reason for the inconsistency in implementations?

[rjrejyea, 2012/09/19 21:56:02]

Because we really need a freebl version of xor. Almost every algorithm has it's
own version. :).


bob

+
+/*
+ * See addemdum to NIST SP 800-38A
+ * Decrypt, Expect CS-1: input. See the comment on the encrypt side
+ * to understand what CS-2 and CS-3 mean.
+ * 
+ * To convert the input buffer to CS-1 from ...
+ *   CS-2 (Schneier): do
+ *       unsigned char tmp[MAX_BLOCK_SIZE];
+ *       pad = inlen % blocksize;
+ *       if (pad) {
+ *          memcpy(tmp, inbuf+inlen-blocksize-pad, blocksize);
+ *          memcpy(inbuf+inlen-blocksize-pad,inbuf+inlen-pad, pad);
+ *          memcpy(inbuf+inlen-blocksize, tmp, blocksize);
+ *       }
+ *   CS-3 (Kerberos): do
+ *       unsigned char tmp[MAX_BLOCK_SIZE];
+ *       pad = inlen % blocksize;
+ *       if (pad == 0) {
+ *           pad = blocksize;
+ *       }
+ *       memcpy(tmp, inbuf+inlen-blocksize-pad, blocksize);
+ *       memcpy(inbuf+inlen-blocksize-pad,inbuf+inlen-pad, pad);
+ *       memcpy(inbuf+inlen-blocksize, tmp, blocksize);
+ */
+SECStatus
+CTS_DecryptUpdate(CTSContext *cts, unsigned char *outbuf, 
+                unsigned int *outlen, unsigned int maxout, 
+                const unsigned char *inbuf, unsigned int inlen,
+                unsigned int blocksize)
+{
+    unsigned char *Pn; 
+    unsigned char Cn_2[MAX_BLOCK_SIZE]; /* block Cn-2 */
+    unsigned char Cn_1[MAX_BLOCK_SIZE]; /* block Cn-1 */
+    unsigned char Cn[MAX_BLOCK_SIZE];   /* block Cn   */
+    unsigned char lastBlock[MAX_BLOCK_SIZE];
+    const unsigned char *tmp;
+    unsigned int tmpLen;
+    int fullblocks, pad, i;
+    SECStatus rv;
+
+    if (inlen < blocksize) {
+        PORT_SetError(SEC_ERROR_INPUT_LEN);
+        return SECFailure;
+    }
+
+    if (maxout < inlen) {
+        *outlen = inlen;
+        PORT_SetError(SEC_ERROR_OUTPUT_LEN);
+        return SECFailure;
+    }
+
+    fullblocks = (inlen/blocksize)*blocksize;

[Ryan Sleevi, 2012/09/11 19:34:30]

This is a misleading variable name, as it's not the number of full blocks (inlen
/ blocksize) + (inlen % blocksize ? 1 : 0), but in fact the number of bytes
necessary to accomodate all of the full blocks.

This subtlety comes into play at lines 215/216, when performing the comparison,
since the constant (2) has to be multiplied by blocksize before comparison.

+    
+    /* even though we expect the input to be CS-1, CS-2 is easier to parse,
+     * so convert to CS-2 immediately. NOTE: this is the same code as in
+     * the comment for encrypt. NOTE2: since we can't modify inbuf unless
+     * inbuf and outbuf overlap, just copy inbuf to outbuf and modify it there
+     */
+    pad = blocksize - (fullblocks - inlen);
+    if (pad != blocksize) {
+        if (inbuf != outbuf) {
+            memcpy(outbuf, inbuf, inlen);

[Ryan Sleevi, 2012/09/11 19:34:30]

This seems rather sub-optimal that an entire copy is made. While I understand
the "easier to understand the code this way" argument, it does seem sub-optimal
for something potentially performance sensitive.

Perhaps this can be re-ordered such that the call to cts->cipher (line 219) only
needs to handle blocks 0..n-2, using the original caller-supplied inbuf, while
blocks n-2..n are handled using the temporary buffers (Cn, Cn-1, Cn-2)

[wtc, 2012/09/14 01:16:42]

I didn't study the cts.c code, so I don't know how to make
the change you suggested. Would you like to give it a try
and send me a patch?

+            /* keep the names so we logically know how we are using the 
+             * buffers */
+            inbuf = outbuf; 
+        }
+        memcpy(lastBlock,        inbuf+inlen-blocksize-pad, blocksize);
+        /* we know inbuf == outbuf now, inbuf is declared const and can't
+         * be the target, so use outbuf for the target here */
+        memcpy(outbuf+inlen-blocksize-pad, inbuf+inlen-pad, pad);
+        memcpy(outbuf+inlen-blocksize,     lastBlock,       blocksize);
+    }
+    /* save the previous to last block so we can undo the misordered chaining*/
+    tmp =  (fullblocks < blocksize*2) ? cts->iv : 
+                        inbuf+fullblocks-blocksize*2;
+    PORT_Memcpy(Cn_2, tmp, blocksize);
+    PORT_Memcpy(Cn, inbuf+fullblocks-blocksize, blocksize);
+    rv = (*cts->cipher)(cts->context, outbuf, outlen, maxout, inbuf, 
+         fullblocks, blocksize);
+    if (rv != SECSuccess) {
+        return SECFailure;
+    }
+    inbuf += fullblocks;
+    inlen -= fullblocks;
+    if (inlen == 0) {
+        return SECSuccess;
+    }
+    outbuf += fullblocks;
+    maxout -= fullblocks;
+
+    /* recover the stolen text */
+    PORT_Memset(lastBlock, 0, blocksize);
+    PORT_Memcpy(lastBlock, inbuf, inlen);
+    PORT_Memcpy(Cn_1, inbuf, inlen);
+    Pn = outbuf-blocksize;
+    /* inbuf points to Cn-1* in the input buffer */
+    /* NOTE: below there are 2 sections marked "make up for the out of order
+     * cbc decryption". You may ask, what is going on here.
+     *   Short answer: CBC automatically xors the plain text with the previous
+     * encrypted block. We are decrypting the last 2 blocks out of order, so
+     * we have to 'back out' the decrypt xor and 'add back' the encrypt xor.
+     *   Long answer: When we encrypted, we encrypted as follows:
+     *       Pn-2, Pn-1, (Pn || 0), but on decryption we can't
+     *  decrypt Cn-1 until we decrypt Cn because part of Cn-1 is stored in
+     *  Cn (see below).  So above we decrypted all the full blocks:
+     *       Cn-2, Cn,
+     *  to get:
+     *       Pn-2, Pn, Except that Pn is not yet corect. On encrypt, we
+     *  xor'd Pn || 0  with Cn-1, but on decrypt we xor'd it with Cn-2
+     *  To recover Pn, we xor the block with Cn-1* || 0 (in last block) and
+     *  Cn-2 to get Pn || Cn-1**. Pn can then be written to the output buffer
+     *  and we can now reunite Cn-1. With the full Cn-1 we can decrypt it,
+     *  but now decrypt is going to xor the decrypted data with Cn instead of
+     *  Cn-2. xoring Cn and Cn-2 restores the original Pn-1 and we can now
+     *  write that oout to the buffer */
+
+    /* make up for the out of order CBC decryption */
+    XOR_BLOCK(lastBlock, Cn_2, blocksize);
+    XOR_BLOCK(lastBlock, Pn, blocksize);
+    /* last buf now has Pn || Cn-1**, copy out Pn */
+    PORT_Memcpy(outbuf, lastBlock, inlen);
+    *outlen += inlen;
+    /* copy Cn-1* into last buf to recover Cn-1 */
+    PORT_Memcpy(lastBlock, Cn-1, inlen);
+    /* note: because Cn and Cn-1 were out of order, our pointer to Pn also
+     * points to where Pn-1 needs to reside. From here on out read Pn in
+     * the code as really Pn-1. */
+    rv = (*cts->cipher)(cts->context, Pn, &tmpLen, blocksize, lastBlock, 
+         blocksize, blocksize);
+    if (rv != SECSuccess) {
+        return SECFailure;
+    }
+    /* make up for the out of order CBC decryption */
+    XOR_BLOCK(Pn, Cn_2, blocksize);
+    XOR_BLOCK(Pn, Cn, blocksize);
+    /* reset iv to Cn  */
+    PORT_Memcpy(cts->iv, Cn, blocksize);
+    /* This makes Cn the last block for the next decrypt operation, which 
+     * matches the encrypt. We don't care about the contexts of last block,
+     * only the side effect of setting the internal IV */
+    (void) (*cts->cipher)(cts->context, lastBlock, &tmpLen, blocksize, Cn,
+                blocksize, blocksize);
+    /* clear last block. At this point last block contains Pn xor Cn_1 xor
+     * Cn_2, both of with an attacker would know, so we need to clear this
+     * buffer out */
+    PORT_Memset(lastBlock, 0, blocksize);

[Ryan Sleevi, 2012/09/11 19:34:30]

nit: Does NSS rely on PORT_Memset for cleansing?

Can't a compiler tell that lastBlock is no longer used (since it's a stack
variable) beyond this point and simply optimize it out?

[rjrejyea, 2012/09/19 21:56:02]

Any data on the stack is still on that stack until overwritten. It's basically a
FIPS thing. The less you have to handwave at the reviewer, the better. You would
need to show a pretty strong performance win not to do this.. (and still have to
show that lastBlock is somehow overwritten somewhere else...

bob

+    /* Cn, Cn_1, and Cn_2 have encrypted data, so no need to clear them */
+    return SECSuccess;
+}
+