Tutorial #5: DCA against OpenWhiteBox AES Chow
Here is the fifth tutorial of our series.
The corresponding materials are available at https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_aes_openwhitebox_chow
The OpenWhiteBox project implemented the Chow construction in Go. As there was no real challenge, we did ours based on their code.
You can either compile your own, following https://github.com/SideChannelMarvels/Deadpool/blob/master/wbs_aes_openwhitebox_chow/target/README.md or use the compiled binaries https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_aes_openwhitebox_chow/target/
You can either generate your own challenge:
./generate-keyOr use the key available in https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_aes_openwhitebox_chow/target/key.txt
Usage is as following:
./encryptECB -in <(echo 000102030405060708090a0b0c0d0e0f|xxd -r -p) -out >(xxd -p)
99d527e5d281e9166825581337dac9c8A TracerGrind needs to know the address range, I wanted to use TracerPIN to acquire a first full trace:
Tracer -t sqlite -- ../target/encryptECB -key ../target/key.txt -in <(echo 000102030405060708090a0b0c0d0e0f|xxd -r -p) -out >(xxd -p)Strangely enough I had to kill (SIGTERM) the encryptECB program to end the trace after I got the "Done!" message otherwise it was pending forever...
killall encryptECB
killall encryptECB
killall encryptECBThe Sqlite trace is about 500Mb large.
Fire tracegraph, load the sqlite trace and rescale with the Overview zoom.
The trace is very large, probably due to some Go magic and loading of the tables... But the crypto part we're interesting is at the bottom where we observe large data reads from the tables. Zooming in the corresponding thickest instruction column, it gives:
We can see most AES rounds occur somewhere between 0x474b40 and 0x475df6 with the data beyond 0xc820080000 and the stack between 0xc8201cc000 and 0xc8201db000 (with some data being read only).
At first I tried to get the data & stack ranges visually to tune the tracer but it seems it's quite dynamic and can vary so at the end I decided to trace all data reads & writes without any filter on the data addresses, only a filter on the instructions address range.
With this information, we can mount the attack with the following parameters:
#!/usr/bin/env python
import sys
sys.path.insert(0, '../../')
from deadpool_dca import *
def processinput(iblock, blocksize):
return ["-key ../target/key.txt -in <(echo %0*x|xxd -r -p) -out >(xxd -p)" % (2*blocksize, iblock)]
def processoutput(output, blocksize):
return int(''.join([x for x in output.split('\n') if len(x)==32][0]), 16)
filters=[Filter('mem_data_rw1', ['R', 'W'], lambda stack_range, addr, size, data: size == 1, lambda addr, size, data: data & 0xFF, '<B')]
T=TracerGrind('../target/encryptECB', processinput, processoutput, ARCH.amd64, 16, addr_range='0x474b40-0x475df6', filters=filters, shell=True)
#T=TracerPIN('../target/encryptECB', processinput, processoutput, ARCH.amd64, 16, addr_range='0x474b40-0x475df6', filters=filters, shell=True)
T.run(200)
bin2daredevil(keywords=filters,
configs={'attack_sbox': {'algorithm':'AES', 'position':'LUT/AES_AFTER_SBOX', 'correct_key':'0x693bb79cd7742262c969595c4f8d895f'},
'attack_multinv':{'algorithm':'AES', 'position':'LUT/AES_AFTER_MULTINV', 'correct_key':'0x693bb79cd7742262c969595c4f8d895f'}})Note that we switched to TracerGrind, which doesn't have the terminating issue. Results will vary with your own randomly generated white-box. It might even be that you can recover the full key at the first step if you're lucky but here is a typical example where the attack may fail on some byte(s) and how to break them. Best results are when using last byte of addresses and considering the highest absolute correlation amongst the bit correlations, so I removed the information about sum(correlations) for clarity:
Once the traces are acquired, I limited the scope of the DCA attack to the first 10% of the traces, where first AES round is supposed to occur. This will make the attack processing faster:
nsamples=131176 => nsamples=13117
daredevil -c mem_data_rw1_200_131176.attack_sbox.config |egrep --line-buffered "(Best|0:)"|grep -v "sum"
Best 10 candidates for key byte #0 according to highest abs(bit_correlations):
0: 0x69 peak: 0.557991 <==
Best bit: 1 rank: 0. -0.557991 0x69 326
Best 10 candidates for key byte #1 according to highest abs(bit_correlations):
0: 0x3b peak: 0.53047 <==
Best bit: 0 rank: 0. 0.51996 0x3b 11478
Best 10 candidates for key byte #2 according to highest abs(bit_correlations):
0: 0xb7 peak: 0.431965 <==
Best bit: 3 rank: 0. 0.431965 0xb7 8533
Best 10 candidates for key byte #3 according to highest abs(bit_correlations):
0: 0x7b peak: 0.437242
Best bit: 2 rank: 1. -0.339942 0x9c 5502
Best 10 candidates for key byte #4 according to highest abs(bit_correlations):
0: 0xd7 peak: 0.520071 <==
Best bit: 2 rank: 0. 0.520071 0xd7 3856
Best 10 candidates for key byte #5 according to highest abs(bit_correlations):
0: 0x74 peak: 0.710302 <==
Best bit: 4 rank: 0. -0.710302 0x74 423
Best 10 candidates for key byte #6 according to highest abs(bit_correlations):
0: 0x22 peak: 0.741022 <==
Best bit: 1 rank: 0. 0.739974 0x22 11980
Best 10 candidates for key byte #7 according to highest abs(bit_correlations):
0: 0x62 peak: 0.803275 <==
Best bit: 2 rank: 0. 0.772174 0x62 8840
Best 10 candidates for key byte #8 according to highest abs(bit_correlations):
0: 0xc9 peak: 0.570085 <==
Best bit: 0 rank: 0. -0.570085 0xc9 7399
Best 10 candidates for key byte #9 according to highest abs(bit_correlations):
0: 0x69 peak: 0.51184 <==
Best bit: 5 rank: 0. -0.370167 0x69 3973
Best 10 candidates for key byte #10 according to highest abs(bit_correlations):
0: 0x59 peak: 0.432934 <==
Best bit: 4 rank: 0. 0.432934 0x59 451
Best 10 candidates for key byte #11 according to highest abs(bit_correlations):
0: 0x5c peak: 0.495607 <==
Best bit: 0 rank: 0. 0.495607 0x5c 12393
Best 10 candidates for key byte #12 according to highest abs(bit_correlations):
0: 0x4f peak: 0.558462 <==
Best bit: 6 rank: 0. 0.558462 0x4f 11662
Best 10 candidates for key byte #13 according to highest abs(bit_correlations):
0: 0x8d peak: 0.528352 <==
Best bit: 0 rank: 0. 0.430689 0x8d 7491
Best 10 candidates for key byte #14 according to highest abs(bit_correlations):
0: 0x89 peak: 0.549066 <==
Best bit: 0 rank: 0. -0.40522 0x89 4020
Best 10 candidates for key byte #15 according to highest abs(bit_correlations):
0: 0x38 peak: 0.399302We see almost all bytes can be properly recovered, only byte #3 fell short (a few extra traces would have fixed it) and byte #15 cannot be recovered.
Let's try the target that worked well for Karroumi to get the missing key byte(s): the application of the multiplicative inverse to the data, a step normally internal to the S-box.
daredevil -c mem_data_rw1_200_131176.attack_multinv.config |egrep --line-buffered "(Best|0:)"|grep -v "sum"
Best 10 candidates for key byte #0 according to highest abs(bit_correlations):
0: 0x69 peak: 0.633298 <==
Best bit: 1 rank: 0. -0.427676 0x69 291
Best 10 candidates for key byte #1 according to highest abs(bit_correlations):
0: 0x3b peak: 0.58249 <==
Best bit: 2 rank: 0. -0.437387 0x3b 11769
Best 10 candidates for key byte #2 according to highest abs(bit_correlations):
0: 0x57 peak: 0.419089
Best 10 candidates for key byte #3 according to highest abs(bit_correlations):
0: 0x9c peak: 0.590739 <==
Best bit: 3 rank: 0. 0.590739 0x9c 5184
Best 10 candidates for key byte #4 according to highest abs(bit_correlations):
0: 0xd7 peak: 0.698239 <==
Best bit: 1 rank: 0. 0.567228 0xd7 3847
Best 10 candidates for key byte #5 according to highest abs(bit_correlations):
0: 0x74 peak: 0.52892 <==
Best bit: 6 rank: 0. -0.52892 0x74 419
Best 10 candidates for key byte #6 according to highest abs(bit_correlations):
0: 0x22 peak: 0.570986 <==
Best bit: 0 rank: 0. -0.542897 0x22 12186
Best 10 candidates for key byte #7 according to highest abs(bit_correlations):
0: 0x62 peak: 0.809602 <==
Best bit: 1 rank: 0. 0.362389 0x62 8740
Best 10 candidates for key byte #8 according to highest abs(bit_correlations):
0: 0xc9 peak: 1 <==
Best bit: 1 rank: 0. -0.46083 0xc9 7410
Best 10 candidates for key byte #9 according to highest abs(bit_correlations):
0: 0x69 peak: 0.565463 <==
Best bit: 0 rank: 0. 0.565463 0x69 3957
Best 10 candidates for key byte #10 according to highest abs(bit_correlations):
0: 0x59 peak: 0.81876 <==
Best bit: 1 rank: 0. -0.81876 0x59 483
Best 10 candidates for key byte #11 according to highest abs(bit_correlations):
0: 0x5c peak: 0.472337 <==
Best bit: 2 rank: 0. -0.472337 0x5c 12392
Best 10 candidates for key byte #12 according to highest abs(bit_correlations):
0: 0x19 peak: 0.429337
Best bit: 0 rank: 9. -0.319439 0x4f 11763
Best 10 candidates for key byte #13 according to highest abs(bit_correlations):
0: 0x8d peak: 0.569942 <==
Best bit: 2 rank: 0. -0.51972 0x8d 8218
Best 10 candidates for key byte #14 according to highest abs(bit_correlations):
0: 0x89 peak: 0.717347 <==
Best bit: 0 rank: 0. 0.543678 0x89 4976
Best 10 candidates for key byte #15 according to highest abs(bit_correlations):
0: 0x5f peak: 0.569512 <==
Best bit: 0 rank: 0. -0.520714 0x5f 1844This time a few other bytes were not recovered (#2 and #12) but we got bytes #3 and #15! So by combining both attacks we managed to recover the full key. In the rare event one byte is not revealed by an attack or the other, try to brute-force it (it's easy by comparing the relative correlation scores if a candidate seems legit or not) or to target other affine transforms than in the original S-box...
So we saw here that the behavior observed in Karroumi is also observable here in Chow with internal encodings. Compared to Karroumi we used 200 trace without tuning (vs. 2000 for Karroumi).
The repository contains also a DFA attack that we will explain in a future tutorial about DFA.