Question/Possible Error in Description of MCT test for AES CBC

[AlexThurston]

I'll begin with the caveat that I could be completely wrong in my statement and perhaps there is a convention that I'm missing but this has to do with with the documentation for the MCT test for CBC found here

It says that the process to follow for MCT test of CBC is:

Key[0] = KEY
IV[0] = IV
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output IV[i]
    Output PT[0]
    For j = 0 to 999
        If ( j=0 )
            CT[j] = AES_CBC_ENCRYPT(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
            CT[j] = AES_CBC_ENCRYPT(Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

I'm focusing on the if section:

 If ( j=0 )
    CT[j] = AES_CBC_ENCRYPT(Key[i], IV[i], PT[j])
    PT[j+1] = IV[i]
Else
    CT[j] = AES_CBC_ENCRYPT(Key[i], PT[j])
    PT[j+1] = CT[j-1]

This states the the first iteration should use the initial IV when performing the AES CBC encryption. Great! That makes sense.

However, on subsequent iterations, the IV is not provided to the AES_CBC_ENCRYPT process. This got me confused. As I did research to figure out how this working, as you might imagine, there were a number of explanations out there on the internet. One of which was that it would in-turn use a null IV. However, doing so did not produce the correct result.

It seems as though in certain languages/implementations, leaving the IV out will force the process to generate a random IV which I also didn't think was correct because then the iteration results would never matched.

What I finally found is a publication dated January 7, 1998 where it described the MCT test as the following:

Initialize KEY0, IV, PT0

    FOR i = 0 TO 399
    {
        IF (i == 0)
            CV0 = IV
        Record i, KEYi, CV0, PT0
        FOR j = 0 TO 9999
        {
            IBj = PTj XOR CVj
            Perform algorithm in encrypt state, resulting in CTj
            IF (j == 0)
                PTj+1 = CV0
            ELSE
                PTj+1 = CTj-1
            CVj+1 = CTj
        }
        Record CTj

        KEYi+1 = KEYi XOR last n bits of CT,
            where n = 128, 192, or 256 (depending on key size)
        PT0 = CT9998
        CV0 = CT9999
    }

Now while I appreciate the the iteration and counts are different, in this code, it is setting the subsequent IV to be the previous CT.

If I make a similar change to the pseudocode (I put **** where the change has been made), ie:

Key[0] = KEY
IV[0] = IV
PT[0] = PT
For i = 0 to 99
    Output Key[i]
    Output IV[i]
    Output PT[0]
    For j = 0 to 999
        If ( j=0 )
            CT[j] = AES_CBC_ENCRYPT(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
****     CT[j] = AES_CBC_ENCRYPT(CT[j-1], Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    AES_KEY_SHUFFLE(Key, CT)
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

I end up getting the correct responses for my vectors in my implementation.

Is it possible that the pseudocode provided here is incorrect, or is the re-using of the CT between iterations something that is understand inherently and documented somewhere and I missed it?

[celic]

The description is derived from https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/aes/AESAVS.pdf (See page 7). I think it is implied in this document that the AES-CBC implementation is handling the IV advancement.

[celic]

If the AES-CBC implementation doesn't do this automatically, then the test harness can plug in the appropriate value for the IV, which would be the previous iteration's CT.

[smuellerDD]

It is the key for all MCT that your IUT needs to retain the state between cipher invocations. I.e. you need to have "steam cipher API" like:

1. cipher_init(&handle, key, iv)
2. cipher_update(handle, pt) ... repeat 2 as long as needed
3. cipher_final(handle) to close the handle

[smuellerDD]

Note, if your IUT does not implement such streaming API, you need to extract the IV after each cipher operation and you need to reuse it for the next invocation. The IV is the only item that gets updated while the cipher performs an operation.

[AlexThurston]

Ah, there's the piece of information that I was not aware of. I didn't know that an IUT needed to retain state between cipher invocations. I understood that CBC does this as it traverses the blocks and uses the CT from the previous block as the IV for the subsequent block, but I didn't know that there was a requirement of the IUT needed to preserve it between invocations.

Is that something that is just well known as FIPS as a requirement? From my perspective as a neophyte entering the world of FIPS, the documentation for the MCT test doesn't really make that fact clear.

[smuellerDD]

Sorry, but you just ought to know that ... It took me also a while to understand that when I started implementing that stuff.

And, in the MCT definitions you will find one or the other error (IIRC one or two for AES). But for TDES, oh boy - read the source code comment in my parser code about the TDES MCT...

[AlexThurston]

No need to apologize,. I had an inkling that this was just something people in the industry knew, but I couldn't for the life of me find where that might be spelt out. I ended up figuring out through a series of experiments.

Thank as always for the input. I'll close this issue out.

[celic]

This is very lightly touched on in https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38a.pdf under Section 6.2. There are separate descriptions for CBC for the first block, and all subsequent blocks. This is likely where the description for the MCT originally came from in the AESAVS document. I do like the idea of being as specific as possible for these descriptions. This might be something that appears in the future.

[SecureExchanges]

Thank for your question. We was facing the same issue.

The sample do not reflect the reality. At least they should specify the language of the code sample.

[SecureExchanges]

@AlexThurston in the same way. How did you interpret this line ? AES Monte Carlo Key Shuffle Key[i+1] = Key[i] xor (MSB(CT[j-1], 128) || MSB(CT[j], 128))

(MSB(CT[j-1], 128) || MSB(CT[j], 128))

if focus on the " || "

Is it something like "Get the Most Signific Bit from CT[j-1] for 128 bit length" and if nothing exist then take the MSB of CT[j] with 128 bit length

OR

is more like : "Take the MSB(CT[j-1],128) => 128 bit and concat with the MSB(CT[j], 128) ==> bit length to get a 256 bits array to perform the Xor

[celic]

"Take the 128 most significant bits of the previous ciphertext and concatenate them with the 128 most significant bits of the current ciphertext."

If you have a suggestion for improving the documentation, let me know.

[SecureExchanges]

From my point of view the || operator is not a concatenation operator.

So the example should not be presented like that, because it is confusing.

The "+" operator seems to me more appropriate as a concatenation operator.

Maybe even just comment out the code to specify that it is a concatenation of bytes array.

Key[i] xor (MSB(CT[j-1], 128) " + " MSB(CT[j], 128)) // Concatenate the MSB([j-1],128) with MSB(CT[j], 128)

And also maybe comment the same line as @AlexThurston face on it, because we face the same issue. It was not clear that the IV supposed to be the previous CT.

CT[j] = AES_CBC_ENCRYPT(Key[i], PT[j]) // The IV should be the previous CT ie: IV = CT[j-1]

It's only suggestion, but that will made code more easier to understand.

[celic]

Both + and || are common concatenation symbols. All NIST cryptography standards use || to denote concatenation, so it is preferred to remain consistent here. As well in the original response to this issue the following text was added before the pseudocodes...

For modes that use an IV, the IV is used in the beginning of each pseudorandom process. The IV is implicitly advanced according to the block cipher mode in use.

It is not always the previous ciphertext, that is just the definition for a CBC mode. The description IV = CT[j-1] may be concise and pleasant for CBC, but for other modes such a description is not as nice. To keep the pseudocode focused on the MCT aspect, we apply the IV transition in this way.

[celic]

I have prepared https://github.com/usnistgov/ACVP/pull/1189 to try to cover the other parts of the question.

[SecureExchanges]

Thanks for the explication.

You are right for the || has a concatenation operator. But if we compare the number of language that use "+" vs "||" ...

My comments are meant to be constructive, in order to reach more people.

I am aware that there are many different languages, but reading a pseudo code with operators that differ from one language to another could deserve some additional comments on the code.

Anyway, thank you very much for your answers because you have unblocked us considerably. Now the "pseudo code" is clear, since we know how to use different operators.

We always end up understanding, but sometimes it takes longer because we have to do try and error.

[celic]

Thanks for the feedback. Unfortunately in the NIST cryptography standards, + already has a meaning, so || is necessary. I did add a sentence on this before the AES Key Shuffle pseudocode in the PR linked.

[SecureExchanges]

I have prepared #1189 to try to cover the other parts of the question.

Another remark for the line : CT[j] = AES_CBC_ENCRYPT(Key[i], PT[j])

On encryption and decryption the new IV will always be CT[j-1]

The note suggest to replace all the PT with CT for encryption vs decryption, but the decryption IV is used from the previous CT and not the previous PT.

ie : Encryption If ( j=0 ) CT[j] = AES_CBC_ENCRYPT(Key[i], IV[i], PT[j]) PT[j+1] = IV[i] Else CT[j] = AES_CBC_ENCRYPT(Key[i],CT[j-1], PT[j]) PT[j+1] = CT[j-1]

Decryption will also use CT[j-1]

     If ( j=0 )
        PT[j] = AES_CBC_DECRYPT(Key[i], IV[i], CT[j])
        CT[j+1] = IV[i]
    Else
        PT[j] = AES_CBC_DECRYPT(Key[i],**CT[j-1]**, CT[j])
        CT[j+1] = PT[j-1]