1
$\begingroup$

Problem

I'm working on an AES implementation in C++, and I have been testing the performance of my code, and its functions. I've noticed a significant performance slowdown in my 'addRoundKey' function. The time it takes to complete the 'addRoundKey' function seems to scale linearly, i.e. if I give it 1mb it takes ~650ms, if I give it 5mb it takes ~3,400ms.

Context

I am not using a AES Library, I am using my own code. To test my code I have been using Google Test to ensure correctness, but also using its execution time to "benchmark" my functions. For each of the function tests below, they take an input of 1mb size. Here are to outputs for the AES function test:

[----------] 7 tests from TestAesFunctions
[ RUN      ] TestAesFunctions.SubByte
[       OK ] TestAesFunctions.SubByte (23 ms)
[ RUN      ] TestAesFunctions.shiftRows
[       OK ] TestAesFunctions.shiftRows (26 ms)
[ RUN      ] TestAesFunctions.mixColumns
[       OK ] TestAesFunctions.mixColumns (34 ms)
[ RUN      ] TestAesFunctions.addRoundKey
[       OK ] TestAesFunctions.addRoundKey (650 ms)
[ RUN      ] TestAesFunctions.invSubByte
[       OK ] TestAesFunctions.invSubByte (21 ms)
[ RUN      ] TestAesFunctions.invShiftRows
[       OK ] TestAesFunctions.invShiftRows (25 ms)
[ RUN      ] TestAesFunctions.invMixColumns
[       OK ] TestAesFunctions.invMixColumns (33 ms)
[----------] 7 tests from TestAesFunctions (819 ms total)

As you can see the 'addRoundKey' function has a significant time increase compared to the rest of the functions. This was unexpected as I would have though the 'addRoundKey' would be super fast because its just XOR, and I didn't think there would be any huge memory searches.

Here is the actual function so you can see:

void AES::addRoundKey(std::vector<unsigned char>& input, const std::vector<unsigned char> roundKey, size_t blockIndex, size_t round)
{
    for (size_t i = 0; i < 4 * Nb; i++) {
        input[blockIndex + i] ^= roundKey[round * Nb * 4 + i];
    }
}

Note that I am doing all my operations in place to hopefully increase performance by not needing to copy to a separate state array and doing the operations on that, then copying into an output. This the indexing could be a little hard to read. So here is where the function is used:

void AES::encryptBlock(std::vector<unsigned char>& input, const std::vector<unsigned char> roundKey, size_t blockIndex)
{
    addRoundKey(input, roundKey, blockIndex, 0);

    size_t round = 1;
    while (round < Nr) {
        subByte(input, blockIndex);
        shiftRows(input, blockIndex);
        mixColumns(input, blockIndex);
        addRoundKey(input, roundKey, blockIndex, round); // Update round key index for each round
        ++round;
    }

    subByte(input, blockIndex);
    shiftRows(input, blockIndex);
    addRoundKey(input, roundKey, blockIndex, round);
}

and Nb is a constant variable for the "number of blocks" so Nb = 4.

*edit: Here is the actual test for 'addRoundKey', here you can see the 1mb of data I am generating (which is multithreaded so it +~12ms to the test), and I am not testing for correctness as I can't if I am generating random data.


TEST(TestAesFunctions, addRoundKey) {
    AES aesObject;
    // Prepare input data
    std::vector<unsigned char> inputData = generateRandomData(1);
    std::vector<unsigned char> state = inputData;

    // Call the addRoundKey function and test
    for (size_t blockIndex = 0; blockIndex < state.size(); blockIndex += 16) {
        aesObject.addRoundKey(state, hexStringToBytesVec("10a58869d74be5a374cf867cfb473859"), blockIndex, 0);
    }

    // Check if the output matches the expected output
    EXPECT_EQ(true, true);
}

It should be fine to just use on 128-bit key as I am just using round = 0, so it should just keep reusing the same given key.

Questions

  1. Is there anything wrong with my approach that is hurting the performance, or is that expected for 'addRoundKey' to be the slowest part of AES?
  2. Are there any recommended optimizations or alternate approaches for 'addRoundKey' that could improve the efficiency?

Note that I want to keep the specifications that we are doing things in-place of my input vector.

Any insights, suggestions or optimizations that better explain this discrepancy is appreciated. Thanks for your help!

$\endgroup$
15
  • 1
    $\begingroup$ Here's a pair of timing experiments to try: (1) loop unroll, since there's only 16 iterations anyway; (2) tell XOR to read from two arrays and write to a third array, followed by memcpy() to put the result where it belongs. // Also, verify your arrays begin on cache-line alignment. And ask the compiler explorer about the code being generated by the optimizer switches you're providing. $\endgroup$
    – J_H
    Dec 9, 2023 at 19:45
  • 1
    $\begingroup$ When you are benchmarking addRoundKey, do you use the same input/roundKey/round input repeatedly, or do you use different inputs/roundKeys/allow round to increase beyond 11 or 15? One possibility (if you consistently use inputs from different memory locations) is that the benchmarks is seeing cache misses (which you likely won't see much of in the actual code). That is, your benchmark code might be giving you misleading results. $\endgroup$
    – poncho
    Dec 9, 2023 at 20:00
  • $\begingroup$ @poncho Yes I am using the same input (state), key, and in my addRoundKey test I am using a for loop to go though each block. I will add the test I made for addRoundKey to the question so you can see it. $\endgroup$
    – Lachlan
    Dec 9, 2023 at 20:07
  • $\begingroup$ Two things: 1) how fast is hexStringToBytesVec("10a58869d74be5a374cf867cfb473859") (and if it does dynamic allocation, how long does that allocation/deallocation take)? Is that's what taking up the time? 2) you increase blockIndex by 16 every iteration, and so likely you are running into cache misses. Either may be causing what you see... $\endgroup$
    – poncho
    Dec 9, 2023 at 20:13
  • $\begingroup$ @poncho I have not tested hexStringToBytesVec, but every other test uses it, so if that was the bottleneck we would probably see the same problem for each function. Also every other test has the same for loop and 16 blockIndex iteration as the inputs are the same structure and type. All other tests are basically the same except for the actual function call in the for loop. So if that were the case wouldn't we have the same cache miss in every test? Or is it special because we have two parameters (Input, roundKey) that addRoundKey has and the others don't? $\endgroup$
    – Lachlan
    Dec 9, 2023 at 20:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.