Cryptography Lab Report 2

by
Lennart Eichhorn
Matriculation number: 759253

1. Simple AES programming

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.

1.1. Inverting the S-Box

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.

Listing 1. Function for inverting the S-Box

link:src/invert-sbox.cpp[role=include]

1.2. Validating the S-Box

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.

Listing 2. Setup for comparing our implementation against OpenSSL

link:src/compare-implementations.cpp[role=include]

2. Simple AES cracking

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.

Listing 3. Supplied data for the second exercise

link:src/key-recovery.cpp[role=include]

2.1. Estimating performance

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.

2.2. Implementing the recovery tool

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.

Listing 4. Our key recovery tool

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..

Listing 5. Output of the key recovery tool

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

3. Conclusion

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..

List of abbreviations

AES: Advanced Encryption Standard 🔗
S-Box: Substitution box 🔗

4. Appendix

Listing 6. Inverted S-Box

link:src/AesFunctions.cppm[role=include]

Listing 7. Simple reference AES implementation

link:src/simple-aes.cpp[role=include]

Listing 8. openssl based AES tool

link:src/openssl-aes.cpp[role=include]

scripts/trailing-scripts.adoc

Oliver-Hanikel/hda-cryptography-lab-2