Triple DES leakage model

[Capt_Jack]

As we all hopefully know that 3DES is a three step operation:

ZA1. Decrypt plain text using key 1
2. Encrypt output from step 1 using key 2
3. Decrypt output from step 2 using key 1

We can figure out what key 1 is by feeding it plain texts, looking at traces and running a CPA attack. The key is deduced from round 1 sbox output, which is 48 bits, which we can get a theoretical output from using a model. So it’ll be one of 256 possible keys once missing 8 bits are reinserted.

Am I right in thinking that in order to deduce what key 2 is, we need to have cracked key 1 so that we know what the input into the second step is order to obtain the theoretical output from the leakage model? Or is there an easier way?

[Alex_Dewar]

Yeah, I’d expect that you’d have to get key 1 before moving onto key 2, though some sort of shortcut might exist. The issue here is the missing 8 bits on the key, which prevents you from getting the correct input to the second DES block, correct?

I don’t have any experience attacking DES, but looking at the algorithm, you should be able to advance the internal state and perform CPA against SBox 1 and 8 in rounds 2 and 3 to determine the remaining 8 bits of the key. From there, you can calculate the input to the second DES block and simply repeat the attack to get the second key (and repeat again to get the third key, if there is one).

EDIT: I’m a little unsure of exactly how PC2 works in the key schedule, but you should still be able to advance the state of the algorithm using the parts of the key that you’ve found and attack the additional key bits as they’re used.

[Capt_Jack]

That makes sense. I didn’t think of attacking outputs from other rounds - will to play with that…

[Capt_Jack]

Just did some experimentation and merging round 1 key and round 8 key leaves a single bit missing But… that can be worked around.

The trickier part will be to build a leakage model for other rounds in the current DES.py file only does output from round 1, so will need to add a new model, once I decipher the thing!

[Alex_Dewar]

From what I can tell here: Data Encryption Standard - Wikipedia and here DES supplementary material - Wikipedia and here DES supplementary material - Wikipedia, I think you can actually get the remaining 8 bits by attacking just the second round. Missing bits [9, 18, 22, 25, 35, 38, 43, 54] get rotated to [8, 17, 21, 24, 34, 37, 42, 53] which are in sboxes [2, 0, 1, 0, 6, 4, 7, 6], so doing a CPA attack on sboxes 0, 1, 2, 4, 6, and 7 should get you the remaining 8 bits.

I’m guessing you went backwards from the output of the third encryption to get 7/8 bits?

[Capt_Jack]

I am still struggling to attack the rounds other than the first on plain DES.

I’ve made significant changes to the DES model to output the sbox values from the required round. I am fairly confident that the sbox values are correct having stared at a load of print() messages but the attacks fail.

I am also fairly certain that the trace I am attacking is from the second round but as it’s not working something isn’t right.

The way I am doing it is thus:

Capturing 100 traces from the XMEGA target. Round 1 comes in at offset 73500 and round 2 at offset 131500, so I am capturing 5000 samples at offset 131500. The 8 sboxes are clearly seen between samples 400 and ~2200.

Running the attack using this code:

import chipwhisperer.analyzer as cwa
from chipwhisperer.analyzer.attacks.models.DES import DES, SBox_output
from chipwhisperer.analyzer.attacks.cpa_algorithms.progressive import CPAProgressive
from chipwhisperer.analyzer.attacks.cpa_new import CPA

attack_round = 2

leak_model = DES(model=SBox_output(attack_round=attack_round),attack_round=attack_round)
attack = cwa.cpa(resync_analyzer, leak_model)
attack.set_target_subkeys([0, 1, 2, 3, 4, 5, 6, 7])
attack.set_trace_source = attack.project.trace_manager()
attack.set_trace_start(0)
attack.set_traces_per_attack(-1)
attack.set_iterations(1)
attack.set_reporting_interval(10)
attack.set_point_range((300,2500))
cb = cwa.get_jupyter_callback(attack, 8)
results = attack.run(cb)

The attack_round tells the model how many rounds to run within the DES routine before exiting, returning the sbox output values for a given byte number sent by the CPA module.

As I am attacking the second round key, I am expecting key 16 1A 01 0A 3D 1E 1F 2A to pop up (round 0 key is 2B 7E 15 16 28 AE D2 A6)

But I am getting no outliers from the attack…

If I target traces from round 1 and set attack_round to 1, it works great.

So, I am either targeting the wrong trace or there’s something wrong with the model.

Halp!

Edit: just a thought… Do I need to know the input into round 2 before getting its output? I wouldn’t have thought so…

[Alex_Dewar]

Not sure exactly what you’re currently doing, but you do need to calculate the input into the second block, which is just the output of the first block XOR the other half block of the plaintext.

[Capt_Jack]

Thanks, that explains why it’s not working. I am using the original plaintext generated by ktp and doing CPA using that against the round 2 output. The model already calculates the input into the second round but it doesn’t feed it back to the CPA routine. Sounds like I need to do it beforehand.

More investigation and no doubt refactoring is required!

[Capt_Jack]

@Alex_Dewar I am getting deeper into this rabbit hole and my knowledge of the attacking processes within CW leave a lot to be desired.

tl;dr - After calculating it, how do I get the round 1 output text into the CPA attack routine/project?

I’ll try and break it down what I think should happen to attack the second round.

1. Run this against the target to collect traces during encryption:

for _ in trange(num_traces):
    scope.adc.offset = 0
    key, pt = ktp.next()
    trace = np.array([])
    for _ in trange(10):
        scope.adc.offset += scope.adc.samples
        dout, t = capture_traces('p',pt)
        trace = np.append(trace, t)

    traces.append(cw.Trace(trace,pt,dout[3:-2],key))

This takes 100 traces with 10 traces in each pass appended together so I can see beyond the 24000 samples to let me capture round 2. The traces and the corresponding plain text are saved in a project. Although I am saving the key, I don’t believe this is used for the attack.

2. The plain text is an input into round 1, which is known and stored in the project.

3. The model calculates round 2 input after round 1 - how do I practically get this round 2 input text into the project to use in the attack?

This is what the model outputs:

$ python3 DES.py
Class: SBox_output

      PLAIN TEXT INPUT: 01 23 45 67 89 AB CD EF
                   KEY: 2B 7E 15 16 28 AE D2 A6
       KEY PERMUTATION: 70 10 56 34 75 6B 46 3E

ROUND 1:
                 INPUT: CC 00 CC FF F0 AA F0 AA
                SUBKEY: 22 10 30 21 32 38 07 3F
 EXPANSION PERMUTATION: 1E 21 15 15 1E 21 15 15
          S-BOX OUTPUT:  5 11 13  3  7  0 12 12
     P-BOX PERMUTATION: 0E 0C 05 0D 0C 01 0A 03
                   XOR: 02 00 05 0D 00 0D 05 0C
           SWAP/OUTPUT: F0 AA F0 AA 20 5D 0D 5C

ROUND 2:
                 INPUT: F0 AA F0 AA 20 5D 0D 5C
                SUBKEY: 16 1A 01 0A 3D 1E 1F 2A
 EXPANSION PERMUTATION: 04 00 0B 3A 21 1A 2B 38
          S-BOX OUTPUT: 10  0  3 15 14 10  6  9
     P-BOX PERMUTATION: 09 0D 0F 04 01 0E 0C 04
                   XOR: 06 0D 05 0E 0E 0E 06 0E
           SWAP/OUTPUT: 20 5D 0D 5C 6D 5E EE 6E

When I run cwa.cpa.attack.run() it uses plain text input 01 23 45 67 89 AB CD EF to do its magic (as an example).

But what I really need is for it to use F0 AA F0 AA 20 5D 0D 5C from round 1 output. This needs to happen for each guess of key byte the attack cycles through, so it needs to happen on the fly, presumably.

I originally thought that I could calculate round 1 output during the initial trace capture, taking the random input and getting round 1 output but without knowing the encryption key, it seems that this won’t achieve much?

I feel like I am missing something very simple but I am, at the moment, lost.

[Alex_Dewar]

I believe it should be sufficient to replace the top 32 bits of your plaintext input with the input to the second round: (something like plaintext[32:] = rnd1_out ^ plaintext[:32]). The internals of our analysis code is pretty messy, as it was heavily tied into the old GUI and we haven’t replaced it, so it’s easier just to do that.

Note that you need the 48 bits of the key that you’ve found to figure out rnd1_out, as the key gets mixed in in that F block.

[Capt_Jack]

Thanks @Alex_Dewar !!

After a bit of refactoring and a bit of faffing, I finally managed a successful attack against round 2 traces, thereby recovering the entire key!

I am going to tidy up the code a bit, both in Jupyter and the model itself and then upload it somewhere for everyone to see.

I should be able to recover the second key in 3DES using a similar method.

[Capt_Jack]

I’ve done a bit of tidying up but it’s still rather messy for my liking.

GitHub - captainjack64/chipwhisperer-stuff

I’ve included the model I am using, the Notebook and the html copy of the notebook as the notebook doesn’t show traces…