Correlation Power Analysis vs AES

Recently, I spent some time learning about power analysis attacks. This has been an interesting journey with many interesting applications. The theory behind this is simple – that different operations (or – crucially – the same operation with different data) consume differing amounts of power, and that by measuring power consumption of a device over time, we can determine (with the help of some statistical trickery) what the device is doing.

All the code for the below, as well as the targets, are downloadable from github.com/CreateRemoteThread/fuckshitfuck. This code is provided as-is, and is a working copy – it may break unexpectedly.

Setup / Acquiring Traces

The first step of our journey is to acquire power traces across a target device. To do this, I built a simple ATMega328p target board:

This is a standard ATMega328p with a voltage regulator running at 3.3v, and a bypass cap to help stabilize the power supply (this realistically didn’t do shit). UART is broken out for communications, and an debug header is present for editing firmware quickly. Two extra debug wires are present, used to trigger the oscilloscope (or simply provide a second informational channel).

Crucially, a 1.5 Ohm shunt resistor is present from the ground pins of the target to the power supply ground. This is used to measure current consumption by the microcontroller.

The board runs a very simple AES target – you can load a key with ‘k’, and encrypt data with ‘e’. When the ‘e’ command is sent, the following steps are taken in order:

  1. a trigger line is increased to a logical high
  2. AES encryption is performed with the currently loaded key
  3. the trigger line is set to logical low
  4. the result is printed to uart out

A single power trace looks something like this:

Along with the trace, we should optimally record the plaintext for the next step of this attack.

Power Consumption Modelling

Our attack targets the power consumption of the first round, exploiting two fundamental properties (in the lack of mitigating factors):

  • The first operation of AES is to xor the plaintext with the key, then use the result to index a known array (the s-box), forming an intermediate value. Therefore, as we known the plaintext, we can know this intermediate value for every possible key byte.
  • We assume that more “1”‘s in the intermediate value means very slightly more power is consumed during the first round.

In isolation, this information is not immediately helpful – our measurement is not accruate enough to extract the key byte through analysis of a single trace. However, if we take, hypothetically, 3 traces, we can begin forming a hypothesis:

  • The plaintext is assumed known
  • If key[0] is byte 1,
    • the intermediate value of key[0] for trace[0] is 0x01
    • the intermediate value of key[0] for trace[1] is 0x11
    • the intermediate value of key[0] for trace[2] is 0xFF
    • Trace 2 will consume more power than trace 1, which consumes more power than trace 0
  • If key[0] is byte 2,
    • the intermediate value of key[0] for trace[0] is 0xFF
    • the intermediate value of key[0] for trace[1] is 0x11
    • the intermediate value of key[0] for trace[2] is 0x01
    • Trace 0 will consume more power than trace 1, which consumes more power than trace 2
  • A similar model is performed for every key[0] from 0 to 255
  • We have taken 3 traces of the target with an unknown key. Whichever key guess’s hypothesis most strongly corresponds with the 3 actual traces with unknown key, is the key guess.
  • This is inherently resistant to noise, as it’s a statistical attack – it’s not realistic to expect 100% correlation strength, but 60% correlation where everything else is 4% is an extremely strong indicator of correctness

This approach scales infinitely, limited only by time (and memory): the attacker may capture as many traces as he or she pleases.

Correlating Traces

A mathematical tool, known as Pearson’s Correlation Coefficient, can be used to quantify how similar one set of traces is (or rather, it’s delta from the mean of all traces) to a hypothesized key byte’s set of traces. This is well expressed by Wikipedia:

It is quite simple to understand once expressed in code. With a little bit of Matplotlib, it is possible to graphically represent Pearson’s correlation coefficient:

Each line in the plot represents a byte of the key, with clear spikes, representing strong correlation, for one byte value (the correct guess) for each position of the key. Even from a low number of noise-tainted initial captures, the results are extremely clear: it is possible to use this method to extract an AES key from a set of power traces, having an encryption oracle.

The same technique is possible against the final round of AES (i.e. only requiring a known ciphertext), but I have not demonstrated this. This may be possible to execute against AES decryption, but I also have not demonstrated this – this may be useful in attacking MAC implementations.

In conclusion, this was a very interesting attack to be able to demonstrate, and the practical applications of this attack method are limitless. I will follow up with a post on a related attack, differential power analysis.

Posted in Bards, Computers, Jesting | Leave a comment

Atredis BH Ticket 2018 Challenge Writeup

Earlier this year, I completed a binary reverse engineering challenge from Atredis Partners. This was interesting, so I will present the writeup below, for posterity. The challenge began with a Slack message from a comrade, who mentioned there was a binary-style challenge available at arkos.atredis.com, port 4444.

Upon connecting, I was greeted with the prompt shown above. A bit of manual testing revealed that I could use the “help” and “read” commands – the “read” command would consistently produce a single byte from a specified location in memory:

Here, I built a memory dumping script which called read in a loop to give me an extract from memory. I extracted according to the memory map, until I hit contiguous blocks of zero (which I assumed to be the end of real data in a mapped section). Immediately, a few interesting tidbits jump out at me.

We can immediately note that in the PROM section starting at 0x4000, there is a reference to “write” and “call”, which appear to be commands:

At this point, I decided to try the “write” and “call” commands – the “write” command seems to allow a single byte to be written with the syntax “write <addr> <byte>”. I couldn’t make the “call” command do anything at this point, but it always printed “JSR <addr>”.

I did some Google, and I found that JSR could stand for Jump Subroutine, an assembly language thing for MOS 6502 microcontrollers. Cool!

With this, I could now fully disassemble the program at 0x8000 in IDA. After some learning about 6502 and some manual effort (the program took 16-bit addresses, which were loaded in two operations of single byte chunks, which was annoying to deal with), I was able to reconstruct some basic application logic flow:

  • There are two points in the application which seem to seek a file from disk: displaying /etc/motd (0x8270), and displaying /var/mail/spool/atredis (0x82a2).
  • Both called “fopen” at 0x8059, after loading a pointer to the filename at $95 and $96
  • “fopen” is a strange loop – it sets an “id” in $99, then calls “disk_read_sector” at 0x8034. It then compares the filename to what was initially entered, and exits the loop if it’s what we’re looking for, or continues the loop if no match.

After a little experimentation, I found that RAM was executable, and I could write shellcode via the “write” command and “call” it successfully. I initially attempted to build a stub which called fopen with a controlled filename, but this didn’t work.

I then wondered if I could simply patch the program – it turns out I could. I then patched the byte at 0x8060, to modify the initial “fopen id”, and 0x8084, to pass the filename check at the end of fopen, and presto, the flag:

This was a fun challenge, and well thought out. Thanks to the Atredis folks for putting this together.

Posted in Bards, Computers, Jesting | Leave a comment

Karma on ESP8266

Earlier this year, I had wondered whether it was feasible to implement the Karma attack on a low-powered device, such as the ESP8266. It turns out this was quite simple, and you can now find a template for this on Github here.

The code is not a complete WiFi pineapple on an ESP – by design, this only implements part of the attack, it is up to the user to provide the “rogue AP host” and network back-end (but on the low-power theme, you might be able to forge this via another ESP8266). No preferred network list functionality is provided here either, but this isn’t too difficult to implement – the ESP is fairly generous in terms of resources for this.

If you want to play around this, the following video is well worth watching. The concepts discussed here are all relevant, no matter the hardware platform (though against modern devices, they have varying degrees of effectiveness – the most effective seems to be preferred network list based trickery, or good old fashioned fake beacons).

Have fun!

Posted in Bards, Computers, Jesting | Leave a comment

Writeups – Mr Reagan, Bluepill (Securityfest CTF)

This weekend, I particpated for a short while in the Securityfest CTF. During the time available, I was able to solve a few challenges – I will present the writeups for two of them here.

Mr Reagan

This challenge was presented as a binary file, which you can download here (note – this is a ~35MB file).

Strangely enough, binwalk shows nothing meaningful, but “file” identifies it as an NTFS filesystem. Running “strings” didn’t extract anything immediately meaningful. A bit of Google led to a freely available tool called “RecuperaBit” – this allowed us to recover the filesystem by ignoring an incorrect partition:

We immediately note several text files which have been deleted, which we can recover – but this does not reveal anything meaningful. Trawling through the filesystem, we see some more deleted files in EFSTMPWP/:

Each of these file parts contains 13 bytes of something that looks like base64 data. A quick Python script to brute force which order the chunks come in, quickly reveals the flag (or close enough to it):

Bluepill

This challenge was presented as a Linux kernel and kernel module, which you can download here.

Running the package as suggested reveals a simple busybox-based system, with one curious entry about bluepill in the dmesg output. We continue our investigation with bluepill.ko:

Thankfully, symbols are left in the binary, making our adventure a bit easier. We start by noting that the kernel object, upon loading, creates the /proc/bluepill object, and installs a write handler via proc_create – whenever we write to /proc/bluepill, pill_choice is called.

The pill_choice function then calls a function called “calc”, and memcmps the result to some hard-coded strings:

The astute reader will notice this isn’t 100% accurate, but we’ll come back to this later. The “calc” function looks complex at first, but we quickly find some magic numbers:

This tells us that the function is effectively an MD5 function, and the structure of the function checks out with a basic description of MD5.

At this point, I looked up the checksums above in crackstation.net, but this turned up nothing, indicating some manner of pre or post-processing on the source data. Going back to the “pill_choice” function, a closer inspection reveals that the MD5sum is xor’ed with the first few characters of /proc/version, which we know from the binary.

A quick Python script reveals the key we need to type into /proc/bluepill for the flag: unfortunately, this was completed after the end of the CTF event, too late to score any points.

Overall, this was an enjoyable CTF – my only regret is starting late on Friday, instead of on Thursday when it actually began in local time. See you all in Viettel Mates CTF in two weeks time.

Posted in Bards, Computers, Jesting | Leave a comment

Writeups – Numbers Game, BabyRE (RCTF – Part 2)

This post continues from my last post on. Two more writeups for RCTF are presented below.

Numbers Game

This challenge was presented as an IP and port, with the clue that we had to “guess”. This challenge ended up being a variation of “Cows and Bulls” (or, if you prefer, the Fallout hacking puzzle). We guess 4 numbers, then are told how many we have in the correct position, and how many numbers have the correct value but are in the wrong position.

A simple Python script solves this cleanly, which you can download here.

Funnily enough, from the Wikipedia article, we note that the minimal average game length is just over 5 turns:

We are provided 6: therefore, our solution must be optimal (fortunately, the solver I found off github was).

BabyRE

This challenge was presented as a Linux binary, which you can download here. While presented as a reverse engineering challenge, I performed only minimal reverse engineering to complete this challenge.

Initial analysis showed that this executable took in some letters and a number, followed by some arbitrary additional input. The output seemed to be a series of dword values. One of what appears to be the encoding steps is shown below:

Based on this alone, I made a few assumptions:

  • The application encoded one character at a time
  • There was no meaningful randomness, despite randomness-based functions being called
  • The order of characters didn’t matter (but this is slightly irrelevant if we have an encoding oracle)

I first tested my hypothesis by providing “test 15” as the first inputs, then encoding “abc” and “cba”. These provided the expected result: that is, one dword value corresponded to each character of input.

I then attempted to encode “RCTF”, which provided dword outputs which corresponded to the contents of the “out” file – I assumed at this point that this was the flag. Further testing confirmed that the order of characters did not matter.

From here, a little bit of Python makes this a trivial solve: we simply encode the entire alphabet, and test this against the “out” file. You can download the script I used here.

Overall, I enjoyed participating in this CTF – this showed me some serious gaps I have with webappsec and pwning. As always, I look forward to improving my skill for the next one.

See you all in “Security Fest CTF” and Faust CTF in two week’s time.

Posted in Bards, Computers, Jesting | Leave a comment