Another dimension, the year is 31337. All software has been eliminated and replaced by far superior, configurable hardware. The experiments started in 2019 when the FFF, the Fraternity for FPGA, published an AES implementation. To show the superiority of their design, individuals would receive the greatest honors if they would be able to recover the key although the FFF deemed this to be an impossible challenge.
In this exercise, we are given 2 files –
aes.vhd. A quick glance at the files as well as the files’ suffix indicate that these are related to Verilog – a language which enables us to write modules to an FPGA.
This exercise becomes significantly easier if one has previous knowledge about Verilog, or Xilinx development environment. This might have a been a problem for some groups, as some tools are necessary (GBs of Vivado installation) to solve this. It might be possible to solve with other methods or tools (we’ll discuss how at the end), but HW development knowledge can obviously help.
Understanding the Challenge
Our first clues are the filenames –
tb.vstands for testbench – a common practice in HW development. This is a file that tests a certain HW module by providing it input signals, and testing what output comes out.
aes.vhd– As our challenge suggests – the exercise is about AES, and this file represents the implementation of the AES module.
Let’s dig a little deeper…
As specified, The AES module is present in
aes.vhd file. The first section is a comment which gives us some clues. Mostly – this is an AES module, which was compiled for Xilinx boards. “
...This VHDL netlist...” – This means this is a compiled version of the Verilog module. We don’t see the code represented as different modules and registers and wires with meaningful names – the Verilog code was compiled to Muxes, Look-Up tables, Flip-Flops etc. Just like C code is compiled into Assembly, Verilog is compiled into HW components.
The module has the following interface, which is pretty self-explanatory:
entity AES128 is port ( CLK : in STD_LOGIC := 'X'; RESET : in STD_LOGIC := 'X'; ENABLE : in STD_LOGIC := 'X'; DONE : out STD_LOGIC; PLAINTEXT : in STD_LOGIC_VECTOR ( 127 downto 0 ); CIPHERTEXT : out STD_LOGIC_VECTOR ( 127 downto 0 ) ); end AES128;
- CLK – Input signal, specifies clock, which is needed for the module to operate. Probably a Rising/Falling edge.
- RESET – Input signal. When on, the state is being reset, and nothing happens.
- ENABLE – Input signal. When on (and reset off), starts the encryption process, and after a certain amount of clock cycles – we should get the output
- DONE – Output signal. A bit specifying when the encrytion operation is done, and we can start reading the data.
- PLAINTEXT – 127 Input signals (16 byte). Specifies the plaintext to encrypt.
- CIPHERTEXT – 127 Input signals (16 byte). Holds the ciphertext once the encryption operation is done.
The thing that is immediately apparent is that the module has no “key” or “iv” inputs. Meaning, it’s supposed to act as a black-box – insert a plaintext, and receive a ciphertext – without specifying the key. This means that the key is a secret, somehow fused into this module, and our guess is that we need to find what it is (as suggested by the exercise’s description).
All the rest of the file describes the internal logic of the module. As said, the module is made up of look-up tables, flip-flops, wires, and muxes. These are used to make up the actual AES encryption logic. Since the code is compiled, we don’t see any “pretty” S-box routines, and byte rotations, but just a lot of binary “a is mapped to b” and “if inputs 1 2 3 are 1, then output is 1”. It’s pretty hard to deduce what the code does this way, and the key somehow got “fused” into the logic. As we’ll soon see, surprisingly, parsing this logic (even though we partially tried) is irrelevant.
The testbench file is supposed to operate the AES module in a simulated environment. This means it’s not supposed to run on actual HW, but rather in a simulator that knows how to mimic all the internal signals, wires and registers. Again, this is a common procedure when working with Vivado, or HW development.
Let’s break the code down to understand what happens.
First, we create test registers, and zero them:
module test; reg RESET = 0; reg ENABLE = 0; reg [127:0] PLAINTEXT = 0;
These are the test-bench registers. Later on, the code will wire them to the actual module in order to instrument it.
Then, the test-bench is doing actions at certain points in time. In order to check how the module operates, we need to simulate a clock signal, provide input, and trigger the module to work. After a certain amount of time, we want to see the module’s output.
Now that we understand that – let’s go over the code.
The test-bench sets the RESET register to 1 after 100ns – to make sure everything is being initialized properly. Then, after additional 100ns the ENABLE register is being reset to 0.
After additional 200ns we stop holding the RESET signal at 1, and set it to 0, and 200ns after that we set the ENABLE register to 1. This is the point in time where the module actually starts to operate.
initial begin # 100 RESET = 1; # 100 ENABLE = 0; # 200 RESET = 0; # 200 ENABLE = 1; # 3000 $stop; end
3000ns after the ENABLE register was set, we stop the simulation. This should be more than enough time to let the module work.
The next piece of code defines a CLK register, and in order to create a CLK signal for the AES module, it negates the register’s value every 10ns.
reg CLK = 0; initial CLK = 0; always #10 CLK = ~CLK;
This creates a “square wave” pattern:
0 1 0 1 0 1 ... _ _ _ _| |_| |_| | ...
Usually, every rising edge (0->1) is used to signal a “pulse”, and this is indeed the case in the AES module.
Next, the code defines a CIPHERTEXT register, which is made up of 127 bits, and DONE register.
Then, the code simply wires the test-bench registers which we’ve just defined, into the AES module registers. Think of it just like connecting wires.
wire [127:0] CIPHERTEXT; wire DONE; AES128 aes128_inst ( .CLK (CLK), .RESET (RESET), .ENABLE (ENABLE), .DONE (DONE), .PLAINTEXT_0 (PLAINTEXT), ... .CIPHERTEXT_0 (CIPHERTEXT), ...
The code monitors the CIPHERTEXT value, but we don’t care for it so much at this point.
initial $monitor("At time %t, value = %h (%0d)", $time, CIPHERTEXT, CIPHERTEXT); endmodule // test
Running the simulation
During the challenge, we spent a fair amount of time trying to understand if any alternative to Xilinx development environment can be found. Perhaps even quickly write a simulation engine ourselves. Downloading Vivado takes a lot of time, and requires a license. Luckily, one of the guys in our team had Vivado already installed, so this sped things up a bit. The alternatives of grabbing a copy somehow or writing a simulator seemed to take a lot of time, and I hope none of the groups failed because some had access to tools that other groups didn’t – a point for thought.
I know that some open-source enviornments do exist, but couldn’t find one that clearly indicated how to process these files, in the limited time-frame of the challenge. If you know otherwise – we’d be happy to know!
Going back to Vivado, it’s relatively easy to run the test-bench (again, previous knowledge is useful here) – Create a new project, add the
aes.vhd module, and add the
tb.v under the simulation dir tree. Press “Run simulation”, some voodoo will happen, and eventually the simulation will run and we can visually see all the signals, specifically the CIPHERTEXT.
The solution turns out to be quite simple, a lot simpler than the list of things we initially tried. These include:
- Clock glitching
- RESET/ENABLE glitching
- Deducing the AES key by trying to figure out the 10th round key (which yields the key itself). This included trying to parse some binary Look-Up tables.
The reason I’m writing this is because this was an interesting learning experience, and the easiest solution is sometimes the best.
Eventually, we wanted to gain slightly more insight into the inner workings of the module, to check our sanity. If you look at the
aes.vhd file, you will notice the following lines:
signal signal_1367 : STD_LOGIC_VECTOR ( 127 downto 0 ); signal signal_1368 : STD_LOGIC_VECTOR ( 3 downto 0 ); signal signal_1369 : STD_LOGIC_VECTOR ( 3 downto 0 ); signal signal_1370 : STD_LOGIC_VECTOR ( 127 downto 0 ); signal signal_1371 : STD_LOGIC_VECTOR ( 127 downto 0 ); signal signal_1372 : STD_LOGIC_VECTOR ( 127 downto 0 ); signal signal_1373 : STD_LOGIC_VECTOR ( 127 downto 0 ); signal signal_1374 : STD_LOGIC_VECTOR ( 31 downto 0 ); signal signal_1375 : STD_LOGIC_VECTOR ( 127 downto 0 );
These are “inner” wires, which we’re not supposed to see outside the module. The simulation does not provide us the status of each of these lines. These are vectors (simply put, 128 lines, one per bit), which contain some inner state, probably related to the PLAINTEXT, CIPHERTEXT, or both – we didn’t really know. The reason we suspect that is because their length is equal to 128 bits – just like our plain and cipher texts.
So we decided to tap these wires – in the same manner that the module shows output signals, we would output all these vectors and see what happens with them in different points in time. We do so by changing the
aes.vhd file like the:
MIDDLETEXT1 : out STD_LOGIC_VECTOR ( 127 downto 0 ) ... replicate per each vector you want to tap. OBUF #### has to be unique.. OBUF_#### : OBUF port map ( I => signal_1367(127), O => MIDDLETEXT1(127) ); ...replicate 128 times, per each signal (per vector, if more than 1)
And the testbench file requires some modification as well:
wire [127:0] MIDDLETEXT1; ... add as many as you want AES128 aes128_inst ( .CLK (CLK), .RESET (RESET), .ENABLE (ENABLE), .DONE (DONE), .PLAINTEXT_0 (PLAINTEXT), ... .MIDDLETEXT1_0 (MIDDLETEXT1)
Doing so for the various internal wires and running the simulation, one can quickly recognize the key – it shows up as hex-encoded ascii characters inside one of the “tap-wires”, at an early stage of the encryption process (right after the ENABLE bit is on).