Writeup – Glitching AES (Donjon CTF)

Update: I am an idiot. But I think this makes the accidental result fun to think about!

Over the past few weeks, I participated in Donjon CTF. This post will document my method for solving the “Glitching AES” challenge, which is presented separately for the purpose of written clarity.

The accompanying files can be found here.

It should be noted that this method is not the “intended solve” – I didn’t understand the intended method, so I used a brute force method.

Glitching AES

This challenge was presented as a large (623MB) text file, the first few lines of which are presented below:

The objective of the challenge was to use this data to recover the AES key, and decrypt a provided ciphertext blob in ECB mode:

I performed a sanity check of looking for the ciphertext blocks in the provided encryption traces, but they were not present. I then reformatted the provided data into numpy traces, using format_to_npy.py. Initial statistical analysis showed that there were no “glitched outputs” – all the fault attempts either resulted in a correct output or a mute. Plotting the output states (mutes vs glitches) shows a 14-round AES-like trace, as follows:

I started by attempting a straightforward DPA attack (with dpa.py, which can be modified to select different models, and optionally discard traces for which points of interest are 0/missing data). against the first-round Sbox output, using only the traces which result in a non-mute response. This resulted in reasonably strong single point correlation for all byte positions:

Unfortunately, the resulting key (“4b596315d21df5a531079c838e11eee6”) was incorrect. I attempted a similar attack using a T-Table outputs model, which produced the same key. I then attempted a last-round attack, which produced similarly strong false correlations for another incorrect key (“c95c9f4d0054e0376518b43e6e4eb7ab”).

I thought at this point that the key was incorrect, but related to the true key, due to the single-point correlations for all bytes. I guessed also that fundamentally, the AES algorithm itself was unchanged except for the addition of more rounds: that is, in each round, the key is changed prior to the sbox, and I couldn’t see it because of the false correlation in first round.

I tested this theory against the second round of AES: by scheduling the initially discovered correct key (“4b…”) to round 2, I performed DPA (using diffs.py, make sure you edit the bytepos target range, and supply a target round) to identify a possible XOR mask prior to SubBytes, which yielded results, for all rounds:

The positional correlation (i.e. one byte after another) was extremely encouraging, as well as the fact that these spikes were generally single points of large differences of means, generally without ghost peaks or other such silliness:

Note that some error correction had to be performed, due to false or weak correlations in specific places:

  • Where the error could be fixed by modifying the leakage point to after MixColumns in the same round, I used 8ball.py.
  • Where the error required propagating to the sbox of the next round (IIRC, this was the case in Round 6 to Round 7), I used 9ball.py. Note that using this can take several hours to identify a single byte, so please be absolutely sure you can’t use 8ball before using 9ball.
  • I used taint_track.py to identify what impact an incorrect byte of AES could have past ShiftRows and MixColumns.

Also, as the brute force went on, the modified AES encryption took increasing amounts of time – an AES progress cache helped with this, allowing me to skip rounds where I knew the result. As an aside, the following behaviour in Python3 is quite interesting (causing some wasted time as I tracked this down in my initial AES cache implementation).

a = [{}] * 10
print(a)
a[2]["lol"] = 2
print(a)

The results of this brute force were stored in an array (in keymod.py). When I had all 14 rounds, I then performed an encryption against the provided plaintexts, and identified a final XOR mask (in test.py and test3.py, the one in keymod.py is old / unused), producing the correct ciphertext for all input plaintexts.

The final step of this challenge is to write a custom decryption function (in test3.py), to reveal the correct flag:

Thankyou to the Ledger Donjon team who wrote this CTF – their challenges were well-crafted and their infrastructure was quite stable throughout the allocated play time. I was able to improve my skills and improve my toolset through this experience, and greatly look forward to the next instance of this CTF (as well as RHME4 and others!).

About Norman

Sometimes, I write code. Occasionally, it even works.
This entry was posted in Bards, Computers, Jesting. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.