Tutorial #3: DCA against SSTIC 2012 challenge

Here is the third tutorial of our series.

Specificities of this tutorial:

• Learning how traces acquired via other channels can fit into the toolchain

The corresponding materials are available at https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_des_sstic2012

This white-box, made by Axel Tillequin, was part of a larger challenge for SSTIC 2012.

Internally this bytecode generates a random plaintext, forwards this to the white-box and to a regular DES encryption using the key provided by the user and then compares both ciphertexts.
Actually, Python bytecode can be decompiled with little effort as shown by the write-up of Jean Sigwald, which contains a decompiled version of the check.pyc file where the white-box part is still left serialized as a pickled object.

This is the decompiled check.py that we will attack. One option could be to instrument a Python interpreter but fortunately it gets even easier: the white-box makes use of a separate Bits class to handle its variables so we have just to add some hooks to record all new instances of that particular class.
So at the end ot the __init__() of class Bits, we add those lines to record the size and the value of any instance freshly created:

        global trace
        trace.append((self.size, self.ival))

To handle more easily the script, we turn it into a library by removing all the unneeded parts: the test if __name__ == "__main__" and everything since the point where arguments are checked: if len(sys.argv) == 1 etc.

A patch file is available in the materials, so from the DCA directory you can just use to apply the changes presented above:

cp ../target/check.py .
patch < check.py.diff

To collect traces, another script is created. It initializes the traces list, prepares random inputs, collect outputs and traces.

#!/usr/bin/env python

import sys
import random
import check

keyword='bits'
for i in range(25):
    check.trace=[]
    M = check.Bits(random.getrandbits(64), 64)
    C = check.WT._cipher(M, 1)
    plain=hex(M).encode('hex')
    cipher=hex(C).encode('hex')
    print "%05i %s -> %s" % (i, plain, cipher)
    with open('trace_%s_%04i_%s_%s.bin' % (keyword, i, plain, cipher), 'wb') as trace:
        trace.write(''.join(["%0*x" % (s/4, v) for s,v in check.trace]).decode('hex'))

The script 01acquire_traces.py reproduces those steps with some extra filtering which are actually purely cosmetic, to show what can be done. The attack works blink fast anyway. The added filtering is to retain only values that are 96-bit wide and to remove duplicates, to bring down the set of traces from 6Mb to 45k.

./01acquire_traces.py
00000 a91ad3f51d3b3f53 -> 09a7287a83b880ff
00001 9f2041256dc882c8 -> f051157cbde77468
00002 4fe6588b85dfe358 -> 43c059e9faf0f3b4
00003 3afb7f183c95b308 -> f394ed40457cadc0
00004 59f7f9dd204c0928 -> fdd3a0825ccff2a6
00005 b386325a0bf88a43 -> 41aad92b0d0897c3
00006 6ab6342fa6be2067 -> 54b3acfa5c1a4ad7
etc

Those are raw traces recorded the same way deadpool_dca is recording them with TracerPIN or TracerGrind. They need to be converted for Daredevil but we can use deadpool_dca helpers for that:

from deadpool_dca import *

bin2daredevil(keyword='bits', config={'algorithm':'DES', 'position':'LUT/DES_SBOX', 'correct_key':'0xfd4185ff66a94afd'})

Then executing the differential analysis on the converted traces:

daredevil -c bits_25_1824.config|egrep "INFO|Best bit"
[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.011740 seconds.
Best bit: 0 rank: 0.               1    0x2d     283
[INFO] Attack of byte number 1 done in 0.009889 seconds.
Best bit: 0 rank: 0.               1    0x18     275
[INFO] Attack of byte number 2 done in 0.017369 seconds.
Best bit: 0 rank: 0.               1    0x3d     267
[INFO] Attack of byte number 3 done in 0.011821 seconds.
Best bit: 2 rank: 0.               1    0x35     257
[INFO] Attack of byte number 4 done in 0.008600 seconds.
Best bit: 0 rank: 0.               1    0x39     251
[INFO] Attack of byte number 5 done in 0.007117 seconds.
Best bit: 0 rank: 0.               1    0x1d     243
[INFO] Attack of byte number 6 done in 0.007232 seconds.
Best bit: 0 rank: 0.               1    0x28     235
[INFO] Attack of byte number 7 done in 0.012887 seconds.
Best bit: 0 rank: 0.               1    0x27     227
[INFO] Total attack of file LUT/DES_SBOX done in 0.087114 seconds.