What is missing from the AES Validation Standard Pseudocode for the Monte Carlo Tests?

Question

I'm trying to use the prescribed validation procedure for AES-128 in CBC mode, as defined in the NIST AESAVS standard. One of the more important parts of the test suite is the Monte Carlo test, which provides an algorithm for generating many 10000 pseudorandom tests cases such that it is unlikely that a hardcoded circuit could fake AES. The algorithm pseudocode therein appears to be taking some liberties with variable scope and definition, so I am hoping someone could help me fill in the missing information to interpret this correctly.

The verbatim algorithm for the 128-bit key case is as follows:

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(Key[i], IV[i], PT[j])
            PT[j+1] = IV[i]
        Else
            CT[j] = AES(Key[i], PT[j])
            PT[j+1] = CT[j-1]
    Output CT[j]
    Key[i+1] = Key[i] xor CT[j]
    IV[i+1] = CT[j]
    PT[0] = CT[j-1]

For the above pseudocode, starting with these initial values:

Key = 9dc2c84a37850c11699818605f47958c
IV = 256953b2feab2a04ae0180d8335bbed6
PT = 2e586692e647f5028ec6fa47a55a2aab

The first three iterations of the outer loop should output:

KEY = 9dc2c84a37850c11699818605f47958c
IV = 256953b2feab2a04ae0180d8335bbed6
PLAINTEXT = 2e586692e647f5028ec6fa47a55a2aab
CIPHERTEXT = 1b1ebd1fc45ec43037fd4844241a437f

KEY = 86dc7555f3dbc8215e6550247b5dd6f3
IV = 1b1ebd1fc45ec43037fd4844241a437f
PLAINTEXT = c1b77ed52521525f0a4ba341bdaf51d9
CIPHERTEXT = bf43583a665fa45fdee831243a16ea8f

KEY = 399f2d6f95846c7e808d6100414b3c7c
IV = bf43583a665fa45fdee831243a16ea8f
PLAINTEXT = 7cbeea19157ec7bbf6289e2dff5e8ee4
CIPHERTEXT = 5464e1900f81e06f67139456da25fc09

It looks like we are using j outside of the inner loop, which I believe is the source of the confusion. I had originally assumed that this meant whatever the final value of the ciphertext CT was (CT[999]), which would lead me to believe that the plaintext for the next outer loop PT[0] is initialized to CT[998]. However, this interpretation doesn't match the expected outputs given.

I also thought that maybe brackets are not indicating an array of values here, but rather they represent the time steps relative to now. However, this also makes referencing j outside of the loop confusing. If the loop has expired, then is i or j the current time?

Am I missing some crucial step here? Is there a typo (there is no errata in the document)?

Could anyone with some experience on the matter comment on the appropriate interpretation?

Answer 1

Some months ago I tried to get the AES CBC MonteCarlo running on Java. I encountered the same problems but in the end I could find a complete and running solution that meets the official NIST vector results.

Before I start - your inital test vector seems to be an own vector but not the one provided by NIST - here is the link to the official NIST-website with all AES testvectors:

NIST-Website: https://csrc.nist.gov/Projects/cryptographic-algorithm-validation-program/Block-Ciphers Montecarlo testvectors: https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/aes/aesmct.zip

My test will start with these data:

[ENCRYPT]
COUNT = 0
KEY = 8809e7dd3a959ee5d8dbb13f501f2274
IV = e5c0bb535d7d54572ad06d170a0e58ae
PLAINTEXT = 1fd4ee65603e6130cfc2a82ab3d56c24
CIPHERTEXT = b127a5b4c4692d87483db0c3b0d11e64

and the function uses a "double" byte array for the inner and outer loop. I do not present the complete sourcode here on SO but the complete code is available in my GitHub repository https://github.com/java-crypto/Known_Answer_Tests with many other tests and test vector files. The encryption/decryption has to be done with NoPadding - don't use AES in default mode as in most cases it would run with PKCS#5/#7 padding.

If you like you can run the code online (reduced to AES CBC 128 MonteCarlo) here: https://repl.it/@javacrypto/AesCbcMonteCarloTest#Main.java

The program will run the complete encryption and decryption test and does an additional cross-check (means the encryption result is checked by a decryption and vice versa).

As it is some months ago that I took care of this I'm just offering my solution in Java code - hopefully it helps you in your understanding of the NIST test procedure.

public static byte[] aes_cbc_mct_encrypt(byte[] PLAINTEXT, byte[] KEYinit, byte[] IVinit) throws Exception {
    int i = 0; // outer loop
    int j = 0; // inner loop
    byte[][] KEY = new byte[101][128];
    byte[][] IV = new byte[1001][128];
    byte[][] PT = new byte[1001][128]; // plaintext
    byte[][] CT = new byte[1001][128]; // ciphertext
    byte[] CTsave = new byte[256]; // nimmt den letzten ct fuer nutzung als neuen iv auf
    // init
    int KEYLENGTH = KEYinit.length * 8;
    KEY[0] = KEYinit;
    IV[0] = IVinit;
    PT[0] = PLAINTEXT;
    for (i = 0; i < 100; i++) {
        for (j = 0; j < 1000; j++) {
            if (j == 0) {
                CT[j] = aes_cbc_encrypt(PT[j], KEY[i], IV[i]);
                CTsave = CT[j]; // sicherung fuer naechsten iv
                PT[j + 1] = IV[i];
            } else {
                IV[i] = CTsave;
                CT[j] = aes_cbc_encrypt(PT[j], KEY[i], IV[i]);
                CTsave = CT[j];
                PT[j + 1] = CT[j - 1];
            }
        }
        j = j - 1; // correction of loop counter
        if (KEYLENGTH == 128) {
            KEY[i + 1] = xor(KEY[i], CT[j]);
        }
        if (KEYLENGTH == 192) {
            KEY[i + 1] = xor192(KEY[i], CT[j - 1], CT[j]);
        }
        if (KEYLENGTH == 256) {
            KEY[i + 1] = xor256(KEY[i], CT[j - 1], CT[j]);
        }
        IV[i + 1] = CT[j];
        PT[0] = CT[j - 1];
        ctCalculated[i] = CT[j].clone();
    }
    return CT[j];
}

public static byte[] xor(byte[] a, byte[] b) {
    // nutzung in der mctCbcEncrypt und mctCbcDecrypt methode
    byte[] result = new byte[Math.min(a.length, b.length)];
    for (int i = 0; i < result.length; i++) {
        result[i] = (byte) (((int) a[i]) ^ ((int) b[i]));
    }
    return result;
}

public static byte[] aes_cbc_encrypt(byte[] plaintextByte, byte[] keyByte, byte[] initvectorByte) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, InvalidAlgorithmParameterException, BadPaddingException, IllegalBlockSizeException {
    byte[] ciphertextByte = null;
    SecretKeySpec keySpec = new SecretKeySpec(keyByte, "AES");
    IvParameterSpec ivKeySpec = new IvParameterSpec(initvectorByte);
    Cipher aesCipherEnc = Cipher.getInstance("AES/CBC/NOPADDING");
    aesCipherEnc.init(Cipher.ENCRYPT_MODE, keySpec, ivKeySpec);
    ciphertextByte = aesCipherEnc.doFinal(plaintextByte);
    return ciphertextByte;
}