The supplied simple AES implementation shown Listing 7 was supplied as a reference. However, the inverse S-Box required for decryption is missing. Our first task is to implement the inverse S-Box and then use it to implement the decryption function.
We wanted a known working encryption and decryption implementation to compare our implementation against. We build a simple implementation using the OpenSSL library, as shown in Listing 8. We then verified that the OpenSSL implementation produces the same output as the simple implementation.
Listing 1 shows our function for calculating the inverted S-Box table. It swaps the indices and values of the S-Box table to create the inverted table.
link:src/invert-sbox.cpp[role=include]
The inverted S-Box (Listing 6) was placed into the AES implementation. We confirmed that the decryption function works correctly by testing the implementation against 1000000 random blocks and keys. As shown in Listing 2, we validated the result for each block by comparing it with the OpenSSL implementation.
link:src/compare-implementations.cpp[role=include]
For the second exercise, we were tasked with recovering a partially lost 128-bit (16-byte) AES key. We were supplied with the first 13 bytes of the key and a ciphertext that is known to decrypt only to contain lowercase letters and the .
character. The partial key and the ciphertext are shown in Listing 3.
link:src/key-recovery.cpp[role=include]
We only know the first 13 bytes of the key, so we need to brute force the remaining 3 bytes. Three bytes are 24 bits, so we must try \$2^24\$ keys. If we can test \$2^21\$ keys per second, we will need \$2^3\$ seconds to test all keys. This is \$8\$ seconds, a reasonable time frame for a brute-force attack.
- NOTE
-
The performance of \$2^21\$ keys per second is a wild guess based on nothing.
We used the AES functions from the previous exercise to implement the recovery tool. Listing 4 shows that we brute force the remaining 3 bytes of the key and check if the characters of the decrypted text match the requirements. If it does, we print the key and the decrypted text.
link:src/key-recovery.cpp[role=include]
Running the tool takes 4.5 seconds on our machine, which aligns with the expected value. The output of the tool is shown in Listing 5. We found the key to be 81596bfb39c62b716e52db9181dabeef
, and the decrypted text is thiswasatriumph.
.
lennart@erms ~/hda-cryptography-lab-2> time ./key-recovery
Found key: 81596bfb39c62b716e52db9181dabeef
Decrypted text is:
thiswasatriumph.
./key-recovery 4,49s user 0,00s system 98% cpu 4,556 total
We successfully implemented the decryption function for the simple AES implementation and verified it against the OpenSSL implementation. We then used the AES functions to recover a partially lost key. We found the key to be 81596bfb39c62b716e52db9181dabeef
and the decrypted text to be thiswasatriumph.
.
link:src/AesFunctions.cppm[role=include]
link:src/simple-aes.cpp[role=include]
openssl
based AES toollink:src/openssl-aes.cpp[role=include]