0

I am using Windows 11 and I plan to implement the code in C++. As you might know, building C++ libraries on Windows is very complicated, so I want to make sure it uses the least amount of dependencies possible.

For more context about the larger project this will be a part of, see this.

I have decided to implement a load-balancing ShadowSocks5 proxy in C++ from scratch. This is a programming challenge, a learning project, and a practical project all in one.

I decided to start from the easiest problem, the encryption I need to use is AES-256-GCM. GCM stands for Galois/Counter_Mode, I haven't figured out how to implement it from reading the Wikipedia article. But the Wikipedia article on Advanced Encryption Standard is very helpful and is one of the primary references I used in implementing this. Another Wikipedia article I referenced is AES key schedule. I got the values for SBOX and RSBOX from this article

Now, here is the implementation, I wrote it all by myself, an effort that took two days:

import json


with open("D:/AES_256.json", "r") as f:
    AES_256 = json.load(f)

MAX_256 = (1 << 256) - 1
SBOX = AES_256["SBOX"]
RCON = AES_256["RCON"]
OCTUPLE = (
    (0, 4),
    (4, 8),
    (8, 12),
    (12, 16),
    (16, 20),
    (20, 24),
    (24, 28),
    (28, 32),
)

SEXAGESY = (
    (0, 1, 2, 3),
    (4, 5, 6, 7),
    (8, 9, 10, 11),
    (12, 13, 14, 15),
    (16, 17, 18, 19),
    (20, 21, 22, 23),
    (24, 25, 26, 27),
    (28, 29, 30, 31),
    (32, 33, 34, 35),
    (36, 37, 38, 39),
    (40, 41, 42, 43),
    (44, 45, 46, 47),
    (48, 49, 50, 51),
    (52, 53, 54, 55),
    (56, 57, 58, 59),
)

HEXMAT = (0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15)
SHIFT = (0, 1, 2, 3, 5, 6, 7, 4, 10, 11, 8, 9, 15, 12, 13, 14)

COLMAT = (
    ((2, 0), (1, 4), (1, 8), (3, 12)),
    ((2, 1), (1, 5), (1, 9), (3, 13)),
    ((2, 2), (1, 6), (1, 10), (3, 14)),
    ((2, 3), (1, 7), (1, 11), (3, 15)),
    ((3, 0), (2, 4), (1, 8), (1, 12)),
    ((3, 1), (2, 5), (1, 9), (1, 13)),
    ((3, 2), (2, 6), (1, 10), (1, 14)),
    ((3, 3), (2, 7), (1, 11), (1, 15)),
    ((1, 0), (3, 4), (2, 8), (1, 12)),
    ((1, 1), (3, 5), (2, 9), (1, 13)),
    ((1, 2), (3, 6), (2, 10), (1, 14)),
    ((1, 3), (3, 7), (2, 11), (1, 15)),
    ((1, 0), (1, 4), (3, 8), (2, 12)),
    ((1, 1), (1, 5), (3, 9), (2, 13)),
    ((1, 2), (1, 6), (3, 10), (2, 14)),
    ((1, 3), (1, 7), (3, 11), (2, 15)),
)


def add_round_key(state: list, key: list) -> list:
    return [a ^ b for a, b in zip(state, key)]


def state_matrix(data: list) -> list:
    return [data[i] for i in HEXMAT]


def sub_bytes(state: list) -> list:
    return [SBOX[i] for i in state]


def shift_rows(state: list) -> list:
    return [state[i] for i in SHIFT]


def rot8(byte: int, x: int) -> int:
    x &= 7
    return (byte << x | byte >> (8 - x)) & 0xFF


def quadword(quad: bytes) -> int:
    a, b, c, d = quad
    return (a << 24) | (b << 16) | (c << 8) | d


def rot_word(word: int) -> int:
    return (word << 8 | word >> 24) & 0xFFFFFFFF


def sub_word(word: int) -> int:
    return (
        (SBOX[(word >> 24) & 0xFF] << 24)
        | (SBOX[(word >> 16) & 0xFF] << 16)
        | (SBOX[(word >> 8) & 0xFF] << 8)
        | SBOX[word & 0xFF]
    )


def galois_mult(x: int, y: int) -> int:
    p = 0
    while x and y:
        if y & 1:
            p ^= x

        if x & 0x80:
            x = (x << 1) ^ 0x11B
        else:
            x <<= 1

        y >>= 1

    return p


def mix_columns(state: list) -> list:
    result = [0] * 16
    for e, row in zip(state, COLMAT):
        for mult, i in row:
            result[i] ^= galois_mult(e, mult)

    return state_matrix(result)


def key_matrix(key: list) -> list:
    mat = []
    for row in SEXAGESY:
        line = []
        for col in row:
            n = key[col]
            line.extend([n >> 24 & 0xFF, n >> 16 & 0xFF, n >> 8 & 0xFF, n & 0xFF])

        mat.append(state_matrix(line))

    return mat


def derive_key(password: bytes) -> list:
    keys = [quadword(password[a:b]) for a, b in OCTUPLE]
    result = keys.copy()
    last = result[7]
    for i in range(8, 60):
        if not i & 7:
            last = sub_word(rot_word(last)) ^ (RCON[i // 8] << 24)
        elif i & 7 == 4:
            last = sub_word(last)

        key = result[i - 8] ^ last
        result.append(key)
        last = key

    return key_matrix(result)


def aes_256_cipher(data: bytes, password: bytes) -> list:
    state = add_round_key(state_matrix(data), password[0])
    for i in range(1, 14):
        state = add_round_key(mix_columns(shift_rows(sub_bytes(state))), password[i])

    return state_matrix(add_round_key(shift_rows(sub_bytes(state)), password[14]))


def get_padded_data(data: bytes | str) -> bytes:
    if isinstance(data, str):
        data = data.encode("utf8")

    if not isinstance(data, bytes):
        raise ValueError("argument data must be bytes or str")

    return data + b"\x00" * (16 - len(data) % 16)


def get_key(password: bytes | int | str) -> list:
    if isinstance(password, int):
        if password < 0 or password > MAX_256:
            raise ValueError("argument password must be between 0 and 2^256-1")

        password = password.to_bytes(32, "big")

    if isinstance(password, str):
        password = "".join(i for i in password if i.isalnum()).encode("utf8")
        if len(password) > 32:
            raise ValueError("argument password must be 32 bytes or less")

    if not isinstance(password, bytes):
        raise ValueError("argument password must be bytes | int | str")

    return derive_key(password.rjust(32, b"\x00"))


def ecb_encrypt(data: bytes | str, password: bytes | str) -> str:
    data = get_padded_data(data)
    key = get_key(password)
    blocks = [aes_256_cipher(data[i : i + 16], key) for i in range(0, len(data), 16)]
    return "".join(f"{e:02x}" for block in blocks for e in block)

AES_256.json

{
    "SBOX": [
        99 , 124, 119, 123, 242, 107, 111, 197, 48 , 1  , 103, 43 , 254, 215, 171, 118,
        202, 130, 201, 125, 250, 89 , 71 , 240, 173, 212, 162, 175, 156, 164, 114, 192,
        183, 253, 147, 38 , 54 , 63 , 247, 204, 52 , 165, 229, 241, 113, 216, 49 , 21 ,
        4  , 199, 35 , 195, 24 , 150, 5  , 154, 7  , 18 , 128, 226, 235, 39 , 178, 117,
        9  , 131, 44 , 26 , 27 , 110, 90 , 160, 82 , 59 , 214, 179, 41 , 227, 47 , 132,
        83 , 209, 0  , 237, 32 , 252, 177, 91 , 106, 203, 190, 57 , 74 , 76 , 88 , 207,
        208, 239, 170, 251, 67 , 77 , 51 , 133, 69 , 249, 2  , 127, 80 , 60 , 159, 168,
        81 , 163, 64 , 143, 146, 157, 56 , 245, 188, 182, 218, 33 , 16 , 255, 243, 210,
        205, 12 , 19 , 236, 95 , 151, 68 , 23 , 196, 167, 126, 61 , 100, 93 , 25 , 115,
        96 , 129, 79 , 220, 34 , 42 , 144, 136, 70 , 238, 184, 20 , 222, 94 , 11 , 219,
        224, 50 , 58 , 10 , 73 , 6  , 36 , 92 , 194, 211, 172, 98 , 145, 149, 228, 121,
        231, 200, 55 , 109, 141, 213, 78 , 169, 108, 86 , 244, 234, 101, 122, 174, 8  ,
        186, 120, 37 , 46 , 28 , 166, 180, 198, 232, 221, 116, 31 , 75 , 189, 139, 138,
        112, 62 , 181, 102, 72 , 3  , 246, 14 , 97 , 53 , 87 , 185, 134, 193, 29 , 158,
        225, 248, 152, 17 , 105, 217, 142, 148, 155, 30 , 135, 233, 206, 85 , 40 , 223,
        140, 161, 137, 13 , 191, 230, 66 , 104, 65 , 153, 45 , 15 , 176, 84 , 187, 22
    ],
    "RCON": [0, 1, 2, 4, 8, 16, 32, 64, 128, 27, 54]
}

It doesn't raise exceptions, but I have absolutely no idea what I am doing.

This is an example output:

In [428]: ecb_encrypt('6a84867cd77e12ad07ea1be895c53fa3', '0'*32)
Out[428]: 'b981b1853c16fbb6adc7cf4a01c9c57b94a3e5ce608239660c324b01400ebdd5d45a5452d22fed94b7ca9d916ac47736'

I have used this website to check the correctness of the output, with the same key and plaintext, AES-256-ECB mode, the cipher text in hex is:

e07beff38697f04e7adbc971adc2a9135f60746178fcd0f1b3040e4d15c920ad0318e084e1666e699891c78f8aa98960

It isn't what my code outputs as you can see.

Why isn't my code working properly?

Improve this question
4
  • 3
    The question is missing focus. As documentation for AES, I recommend NIST FIPS 197 (AES), which, among other things, provides a link to test vectors with intermediate values in Appendix C, see here. In the Encryption - Block Ciphers section under FIPS 197 - AES you will find the test vectors, e.g. for AES-128. Commented Mar 29 at 8:07
  • 2
    Incidentally, there is also a website: legacy.cryptool.org/en/cto/aes-step-by-step, that allows you to determine intermediate values and also contains various test vectors as examples. If you debug your code with one of these test vectors, you should be able to narrow down the problem. Commented Mar 29 at 8:14
  • 1
    "building C++ libraries on Windows is very complicated" -- no. Building C++ generally is complicated, that's why people developed CMake, Bazel, bjam and other tools. Commented Mar 29 at 16:36
  • For a start, provide a minimal reproducible example. Your code above loads a JSON file and then defines some functions, but it doesn't really do anything. Commented Mar 29 at 16:39

1 Answer 1

Reset to default
1

I have fixed my code, thanks to this comment, I have used this website to check all the intermediate results, and I walked through all of them step by step, and I got the right results in the end.

I am not good at explaining things, so I will just describe the fixes I implemented.

There were multiple issues in the code, first of all the padding is incorrect, I don't know how to implement padding yet, but it should be extremely easy at this point, but in the original code the data will be padded if its length is a multiple of 16, I fixed that.

Then the order of operations is all wrong, the key is derived correctly, but state_matrix is wrongly applied and key_matrix is bugged, as a result the subsequent steps are all wrong. Both of the aforementioned functions aren't needed.

The keys should be in the original order, in round zero first the data block should be mixed with the key using bitwise XOR, then in rounds 1 to 13 the data is first substituted with corresponding values in SBOX, sub_bytes was implemented correctly, and then the data needs to be permuted, this wasn't implemented correctly.

I don't know how to derive the indices needed, but the correct indices I need are these: (0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11)

Next we need to apply Galois matrix multiplication, it wasn't implemented correctly, I have fixed it.

Fixed code

import json


with open("D:/AES_256.json", "r") as f:
    AES_256 = json.load(f)

MAX_256 = (1 << 256) - 1
SBOX = AES_256["SBOX"]
RSBOX = AES_256["RSBOX"]
RCON = AES_256["RCON"]
PERMI = (0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11)
I240 = (
    (0, 16),
    (16, 32),
    (32, 48),
    (48, 64),
    (64, 80),
    (80, 96),
    (96, 112),
    (112, 128),
    (128, 144),
    (144, 160),
    (160, 176),
    (176, 192),
    (192, 208),
    (208, 224),
    (224, 240),
)


def sub_bytes(state: list) -> list:
    return [SBOX[i] for i in state]


def permute_state(state: list) -> list:
    return [state[i] for i in PERMI]


def add_round_key(state: list, key: list) -> list:
    return [a ^ b for a, b in zip(state, key)]


def rot8(byte: int, x: int) -> int:
    x &= 7
    return (byte << x | byte >> (8 - x)) & 0xFF


def rot_word(word: list) -> int:
    return word[1:] + [word[0]]


def sub_word(word: list) -> int:
    a, b, c, d = word
    return [SBOX[a], SBOX[b], SBOX[c], SBOX[d]]


def galois_mult(x: int, y: int) -> int:
    p = 0
    while x and y:
        if y & 1:
            p ^= x

        if x & 0x80:
            x = (x << 1) ^ 0x11B
        else:
            x <<= 1

        y >>= 1

    return p


def mix_column(state: list) -> list:
    a, b, c, d = state
    a2 = galois_mult(a, 2)
    b2 = galois_mult(b, 2)
    c2 = galois_mult(c, 2)
    d2 = galois_mult(d, 2)
    a3 = galois_mult(a, 3)
    b3 = galois_mult(b, 3)
    c3 = galois_mult(c, 3)
    d3 = galois_mult(d, 3)
    return a2 ^ b3 ^ c ^ d, a ^ b2 ^ c3 ^ d, a ^ b ^ c2 ^ d3, a3 ^ b ^ c ^ d2


def mix_columns(state: list) -> list:
    result = []
    for i in range(0, 16, 4):
        result.extend(mix_column(state[i : i + 4]))

    return result


def derive_key(password: bytes) -> list:
    result = list(password).copy()
    last = result[28:]
    for i in range(32, 240, 4):
        j = i // 4
        if not j & 7:
            last = sub_word(rot_word(last))
            last[0] ^= RCON[j // 8]
        elif j & 7 == 4:
            last = sub_word(last)

        key = [a ^ b for a, b in zip(result[i - 32 :], last)]
        result.extend(key)
        last = key

    return result


def aes_256_cipher(data: bytes, password: bytes) -> list:
    state = add_round_key(data, password[0])
    for i in range(1, 14):
        state = add_round_key(mix_columns(permute_state(sub_bytes(state))), password[i])

    return add_round_key(permute_state(sub_bytes(state)), password[14])


def get_padded_data(data: bytes | str) -> bytes:
    if isinstance(data, str):
        data = data.encode("utf8")

    if not isinstance(data, bytes):
        raise ValueError("argument data must be bytes or str")

    l = len(data)
    return data + b"\x00" * ((l + 15 & -16) - l)


def get_key(password: bytes | int | str) -> list:
    if isinstance(password, int):
        if password < 0 or password > MAX_256:
            raise ValueError("argument password must be between 0 and 2^256-1")

        password = password.to_bytes(32, "big")

    if isinstance(password, str):
        password = "".join(i for i in password if i.isalnum()).encode("utf8")
        if len(password) > 32:
            raise ValueError("argument password must be 32 bytes or less")

    if not isinstance(password, bytes):
        raise ValueError("argument password must be bytes | int | str")

    return derive_key(password.rjust(32, b"\x00"))


def ecb_encrypt(data: bytes | str, password: bytes | str) -> str:
    data = get_padded_data(data)
    key = get_key(password)
    key = [key[a:b] for a, b in I240]
    blocks = [aes_256_cipher(data[i : i + 16], key) for i in range(0, len(data), 16)]
    return b"".join(bytes(block) for block in blocks).hex()

Testing:

hexdigits = "0123456789abcdefABCDEF"


def hex2bytes(s: str) -> list:
    result = []
    skip = 0
    for i, c in enumerate(s):
        if skip:
            skip = 0
            continue
        if c in hexdigits:
            result.append(int(s[i : i + 2], 16))
            skip = 1

    return result

password = hex2bytes('603deb1015ca71be2b73aef0857d77811f352c073b6108d72d9810a30914dff4')
data = get_padded_data(bytes(hex2bytes('6bc1bee22e409f96e93d7e117393172a')))

In [177]: ecb_encrypt(bytes(data), bytes(password))
Out[177]: 'f3eed1bdb5d2a03c064b5a7e3db181f8'

In [178]: %timeit ecb_encrypt(bytes(data), bytes(password))
296 μs ± 3.58 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

The output is the same as the output for the AES-256-ECB test vector 1 example given by the linked website.

In [179]: ecb_encrypt('6a84867cd77e12ad07ea1be895c53fa3', '00000000000000000000000000000000')
Out[179]: 'e07beff38697f04e7adbc971adc2a9135f60746178fcd0f1b3040e4d15c920ad'

The above example output is the same as the output from this website if AES-256-ECB without padding is selected and the output is formatted as hex.

I am working on decryption and adding more modes and then porting it to C++.

I have figured out how to implement PKCS5 padding:

def pkcs5_pad(data: bytes) -> bytes:
    if not isinstance(data, bytes):
        raise ValueError("argument data must be bytes")

    pad = 16 - (len(data) & 15)
    return data + bytes([pad] * pad)


def pkcs5_unpad(data: bytes) -> bytes:
    if not isinstance(data, bytes):
        raise ValueError("argument data must be bytes")

    pad = data[-1]
    if pad < 1 or pad > 16 or data[-pad:] != bytes([pad] * pad):
        raise ValueError("invalid padding")

    return data[:-pad]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Just so you know I have finished implementing AES-256-ECB encryption and decryption and I have thoroughly verified its correctness, I will implement CBC and GCM modes and I will then reimplement my ideas in C++, and I will post the implementations on Code Review, one question for each language.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.