AES CBC decryption validation for Monte Carlo Tests

Question

I'm trying to perform MCT on AES CBC. The pseudocode is documented here: https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/aes/AESAVS.pdf section 6.4.2

Note that there is a mistake in the pseudocode, which is revealed here: What is missing from the AES Validation Standard Pseudocode for the Monte Carlo Tests?

By working in combination with these two references, I am able to come up with a working encryption test for the MCT. The following code shows the working encrypt module (given an initial key, iv, and plaintext as hex strings):

def monte_carlo_encrypt(key_len, initial_key, initial_iv, initial_pt):

    key_array = []
    iv_array = []
    pt_array = []
    ct_array = []

    key_array.append(bytes.fromhex(initial_key))
    iv_array.append(bytes.fromhex(initial_iv))
    pt_array.append(bytes.fromhex(initial_pt))

    for j in range(0, 1000):
        if j == 0:
            ct = encrypt(key_array[0], iv_array[0], pt_array[j])
            ct_array.append(ct)
            pt_array.append(iv_array[0])
        else:
            ct = encrypt(key_array[0], ct_array[j - 1], pt_array[j])
            ct_array.append(ct)
            pt_array.append(ct_array[j - 1])

    if key_len == 128:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], ct_array[j])))
    elif key_len == 256:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], ct_array[j - 1] + ct_array[j])))

    iv_array.append(ct_array[-1])
    pt_array.clear()
    pt_array.append(ct_array[-2])

    return key_array[-1], iv_array[-1], pt_array[-1], ct_array[-1]
                    
for k in range(0, 100):
    (next_key, next_iv, next_pt, next_ct) = monte_carlo_encrypt(key_len * 8,
                                                                key.hex().upper(),
                                                                iv.hex().upper(),
                                                                given_pt.hex().upper())

     key = next_key
     iv = next_iv
     given_pt = next_pt

The above test produces the correct results, which can be tested with the standards outlined in the stackoverflow question linked above.

Now the issue comes up when I try to adapt this for decryption. According to the NIST reference, "The pseudocode for
decryption can be obtained by replacing all PT’s with CT’s and all CT’s with PT’s. "

So, I tried that, and came up with this:

def monte_carlo_decrypt(key_len, initial_key, initial_iv, initial_ct):

    key_array = []
    iv_array = []
    pt_array = []
    ct_array = []

    key_array.append(bytes.fromhex(initial_key))
    iv_array.append(bytes.fromhex(initial_iv))
    ct_array.append(bytes.fromhex(initial_ct))

    for j in range(0, 1000):
        if j == 0:
            pt = decrypt(key_array[0], iv_array[0], ct_array[j])
            pt_array.append(pt)
            ct_array.append(iv_array[0])
        else:
            pt = decrypt(key_array[0], pt_array[j - 1], ct_array[j])
            pt_array.append(pt)
            ct_array.append(pt_array[j - 1])

    if key_len == 128:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], pt_array[j])))
    elif key_len == 256:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], pt_array[j - 1] + pt_array[j])))

    iv_array.append(pt_array[-1])
    ct_array.clear()
    ct_array.append(pt_array[-2])

    return key_array[-1], iv_array[-1], pt_array[-1], ct_array[-1]

for k in range(0, 100):
    (next_key, next_iv, next_pt, next_ct) = monte_carlo_decrypt(key_len * 8,
                                                                key.hex().upper(),
                                                                iv.hex().upper(),
                                                                given_ct.hex().upper())
     key = next_key
     iv = next_iv
     given_ct = next_ct

But this decryption module gets the decryption wrong on the very first iteration. Given:

        "iv": "9982F2D532BC341791ECC30A1FEA9A3F",
        "key": "A58C28340553879F488E161CF815D104",
        "ct": "349F129B75B99E845D99090B26801D12"

It should produce:

            "key": "A58C28340553879F488E161CF815D104",
            "iv": "9982F2D532BC341791ECC30A1FEA9A3F",
            "pt": "9B2F1D63DE3809F47E40EFB885F01277",
            "ct": "349F129B75B99E845D99090B26801D12"

But mine produces:

                            "key": "A58C28340553879F488E161CF815D104",
                            "iv": "9982F2D532BC341791ECC30A1FEA9A3F",
                            "pt": "23119C0130042FDA973D171E9E9E4921",
                            "ct": "349F129B75B99E845D99090B26801D12"

Does anyone see where I went wrong with my decryption implementation?

Looks like an accidental swap of ct and pt: `pt_array[-1]` is returned as `next_ct` and `ct_array[-1]` as `next_pt`. — Topaco, Oct 18 '21 at 12:44
Good catch, that was a mistake in the code I pasted above. I had actually fixed it in the code I was testing on my system, but forgot to update my original code. Unfortunately, I am still running into the same issue. I've updated the code accordingly to correct for the mistake you pointed out though, thank you. The results are unchanged, as the original results I posted are from the code without this error. — factor2, Oct 18 '21 at 13:13
In addition, the key calculation must be changed for decryption. Furthermore, for decryption, the last IV of the inner (1000) loop for encryption is to be used as the start IV. S. online, encryption and decryption: https://replit.com/@3hK8cL8H24hwiS7/PutridBusyCheckpoint — Topaco, Oct 18 '21 at 22:37
Thanks for your help Topaco. Your code worked for me if I started with the encrypt function, and fed the results back into the decrypt function. However, starting with the decryption test vectors given (not the results from my encrypt function) I still ended up getting the wrong answer. However, I ended up figuring out the algorithm, see my answer below if your interested. Thanks again for your help! — factor2, Oct 19 '21 at 16:20
Yes. Conversely, I cannot decrypt the test vector/ciphertext from the [NIST document](https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/aes/AESAVS.pdf) using the decryption function from your answer. So this algorithm seems to be different from the algorithm of the NIST document and the test vectors you applied are compatible to the algorithm you used, but not to that of the NIST document. But anyway, your test vectors are satisfied and that's probably what matters to you. — Topaco, Oct 19 '21 at 19:19
I wish there was better standardization/consistency between all these vectors. It's a complicated subject to begin with, and conflicting documentation makes it so much worse! — factor2, Oct 21 '21 at 13:06

score 0 · Accepted Answer · answered Oct 19 '21 at 16:18

I figured out the answer. I found this reference, which was much more helpful in terms of pseudocode than the NIST reference: https://www.ipa.go.jp/security/jcmvp/jcmvp_e/documents/atr/atr01b_en.pdf section 3.4.3.2.2

Here is the working decrypt code:

def monte_carlo_decrypt(key_len, initial_key, initial_iv, initial_ct):

    key_array = []
    iv_array = []
    pt_array = []
    ct_array = []

    key_array.append(bytes.fromhex(initial_key))
    iv_array.append(bytes.fromhex(initial_iv))
    ct_array.append(bytes.fromhex(initial_ct))

    for j in range(0, 1000):
        pt = decrypt(key_array[0], iv_array[j], ct_array[j])
        pt_array.append(pt)
        if j == 0:
            tmp = ct_array[j]
            ct_array.append(iv_array[j])
            iv_array.append(tmp)
        else:
            iv_array.append(ct_array[j])
            ct_array.append(pt_array[j - 1])

    if key_len == 128:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], pt_array[j])))
    elif key_len == 256:
        key_array.append(bytes(a ^ b for a, b in zip(key_array[0], pt_array[j - 1] + pt_array[j])))

    iv_array.append(pt_array[-1])
    ct_array.clear()
    ct_array.append(pt_array[-2])

    return key_array[-1], iv_array[-1], pt_array[-1], ct_array[-1]

for k in range(0, 100):
    (next_key, next_iv, next_pt, next_ct) = monte_carlo_encrypt(key_len * 8,
                                                            key.hex().upper(),
                                                            iv.hex().upper(),
                                                       given_pt.hex().upper())
    key = next_key
    iv = next_iv
    given_pt = next_pt

AES CBC decryption validation for Monte Carlo Tests

1 Answers1