34
\$\begingroup\$

I've implemented AES (128, 192 and 256) in C++ and I'm looking to improve the code to make it not "DIY-crypto-bad", if at all possible. I've also been trying to optimize my code, and so far I've gotten it to the point where I can encrypt a 10MB webm file in about 3s.

Here's the output of my small "Benchmarking" program:

Read file, filesize 10878713B, 10.3747MB
Done padding
Encryption of 10878713B (10.3747MB) took 3759.78ms
Average speed of 2.7594MB/s
Decryption of 10878713B (10.3747MB) took 3305.84ms
Average speed of 3.13831MB/s

The file is being encrypted in CBC mode. For my Galois multiplications, I've used lookup-tables as calculating them took a very long time. I'm padding the file by inserting the amount of needed padding bytes after the data (PKCS7, if I'm not mistaken).

AES.hpp:

/**
 *  @author thomas
 *  @date   01/11/17.
 */

#ifndef AES_HPP
#define AES_HPP

#include <cstring>

//#include <array>
#include <iostream>
#include <vector>

#include <BlockCipher/BlockCipher.hpp>
#include <Util/Types.hpp>
#include <Util/Util.hpp>

namespace Crypto
{
    class AES : public BlockCipher
    {
        private:
            constexpr static uint8 S_BOX [256] =
            {
                    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
                    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
                    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
                    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
                    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
                    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
                    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
                    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
                    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
                    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
                    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
                    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
                    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
                    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
                    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
                    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
            };

            constexpr static uint8 INV_S_BOX [256] =
            {
                    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
                    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
                    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
                    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
                    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
                    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
                    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
                    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
                    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
                    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
                    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
                    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
                    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
                    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
                    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
                    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
            };

            constexpr static uint8 RCON [11] = {0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36};

            void KeyExpansion(const uint8 key [], uint8 expandedKey[]) const;

            static void KeyScheduleCore (uint8 roundNumber, const uint8 keyIn[4], uint8 keyOut[4]);

            static void AddRoundKey (uint8 state[4][4], const uint8 roundKey[4][4]);

            static void SubBytes (uint8 state[4][4]);

            static void ShiftRows (uint8 state[4][4]);

            static void MixColumns (uint8 state[4][4]);

            static void InvSubBytes (uint8 state[4][4]);

            static void InvShiftRows (uint8 state[4][4]);

            static void InvMixColumns (uint8 state[4][4]);

        public:
            AES () = delete;

            explicit AES (uint16 keyLen);

            explicit AES (const BlockCipher& blockCipher);

            explicit AES (const AES& aes);

            void encrypt(const uint8 input[], const uint8 key[], uint8 output[]) const override;

            void decrypt(const uint8 input[], const uint8 key[], uint8 output[]) const override;
    };
}

#endif // AES_HPP

And here's the implementation:

/**
 *  @author thomas
 *  @date   01/11/17.
 */

#include <BlockCipher/AES.hpp>

namespace Crypto
{
    AES::AES(uint16 keyLen) : BlockCipher ("AES-" + std::to_string(keyLen), keyLen, 128/8) {}

    AES::AES(const BlockCipher& blockCipher) : BlockCipher (blockCipher) {}

    AES::AES(const AES& aes) : BlockCipher (aes) {}

    void AES::encrypt(const uint8 input[], const uint8 key[], uint8 output[]) const
    {
        /*
         * Initial Set-up phase.
         * Setting some variables like maximum iterators, sizes, IV's, ...
         */

        int8 numRounds = 0;
        uint8 state [4][4]=
        {   {input[0], input[4], input[8], input[12]},
            {input[1], input[5], input[9], input[13]},
            {input[2], input[6], input[10], input[14]},
            {input[3], input[7], input[11], input[15]}  };

        uint8 expandedKeyLength = 0;

        switch (this->keyLen)
        {
            case 128:
            {
                numRounds = 10;
                expandedKeyLength = 176;    // We need 176 bytes, we store blocks of 4 bytes, so 176 / 4
                break;
            }

            case 192:
            {
                numRounds = 12;
                expandedKeyLength = 208;    // We need 208 bytes, we store blocks of 4 bytes, so 208 / 4
                break;
            }

            case 256:
            {
                numRounds = 14;
                expandedKeyLength = 240;    // We need 240 bytes, we store blocks of 4 bytes, so 240 / 4
                break;
            }
            default:
            {
                throw std::runtime_error("Invalid key length, must be 128 bits, 192 bits or 256 bits for AES.");
            }
        }

        uint8 expandedKey [expandedKeyLength];
        this->KeyExpansion(key, expandedKey);

        /*
         * Encryption
         */

        uint8 roundKey [4][4]=
        {   {expandedKey[0], expandedKey[4], expandedKey[8], expandedKey[12]},
            {expandedKey[1], expandedKey[5], expandedKey[9], expandedKey[13]},
            {expandedKey[2], expandedKey[6], expandedKey[10], expandedKey[14]},
            {expandedKey[3], expandedKey[7], expandedKey[11], expandedKey[15]}  };

        AES::AddRoundKey (state, roundKey);

        for (int8 roundCounter = 1; roundCounter <= numRounds; roundCounter++)
        {
            // Can't memcpy this because it involves a transposition
            for (uint8 i = 0; i < 4; i++)
            {
                for (uint8 j = 0; j < 4; j++)
                {
                    roundKey[i][j] = expandedKey[(roundCounter * this->blockSize) + (j * 4) + i];
                }
            }

            AES::SubBytes(state);

            AES::ShiftRows(state);

            if (roundCounter != numRounds)
            {
                // Apply MixColumns in all rounds but the last
                AES::MixColumns(state);
            }

            AES::AddRoundKey(state, roundKey);
        }

        // Copying final state to output
        for (uint8 i = 0; i < 4; i++)
        {
            for (uint8 j = 0; j < 4; j++)
            {
                output[(j * 4) + i] = state[i][j];
            }
        }
    };

    void AES::decrypt(const uint8 input[], const uint8 key[], uint8 output[]) const
    {
        /*
         * Initial Set-up phase.
         * Setting some variables like maximum iterators, sizes, IV's, ...
         */

        int8 numRounds = 0;
        uint8 state [4][4]=
        {   {input[0], input[4], input[8], input[12]},
            {input[1], input[5], input[9], input[13]},
            {input[2], input[6], input[10], input[14]},
            {input[3], input[7], input[11], input[15]}  };
        uint8 expandedKeyLength = 0;

        switch (this->keyLen)
        {
            case 128:
            {
                numRounds = 10;
                expandedKeyLength = 176;    // We need 176 bytes, we store blocks of 4 bytes, so 176 / 4
                break;
            }

            case 192:
            {
                numRounds = 12;
                expandedKeyLength = 208;    // We need 208 bytes, we store blocks of 4 bytes, so 208 / 4
                break;
            }

            case 256:
            {
                numRounds = 14;
                expandedKeyLength = 240;    // We need 240 bytes, we store blocks of 4 bytes, so 240 / 4
                break;
            }
            default:
            {
                throw std::runtime_error("Invalid key length, must be 128 bits, 192 bits or 256 bits for AES.");
            }
        }

        uint8 expandedKey [expandedKeyLength];
        this->KeyExpansion(key, expandedKey);

        uint8 roundKey [4][4]=
        {   {expandedKey[expandedKeyLength - 16], expandedKey[expandedKeyLength - 12], expandedKey[expandedKeyLength - 8], expandedKey[expandedKeyLength - 4]},
            {expandedKey[expandedKeyLength - 15], expandedKey[expandedKeyLength - 11], expandedKey[expandedKeyLength - 7], expandedKey[expandedKeyLength - 3]},
            {expandedKey[expandedKeyLength - 14], expandedKey[expandedKeyLength - 10], expandedKey[expandedKeyLength - 6], expandedKey[expandedKeyLength - 2]},
            {expandedKey[expandedKeyLength - 13], expandedKey[expandedKeyLength - 9], expandedKey[expandedKeyLength - 5], expandedKey[expandedKeyLength - 1]}   };

        AES::AddRoundKey(state, roundKey);

        /*
         *  Decryption
         */

        for (int8 roundCounter = (int8)(numRounds - 1); roundCounter >= 0; roundCounter--)
        {
            // Can't memcpy this because it involves a transposition
            for (uint8 i = 0; i < 4; i++)
            {
                for (uint8 j = 0; j < 4; j++)
                {
                    roundKey[i][j] = expandedKey[(roundCounter * this->blockSize) + (4 * j)  + i];
                }
            }

            AES::InvShiftRows(state);

            AES::InvSubBytes(state);

            AES::AddRoundKey(state, roundKey);

            if (roundCounter != 0)
            {
                // Apply MixColumns in all rounds but the first
                AES::InvMixColumns(state);
            }
        }

        // Copying final state to output
        for (uint8 i = 0; i < 4; i++)
        {
            for (uint8 j = 0; j < 4; j++)
            {
                output[(j * 4) + i] = state[i][j];
            }
        }
    }

    void AES::KeyExpansion(const uint8 key [], uint8 expandedKey[]) const
    {
        uint8 initialKeyLength = 0;
        uint8 expandedKeyLength = 0;
        uint8 n = 0;
        uint8 m = 0;

        switch (this->keyLen)
        {
            case 128:
            {
                n = 16;
                m = 0;
                initialKeyLength = 16;
                expandedKeyLength = 176;    // We need 176 bytes, we store blocks of 4 bytes, so 176 / 4
                break;
            }

            case 192:
            {
                n = 24;
                m = 2;
                initialKeyLength = 24;
                expandedKeyLength = 208;    // We need 208 bytes, we store blocks of 4 bytes, so 208 / 4
                break;
            }

            case 256:
            {
                n = 32;
                m = 3;
                initialKeyLength = 32;
                expandedKeyLength = 240;    // We need 240 bytes, we store blocks of 4 bytes, so 240 / 4
                break;
            }
            default:
            {
                throw std::runtime_error("Invalid key length, must be 128 bits, 192 bits or 256 bits for AES.");
            }
        }

        uint8 keySizeIterator = 0;

        memset(expandedKey, 0, expandedKeyLength);
        memcpy(expandedKey, key, initialKeyLength);

        keySizeIterator += initialKeyLength;

        // Start generating new words
        for (uint8 rconIterator = 1; keySizeIterator < expandedKeyLength; rconIterator++)
        {
            uint8 t [4];
            memcpy(t, expandedKey + (keySizeIterator - 4), 4);  // Get previous 4 bytes

            uint8 g [4];
            KeyScheduleCore(rconIterator, t, g);

            memcpy(t, expandedKey + (keySizeIterator - n), 4 * sizeof(uint8));

            // todo: cast-interpret as 4-byte pointer to reduce to a single XOR operation
            for (uint8 i = 0; i < 4; i++)
            {
                t[i] ^= g[i];
            }

            memcpy(expandedKey + keySizeIterator, t, 4 * sizeof(uint8));
            keySizeIterator += 4;

            for (uint8 i = 0; (i < 3) && (keySizeIterator < expandedKeyLength); i++)
            {
                memcpy(t, expandedKey + (keySizeIterator - 4), 4 * sizeof(uint8));

                uint32* resultPtr = (uint32*)(expandedKey + keySizeIterator);
                uint32* tPtr = (uint32*)t;
                uint32* rhsPtr = (uint32*)(expandedKey + keySizeIterator - n);

                *resultPtr = *tPtr ^ *rhsPtr;
                /*
                for (uint8 j = 0; j < 4; j++)
                {
                    expandedKey[keySizeIterator + j] = t[j] ^ expandedKey[keySizeIterator - n + j];
                }
                */

                keySizeIterator += 4;
            }

            if ((this->keyLen == 256)  && (keySizeIterator < expandedKeyLength))
            {
                memcpy(t, expandedKey + (keySizeIterator - 4), 4 * sizeof(uint8));  // Get previous 4 bytes

                for (uint8 i = 0; i < 4; i++)
                {
                    t[i] = S_BOX[t[i]];
                }

                uint32* resultPtr = (uint32*)(expandedKey + keySizeIterator);
                uint32* tPtr = (uint32*)t;
                uint32* rhsPtr = (uint32*)(expandedKey + keySizeIterator - n);

                *resultPtr = *tPtr ^ *rhsPtr;

                /*
                for (uint8 i = 0; i < 4; i++)
                {
                    expandedKey[keySizeIterator + i] = t[i] ^ expandedKey[keySizeIterator - n + i];
                    //t[i] ^= expandedKey[keySizeIterator - n - 4 + i];
                }
                */

                //memcpy(expandedKey + (keySizeIterator - 3 - 1), t, 4 * sizeof(uint8));
                keySizeIterator += 4;
            }

            for (uint8 i = 0; (i < m) && (keySizeIterator < expandedKeyLength); i++)
            {
                memcpy(t, expandedKey + (keySizeIterator - 4), 4 * sizeof(uint8));  // Get previous 4 bytes

                uint32* resultPtr = (uint32*)(expandedKey + keySizeIterator);
                uint32* tPtr = (uint32*)t;
                uint32* rhsPtr = (uint32*)(expandedKey + keySizeIterator - n);

                *resultPtr = *tPtr ^ *rhsPtr;

                /*
                for (uint8 j = 0; j < 4; j++)
                {
                    expandedKey[keySizeIterator + j] = t[j] ^ expandedKey[keySizeIterator - n + j];
                }
                */
                keySizeIterator += 4;
            }
        }
    }

    void AES::KeyScheduleCore(uint8 roundNumber, const uint8 keyIn[4], uint8 keyOut[4])
    {
        //todo memcpy
        //for (uint8 i = 0; i < 4; i++)
        //{
        //  keyOut[i] = keyIn[i];
        //}
        memcpy(keyOut, keyIn, 4);
        //keyOut = keyIn;

        // Rotate
        uint8 tmp = keyOut[0];

        for (uint8 i = 0; i < 3; i++)
        {
            keyOut[i] = keyOut[i+1];
        }

        keyOut[3] = tmp;

        // Substitute
        for (uint8 i = 0; i < sizeof(uint32); i++)
        {
            keyOut[i] = AES::S_BOX[keyOut[i]];
        }

        // Apply RCON to rightmost byte
        keyOut[0] = keyOut[0] ^ RCON[roundNumber];
    }

    void AES::AddRoundKey(uint8 state[4][4], const uint8 roundKey[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            uint32* keyPtr = (uint32*) roundKey[i];
            uint32* statePtr = (uint32*) state[i];
            *statePtr ^= *keyPtr;
            /*
            for (uint8 j = 0; j < 4; j++)
            {
                state[i][j] ^= roundKey[i][j];
            }
             */
        }
    }

    void AES::SubBytes(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            for (uint8 j = 0; j < 4; j++)
            {
                state[i][j] = AES::S_BOX[state[i][j]];
            }
        }
    }

    void AES::ShiftRows(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            if (i > 0)
            {
                uint8 row [4];
                for (uint8 j = 0; j < 4; j++)
                {
                    row[j] = state[i][j];
                }

                for (uint8 j = 0; j < 4; j++)
                {
                    state[i][j] = row[(i + j) % 4]; // I got this formula by first writing down all shifts
                                                    // And then collapsing/generalizing them piece-by-piece
                }
            }
        }
    }

    void AES::MixColumns(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            uint8 col [4] = {state[0][i], state[1][i], state[2][i], state[3][i]};

            state[0][i] = GALOIS_TABLE_2[col[0]] ^ GALOIS_TABLE_3[col[1]] ^ col[2] ^ col[3];
            state[1][i] = col[0] ^ GALOIS_TABLE_2[col[1]] ^ GALOIS_TABLE_3[col[2]] ^ col[3];
            state[2][i] = col[0] ^ col[1] ^ GALOIS_TABLE_2[col[2]] ^ GALOIS_TABLE_3[col[3]];
            state[3][i] = GALOIS_TABLE_3[col[0]] ^ col[1] ^ col[2] ^ GALOIS_TABLE_2[col[3]];
        }
    }

    void AES::InvSubBytes(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            for (uint8 j = 0; j < 4; j++)
            {
                state[i][j] = INV_S_BOX[state[i][j]];
            }
        }
    }

    void AES::InvShiftRows(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            if (i > 0)
            {
                uint8 row [4];
                for (uint8 j = 0; j < 4; j++)
                {
                    row[j] = state[i][j];
                }

                for (int8 j = 3; j >= 0; j--)
                {
                    state[i][j] = row[(j + (4- i)) % 4];
                }
            }
        }
    }

    void AES::InvMixColumns(uint8 state[4][4])
    {
        for (uint8 i = 0; i < 4; i++)
        {
            uint8 col [4] = {state[0][i], state[1][i], state[2][i], state[3][i]};

            state[0][i] = GALOIS_TABLE_14[col[0]] ^ GALOIS_TABLE_11[col[1]] ^ GALOIS_TABLE_13[col[2]] ^ GALOIS_TABLE_9[col[3]];
            state[1][i] = GALOIS_TABLE_9[col[0]] ^ GALOIS_TABLE_14[col[1]] ^ GALOIS_TABLE_11[col[2]] ^ GALOIS_TABLE_13[col[3]];
            state[2][i] = GALOIS_TABLE_13[col[0]] ^ GALOIS_TABLE_9[col[1]] ^ GALOIS_TABLE_14[col[2]] ^ GALOIS_TABLE_11[col[3]];
            state[3][i] = GALOIS_TABLE_11[col[0]] ^ GALOIS_TABLE_13[col[1]] ^ GALOIS_TABLE_9[col[2]] ^ GALOIS_TABLE_14[col[3]];
        }
    }
}

I've verified the correctness of my implementation using NIST test vectors, used ECB vectors for verifying the actual algorithm and used the CBC vectors to verify that my CBC is working correctly) and catch unit tests.

I should note that I would like to avoid using the AES-NI processor extension. I know it can speed up my implementation quite a bit, but it would defeat the purpose of implementing it in the first place.

NOTE: This code is not intended for professional use. It is a personal project, but since people are always saying it's almost impossible to "do crypto right", I figured I'd give it a go.

I was linking my Release-Build-Performance-Tester to a Debug-Built version of my library, which resulted in a debug-version of my Performance tester, After building my library as a release build. This is the performance I get:

Read file, filesize 10878713B, 10.3747MB
Done padding
Encryption of 10878713B (10.3747MB) took 929.581ms
Average speed of 11.1607MB/s
Decryption of 10878713B (10.3747MB) took 764.709ms
Average speed of 13.5669MB/s
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Nov 9 '17 at 14:57
  • \$\begingroup\$ This is an old thread so I don't know if you are monitoring it anymore. But can you elaborate on what you said? "I should note that I would like to avoid using the AES-NI processor extension. I know it can speed up my implementation quite a bit, but it would defeat the purpose of implementing it in the first place." \$\endgroup\$ – Neil Weicher Apr 9 '18 at 22:07
  • \$\begingroup\$ There's x86 assembly instructions that perform AES, Thesd are called the AES-NI instructions, they are much faster than a/my software implementation (upwards of 700MB/s), But if I used them, well..., I wouldn't be implementing AES, I'd just be using Intel's implementation. Here's some info on AES-NI: en.m.wikipedia.org/wiki/AES_instruction_set \$\endgroup\$ – shmoo6000 Apr 9 '18 at 22:14
  • \$\begingroup\$ Maybe I'm missing something, but unless you are implementing AES just as an exercise, why wouldn't you take advantage of the hardware acceleration if supported? Is it more vulnerable to certain attacks? \$\endgroup\$ – Neil Weicher Apr 10 '18 at 7:52
  • \$\begingroup\$ You're completely right, if your platform supports these extensions and you're writing production code, you should use the AES-NI extensions. I was implementing AES for the fun of it though ('as an exercise'), so using the extensions would defeat the whole point of implementing AES in the first place \$\endgroup\$ – shmoo6000 Apr 10 '18 at 7:55
21
\$\begingroup\$

I'm looking to improve the code to make it not "DIY-crypto-bad", if at all possible

I work in security. This is not my area, but I have a non-zero amount of knowledge on implementing secure cryptographic primitives, and from a cursory look I found some issues.

For starters:

keyOut[i] = AES::S_BOX[keyOut[i]];

and

state[i][j] = AES::S_BOX[state[i][j]];

and

state[i][j] = INV_S_BOX[state[i][j]];

You are indexing into an array using secret information, which means that your memory accesses and cache timings will vary depending on this secret information. An attacker can measure your execution time (or power consumption) to steal such information. This is called a "side channel attack".

Also, note that AES+CBC without an HMAC is not sufficient in most cases. You still need a way to ensure integrity, i.e. the decrypted plaintext has not been tampered. People naively think that any change to the ciphertext will completely garble the decrypted plaintext, but this is not actually true for CBC. For example, if you flip one bit in a block, it'll indeed garble that block, but the next block will be ok except for having a flipped bit in the same position. Here's an exercise where the goal is to change the text inside a ciphertext without having the key.

On the same vein of not checking for integrity, there's also the Padding Oracle Attack that enables an attacker to completely decrypt a ciphertext only by submitting ciphertexts and observing if the padding was correct or not.

There may or may not be other errors, but this is a good place to start. If you want more examples on how cryptosystems get broken, I recommend the Cryptopals Challenge. It's very hands-on and an eye opener on why DIY-crypto is hard.

EDIT: I see some answers in the chat suggesting that the timing attacks should be protected by using threads that sleep for a fixed amount of time. I don't think that's sound, and I've never seen it done in verified implementations. Here's a question from crypto.stackexchange on how to properly protect yourself from this.

\$\endgroup\$
25
\$\begingroup\$

Since there are only three valid key sizes for AES, it makes sense to not even let the AES class be instantiated with any uint16 value. I would introduce an enum similar to this:

enum class AesKeyLen
{
    Aes128,
    Aes192,
    Aes256
};

And then change the uint16 constructor to this:

explicit AES (AesKeyLen keyLen);

Sure, they could still pass bad values, but they have to try harder by explicitly creating an invalid enum value. Also, making it a scoped enum provides extra type-safety and prevents naming clashes.

Either way, I think it makes sense to throw out of the constructor immediately if the key length is wrong instead of waiting until the encrypt function.

If you want to enforce a valid value at compile-time, you can use a static_assert, or you can use a smart-enum pattern. This is an example hacked together real quick:

class AesKeyLen
{    
private:
    uint16 _length;

    AesKeyLen(uint16 len)
    {
        _length = len;
    }

public:
    uint16 length()
    {
        return _length;
    }

    static AesKeyLen Aes128()
    {
        return AesKeyLen(128);
    }

    static AesKeyLen Aes192()
    {
        return AesKeyLen(192);
    }

    static AesKeyLen Aes256()
    {
        return AesKeyLen(256);
    }
};

And then replace the uint16 constructor again:

explicit AES (AesKeyLen keyLen);
\$\endgroup\$
  • 2
    \$\begingroup\$ There is little point moving to static constructors over a single enum-constructor: if someone is foolish enough to try and circumvent the enum, they are foolish enough to overwrite the memory in your class instance. Also known as You can protect against Murphy, but not against Machiavelli. \$\endgroup\$ – Matthieu M. Nov 9 '17 at 10:35
  • 2
    \$\begingroup\$ Integers are never implicitly cast even into unscoped enums (unlike enum-to-int casts) — this was since the first C++ standard. You must be confusing with the C behavior, where casts in both directions are implicit. \$\endgroup\$ – Ruslan Nov 9 '17 at 19:19
14
\$\begingroup\$

Interface Design:

        void encrypt(const uint8 input[], const uint8 key[], uint8 output[]) const override;

        void decrypt(const uint8 input[], const uint8 key[], uint8 output[]) const override;

Your encrypt and decrypt is very limiting. This means you need to load the whole of your input into memory before you can start any operations. It would be nicer to have a stream/iterator like interface that allowed you simply read the data as needed.

        void encrypt(std::istream& input, const uint8 key[], std::ostream& output) const override;

        void decrypt(std::istream& input, const uint8 key[], std::ostream& output) const override;

Coding wise there is nothing really interesting to comment on. It looks pretty bog standard simple code. I don't see any clear performance killers.

\$\endgroup\$
  • 2
    \$\begingroup\$ You're right that I need to load the whole of my input into memory, but AES works on 128 bit (16 byte) blocks. Is that really so bad? It wouldn't work on a stream anyway because it needs those 16 bytes to work. If you want AES to work like a stream (cipher) you need another mode of operation (I believe this is possible in CFB and OFB) \$\endgroup\$ – shmoo6000 Nov 8 '17 at 20:07
  • 2
    \$\begingroup\$ Why can't you just read 16 bytes from the stream at a time. Encrypt/Decrypt write the resulting value to the output. Repeat until end of stream. \$\endgroup\$ – Martin York Nov 8 '17 at 22:55
  • 1
    \$\begingroup\$ I don't see how providing the data via a stream or a static array changes how an internal encryption mode is set! This is just a way to get the data into the algorithm. \$\endgroup\$ – Martin York Nov 9 '17 at 2:49
  • 2
    \$\begingroup\$ @Loki, you're right that being able to use a cipher with C++ streams would be very useful. I disagree with you that including that functionality at this level would be a good thing. To my mind, that's something that would make a nice next-layer interface, making use of block-cipher primitives and providing the chaining and padding needed to make a stream-cipher. I'd definitely want to keep its implementation away from the details of implementing the block cipher. \$\endgroup\$ – Toby Speight Nov 9 '17 at 8:25
  • 2
    \$\begingroup\$ @LokiAstari: I think you're misunderstanding the usage of encrypt as well; see my comment immediately above. I suppose the real lesson for the OP to learn from this answer is "you should document your functions". \$\endgroup\$ – Hurkyl Nov 10 '17 at 13:18
13
\$\begingroup\$

I think the header could be trimmed down a lot. The constant tables belong in the implementation file since they are not needed for the definition of the class.

Since the AES class does not hold any state (except for that inherited from BlockCipher), I would not declare the private functions in the header, but only keep them in the implementation file in an anonymous namespace.

The code for (i = 0; i < n; i++) if (i > 0) can be written shorter, as for (i = 1; ….

\$\endgroup\$
  • \$\begingroup\$ I also thought about making the private static methods just regular static functions, but I didn't want to pollute the "Crypto" namespace with functions that shouldn't be accessed by anyone but the AES algorithm. I thought about creating an "AES" namespace, but that created naming conflicts, instead of renaming it to "AES_Utils" or something, I just decided to make the functions private methods. Edit: I just noticed you said "static" functions, so no namespace pollution in that case, That might actually be a good idea, thanks!" \$\endgroup\$ – shmoo6000 Nov 8 '17 at 21:09
  • 1
    \$\begingroup\$ If you look at the KeyExpansion, you can see that it uses the value "rconIterator" for the KeyScheduleCore. rconIterator is raised by one every "round" of key expansion. In a round of key expansion for AES128, you add 16 bytes, for AES192 you add 24 bytes, for AES256 you add 32 bytes. This confirms Wikipedia, in that you need less RCON values for longer keys: "Only the first some of these constants are actually used – up to rcon[10] for AES-128 (as 11 round keys are needed), up to rcon[8] for AES-192, up to rcon[7] for AES-256." (en.wikipedia.org/wiki/Rijndael_key_schedule#Rcon) \$\endgroup\$ – shmoo6000 Nov 8 '17 at 21:13
  • \$\begingroup\$ Ah, thanks, it's confusing when the term round is used with two different meanings in the same algorithm. :) \$\endgroup\$ – Roland Illig Nov 8 '17 at 22:38
  • 5
    \$\begingroup\$ Instead of static functions, anonymous namespace should be used since we are talking about C++. \$\endgroup\$ – n0rd Nov 9 '17 at 1:26
11
\$\begingroup\$

You don't show us the BlockCipher base class, but it appears that it imposes a terrible interface on us:

void encrypt(const uint8 input[], const uint8 key[], uint8 output[])
    const override;

void decrypt(const uint8 input[], const uint8 key[], uint8 output[])
    const override;

I'm assuming that uint8 is a simple typedef of std::uint8_t (though not sure why you don't go the whole hog and call it u8 as many abbreviators do).

The problem here is that we don't get any compile-time checking of the correctness of the arguments. As our input and output block sizes are fixed at 128 bits, I'd expect something more like:

void encrypt(const uint8 (&input)[16], const uint8 key[], uint8 (&output)[16])
    const override;
// and a similar decrypt

Or possibly even

void encrypt(const InputBlock& input, const Key& key, OutputBlock& output)
    const override;

where the array types can be defined by BlockCipher if it's declared as

class BlockCipher<std::size_t KeySize,
                  std::size_t InputSize,
                  std::size_t OutputSize = InputSize>
\$\endgroup\$
4
\$\begingroup\$

As other have said, an AES implementation should also be secured against timing/cache attacks and other fun side-channels.

And as explained in the linked crypto.SE QA, you should typically avoid all non-constant operations on secret data, and yet currently you're relying on table lookups as explained in BoppreH's answer, as anybody implementing AES from scratch would.
But those are not constant-time.

I recommend you read that link, which talks about a constant time implementation of AES. As explained there, the usual way to obtain a constant-time AES implementation is to perform "bit-slicing". Bit-slicing implies working at the bit level, with bitwise operations that are directly constant-time and to basically build an "AES" boolean circuit and translate it into C(++) code.
Yet, this is not the only way, since the table is just a memoized function in the end, you could also compute the function explicitly at each iteration, if you do not care much about performances.

Finally you might be asking yourself why it is always a bad idea to roll your own crypto and to publish it on the net, that is mostly because you'll end up with other people able to take your implementation to do their stuff without caring about the security implications...
For example, the Matrix's OLM library is relying on a non constant time AES implementation, even if its creator, Brad Conte, actually said about it that:

"Note that these are not cryptographically secure implementations."

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.