Tutorial #1: DCA against Wyseur 2007 challenge
This is the first tutorial of a series on white-box practical attacks.
It was published as part of a blog post How to crack a white-box without much effort at the occasion of the Troopers16 talk.
The corresponding materials are available at https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_des_wyseur2007
Let's take the white-box challenge that Brecht Wyseur put online in 2007.
It's a GNU/Linux command-line binary (a Windows version is available too) called wbDES, which encrypts a single plaintext block with a fixed key:
./wbDES 11 22 33 44 55 66 77 88
INPUT: 11 22 33 44 55 66 77 88.
OUTPUT: c4 03 d3 2e 2b c6 cf ee.
First step is to trace the executable so it's naturally in the Tracer repository that we'll find ammunitions. TracerGrind is an instrumentation plugin for Valgrind while TracerPIN is one for Intel PIN. TraceGraph is a GUI to visualize execution traces. In this example we'll start with TracerPIN and TraceGraph. We could jump directly to the attack but it's always nice to have some visual support, which is especially useful to find the sweet spot where the actual crypto is activated in larger binaries.
Once it's installed, acquiring an execution trace is as easy as:
Tracer -t sqlite -- ./wbDES 11 22 33 44 55 66 77 88Alternatively, acquiring a trace with TracerGrind can be done by first identifying the address range of the binary:
objdump -p wbDES |grep -A1 LOAD|grep -B1 "r.x"
LOAD off 0x00000000 vaddr 0x08048000 paddr 0x08048000 align 2**12
filesz 0x00002088 memsz 0x00002088 flags r-xThen, using that information:
valgrind --tool=tracergrind --filter=0x08048000-0x08100000 --output=wbDES.trace ./wbDES 11 22 33 44 55 66 77 88
sqlitetrace wbDES.trace wbDES.sqliteThe trace, no matter if you used TracerPIN or TracerGrind, is now in a sqlite database containing all the executed instructions, read and written data and their addresses. To have a quick overview of what's happening, we'll use TraceGraph, the third tool of that repository.
tracegraph &
From there you can open the sqlite DB file and open our fresh trace. After rescaling with the "Overview zoom" command you'll get something like this:
The execution goes from top to bottom, the horizontal axis being the memory address range. We see on the left the instructions in black looping while reading quite a lot of data somehow linearly, shown in the green diagonal, while on the far right things happen on the stack. Let's zoom on the stack:
Now the DES rounds are visible. To perform the DCA attack, one needs to collect several traces during the first or the last DES round. In large or slow implementations TraceGraph is helpful to define a range to target only e.g. the first round but our example is so small that we can blindly trace the entire execution.
Acquisition of traces is made easy with some script available in the Deadpool repository. The scripts configured for this challenge are in https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_des_wyseur2007/DCA. The configuration is typically limited to: specifying the executable to attack, how to provide plaintexts to the target, how to read the ciphertexts back, how many traces you want, what to trace (here the addresses of the data being read from memory), and if you prefer to use Valgrind or PIN. So just run it:
./trace_it.py
00000 F9B247990D90C1F3 -> AE90B8FBD1FC36CD
00001 0FD6AE2BD86D6178 -> EBA637804BB3417F
00002 222C10E967C93DFB -> 3130E6D763CB113D
00003 582CBC2F0DBAA3DA -> 36F1FDF96EF99F5C
00004 77F7E7B85708F642 -> 5526806DBBF8F57C
00005 3FAD5C7299310488 -> 0162523640E445B9
00006 04305FFFA97E76FF -> E4CFAD2453A2B74E
etc
By default the script is using TracerPIN but you can change it to use TracerGrind if you want to test it, cf commented line in trace_it.sh.
The traces will be attacked by our last tool in the Daredevil repository.
It's also possible to save traces in a format comatible with Riscure Inspector tool.
Now traces can be attacked by Daredevil.
Here, looking at the mem_addr1_rw1_100_72080.* set, which is the set of 100 traces made of the last byte of the addresses (addr1) of the 1-byte data having been read from or written to memory (rw1). There were indeed 72080 such bytes. We have:
daredevil -c mem_addr1_rw1_100_72080.config
[CONFIGURATION]
[GENERAL]
Number of threads: 8
Index first sample: 0
Number of samples: 72072
Total number traces: 100
Target number traces: 100
Total number keys: 64
Attack order: 1
Return Type: d
Window size: 0
Algorithm: DES
Round: 0
Bytenum: all
Target all bits individually.
Secret Key: 0x30 32 34 32 34 36 32 36
Round Key: 0x14 02 32 2c 31 20 0f 07
Lookup table layout: [8x64]
Memory: 4.00GB
Keep track of: 20
Separator : STANDARD
[TRACES]
Traces files: 1
Traces type: i
Transpose traces: True
Total number samples: 72080
Traces:
1. mem_addr1_rw1_100_72080.trace [100x72080]
[GUESSES]
Guesses files: 1
Guesses type: u
Transpose guesses: True
Total columns guesses: 8
Guesses:
1. mem_addr1_rw1_100_72080.plain [100x8]
[/CONFIGURATION]
[INFO] Lookup table specified at LUT/DES_SBOX
[ATTACK] Computing 1-order correlations...
[ATTACK] Key byte number 0
[ATTACK] Target bit number 0
[ATTACK] Target bit number 1
[ATTACK] Target bit number 2
[ATTACK] Target bit number 3
Best 10 candidates for key byte #0 according to sum(abs(bit_correlations)):
0: 0x14 sum: 4 <==
1: 0x2b sum: 3.58645
2: 0x30 sum: 3.52682
3: 0x1a sum: 3.4982
4: 0x22 sum: 3.49573
5: 0x00 sum: 3.49277
6: 0x36 sum: 3.48577
7: 0x0d sum: 3.43495
8: 0x35 sum: 3.42967
9: 0x06 sum: 3.42686
Best 10 candidates for key byte #0 according to highest abs(bit_correlations):
0: 0x14 peak: 1 <==
1: 0x2b peak: 1
2: 0x30 peak: 1
3: 0x35 peak: 0.904534
4: 0x36 peak: 0.904534
5: 0x00 peak: 0.904534
6: 0x01 peak: 0.904534
7: 0x02 peak: 0.904534
8: 0x03 peak: 0.904534
9: 0x04 peak: 0.904534
[INFO] Attack of byte number 0 done in 0.242451 seconds.
Best bit: 0 rank: 0. -1 0x14 5661
[ATTACK] Key byte number 1
[ATTACK] Target bit number 0
[ATTACK] Target bit number 1
[ATTACK] Target bit number 2
[ATTACK] Target bit number 3
Best 10 candidates for key byte #1 according to sum(abs(bit_correlations)):
0: 0x02 sum: 3.80178 <==
1: 0x2c sum: 3.53753
2: 0x37 sum: 3.52637
3: 0x2f sum: 3.52264
4: 0x13 sum: 3.51584
5: 0x22 sum: 3.45297
6: 0x05 sum: 3.43646
7: 0x09 sum: 3.43646
8: 0x30 sum: 3.43607
9: 0x2b sum: 3.42967
Best 10 candidates for key byte #1 according to highest abs(bit_correlations):
0: 0x02 peak: 1 <==
1: 0x05 peak: 1
2: 0x09 peak: 1
3: 0x22 peak: 1
4: 0x3e peak: 1
5: 0x2f peak: 1
6: 0x2c peak: 1
7: 0x34 peak: 0.904534
8: 0x37 peak: 0.904534
9: 0x38 peak: 0.904534
[INFO] Attack of byte number 1 done in 0.212039 seconds.
Best bit: 3 rank: 0. 1 0x02 65620
etc
Here we already provided the correct DES key in the configuration file and the tool returned the rank of each of the correct 6-bit round key bytes amongst all the key candidates. 100 traces are largely enough to rank the correct key bytes in first position (rank=0) and actually about 20 is already enough. Comparatively, we talk about hundreds of thousands of traces when attacking smartcards...
To demonstrate an attack without knowing the key, one can edit the generated mem_addr1_rw1_100_72080.config file to comment out the correct key and choose which 6-bit key byte to break (e.g. bytenum=0 to attack the first DES S-Box).
Run again the attack:
...
[ATTACK] Computing 1-order correlations...
[ATTACK] Key byte number 0
[ATTACK] Target bit number 0
...
Best 10 candidates for key byte #0 according to sum(abs(bit_correlations)):
0: 0x14 sum: 4
1: 0x2b sum: 3.58645
2: 0x30 sum: 3.52682
3: 0x1a sum: 3.4982
4: 0x22 sum: 3.49573
5: 0x00 sum: 3.49277
6: 0x36 sum: 3.48577
7: 0x0d sum: 3.43495
8: 0x35 sum: 3.42967
9: 0x06 sum: 3.42686
Best 10 candidates for key byte #0 according to highest abs(bit_correlations):
0: 0x14 peak: 1
1: 0x2b peak: 1
2: 0x30 peak: 1
3: 0x35 peak: 0.904534
4: 0x36 peak: 0.904534
5: 0x00 peak: 0.904534
6: 0x01 peak: 0.904534
7: 0x02 peak: 0.904534
8: 0x03 peak: 0.904534
9: 0x04 peak: 0.904534
[INFO] Attack of byte number 0 done in 0.327710 seconds.
[INFO] Total attack of file LUT/DES_SBOX done in 0.335882 seconds.
The first key byte of the first round key is, according to the tool: 0x14.
Repeating the attack on the other S-Boxes reveals that the 6-bit keys of the first round are 14:02:32:2c:31:20:0f:07 and the corresponding DES key is 3032343234363236 because, yes, DES key scheduling is invertible.
Verification:
echo 11 22 33 44 55 66 77 88|xxd -r -p|openssl enc -e -des-ecb -nopad -K 3032343234363236|xxd -p
c403d32e2bc6cfee
You've maybe notice that trace_it.py created also another set of traces stack_w1_100_3104.*. Those are the 1-byte data having been written to the stack.
daredevil -c stack_w1_100_3104.config
...
[INFO] Attack of byte number 0 done in 0.026499 seconds.
Best bit: 3 rank: 5. -0.557003 0x14 1669
[INFO] Attack of byte number 1 done in 0.024592 seconds.
Best bit: 0 rank: 15. -0.522976 0x2 839
Best bit: 3 rank: 2. 0.59103 0x2 914
etc
Here the attack clearly fails. So there is no obvious correlation between 1-byte values written to the stack and outputs of the DES S-Boxes.
But you can tell Daredevil to target other bits than the direct output of the S-Boxes.
E.g. to target the first round output, i.e. the S-Boxes outputs combined with the left part of the cipher input, edit stack_w1_100_3104.config and uncomment:
des_switch=DES_8_64_ROUND
Run again the attack:
daredevil -c stack_w1_100_3104.config |egrep "INFO|Best"
[INFO] File LUT/DES_SBOX not found, using /usr/local/share/daredevil/LUT/DES_SBOX instead.
[INFO] Lookup table specified at LUT/DES_SBOX
[INFO] Attack of byte number 0 done in 0.054851 seconds.
Best bit: 0 rank: 0. -0.748347 0x14 410
[INFO] Attack of byte number 1 done in 0.041822 seconds.
Best bit: 0 rank: 0. 0.578091 0x2 402
[INFO] Attack of byte number 2 done in 0.042047 seconds.
Best bit: 0 rank: 0. 0.461261 0x32 2787
[INFO] Attack of byte number 3 done in 0.036135 seconds.
Best bit: 0 rank: 0. 0.700786 0x2c 421
[INFO] Attack of byte number 4 done in 0.037413 seconds.
Best bit: 0 rank: 0. 0.522245 0x31 418
[INFO] Attack of byte number 5 done in 0.049754 seconds.
Best bit: 0 rank: 0. 0.500103 0x20 451
[INFO] Attack of byte number 6 done in 0.032009 seconds.
Best bit: 0 rank: 7. -0.394506 0xf 427
Best bit: 1 rank: 0. -0.655525 0xf 591
[INFO] Attack of byte number 7 done in 0.040835 seconds.
Best bit: 2 rank: 0. -0.470212 0x7 598
[INFO] Total attack of file LUT/DES_SBOX done in 0.335672 seconds.
And this one worked, which is the attack we discussed in our paper.
Right now Daredevil doesn't attack yet all key bytes at once automatically so you've to break them one by one. But things will evolve, so expect the instructions and features of the tools to change soon, stay tuned!