feature: AES for symmetric operations

[Dustin-Ray]

We propose the addition of support for Advanced Encryption Standard (AES) encryption. AES is one of the most widely used and secure encryption algorithms available, and its implementation would significantly enhance the capabilities and security features of our library. Below, I have outlined some of the key benefits and justifications for incorporating AES:

Benefits of Adding AES: Industry Standard: AES is an industry-standard encryption algorithm that is widely accepted and used across various sectors. Incorporating AES would align our library with industry best practices and standards.

Strong Security: AES offers strong encryption capabilities with key sizes of 128, 192, and 256 bits, providing robust protection against brute-force attacks and other cryptographic attacks.

Efficiency: AES is known for its efficiency and speed, especially in hardware implementations. Adding AES would ensure that our library can provide fast encryption and decryption processes, which is crucial for real-time applications.

Versatility: AES is versatile and can be used in various modes (e.g. CBC, CFB, OFB, and GCM) depending on the application's requirements. This versatility allows for a wide range of use cases to be covered by our library.

Interoperability: Implementing AES would enhance the interoperability of our library with other systems and tools that use AES, facilitating smoother integration in diverse environments.

Suggested Implementation: I suggest that we implement AES in accordance with the NIST Federal Information Processing Standards Publication 197. Additionally, we should ensure that we provide support for different modes of operation and allow users to easily select key sizes based on their security requirements.

Required updates to the library:

1. AES implementation and block cipher functionalities are added under src/aes
2. In src/ops, all symmetric operations are updated to allow for a user-configurable selection of encryption algorithm (this would be a selection between AES and KMACxof)
3. test cases will need to be added to ensure AES NIST compliance.
4. benches should be added to test AES throughput

[HLRichardson-Git]

A Good Start

The Advanced Encryption Standards (AES) functions have been implemented for all key sizes (128/192/256) and can be found in src/aes/aes_functions.rs there you will find the encrypt and decrypt block cipher along with the necessary operations. All functions were based on the Federal Information Processing Standards (FIPS) Publication 197. This is the most updated version.

I tried to use the same naming conventions as the FIPS 197 publication but chose to go with Rust's snake_case naming convention for better readability. Another note to add is that I chose to rename the encryption and decryption cipher from Cipher and InvCipher to encrypt_block and decrypt_block respectively. I also for some reason named the KeyExpansion as expand_key, this can be named key_expansion to better reflect the FIPS 197 publication.

A couple of AES functions in src/aes/aes_functions.rs that may need to be looked at are:

1. shift_rows: I am pretty new to Rust, so I am unsure how it deletes the memory of the 'first' variable. It is not unbelievable that this could be scraped from memory somehow giving an attacker partial information about the data.
2. mix_columns: This unlike the OpenSSL library uses a lookup table to complete Galois Multiplication. This gives our implementation an increase in performance, but at the cost of memory. This can be revisited in the future to see if we value memory over performance.

Currently (11/13/2023) it does not support padding in any form. This is obviously a practical problem as any user trying to use AES would only be able to encrypt/ decrypt data that is a multiple of 16 bytes. It is planned to add functionality for PKCS#7 as described in RFC 5652. There are additional padding methods such as ANSI X9.23 and ISO/IEC 7816-4 which could be added in the future.

Implementing more Modes of Operations

Currently (11/13/2023) I have only implemented the Electronic Code Book (ECB) block cipher mode to capyCRYPT. The ECB mode can be found at src/aes/aes_modes.rs along with any future modes added. The reason I implemented ECB first was because it is the most simple to implement and test the AES functions. If you wish to learn more about the ECB mode and other modes I will mention check out my post about modes of operations. Keep in mind that ECB mode is not considered safe to use, so I am unsure if this will give us a problem in the future. Thankfully the code is modular so removing AES_ECB is as easy as deleting encrypt_aes_ecb and decrypt_aes_ecb from src/aes/aes_modes.rs.

Currently, it is planned to implement the following modes of operations:

1. Cipher Block Chaining (CBC)
2. Output feedback (OFB)
3. Counter (CTR)
4. Galois Counter Mode (GCM)

These, unlike ECB, are considered safe, and some give an added benefit such as GCM which provides message authentication, or OFB which doesn't require padding. Note if you plan to add additional modes of operation that all AES algorithm functions can be found in src/aes/aes_functions.rs, the only needed additions should be in src/aes/aes_modes.rs. If we wish to keep this file clean we may want to implement functions that we use in the modes to be in src/aes/aes_utils.rs or another created file in src/aes/.

Testing AES for capyCRYPT

All current AES tests are inside tests/aes_tests.rs inside there you will find individual functions to test encryption and decryption of each key size with each mode (currently all key sizes and only ECB mode), here is an example:

fn test_aes_128_ecb_encrypt() {
        let key_string = "10a58869d74be5a374cf867cfb473859";

        let input = hex::decode("00000000000000000000000000000000").unwrap();
        let mut output: Vec<u8> = Vec::new();
        encrypt_aes_ecb(&input, &mut output, key_string);

        let expected = "6d251e6944b051e04eaa6fb4dbf78465";
        assert_eq!(hex::encode(output), expected)
    }

I found these test vectors inside The Advanced Encryption Standard Algorithm Validation Suite (AESAVS). This document was publicized on November 15, 2002, so I am unsure if I should be using more recent tests, but I can't see a problem with using them :) (famous last words).

Improving AES in capyCRYPT

You may have noticed that I didn't mention any benchmarks for the implementation. That is because I didn't make any. To be honest, I have never really given it a thought, and I always put it off so I have never gotten much experience making benchmarks. If someone wants to let me keep kicking that can down the road and implement them, I highly welcome you to it :).

Other improvements besides the benchmarks and adding more modes would be a security review. I only know vulnerabilities such as code injection, buffer overflow, and side-channel attacks in theory, not in practice.

[Dustin-Ray]

This is an awesome start, youve got a very solid and straightforward implementation and its looking fantastic.

1. shift_rows: I am pretty new to Rust, so I am unsure how it deletes the memory of the 'first' variable. It is not unbelievable that this could be scraped from memory somehow giving an attacker partial information about the data.

You can read a bit into the rust ownership model, we dont have to worry about garbage collection here. As soon as something leaves scope, it is automatically dropped. We dont have to account for null pointers or any leftover memory like in c++, this is the beauty of guaranteed memory safety. Your approach is safe as far as memory management goes :D

Review notes and preparing for merge

There's not much to criticize here, you can comfortably move in this direction and I think we will be in great shape. There are a couple of things we can do right off the bat:

2. This gives our implementation an increase in performance, but at the cost of memory. This can be revisited in the future to see if we value memory over performance.

Ill take it. We unrolled keccak which made the binary pretty huge so we're in too deep now to worry about it lol, performance > memory in this library

1. Here, I think we need to replace these values with enums:

// set values of n_w and n_r based on key bit length.
let (n_w, n_r) = match key_length {
  128 => (4, 10),
  192 => (6, 12),
  256 => (8, 14),
  _ => panic!("Unsupported key length"),
};

You can choose to worry about this or not its totally up to you, this was a bad choice on my part to do it this way originally, but a better option is to use enums to present the caller with all possible options instead of having them guess a string. Again, you can choose to tackle that or not, I think we can merge without it

2. Since this file: src/aes/aes_utils.rs contains what appears to be constants, lets please rename it to src/aes/aes_constants.rs

3. The idea is to eventually add a function into src/ops.rs which the Message type will implement. Following the patterns of the rust aes crate, we want to do everything in-place. The Message struct contains a data field called msg:

impl Message {
    pub fn new(data: Vec<u8>) -> Message {
        Message {
            msg: Box::new(data),
            d: None,
            sym_nonce: None,
            asym_nonce: None,
            digest: None,
            op_result: None,
            sig: None,
        }
    }
}

If we are encrypting, we want to read everything from msg, and replace it with the result of the encryption. This way, we dont store a copy of the message or keystream on the heap. Same with decryption, we replace the msg with the result, even if it fails. Future upgrades will be to recover from a failure, but we dont have to worry about this right now.

Heres an example of how xor_bytes does it:

/// XORs byte streams in place using iterators
/// * `a`: mut references to `Vec<u8>`, will be replaced with result of XOR
/// * `b`: immut ref to `Vec<u8>`, dropped after function returns
/// * `Remark`: Probable bottleneck unless impl with SIMD.
pub fn xor_bytes(a: &mut Vec<u8>, b: &Vec<u8>) {
    assert_eq!(a.len(), b.len());
    a.iter_mut().zip(b.iter()).for_each(|(x1, x2)| *x1 ^= *x2);
}

This is all I can really find at this point, this is a basically flawless first shot at some crucial functionality that makes the library even more awesome. Nicely done!

[HLRichardson-Git]

Changes

Regarding @drcapybara notes, I made the change:

Since this file: src/aes/aes_utils.rs contains what appears to be constants, let's please rename it to src/aes/aes_constants.rs

I also modified aes_functions.rs aes_modes.rs and aes_tests.rs to allow for in-place encryption and decryption so that we have better memory efficiency. This was to improve from this feedback:

The idea is to eventually add a function into src/ops.rs which the Message type will implement. Following the patterns of the rust aes crate, we want to do everything in-place.

Therefore our new tests have been re-organized as we nolonger need an output vector, here is an example of a new test in aes_tests.rs

#[test]
    fn test_aes_128_ecb_encrypt() {
        let key_string = "10a58869d74be5a374cf867cfb473859";

        let mut input = Message::new(hex::decode("00000000000000000000000000000000").unwrap());

        encrypt_aes_ecb(&mut input.msg, key_string);

        let expected = "6d251e6944b051e04eaa6fb4dbf78465";
        assert_eq!(hex::encode(*input.msg), expected)
    }

What I did to implement in-place encryption/ decryption

I mentioned above I modified aes_functions.rs aes_modes.rs and aes_tests.rs to implement in-place encryption/ decryption. To do that most of the changes were in aes_functions.rs and I removed the output variable passed to the encrypt_block and decrypt_block functions and changed our input variable to be mutable. In this new change instead of pushing an output vector, we replace the input vector with the encrypted/ decrypted state block as you can see:

// Replace input with encrypted state.
        for j in 0..NB {
            for i in 0..NB {
                input[block_index + i + 4 * j] = state[i][j];
            }
        }

This *should work because the input should always be a multiple of 16 bytes. This is actually not the case currently because we still do not have any padding operation, but that is planned.

[Dustin-Ray]

This solution is wonderfully elegant and actually completely avoids #20. In this case, you arent even creating a copy of the encryption on the heap which is fantastic and aligns well with established practices in crates like the primary implementation of AES in rust. Youve achieved constant memory usage in one fell swoop. Nicely done!

Preparing for merge:

1. Your comment about the security of ECB is correct and I dont think we should allow it as an option at all. To merge this PR, lets at a bare minimum shoot for CTR or CBC, preferably CTR because of the ease of implementation, and Im also curious to see if we can nudge the rust compiler into parallelizing this thing on its own.
2. Padding: I assume we will need padding up and running for this as well to support arbitrary length messages.
3. Docs: Lets keep the heavy docs in src/ops.rs since they face the caller. The should mirror what you see for the other ops. The docs look quite dense but you can copy most of what you see in other ops like pw_enc and should be fine.
4. Implement aes_enc and aes_dec in ops as trait implementations for the Message type. You're aiming for this:

// Get a random password
let pw = get_random_bytes(64);
// Get 5mb random data
let mut msg = Message::new(get_random_bytes(5242880));
msg.aes_encrypt(&pw);
// Decrypt the data
msg.aes_decrypt(&pw);
// Verify operation success
assert!(msg.op_result.unwrap());

Assuming other modes will be supported, we can open another issue and PR to create more of an api-style situation later. For now, we can keep this PR simple tackling the above points 1 - 4. This is a great result so far! Thanks for your efforts on this!

[HLRichardson-Git]

Quite a large update since the last push to prepare for the merge most of the issues posted by @drcapybara were implemented in the current version. Here is what has changed:

What Has Changed

The first big change was the removal of src/aes/aes_modes.rsThis was because this functionality was moved to src/ops.rs under the AesEncryptable trait. It made more sense to just have the modes of operations defined there instead of calling the function. As a consequence utility functions such as apply_pcks7_padding, remove_pcks7_padding, and xor_blocks have been moved to src/aes/aes_functions which can be found below the AES struct implementation.

Now let's go over the issues mentioned above in order:

Your comment about the security of ECB is correct and I don't think we should allow it as an option at all. To merge this PR, let's at a bare minimum shoot for CTR or CBC, preferably CTR because of the ease of implementation, and I'm also curious to see if we can nudge the rust compiler into parallelizing this thing on its own.

ECB (Electronic Code Book) has been removed since it is not considered secure. Since then I have implemented CBC (Cipher Block Chaining) mode, and it is currently the only mode available. But future planned modes of operations are:

1. Output feedback (OFB)
2. Counter (CTR)
3. Galois Counter Mode (GCM)

More can be added, but these are some of the most popular ones.

Padding: I assume we will need padding up and running for this as well to support arbitrary-length messages.

As briefly mentioned above PCKS#7 has been added (note: PCKS#7 = PCKS#5) and can be found in src/aes/aes_functionsThis allows for modes like CBC to be able to encrypt arbitrary length messages. More padding schemes can be added in the future, but functionality to allow a user to choose the scheme would also be needed.

Docs: Lets keep the heavy docs in src/ops.rs since they face the caller. The should mirror what you see for the other ops. The docs look quite dense but you can copy most of what you see in other ops like pw_enc and should be fine. Implement aes_enc and aes_dec in ops as trait implementations for the Message type. You're aiming for this:

As wanted, AES has now been added as a trait usable with Message. This can be found under AesEncryptable in src/ops.rs. An example of it being used can be found in tests/aes_tests.rs, currently 3 tests are present for each key size (128/192/256), here is an example of the 128-bit key test using new AES traits:

fn aes_128_cbc() {
    let key = get_random_bytes(16); // 16 bytes -> 128 bits
    let mut input = Message::new(get_random_bytes(5242880));

    input.aes_encrypt_cbc(&key);
    input.aes_decrypt_cbc(&key);

    assert!(input.op_result.unwrap());
}

Difficulties Faced

First when creating aes_decrypt_cbc I found myself in the problem of needing past data which was overwritten because of our in-place encryption/ decryption. My solution was a temporary variable to store the 16 bytes before decryption. This was necessary because if not, the data would be lost to decryption and the operation would fail. I want to work to find a cleaner solution to this, as I find the solution a little sloppy and costs a bit of memory.

Second was converting all functions that took our given key which prior, was a string, to take a u8 vector. This was less a hard problem, but more of a testing nightmare as I had to find and change code that was reliant on the key being a string. This turned out being for the better as we were changing the string to a u8 vector anyways in key_expansion so we saved a bit of memory.

Third was using the ke_ka pattern for deriving an encryption and authentication key. I am honestly unfamiliar with security best practices with functions such as KMAC, but I mirrored what @drcapybara has previously done in functions like pw_encrypt. This is what I did for aes_encrypt_cbc and aes_decrypt_cbc:

    let iv = get_random_bytes(16);
    let mut ke_ka = iv.clone();
    ke_ka.append(&mut key.to_owned());
    let ke_ka = kmac_xof(&ke_ka, &[], 512, "AES", 256);
    let ke = &ke_ka[..key.len()].to_vec(); // Encryption Key
    let ka = &ke_ka[key.len()..].to_vec(); // Authentication Key

So if any unforeseen security flaw is present please let me know.

[Dustin-Ray]

My solution was a temporary variable to store the 16 bytes before decryption.

I think this is just fine. 16 bytes is a trivial amount of memory and this is only happening once per invocation, so this is a good solution for now.

There are a few small changes to make to the docs and then I think you are ready to merge!

please define what P is here same note here, please define C move this comment to aes_functions

Once you have this addressed, run: cargo fmt and cargo clippy. Address anything with clippy, if its something else in the library that you didnt work on then dont worry about it for now. After you run those, open up a PR. You will probably need to pull down the README as I think it has changed since you opened your branch. Let me know if you have any troubles with that or if your merge is blocked due to conflicts. This is awesome!

[Dustin-Ray]

You dont have to do this to merge the PR but I would highly recommend adding benches for AES so that you have an accurate idea of the performance. Check out #13 for super easy instructions on how to get started. The benching code looks dense if youre new to rust but most of it can easily be copied and pasted. You end up with these really awesome charts and metrics in the end, its very worth doing.

[Dustin-Ray]

Also if youre interested, if the number of loops is known, we could consider unrolling the loops as we do in our keccak implementation. check this out:

try:

cargo add loop-unroll

use loop_unroll::unroll_for_loops;

#[unroll_for_loops]
for i in 0..4 {
    // loop body
}

so you add the header to the loop and then it should compile out as unrolled which interestingly can lead to massive speed ups in some cases. The keccak implementation trades readability for unrolled loops but I would be interested to know how this affects things.

we dont need this to merge the PR though this is just for consideration.

[Dustin-Ray]

Merged! Nicely done! Happy to merge in CTR or any other modes you feel like tackling!

[Dustin-Ray]

Im going to close this issue as it only relates to AES itself, which we now have thanks to you. If you'd like to add more modes or performance improvements, lets open it up in another issue.